Zachodniopomorski Uniwersytet Technologiczny w Szczecinie
Wykłady

Układy równań liniowych. Rozwiązywanie metodą Gaussa

Przykład
  1. \[ \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.
    Uwaga
    Zapis 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\)'').
  2. \[\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.
  3. \[\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.
  4. \[\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.
Układ równań liniowych jest jednoznacznie wyznaczony przez tablicę liczb \begin{equation}\tag{1} \label{eq:macierz_wspolczynnikow} A=\left(\begin{array}{cccc} a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&\dots&a_{mn}\\ \end{array}\right) \end{equation} oraz wektor \[ B=\left(\begin{array}{c}b_1\\b_2\\\vdots\\b_m\end{array}\right). \]
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:
  1. [ZI] zastąpienie pewnego wiersza jesgo \(\lambda\) – krotnością (\(\lambda\ne0\)): \[ z_k^\prime=\lambda z_k, \]
  2. [ZII] dodanie \(\lambda\) – krotności pewnego wiersza do innego wiersza: \[ z_l^\prime=z_l+\lambda z_k,\quad k\ne l, \]
  3. [ZIII] zamana dwóch wierszy: \[ z_k^\prime=z_l,\quad z_l^\prime=z_k \]
nazywamy elementarnymi przekształceniami wierszy macierzy \(A^R\) (operacjami elementarnymi na wierszach). Analogicznie definiujemy elementarne przkształcenia kolumn (SI – SIII) macierzy.
Twierdzenie
Przekształcenia elemantarne wierszy są odwracalne za pomocą przekształceń elementarnych i nie zmieniają zbioru rozwiązań układu równań.
Przekształcenia odwrotne do przekształceń elementarnych:
  • 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.
  1. Jeśli wszystkie współczynniki równania są równe zero, nie przekształcamy układu.
  2. 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.
  3. Zamieniamy wiersze tak, by współczynnik \((1,1)\) (w pierwszej kolmnie, pierszym wierszu) był niezerowy.
  4. 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*}
Krok drugi. Postępujemy analogicznie aż do momentu, kiedy dotrzemy do ostatniego wiersza bądź ostatniej kolumny macierzy \(A^R\).
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\}\).
Takie przekształcenie nazywa się eliminacją Gaussa.
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\).
Rozwiązanie \((y_1,y_2,\dots,y_n)\) równania o macierzy rozszerzonej \eqref{macierz_rozszerzona} (będące permutacją – tzn. ciągiem o innej kolejności elementów – rozwiązania układu wyjściowego) dane jest rekurencyjnie: \begin{align*} y_n&=\lambda_n,\qquad\lambda_n\in\mathbb R,\\ y_{n-1}&=\lambda_{n-1},\qquad\lambda_{n-1}\in\mathbb R,\\ \dots\\ y_{r+1}&=\lambda_{r+1},\qquad\lambda_{r+1}\in\mathbb R,\\ y_r&=\frac{1}{a_{rr}^\prime}\left(-a_{r,r+1}^\prime y_{r+1}-\dots-a_{rn}^\prime y_n+b_r\right),\\ y_{r-1}&=\frac{1}{a_{r-1,r-1}^\prime}\left(-a_{r-1,r}^\prime y_r-\dots-a_{r-1,n}^\prime y_n+b_{r-1}\right),\\ \dots\\ y_1&=\frac{1}{a_{11}^\prime}\left(-a_{12}^\prime y_2-\dots-a_{1n}^\prime y_n+b_1\right). \end{align*}
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ń:
  1. \[\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.\]
  2. \[\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.\]
  3. \[\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.\]