Układy równań liniowych. Rozwiązywanie metodą Gaussa
Przykład
-
\[
\begin{array}{cccccc}
5x&-&2y&=&1&/\cdot3\\
2x&+&3y&=&8&/\cdot2\\\hline
19x&&&=&19&/:19\\
x&&&=&1&
\end{array}
\]
Po podstawieniu do pierwszego równania otrzymujemy
\[
\begin{array}{cccccl}
5&-&2y&=&1&/-5\\
&-&2y&=&-4&/:(-2)\\
&&2&=&2&
\end{array}
\]
W ten sposób zostało pokazane, że jeśli jakaś para liczb spełnia wyjściowy układ, to są to liczby \(x=1\) i \(y=2\). Istenieje zatem co najwyżej jedno rozwiązanie. Para \(x=1\) i \(y=2\) jest faktycznie rozwiązaniem układu równań, co można pokazać przez podstawienie. Układ równań jest oznaczony.
UwagaZapis równań z góry na dół oznacza, że ,,dolne'' równanie wynika z ,,górnego''. Jeśli zapisane w ten sposób równania są równoważne i chcemy to zaznaczyć (np. po to, by nie trzeba było podstawiać rozwiązania), należy to zrobić, używając znaku równoważności (,,\(\Longleftrightarrow\)'').
- \[\begin{array}{rcccccr} x&-&y&+&z&=&1\\ x&+&y&+&z&=&1\\ -x&+&y&-&z&=&-1 \end{array}\] Ostatnie równanie jest przeciwne do pierwszego, jest zatem automatycznie spełnione, jeśli spełnione jest pierwsze równanie. Odejmowanie i dodawanie pierwszych dwóch równań daje \[\begin{array}{rcrcrcrl} &-&2y&&&=&0&/:(-2)\\ 2x&&&+&2z&=&2&/:2\\\\ &&y&&&=&0&\\ x&&&+&z&=&1&\\\\ &&y&&&=&0&\\ x&&&&&=&1-z&. \end{array}\] Rozwiązanie musi by\' c postaci \((1-z,0,z)\), \(z\in\mathbb{R}\). Przez podstawienie sprawdza się, że każda taka trójka liczb fakycznie spełnia układ równań. Jest to jednoparametrowa rodzina rozwiązań, a układ taki nazywamy nieoznaczonym.
- \[\begin{array}{rcrcrcr} x&-&y&+&z&=&0\\ x&+&y&-&z&=&1\\ x&-&5y&+&5z&=&-3 \end{array}\] Pierwsze równanie pozostaje niezmienione, od drugiego odejmujemy pierwsze, od trzeciego odejmujemy pierwsze: \[\begin{array}{rcrcrcr} x&-&y&+&z&=&0\\ &&2y&-&2z&=&1\\ &-&4y&+&4z&=&-3. \end{array}\] Suma dwukrotności drugiego równania i trzeciego równania ma postać \[0=-1.\] Równanie to jest nierozwiązywalne, zatem zały układ jest nierozwiązywalny. Nazywamy go sprzecznym.
- \[\begin{array}{rrcrcrcr} I:&x&-&y&+&z&=&0\\ II:&x&+&y&-&z&=&1\\ III:&x&+&y&+&z&=&0\\\\ I+II:&2x&&&&&=&1\\ I+II-2\cdot III:&&-&2y&-&2z&=&1\\ III:&x&+&y&+&z&=&0 \end{array}\] Rozwiązaniem przekształconego układu jest \(x=1/2\), \(y=-1/2\), \(z=0\). Jednak ta trójka liczb nie spełnia układu wyjściowego. Jednocześnie przy tego rodzaju przekształceniach jest oczywiste, \. ze rozwiązanie układu wyjściowego jest jednocześnie rozwiązaniem układuprzekształconego. Jednak skoro istnieje rozwiąznie układu przekształcoengo, niebk edące rozwiązaniem układu wyjściowego, te układy nie są równoważne. Przekształcenia nie są odwracalne. Patrz również: uwaga po pierwszym przykładzie.
Definicja
Równanie liniowe z \(n\) niewiadomymi \(x_1\), \(x_2\), \(\dots\), \(x_n\) jest równaniem postaci
\[
a_1x_1+a_2x_2+\dots+A-nx_n=b
\]
o współczynnikach \(a_1\), \(a_2\), \(\dots\), \(a_n\) oraz \(b\) (współczynnik wolny). Jeśli \(b=0\), równanie nazywamy jednorodnym. Układ \(m\) równań liniowych
\[
\begin{array}{ccccccccc}
a_{11}x_1&+&a_{12}x_2&+&\dots&+&a_{1n}x_n&=&b_1\\
a_{21}x_1&+&a_{22}x_2&+&\dots&+&a_{2n}x_n&=&b_2\\
\dots&&\dots&&\dots&&\dots&&\dots\\
a_{m1}x_1&+&a_{m2}x_2&+&\dots&+&a_{mn}x_n&=&b_m
\end{array}
\]
nazywamy jednorodnym, jeśli \(b_1=b_2=\dots=b_m=0\). Zapisujemy go również w postaci
\[
\sum_{j=1}^na_{kj}x_j=b_k,\qquad k=1,2,\dots,m.
\]
Rozwiązaniem układu równań jest ciąg liczb takich, że po podstawieniu ich za \(x_1\), \(x_2\), \(\dots\), \(x_n\) uzyskujemy \(m\) prawdziwych równości.
Uwaga
Jednorodny układ równań posiada zawsze rozwiązanie zerowe.
Definicja
Tablice postaci \eqref{macierz_wspolczynnikow} nazywamy macierzami rozmiaru \(m\times n\). Macierz \(A\) nazywa się macierzą współczynników układu równań, a \(m\times(n+1)\) macierz
\begin{equation}\tag{2} \label{macierz_rozszerzona}
A^R=\left(\begin{array}{ccccc}
a_{11}&a_{12}&\dots&a_{1n}&b_1\\
a_{21}&a_{22}&\dots&a_{2n}&b_2\\
\vdots&\vdots&\ddots&\vdots&\vdots\\
a_{m1}&a_{m2}&\dots&a_{mn}&b_m\\
\end{array}\right)
\end{equation}
rozszerzoną (uzupełnioną) macierzą współczynników. \(B\) to kolumna wyrazów wolnych.
Definicja
Niech \(z_k\) oznacza \(k\) – ty wiersz rozszerzonej macierzy współczynników układu równań. Następujące przekształcenia:
- [ZI] zastąpienie pewnego wiersza jesgo \(\lambda\) – krotnością (\(\lambda\ne0\)): \[ z_k^\prime=\lambda z_k, \]
- [ZII] dodanie \(\lambda\) – krotności pewnego wiersza do innego wiersza: \[ z_l^\prime=z_l+\lambda z_k,\quad k\ne l, \]
- [ZIII] zamana dwóch wierszy: \[ z_k^\prime=z_l,\quad z_l^\prime=z_k \]
Twierdzenie
Przekształcenia elemantarne wierszy są odwracalne za pomocą przekształceń elementarnych i nie zmieniają zbioru rozwiązań układu równań.
- do (ZI): \(z_k=(1/\lambda)z_k^\prime\),
- do (ZII): \(z_l=z_l^\prime-\lambda z_k\),
- do (ZIII): ponowna zamiana tych samych wierszy.
Uwaga
Spośród przkształceń elementarnych kolumn do rozwiązywania układów równań stosuje się zamianę dwóch kolumn (poza kolumną wolnych współczynników). Zmienia to wprawdzie zbiór rozwiązań równania, ale w sposób kontrolowany, tzn. poprzez zamianęniewiadomych.
Gaussa metoda eliminacji
Do rozwiązywania układów równań liniowych stosuje się następujący algorytm:\\ Krok pierwszy. Ze wszystkich równań poza pierwszym zostaje za pomocą przekształceń elementarnych wyeliminowana pierwsza niewiadoma.- Jeśli wszystkie współczynniki równania są równe zero, nie przekształcamy układu.
- Jeśli wszystkie współczynniki pierwszej kolumny układu są równe zero, zamieniamy tę kolumnę z inną kolumną (poza kolumną wyrazów wolnych), w której nie wszystkie współczynniki są równe zero.
- Zamieniamy wiersze tak, by współczynnik \((1,1)\) (w pierwszej kolmnie, pierszym wierszu) był niezerowy.
- Po kolei przeprowadzamy następujące przekształcenia elementarne: \begin{align*} z_2^\prime&=z_2-l_{21}z_1,\,l_{21}=a_{21},a_{11}\qquad(\text{wówczas } a_{21}^\prime=a_{21}-\frac{a_{21}}{a_{11}}\cdot a_{11}=0),\\ z_3^\prime&=z_3-l_{31}z_1,\,l_{31}=a_{31},a_{11}\qquad(\text{wówczas } a_{31}^\prime=a_{31}-\frac{a_{31}}{a_{11}}\cdot a_{11}=0),\\ \dots&\dots\\ z_m^\prime&=z_m-l_{m1}z_1,\,l_{m1}=a_{m1},a_{11}\qquad(\text{wówczas } a_{m1}^\prime=a_{m1}-\frac{a_{m1}}{a_{11}}\cdot a_{11}=0). \end{align*}
Twierdzenie
Za pomocą elementarnych przekształceń ZI – ZIII oraz SIII można rozszerzonę macierz układu równań liniowych przekształcić do postaci schodkowej
\begin{equation}\tag{3}\label{macierz_schodkowa}
\left(\begin{array}{ccccccc}
a^\prime_{11}&a^\prime_{12}&\dots&a^\prime_{1r}&a^\prime_{1,r+1}&\dots&b^\prime_1\\
0&a^\prime_{22}&\dots&a^\prime_{2r}&a^\prime_{2,r+1}&\dots&b^\prime_2\\
\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\
0&0&\dots&a^\prime_{rr}&a^\prime_{r,r+1}&\dots&b^\prime_r\\
0&0&\dots&0&0&\dots&b^\prime_{r+1}\\
\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\
0&0&\dots&0&0&\dots&0
\end{array}\right)
\end{equation}
Przy tym zachodzi \(a_{jj}\ne0\) dla \(j=1,2,\dots,r\) oraz \(1\leq r\leq\min\{m,n\}\).
Twierdzenie
Układ równań liniowych jest rozwiązywalny wtedy i tylko wtedy, gdy w macierzy \eqref{macierz_schodkowa} zachodzi \(b_k^\prime=0\) dla \(k=r+1,\dots,m\).
Uwaga
Innym sposobem rozwiązania układu równań jest doprowadzenie macierzy schodkowej za pomocą przekształceń elementarnych do postaci
\[
\left(\begin{array}{ccccccc}
1&0&\dots&0&0&\dots&b^\prime_1\\
0&1&\dots&0&0&\dots&b^\prime_2\\
\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\
0&0&\dots&1&0&\dots&b^\prime_r\\
0&0&\dots&0&0&\dots&b^\prime_{r+1}\\
\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\
0&0&\dots&0&0&\dots&0
\end{array}\right)
\]
Jeśli \(b_{r+1}^\prime=0\), rozwiązaniem układu równań jest \((b_1^\prime,b_2^\prime,\dots,b_r^\prime,\lambda_{r+1},\dots,\lambda_n)\), \(\lambda_k\in\mathbb R\) dla \(k=r+1,\dots,n\). W przeciwnym wypadku układ jest sprzeczny.
Przykład
Rozwiąż układy równań:
- \[\left\{\begin{array}{rcrcrcrcr} 8x&+&6y&+&5z&+&2t&=&21,\\ 3x&+&3y&+&2z&+&t&=&10,\\ 4x&+&2y&+&3z&+&t&=&8,\\ 3x&+&5y&+&z&+&t&=&15,\\ 7x&+&4y&+&5z&+&2t&=&18. \end{array}\right.\]
- \[\left\{\begin{array}{rcrcrcrcrcr} 6x&+&4y&+&5z&+&2t&+&3u&=&1,\\ 3x&+&2y&+&4z&+&t&+&2u&=&3,\\ 3x&+&2y&-&2z&+&t&&&=&-7,\\ 9x&+&6y&+&z&+&3t&+&2u&=&2. \end{array}\right.\]
- \[\left\{\begin{array}{rcrcrcrcrcr} x&+& y&+&3z&-&2t&+&3u&=&1,\\ 2x&+&2y&+&4z&-&t&+&3u&=&2,\\ 3x&+&3y&+&5z&-&2t&+&3u&=&1,\\ 2x&+&2y&+&8z&-&3t&+&9u&=&2. \end{array}\right.\]