Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

obrazek

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Równania

Rozkład LU i układ równań liniowych

SPIS TREŚCI
Podrozdziały

Definicje

Do rozwiązania układu równań można wykorzystać rozkład LU. Postępujemy następująco:

Mamy dany układ równań n  liniowych z n  niewiadomymi:

Zapiszmy ten układ w postaci macierzowej:

Załóżmy, iż dokonaliśmy rozkładu LU macierzy współczynników A:

Nasze równanie możemy teraz zapisać jako:

Ponieważ mnożenie macierzy jest łączne, to:

Robimy podstawienie:

Otrzymujemy:

Rozwiązanie układu jest dwuetapowe. Najpierw wyznaczamy macierz Y  z ostatniego równania, a następnie wyznaczamy macierz X  z podstawienia:

Okazuje się, że ze względu na postać macierzy L  i U  rozwiązanie takiego układu jest bardzo proste. Rozpiszmy pierwsze równanie macierzowe:

Z pierwszego równania w układzie od razu dostajemy wartość pierwszej niewiadomej y:

Wstawiając ją do równania drugiego wyliczamy drugą niewiadomą y:

Wyliczone wartości niewiadomych y  wstawiamy do równania trzeciego i otrzymujemy:

Metoda ta nosi nazwę podstawiania w przód ( ang. forward-substitution ). Uogólniając, widzimy wyraźnie, że niewiadomą y i wyliczamy z poprzednio wyliczonych niewiadomych y 1, y 2, ..., y i - 1. Wzór jest następujący:

Gdy znajdziemy wektor Y, to przechodzimy do drugiego równania macierzowego:

Rozpiszmy je:

Tutaj mamy sytuację odwrotną do poprzedniej. Rozwiązywanie rozpoczynamy od ostatniego równania:

Wyliczoną wartość xn wstawiamy do równania przedostatniego:

Niewiadome x wyliczamy od ostatniej do pierwszej. Taka metoda postępowania nosi nazwę podstawiania wstecz ( ang. back-substitution ). Wzór uogólniony ma postać:

Rozwiązanie układu istnieje, jeśli wszystkie elementy przekątnej głównej macierzy U  są niezerowe. Warunek ten jest sprawdzany w algorytmie rozkładu LU.

Zwróć uwagę, iż macierze X  i Y  mogą być tą samą macierzą X, ponieważ w obu fazach wyliczania niewiadomych elementy y  nie kolidują z elementami x.

Na początek:  podrozdziału   strony 

Rozkład LU w rozwiązywaniu układu równań liniowych

Metoda rozwiązywania układu równań liniowych z wykorzystaniem rozkładu LU jest następująca:

  1. Dokonujemy rozkładu LU macierzy współczynników A.
  2. Jeśli macierz A  jest zdegenerowana, to układ równań nie ma rozwiązania. Kończymy
  3. Dokonując podstawień w przód wyznaczamy macierz Y ( może być w macierzy X ).
  4. Dokonując podstawień wstecz wyznaczamy macierz X.

Algorytm rozwiązywania układu równań liniowych z wykorzystaniem rozkładu LU

Dane wejściowe:

ε dokładność przyrównania do zera
n stopień macierzy
A macierz n × n współczynników
B macierz n × 1 z wyrazami wolnymi
X macierz n × 1 dla rozwiązań

Dane wyjściowe

true/false określa, czy operacja powiodła się, czy nie.
X macierz n × 1 z wartościami niewiadomych, jeśli wynikiem jest true.

Zmienne pomocnicze

i,j,k indeksy
s suma
W macierz 1 × n z numerami wierszy macierzy A.
maxw numer wiersza z elementem maksymalnym
maxe moduł elementu maksymalnego
akk element macierzy A  leżący na jej przekątnej po piwotowaniu

Lista kroków

K01: Dla i = 0,1,...,n – 1:
wykonuj W  [ i ] ← i
ustawiamy wektor wierszowy
K02: Dla k = 0,1,...,n – 1:
wykonuj kroki K03...K12
rozpoczynamy rozkład LU
K03:     maxw ← k wiersz z elementem maksymalnym
K04:     maxe ← | A [ W [ k ], k ] | moduł elementu maksymalnego
K05:     Dla i = k + 1, k + 2,..., n – 1:
    wykonuj krok K07
szukamy elementu większego
K06:         Jeśli | A [W [ i ], k ] | > maxe,
        to maxw ← i
            maxe ← | A [ W [ i ], k ] |
 
K07:     Jeśli maxe ≤ ε,
    to zakończ z wynikiem false
macierz jest zdegenerowana
K08:     Jeśli maxw ≠ W [ k ],
    to W [ k ] ↔ W [ maxw ]
znaleziono element maksymalny
K09:     akk ← A [ W [ k ], k ] rozkład LU
K10:     Dla i = k + 1, k + 2,...,n – 1:
    wykonuj
: A [ W [ i ], k ] ← A [ W [ i ], k ] / akk
normalizacja kolumny
K11:     Dla i = k + 1,k + 2,...,n – 1:
    wykonuj krok K12
modyfikujemy podmacierz
K12:     Dla j = k + 1,k + 2,...,n – 1:
    wykonuj:
        A [ W [ i ], j ] ← A [ W [ i ], j ] - A [ W [ i ], k ] × A [ W [ k ], j ]
 
K13: X [ 0 ] ← B  [ W [ 0 ] ] w X tworzymy macierz Y
K14: Dla i = 1,...,n – 1:
wykonuj kroki K15...K17
stosujemy podstawienia w przód
K15:     s  ← B  [ W  [ i ] ]  
K16:     Dla j = 0,...,i – 1:
    wykonuj s  ← s – A  [ W  [ i ], j ] × X [ j ]
 
K17:     X  [ i ] ← s  
K18: X [ n – 1 ] ← X  [ n – 1 ] / A  [ W  [ n – 1], n – 1] w X wyliczamy niewiadome x
K19: Dla i = n – 2,...,0:
wykonuj kroki K20...K22
stosujemy podstawienia wstecz
K20:     s ← X  [ i ]  
K21:     Dla j = n – 1,...,i + 1:
    wykonuj s ← s – A  [ W  [ i ], j ] × X  [ j ]
 
K22:     X  [ i ] ← s / A  [ W [ i ], i ]  
K23: Zakończ z wynikiem true  

Poniższy program jest przykładową realizacją powyższego algorytmu. W programie łączymy macierz współczynników A  z macierzą wyrazów wolnych B  w jedną macierz AB  o rozmiarze n  × n  + 1. Dane wejściowe do programu są następujące:

Pierwsza liczba określa liczbę równań i niewiadomych n. Następne liczby określają współczynniki przy niewiadomych oraz wyrazy wolne. Należy wprowadzać je wierszami. Pierwsze n  liczb w każdym wierszu to kolejne współczynniki przy niewiadomych. Po tych n  współczynnikach należy wprowadzić wyraz wolny. Wierszy takich musi być n.

Układ równań:

Dane wejściowe:

5
-1 2 -3 3 5 56
8 0 7 4 -1 62
-3 4 -3 2 -2 -10
8 -3 -2 1 2 14
-2 -1 -6 9 0 28
Przykładowy program w języku C++
// Eliminacja Gaussa
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//---------------------------

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

const double EPS = 0.000000001;

// Funkcja rozwiązuje układ równań
// metodą rozkładu LU
// n - stopień macierzy
// AB - wskaźnik macierzy n x (n +1)
// X - wskaźnik macierzy rozwiązań n x 1
// Jeśli układ został rozwiązany, to wynikiem jest true.
// Inaczej wynikiem jest false.
//------------------------------------------------------

bool LUeq(int n, double ** AB, double * X)
{
    int i, j, k, * W, maxw;
    double s, akk, maxe;

    // Tworzymy wektor wierszowy
    W = new int [n];

    // Inicjujemy wektor wierszowy numerami wierszy
    for(i = 0; i < n; i++) W[i] = i;

    // Rozkład LU
    for(k = 0; k < n; k++)
    {
        maxw = k; // numer wiersza z elementem max
        maxe = fabs(AB[W[k]][k]);

        // Szukamy elementu max
        for(i = k + 1; i < n; i++)
            if(fabs(AB[W[i]][k]) > maxe)
            {
                maxw = i;
                maxe = fabs(AB[W[i]][k]);
            }

        // Jeśli max jest zero, to macierz jest zdegenerowana
        if(maxe <= EPS)
        {
            delete [] W;
            return false;
        }

        // Jeśli max nie leży na przekątnej, zamieniamy wiersze
        if(maxw != k) swap(W[k], W[maxw]);

        // Dzielnik
        akk = AB[W[k]][k];

        // Normalizujemy kolumnę
        for(i = k + 1; i < n; i++) AB[W[i]][k] /= akk;

        // Modyfikujemy podmacierz
        for(i = k + 1; i < n; i++)
            for(j = k + 1; j < n; j++) AB[W[i]][j] -= AB[W[i]][k] *  AB[W[k]][j];
    }

    // Teraz rozwiązujemy układ równań w dwóch etapach
    // Najpierw w X wyznaczamy macierz Y stosując podstawienia w przód

    X[0] = AB[W[0]][n];
    for(i = 1; i < n; i++)
    {
        s = AB[W[i]][n];
        for(j = 0; j < i; j++) s -= AB[W[i]][j] * X[j];
        X[i] = s;
    }

    // Wyznaczamy X stosując podstawienia wstecz

    X[n - 1] /= AB[W[n - 1]][n - 1];

    for(i = n - 2; i >= 0; i--)
    {
        s = X[i];
        for(j = n - 1; j > i; j--) s -= AB[W[i]][j] * X[j];
        X[i] = s / AB[W[i]][i];
    }

    delete [] W;
    return true;
}

// Program główny
//---------------

int main()
{
    setlocale(LC_ALL,"");

    cout << setprecision(5) << fixed;

    cout << "Rozwiązywanie układu równań liniowych metodą rozkładu LU" << endl
         << "--------------------------------------------------------" << endl << endl
         << "Wpisz dane wejściowe:" << endl << endl;

    int n;     // Liczba równań w układzie

    cin >> n;

    int i,j;

    // Tworzymy dynamicznie potrzebne macierze

    double ** AB ; // Macierz współczynników przy niewiadomych x oraz wyrazów wolnych
    double * X ;   // Macierz niewiadomych

    AB = new double * [n];
    X  = new double [n];

    for(i = 0; i < n; i ++) AB[i] = new double [n + 1];

    // Odczytujemy dane układu równań

    for(i = 0; i < n; i++)
        for(j = 0; j <= n; j++) cin >> AB[i][j];

    cout << endl;

    // Rozwiązujemy układ równań

    if(LUeq(n,AB,X))
    {
        for(i = 0; i < n; i++)
            cout << "x" << i << " = " << setw(12) << X[i] << endl;
    }
    else cout << "Błąd w trakcie obliczeń!!!" << endl;

    cout << endl;

    // Usuwamy tablice dynamiczne

    for(i = 0; i < n; i++) delete [] AB[i];
    delete [] AB;
    delete [] X;

    return 0;
}
Wynik
Rozwiązywanie układu równań liniowych metodą rozkładu LU
--------------------------------------------------------

Wpisz dane wejściowe:

5
-1 2 -3 3 5 56
8 0 7 4 -1 62
-3 4 -3 2 -2 -10
8 -3 -2 1 2 14
-2 -1 -6 9 0 28

x0 =      1.00000
x1 =      3.00000
x2 =      5.00000
x3 =      7.00000
x4 =      9.00000
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.