Układy równań liniowych

W tej części opiszemy metodę rozwiązywania układów $ m $ równań z $ n $ niewiadomymi o współczynnikach rzeczywistych.

Układy równań, macierze

W tej części opiszemy metodę rozwiązywania układów $ m $ równań z $ n $ niewiadomymi o współczynnikach rzeczywistych, tzn.\ układów

$ (\ast)\hspace*{70pt}\left\{  \begin{array}{ccccccccc}      a_{11}x_1& + &     a_{12}x_2 & + & \cdots & + & a_{1n} x_n& = & b_1 \\      a_{21}x_1& + &     a_{22}x_2 & + & \cdots & + & a_{2n} x_n& = & b_2 \\      \vdots   &   &       \vdots  &    &        &  & \vdots     &   & \vdots\\      a_{m1}x_1& + &     a_{m2}x_2 & + & \cdots & + & a_{mn} x_n& = & b_m \\  \end{array} \right. $\ ,

gdzie $ a_{ij}\in\R $ są stałymi współczynnikami, $ b_i\in\R $ są stałymi wyrazami wolnymi, a symbole $ x_j $ oznaczają niewiadome.

Definicja (#) Jeśli wszystkie wyrazy wolne $ b_i $ sa zerami, to układ jest jednorodny.

Współczynniki układu $ (\ast) $ można zapisać w postaci $ (m\times n) $-macierzy

$$\left[\begin{array}{ccccc} a_{11}&a_{12}&\ldots&a_{1n}\\ a_{21}&a_{22}&\ldots&a_{2n}\\ \vdots & \vdots &  & \vdots \\ a_{m1}&a_{m2}&\ldots&a_{mn}  \end{array}\right]; $$

współczynnik $ a_{ij} $ nazywamy $ (i,j) $-tym wyrazem macierzy, a $ (m\times 1) $-macierze i $ (1\times n) $-macierze

$$\mk{c}{a_{1j}\\a_{2j}\\\ldots\\a_{mj}}\mbox{ \ i \ }  [a_{i1},a_{i2},\ldots,a_{in}]$$

nazywamy odpowiednio $ j $-tą kolumną i $ i $-tym wierszem macierzy.

Następujące dwie interpretacje będą odgrywały w przyszłości ważną rolę.

Niech $ \R^m $ będzie przestrzenią kolumn o $ m $ elementach, tzn.\ $ (m\times 1) $-macierzy. Elementy $ \R^m $ będziemy nazywali wektorami wymiaru $ m $, a wyraz takiego wektora stojący w $ i $-tym wierszu jego $ i $-tą współrzędną. Wektor, który ma wszystkie współrzędne zerowe nazywamy {\em wektorem zerowym} i oznaczamy symbolem \nolinebreak $ \0 $. Wektory z $ \R^m $ dodajemy, sumując $ i $-te współrzędne i mnożymy przez liczby (lub symbole $ x $), mnożąc każdą współrzędną osobno.

Tak więc układ ($ \ast $) zapisuje się w postaci

\[  (\ast w)\hspace*{80pt}  x_1\left[\begin{array}{c}a_{11}\\a_{21}\\ \vdots \\a_{m1} \end{array}\right]+  x_2\left[\begin{array}{c}a_{12}\\a_{22}\\ \vdots \\a_{m2} \end{array}\right]+\ldots+  x_n\left[\begin{array}{c}a_{1n}\\a_{2n}\\ \vdots \\a_{mn} \end{array}\right]=  \left[\begin{array}{c}b_1\\b_2\\ \vdots \\b_m  \end{array}\right]. \]

Określając iloczyn macierzy o $ n $ kolumnach przez wektor wymiaru $ n $ o współrzędnych $ x_i $ wzorem

$$\left[\begin{array}{ccccc} a_{11}&a_{12}&\ldots&a_{1n}\\ a_{21}&a_{22}&\ldots&a_{2n}\\ \vdots & \vdots &  & \vdots \\ a_{m1}&a_{m2}&\ldots&a_{mn}  \end{array}\right]  \left[\begin{array}{c}x_1\\x_2\\ \vdots \\x_n  \end{array}\right]=  x_1\left[\begin{array}{c}a_{11}\\a_{21}\\ \vdots \\a_{m1} \end{array}\right]+  x_2\left[\begin{array}{c}a_{12}\\a_{22}\\ \vdots \\a_{m2} \end{array}\right]+\ldots+  x_n\left[\begin{array}{c}a_{1n}\\a_{2n}\\ \vdots \\a_{mn} \end{array}\right]$$

i przyjmując oznaczenia

$$A=\left[\begin{array}{ccccc} a_{11}&a_{12}&\ldots&a_{1n}\\ a_{21}&a_{22}&\ldots&a_{2n}\\ \vdots & \vdots &  & \vdots \\ a_{m1}&a_{m2}&\ldots&a_{mn}  \end{array}\right],\quad X=\left[\begin{array}{c}x_1\\x_2\\ \vdots \\x_n  \end{array}\right],\quad B=\left[\begin{array}{c}b_1\\b_2\\ \vdots \\b_m  \end{array}\right], $$

układ równań ($ \ast $) można zapisać w postaci

\[ (\ast m)\hspace*{200pt}AX=B. \]

Tak więc rozwiązanie układu ($ \ast $) polega na wyznaczeniu, o ile istnieją, wszystkich wektorów $ X $ takich, że wektor wyrazów wolnych $ B $ jest iloczynem macierzy współczynników $ A $ i wektora $ X $.

Definicja (#) Układ równań $ AX=B $, który nie ma rozwiązań nazywamy sprzecznym.

Redukcja wierszowa macierzy

Definicja (#) Dwa układy $ m $ równań z $ n $ niewiadomymi nazywamy równoważnymi jeśli mają taki sam zbiór rozwiązań (w szczególności, jeśli oba są sprzeczne).

Opiszemy teraz trzy operacje na układach równań, które nie zmieniają zbioru rozwiązań i pozwalają zastąpić dany układ równań układem równoważnym o przejrzystej, ``schodkowej'' strukturze:

(I)$ _{a(i)+(k)} $    dodanie do $ k $-tego równania $ i $-tego równania pomnożonego przez $ a $,

(II)$ _{(i)(k)} $    zamiana miejscami $ i $-tego równania z $ k $-tym,

(III)$ _{c(i)} $    pomnożenie $ i $-tego równania przez liczbę $ c\neq 0 $.

Twierdzenie (#) Wykonanie na układzie równań liniowych jednej z wymienionych wyżej operacji nie zmienia zbioru rozwiązań tego układu.
Dowód: Teza jest oczywista dla operacji typu (II) i (III). Rozpatrzmy operację (I)$ _{a(i)+(k)} $ przeprowadzającą układ ($ \ast $) na układ $ (\ast)' $, w którym zmienia się jedynie $ k $-te równanie, otrzymane w wyniku dodania stronami do $ k $-tego równania układu $ (\ast) $ równania $ i $-tego, obustronnie pomnożonego przez $ a $.

Jest jasne, że każde rozwiązanie układu ($ \ast $) jest także rozwiązaniem układu $ (\ast)' $. Ponieważ operacja (I)$ _{(-a)(i)+(k)} $ (odwrotna do (I)$ _{a(i)+(k)} $) przeprowadza układ $ (\ast)' $ na układ $ (\ast) $, także rozwiązania układu $ (\ast)' $ są rozwiązaniami $ (\ast) $. To pokazuje równoważność obu układów. □

Przy takich przekształceniach układu równań $ AX=B $, celowe jest pomijanie zmiennych i wykonywanie operacji na wierszach {\em macierzy rozszerzonej} tego układu

$$[A|B]=[A_1,\ldots,A_n|B],$$

gdzie $ A_j $ są kolejnymi kolumnami macierzy $ A $, $ B $ jest dopisaną jako ostatnia kolumną wyrazów wolnych, a kreska oddzielająca $ B $ od poprzednich kolumn nie ma formalnego znaczenia i ma jedynie przypominać, że przy przejściu do układu równań, rola ostatniej kolumny jest inna niż pozostałych.

Operacjom na układach równań odpowiadają następujące {\em operacje elementarne na wierszach macierzy}:

(I)$ _{a(i)+(k)} $    dodanie do $ k $-tego wiersza $ i $-tego pomnożonego przez $ a $,

(II)$ _{(i)(k)} $    zamiana miejscami $ i $-tego wiersza z $ k $-tym,

(III)$ _{c(i)} $    pomnożenie $ i $-tego wiersza przez liczbę $ c\neq 0 $.

Opiszemy teraz pewne macierze o szczególnie prostej postaci i pokażemy, że każdą macierz można sprowadzić do macierzy takiej postaci operacjami typu (I) i (II), zob.\ Uwagę [link].

Definicja (#) Mówimy, że macierz jest w postaci schodkowej jeśli spełnione są dwa warunki:

     {(S1)}\ \ żaden wiersz zerowy tej macierzy nie poprzedza wiersza niezerowego,

     {(S2)}\ \ pierwsze niezerowe wyrazy (schodki) kolejnych niezerowych wierszy tej macierzy stoją w kolumnach o rosnących numerach.

Twierdzenie (#) Dowolną macierz można sprowadzić do postaci schodkowej operacjami elementarnymi typu {\em(I)} i {\em(II)} na wierszach tej macierzy.
Dowód: Niech $ A $ będzie $ (m\times n) $-macierzą mającą niezerowe wyrazy i niech $ j_1 $ będzie numerem pierwszej niezerowej kolumny $ A $. Zamieniając w razie potrzeby wiersze macierzy $ A $ miejscami (operacja typu (II)) można otrzymać macierz $ \widetilde{A} $ mającą niezerowy wyraz $ a_{1j_{1}} $ w pierwszym wierszu kolumny o numerze $ j_{1} $:

$$\widetilde{A} = \left[\begin{array}{rcrcrcc} 0&\ldots&0&a_{1j_{1}}&\ldots&a_{1n}\\ 0&\ldots&0&a_{2j_{1}}&\ldots&a_{2n}\\\vdots &  &\vdots &\vdots &  & \vdots\\ 0&\ldots&0&a_{mj_{1}}&\ldots&a_{mn}\\\end{array}\right].$$

Odejmując kolejno, dla $ i = 2,3,\ldots ,m $, od $ i $-tego wiersza macierzy $ \widetilde{A} $ pierwszy wiersz pomnożony przez $ a_i=\frac{a_{i j_{1}}}{a_{1j_{1}}} $ (czyli wykonując operację

(I)$ _{(-a_i)(1)+(i)} $) otrzymujemy macierz $ A' $, w której kolumny o numerach mniejszych niż $ j_{1} $ są zerowe, a jedynym niezerowym wyrazem w kolumnie o numerze $ j_{1} $ jest $ a_{1j_{1}} $:

$$A'= \left[\begin{array}{rcrccrc}  0&\ldots &0&a_{1j_{1}}&a_{1j_{1}+1}&\ldots&a_{1n}\\  0&\ldots&0&0&a_{2j_{1}+1}'&\ldots&a_{2n}'\\  \vdots &  &\vdots &\vdots&\vdots &  & \vdots \\  0&\ldots&0&0&a_{mj_{1}+1}'&\ldots&a_{mn}'\\  \end{array}\right].$$

W następnym kroku powtarzamy tę procedurę dla macierzy $ A' $ ignorując wyrazy pierwszego wiersza tej macierzy. Znajdujemy $ j_2>j_1 $ i macierz $ A''\in\M{m}{n}{\R} $ (pierwszy wiersz $ A'' $ jest taki jak pierwszy wiersz $ A' $) taką, że wyraz drugiego wiersza kolumny o numerze $ j_2 $ jest niezerowy, a wszystkie wyrazy pod nim oraz wyrazy z wcześniejszych kolumn (z wyjątkiem ignorowanych wyrazów pierwszego wiersza) są zerowe.

Po kolejnych analogicznych krokach dochodzimy do $ (m\times n) $-macierzy $ A^{(r)} $ w postaci schodkowej mającej w $ r $ niezerowych wierszach pierwsze niezerowe wyrazy (schodki) w kolumnach o numerach $ j_1<\ldots<j_r $. □

Uwaga (#) W twierdzeniu [link] można ograniczyć się do operacji typu (I). Operację (II)$ _{(1)(i)} $, którą stosowaliśmy przy przejściu od $ A $ do $ \widetilde{A} $ w przypadku, gdy w kolumnie o numerze $ j_1 $ pierwszy wyraz jest zerowy, a $ i $-ty różny od zera, można zastąpić operacją (I)$ _{1(i)+(1)} $. Analogicznie można postępować w kolejnych krokach.

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' $).