7025752573

4 Wykład 1. Metody numeryczne - równania liniowe

1.0.2. Algorytm eliminacji Gaussa-Jordana

Najbardziej podstawową metodą rozwiązywania układu równań liniowych jest metoda eliminacji Gaussa-Jordana. Pierwszy etap (etap eliminacyjny) tej metody polega na zastąpieniu układu równań (1.5) układem:

Ux = f    (1.6)

w którym macierz U jest trójkątną macierzą górną (wszystkie elementy poniżej przekątnej głównej są zerowe).

W drugim etapie (etap odwrotny) rozwiązywany jest układ począwszy od ostatniego wiersza macierzy. Kolejne wiersze, do pierwszego włącznie są określane w oparciu o rozwiązanie uzyskane w poprzednich wierszach. Dokładniej, układ równań:

a\\ a\2 ... a\n		xi		bi '
021 «22 • • • <*2 n		X2	=	b2
ani an2 ... ann		xn		bn

(1.7)

jest poddany postępowaniu eliminacyjnemu, które polega na pomnożeniu pierwszego równania (tj współczynników wiersza macierzy A i wektora b) przez czynnik:

m,i = ^-    (1.8)

i odjęciu go od i-tego równania. W wyniku tej procedury w pierwszej kolumnie macierzy wyeliminowane zostają wszystkie współczynniki z wyjątkiem współczynnika w pierwszym wierszu, tj.:

^aU ^a\2 ••• ^a\n		’ Xl		K
0 ^fl22 ••• ^a2n		x2	=	*2
O •		xn		K .

(1.9)

W kolejnym przebiegu powtarza się powyższą procedurę dla wierszy 2,n eliminując elementy drugiej kolumny macierzy. Postępując analogicznie z pozostałymi wierszami uzyskujemy na końcu macierz U, która jest macierzą trójkątna górną:

Wll U\2 ••• U\n		x\		fi
0 U22 ... U2n		x2	=	fi
0 0 ... unn		^X" .		Sn .

(1.10)

W etapie odwrotnym, poczynając od ostatniego wiersza układu równań (1.6) wyznacza się rozwiązanie:

(1.11)

_ _ Sn

a następnie dla każdego wiersza wyżej odpowiednio:

(1.12)

X_n-1 = -

fn—1 tln—lXn

Całe postępowanie przypomina formalnie rozwiązywanie układów równań metodą przeciwnych współczynników (etap eliminacyjny) i syntezę rozwiązania metodą podstawiania (etap odwrotny).