|
Nie obrażaj więc mojej inteligencji poprzez czynione na pokaz zaniżanie własnej.
Układy równań liniowych 11
UKŁADY RÓWNAŃ LINIOWYCH
1. Wstęp
Rozwiązanie układu równań liniowych o postaci:
[1]
polega na znalezieniu wartości zmiennych jeśli znane są wartości współczynników i . Układ [1] można zapisać za pomocą sumy: [2] lub w postaci macierzowej:
AX=B [3]
gdzie: A = B = X = [4]
Jeśli macierz A jest nieosobliwa (det A ¹ 0) to układ [1] posiada tylko jedno rozwiązanie. W całym rozdziale zakładamy, że macierz A i wektor B są rzeczywiste. Istnieje wiele metod znajdowania rozwiązania układu [1]. Metody te można podzielić na dwie grupy: - metody dokładne (wzory Cramera, metoda Gaussa, metoda Gaussa-Jordana, metoda wyboru elementu podstawowego, metoda Choleskiego czyli rozkładu na macierze L i U), - metody iteracyjne (metoda Jacobiego zwana też metodą iteracji prostej, metoda Seidela, metoda relaksacji).
2. Wzory Cramera
Jeśli macierz A jest nieosobliwa to układ [1] jest oznaczony i można wykazać, że rozwiązania dokładne ma postać:
[5]
gdzie: Ai =
jest macierzą utworzoną z macierzy A, w której w miejsce i-tej kolumny wstawiono wektor B. Metoda oparta na wzorach Cramera wymaga obliczenia wartości n+1 wyznaczników. Dla dużych układów równań metoda ta jest mało efektywna ze względu na dużą złożoność obliczeniową oraz istotny wpływ błędów operacji arytmetycznych.
3. Metoda eliminacji Gaussa
Metoda eliminacji Gaussa polega na sprowadzeniu układu równań AX=B do układu o postaci A(n)X=B(n) gdzie A(n) jest macierzą trójkątną górną, a następnie rozwiązaniu tego trójkątnego układu równań. Niech dany będzie układ równań:
[6]
zakładając że pomnóżmy pierwsze równanie przez i odejmijmy od i-tego równania , otrzymamy wtedy
[7]
gdzie , . Następnie pomnóżmy drugie równanie przez () i odejmijmy od i-tego równania , otrzymamy więc
[8]
gdzie , . Kontynuując takie postępowanie otrzymamy układ trójkątny
[9]
gdzie , , . Rozwiązanie tego układu równań jest proste. Rozwiązujemy go od „tyłu” tzn. obliczamy kolejno wg wzorów:
. [10]
4. Metoda wyboru elementu podstawowego
W trakcie przekształcania układu równań do układu z macierzą trójkątną górną musi być spełniony warunek . [11] Również przypadek gdy moduł współczynnika ma bardzo małą wartość może prowadzić do znacznych błędów zaokrąglania spowodowanych operacją dzielenia przez bardzo małą wartość. Aby uniknąć dzielenia przez zero lub przez małe liczby stosuje się metodę wyboru elementu podstawowego. Algorytm jest następujący: 1. W pierwszym kroku wyszukujemy element o maksymalnym module wśród wszystkich współczynników . Niech nim będzie element leżący w r-tym wierszu i s-tej kolumnie. Zamieniamy r-ty wiersz z pierwszym a następnie s-tą kolumnę z pierwszą. Dalej dokonujemy redukcji macierzy wg wzoru [7]. lW drugim kroku wyszukujemy elementu o maksymalnym module wśród wszystkich współczynników l. Zamieniamy odpowiednio p-ty wiersz z drugim wierszem i q-tą kolumnę z drugą itd. Jeśli w którymś kroku znaleziony element o maksymalnym module jest równy zeru to obliczenia przerywamy. Oznacza to bowiem, że , czyli układ jest albo sprzeczny albo nieoznaczony. Należy również zapamiętywać wszystkie kolejne zamiany kolumn, ponieważ powodują one zmianę kolejności niewiadomych w wektorze X.
5. Metoda Gaussa-Jordana
Metoda ta stanowi pewną modyfikację metody Gaussa. Otóż przekształca się układ równań [6] do układu w którym macierz współczynników jest macierzą jednostkową AX=B ® EX=B(n) wg następującego algorytmu. Dzielimy obustronnie pierwszy wiersz układu równań [6] przez współczynnik a następnie mnożymy przekształcony pierwszy wiersz przez współczynnik i odejmujemy od i-tego wiersza . Otrzymamy
gdzie , . W otrzymanym układzie równań dzielimy drugi wiersz przez współczynnik a następnie mnożymy przekształcony drugi wiersz przez współczynnik i odejmujemy od i-tego wiersza . Otrzymamy
gdzie , .
Kontynuując obliczenia po „k” krokach otrzymamy
[12] gdzie , . Po „n-1” krokach otrzymamy (realizujemy obliczenia wg wzoru [12] dla )
W ostatnim n-tym kroku wystarczy podzielić ostatnie równanie przez współczynnik a następnie wyrugować zmienną z równań 1,2 do n-1, czyli rozwiązaniem jest: [13] . W trakcie eliminacji Gaussa-Jordana współczynniki . Aby warunek ten był spełniony należy również stosować metodę wyboru elementu podstawowego.
6. Metoda rozkładu na macierze L i U
Rozpatrzmy układ równań opisany równaniem [3] AX=B. Twierdzenie 1. Jeśli wszystkie wyznaczniki podmacierzy Aii ( i = 1,2,..., n-1) utworzonych z „i” pierwszych kolumn i wierszy macierzy A licząc odpowiednio z lewej do prawej strony i z góry na dół, są różne od zera () to istnieje jednoznaczny rozkład macierzy A na dwie macierze trójkątne L i U, odpowiednio dolną z jedynkami na przekątnej głównej i górną o postaci: A=LU [14]
gdzie L = U = . [15]
Algorytm rozwiązania układu równań AX=B jest więc następujący. Wstawiając równanie [14] do [3] otrzymamy LUX=B, które możemy rozbić na dwa równania LY=B i UX=Y. Z pierwszego równania wyznaczamy wektor Y a z drugiego wektor X. Zaletą takiego rozbicia jest fakt, że obydwa wektory otrzymujemy natychmiast, bowiem rozwiązujemy dwa układy równań z macierzami trójkątnymi: [16]
[17]
Elementy macierzy L i U można wyznaczyć dwoma sposobami. 1. Istnieje ścisły związek między rozkładem macierzy A na macierze L i U a metodą eliminacji Gaussa. Można wykazać, że elementy kolejnych kolumn macierzy L są równe współczynnikom przez które mnożone są w kolejnych krokach wiersze układu równań celem dokonania eliminacji niewiadomych w odpowiednich kolumnach . [18] Natomiast macierz U jest równa macierzy trójkątnej uzyskanej w eliminacji Gaussa, czyli ... |
Menu
|