Eliminacja Gaussa

Metoda eliminacji Gaussa polega na wykorzystaniu Twierdzenia [link] do analizy układów równań liniowych.

Niech $ AX=B $ będzie układem $ m $ równań z $ n $ niewiadomymi.

Zgodnie z Twierdzeniem [link], macierz rozszerzoną $ [A|B] $ można zredukować operacjami elementarnymi typu (I) i (II) (ignorując kreskę oddzielającą $ A $ i $ B $) do postaci schodkowej $ [A'|B'] $, przy czym, zgodnie z Twierdzeniem [link], układy równań $ AX=B $ i $ AX'=B' $ są równoważne.

Tak więc, należy ustalić, czy układ $ A'X=B' $ jest niesprzeczny i jeśli tak - wyznaczyć wszystkie jego rozwiązania.

Załóżmy, że macierz $ [A'|B'] $ ma $ r $ niezerowych wierszy, których pierwsze niezerowe wyrazy stoją w kolumnach o numerach $ j_1<j_2<\ldots<j_r $.

Jeśli $ j_r=n+1 $ (schodek ostatniego niezerowego wiersza macierzy $ [A'|B'] $ znajduje się w ostatniej kolumnie $ B' $ tej macierzy), to układ $ A'X=B' $ (a więc i układ $ AX=B $) jest sprzeczny.

W przeciwnym wypadku ($ j_r<n+1 $) wszystkie rozwiązania układu $ AX=B $ znajdujemy wyznaczając z układu $ A'X=B' $ niewiadome $ x_{j_1},x_{j_2},\ldots,x_{j_r} $ ({\em zmienne zależne}) w zależno"sci od pozostałych niewiadomych, które mogą przyjmować dowolne warto"sci ({\em zmienne niezależne, parametry}).

Kolejne zmienne zależne $ x_{j_r},x_{j_{r-1}},\ldots x_{j_1} $ wyznaczamy wtedy z kolejnych równań układu $ A'X=B' $, zaczynając od ostatniego niezerowego (tak więc, w pewnym sensie, wyznaczając kolejne zmienne zależne od ostatniej do pierwszej ``wchodzimy po schodkach'' układu równań).

Zmienna zależna $ x_{j_k} $ wyliczana z $ k $-tego równania zależy wyłącznie od zmiennych niezależnych o numerach większych niż $ j_k $ (za zmienne zależne o numerach większych niż $ j_k $ podstawiamy znalezione wcze"sniej zależno"sci).

Uwaga (#) Rozwiązanie $ X\in\R^n $ zależy od $ n-r $ współrzędnych $ X $ - zmiennych niezależnych i można je przedstawić w postaci (zwanej rozwiązaniem ogólnym układu $ AX=B $)

   $ X=X_0+t_1X_1+t_2X_2+\ldots+t_pX_p\ , $

gdzie $ t_1,t_2,\ldots,t_p $ są zmiennymi niezależnymi ($ p=(n-r) $ jest liczbą kolumn macierzy $ A' $ bez schodków).

W praktyce, zamiast wyliczać rozwiązanie ogólne $ X $, wygodnie jest obliczyć wektory $ X_0,X_1,\ldots,X_p $ występujące we wzorze na $ X $, podstawiając za zmienne niezależne odpowiednie wartości:

\qquad $ X_0 $ jest rozwiązaniem $ A'X=B' $ odpowiadającym parametrom $ t_j=0 $ dla $ j=1,2,\ldots,p $,

\qquad $ X_k $ jest rozwiązaniem $ A'X=\0 $ odpowiadającym parametrom $ t_k=1 $ oraz $ t_j=0 $ dla $ j\neq k $

\hspace*{37pt} ($ X_k=(X_0+X_k)-X_0 $ jest rozwiązaniem $ A'X=\0 $ jako różnica dwóch rozwiązań $ A'X=B' $).