9. Układy równań liniowych

W tym rozdziale zbadamy układy równań liniowych, stosując do tego wprowadzone już pojęcia algebry liniowej. Rozważmy następujący układ $r$ równań liniowych z $n$ niewiadomymi $x_1,\dots,x_n$.

$$\mbox{[U]}\left\{\begin{array}{ccccccccc} a_{11}x_1&+&a_{12}x... ...r1}x_1&+&a_{r2}x_2&+&\cdots&+&a_{rn}x_n&=&b_r\end{array}\right.$$

gdzie $a_{ij},b_i$ są ustalonymi liczbami rzeczywistymi (parametrami). W związku z układem [U] rozważymy następujące pytania.

1. Czy układ [U] ma rozwiązanie w zbiorze liczb rzeczywistych ${\mathbb{R}}$ ?

2. Jak opisać zbiór rozwiązań [U] ?

3. Jak praktycznie rozwiązać układ [U] ?

Gdy $b_1,\dots,b_r=0$, mówimy, że układ [U] jest jednorodny. Oznaczmy przez [UJ] układ równań powstały z układu [U] przez zastąpienie parametrów $b_1,\dots,b_r$ zerami. [UJ] nazywamy jednorodnym układem równań związanym z [U].

Parametry $a_{ij}$ układu [U] tworzą macierz $A=[a_{ij}]_{r\times n}$ zwaną macierzą główną układu [U] (i układu [UJ]). Kolejne kolumny macierzy $A$ odpowiadają kolejnym niewiadomym $x_i$. Gdy do macierzy $A$ dopiszemy jako ostatnią kolumnę parametry $b_1,\dots,b_r$, dostaniemy macierz $A_s$ wymiaru $r\times (n+1)$, zwaną macierzą rozszerzoną układu [U].

Macierz $A$ wyznacza przekształcenie liniowe $F_A:{\mathbb{R}}^n\rightarrow {\mathbb{R}}^r$ dane wzorem $F_A(X)=A\cdot X$. Traktując zmienne $x_1,\dots,x_n$ jako współrzędne wektora $X\in {\mathbb{R}}^n$, możemy zapisać układ równań [U] w następujących równoważnych postaciach.

$$\mbox{[U]}\Leftrightarrow A\cdot X=B \mbox{ (postać macierzowa)}\Leftrightarrow F_A(X)=B\mbox{ (postać funkcyjna)},$$

gdzie

$$X=\left[\begin{array}{c}x_1\\ \vdots x_n\end{array}\right], B=\left[\begin{array}{c}b_1 \vdots b_r\end{array}\right].$$

Oznaczmy przez ${\cal Z}$ zbiór rozwiązań układu [U], zaś przez ${\cal Z}_j$ zbiór rozwiązań układu [UJ]. Zbiory te traktujemy jak podzbiory przestrzeni ${\mathbb{R}}^n$.

Fakt 9.1   1) ${\cal Z}_j=Ker(F_A)$. W szczególności, ${\cal Z}_j$ jest podprzestrzenią ${\mathbb{R}}^n$ i zawiera wektor zerowy.
2) Układ [U] ma rozwiązanie $\iff B\in Im(F_A)$. Wówczas zbiór rozwiązań ${\cal Z}$ jest warstwą $Ker(F_A)$ w przestrzeni ${\mathbb{R}}^n$.

Dowód. 1) wynika natychmiast z funkcyjnej postaci ukladu równań [UJ]. $Ker(F_A)$ jest podprzestrzenią ${\mathbb{R}}^n$ na mocy faktu 4.9.

2) Układ [U] ma rozwiązanie $\iff {\cal Z}\neq\emptyset\iff$ $F_A(X)=B$ dla pewnego $X\in {\mathbb{R}}^n\iff B\in Im(F_A)$. Załóżmy, że $X_0$ jest pewnym rozwiązaniem [U], to znaczy $F_A(X_0)=B$. Pokażemy, że ${\cal Z}=X_0+Ker(F_A)$ jest warstwą $Ker(F_A)$. Dla $X\in {\mathbb{R}}^n$ mamy

$$X\in Z\iff F_A(X)=B\iff F_A(X)=F_A(X_0)\iff$$

$$F_A(X-X_0)=0\iff X-X_0\in Ker(F_A)\iff X\in X_0+Ker(F_A).$$

Przy pomocy następnego twierdzenia możemy łatwo rozstrzygnąć, czy układ [U] ma rozwiązanie.

Twierdzenie 9.2 (Kronecker-Capelli)   Układ [U] ma rozwiązanie $\iff$ rząd macierzy głównej układu [U] = rząd macierzy rozszerzonej tego układu.

Dowód. Zapiszmy macierz $A$ jako ciąg kolumn $A=(A_1,\dots,A_n)$. Mamy $A_i=F_A(E_i)$ dla $i=1,\dots,n$. Na mocy uwagi 4.11 wektory
$F_A(E_1),\dots,F_A(E_n)$ generują $Im(F_A)$. Zatem z faktu 9.1 wynika, że

$$\mbox{układ [U] ma rozwiązanie }\iff B\in Im(F_A)\iff B\in Lin(A_1,\dots,A_n)$$

$$\iff \mbox{rząd}(A_1,\dots,A_n)=\mbox{rząd}(A_1,\dots,A_n,B)=\mbox{rząd}(A_s).$$

Uwaga 9.3   Przestrzeń liniowa ${\cal Z}_j$ rozwiązań układu jednorodnego [UJ] ma wymiar $d=n-\mbox{rząd}(A)$.

Dowód. $Z_j=Ker(F_A), F_A:{\mathbb{R}}^n\rightarrow {\mathbb{R}}^r,\ \dim(Im(F_A))=\mbox{rząd}(A)$ oraz na mocy twierdzenia 4.12, $n=\dim({\mathbb{R}}^n)=\dim(Ker(F_A))+\dim(Im(F_A))$. Stąd natychmiast dostajemy tezę.

Załóżmy, że układ [U] ma rozwiązanie (tzn. jest niesprzeczny). Na mocy faktu 9.1, ${\cal Z}=X_0+{\cal Z}_j$, gdzie $X_0$ jest dowolnym rozwiązaniem [U]. Niech $X_1,\dots,X_d$ będzie bazą przestrzeni ${\cal Z}_j$. Wówczas zbiór rozwiązań ${\cal Z}$ możemy opisać równaniem w postaci parametrycznej

$$X=X_0+t_1X_1+\cdots+t_dX_d, t_1\dots,t_d\in {\mathbb{R}}.$$

Równanie parametryczne $X=t_1X_1+\cdots+t_dX_d, t_1,\dots,t_d\in {\mathbb{R}}$, opisuje podprzestrzeń ${\cal Z}_j$. Z tego względu dowolną bazę $X_1,\dots,X_d$ przestrzeni ${\cal Z}_j$ nazywamy fundamentalnym układem rozwiązań układu równań [UJ].

Do rozwiązywania układu równań [U] w praktyce służy metoda eliminacji niewiadomych, zwana też metodą Gaussa. By opisać tę metodę, zauważmy, że następujące operacje na równaniach układu [U] nie zmieniają zbioru rozwiązań ${\cal Z}$:

1. Zamiana miejscami równań $i$-tego i $j$-tego ($i\neq j$).
2. Dodanie do $i$-tego równania stronami skalarnej krotności $j$-tego równania ($i\neq j$).
3. Pomnożenie $i$-tego równania stronami przez skalar $t\neq 0$.

Operacje te wygodnie jest przeprowadzać nie bezpośrednio na układzie [U], lecz na jego macierzy rozszerzonej $A_s$. Wówczas odpowiadają one operacjom (1),(2),(3) z faktu 7.7.

Metoda Gaussa polega na takim przekształceniu macierzy rozszerzonej $A_s$ układu [U] poprzez operacje z faktu 7.7, by otrzymać macierz $A_s'$ (wymiaru $r\times n$) z uporządkowanymi wierszami. Macierz ta odpowiada pewnemu układowi równań [U'] równoważnemu układowi [U]. Jeśli teraz w macierzy $A_s'$ wyraz wiodący w pewnym wierszu znajduje się w ostatniej kolumnie, to układ równań [U] jest sprzeczny (nie ma rozwiązań). W przeciwnym razie układ [U] jest niesprzeczny i możemy znaleźć jego rozwiązania w następujący sposób.

Zmienne $x_i$ odpowiadające kolumnom macierzy $A_s'$ zawierającym wyraz wiodący w jakimś wierszu nazywamy zmiennymi związanymi, pozostałe zmienne nazywamy zmiennymi parametrycznymi. Przekształcamy układ [U'] wyrażając zmienne związane przy pomocy parametrów układu [U'] i zmiennych parametrycznych, dostając w ten sposób parametryczne rozwiązanie układu [U]. Prześledzimy teraz tę metodę na przykładzie.

Przykład. Rozważmy układ

$$\mbox{[U]}\left\{\begin{array}{ccccccccc} -x_1&+&3x_2&+&2x_3&... ...3\\ x_1&+&\mbox{}&\mbox{}&x_3&+&4x_4&=&3\\ \end{array}\right.$$

Przekształcamy macierz rozszerzoną tego układu doprowadzając ją do postaci z uporządkowanymi wierszami.

$$\left[\begin{array}{rrrrr}-1&3&2&-1&0\\ 1&-2&-1&2&1\\ 2&-3&... ...!\!\begin{array}{l}\mbox{} \mbox{} -3[2] -3[2]\end{array}$$

$$\longrightarrow\left[\begin{array}{rrrrr}-1&3&2&-1&0 0&1&1&1&1\\ 0&0&0&0&0 0&0&0&0&0\end{array}\right]$$

Ostatnia macierz ma uporządkowane wiersze. Zmienne zależne to w naszym przypadku $x_1$ i $x_2$, zaś zmienne parametryczne to $x_3$ i $x_4$. Uzyskana macierz odpowiada równoważnemu układowi równań

$$\mbox{[U']} \left\{\begin{array}{ccccccccc} -x_1&+&3x_2&+&... ...4&=&0 \mbox{}&\mbox{}&x_2&+&x_3&+&x_4&=&1\ \end{array}\right.$$

$$\iff\left\{\begin{array}{ccc}x_2&=&1-x_3-x_4\\ x_1&=&3-x_3-4x_4\end{array}\right., x_3,x_4\in {\mathbb{R}}.$$

Widzimy, że gdy $x_3,x_4$ przebiegają ${\mathbb{R}}$, ostatni układ równości daje nam wszystkie rozwiązania układu [U]. Dla $x_3=x_4=0$ dostajemy konkretne rozwiązanie

$$X_0=\left[\begin{array}{c}3 1 0\\ 0\end{array}\right].$$

Dowolne rozwiązanie układu [U] jest więc postaci

$$X=\left[\begin{array}{c}3-x_3-4x_4 1-x_3-x_4 x_3\\ x_4\e... ...{r}-4 -1 0 1\end{array}\right], x_3,x_4\in {\mathbb{R}}.$$

Wektory

$$X_1=\left[\begin{array}{r}-1 -1 1\\ 0\end{array}\right], X_2=\left[\begin{array}{r}-4 -1 0\\ 1\end{array}\right]$$

są fundamentalnym układem rozwiązań jednorodnego układu [UJ] związanego z [U]. Układ taki można wybrać na wiele sposobów. Wiemy, że dowolne rozwiązanie układu [UJ] ma postać

$$X=\left[\begin{array}{c}-x_3-4x_4 -x_3-x_4 x_3\\ x_4\end{array}\right], x_3,x_4\in {\mathbb{R}}.$$

Niech $F:{\mathbb{R}}^2\rightarrow {\mathbb{R}}^4$ będzie funkcją liniową daną wzorem

$$F\left[\begin{array}{cc}x_3 x_4\end{array}\right]=\left[\begin{array}{c}-x_3-4x_4 -x_3-x_4 x_3\\ x_4\end{array}\right].$$

Widzimy, że $F$ jest 1-1 oraz $Im(F)$ jest zbiorem rozwiązań układu [UJ]. $F$ jest izomorfizmem między ${\mathbb{R}}^2$ i $Im(F)$, dlatego przekształca dowolną bazę przestrzeni ${\mathbb{R}}^2$ na bazę przestrzeni $Im(F)$, czyli na fundamentalny układ rozwiązań układu [UJ]. Wektory $X_1,X_2$ są obrazami względem $F$ wektorów bazowych $E_1\ (x_3=1,x_4=0)$ i $E_2 (x_3=0,x_4=1)$.

Jeślibyśmy w 3 równaniu układu [U] zmienili liczbe $3$ po prawej stronie równości na liczbę $5$, to stosując powyższe operacje doprowadzilibyśmy macierz rozszerzoną układu [U] do postaci z uporządkowanymi wierszami, gdzie wyraz wiodący w 3 wierszu znajdowałby sie w ostatniej kolumnie. Byłby to więc układ sprzeczny.

Rozważymy teraz szczególny przypadek układu $n$ równań liniowych z $n$ niewiadomymi (stosujemy zapis macierzowy)

$$(*) A\cdot X=B,$$

gdzie $A$ jest macierzą wymiaru $n\times n$, $B\in {\mathbb{R}}^n$, zaś $X$ jest niewiadomym wektorem z ${\mathbb{R}}^n$. Załóżmy, że $A$ jest odwracalna. Wówczas $A\cdot X=B\iff X=A^{-1}\cdot B$, zatem w tym przypadku $(*)$ ma jedyne rozwiązanie.

Możemy teraz uzasadnić ``bezwyznacznikową metodę'' obliczania macierzy odwrotnej $A^{-1}$ opisaną w rozdziale 6. Rozważmy mianowicie układ równości $A\cdot X=Y$, gdzie $X,Y\in {\mathbb{R}}^n$. Możemy go zapisać w postaci

$$A\cdot X= I\cdot Y$$

i we współrzędnych

$$\left\{\begin{array}{ccccccccccc} a_{11}x_1+&\cdots&+a_{1n}x_... ...=&0\cdot y_1&+&0\cdot y&+&\cdots&+&1\cdot y_n\end{array}\right.$$

Operacje opisane w rozdziale 6 odpowiadają równoważnym przekształceniom tego układu równości, prowadzącym do macierzowej równości

$$I\cdot X=C\cdot Y\iff X=CY$$

dla pewnej macierzy $C$. Dlatego $A^{-1}Y=X\iff AX=Y\iff CY=X$ dla wszystkich $X,Y\in {\mathbb{R}}^n$. Stąd wynika, że $C=A^{-1}$.

Powróćmy do układu równań $(*)$. Zapiszmy macierz $A$ w postaci ciągu kolumn $A=(A_1,\dots,A_n)$. Przez $A_{x_i}$ oznaczamy macierz powstałą przez zastąpienie w macierzy $A$ $i$-tej kolumny przez $B$. Następujące twierdzenie pokazuje kolejne zastosowanie wyznacznika.

Twierdzenie 9.4 (Cramer)   Jeśli $\det(A)\neq 0$, to układ $(*)$ ma jedyne rozwiązanie $x_1,\dots,x_n$ dane wzorem

$$x_i=\frac{\det(A_{x_i})}{\det(A)}.$$

Dowód. Jeśli $\det(A)\neq 0$, to macierz $A$ jest odwracalna, więc istnieje jedyne rozwiązanie $x_1,\dots,x_n$ układu równań $(*)$. Lewą stronę $(*)$ możemy zapisać jako $x_1A_1+x_2A_2+\cdots+x_nA_n$. Zatem

$$B=x_1A_1+x_2A_2+\cdots+x_nA_n$$

jest linową kombinacją kolumn $A_1,\dots,A_n$ ze współczynnikami $x_1,\dots,x_n$. Dlatego

$$\det(A_{x_i})=\det(A_1,\dots\overbrace{B}^i,\dots,A_n)=$$

$$\det(A_1,\dots,\overbrace{x_1A_1+\cdots+x_nA_n}^i,\dots,A_n)=$$

$$\sum_{j=1}^n\det(A_1,\dots,\overbrace{x_jA_j}^i,\dots,A_n)=\sum_{j=1}^nx_j\det(A_1,\dots,\overbrace{A_j}^i,\dots,A_n)$$

$$=x_i\cdot \det(A),$$

gdyż dla $j\neq i, \det(A_1,\dots,\overbrace{A_j}^i,\dots,A_n)=0$, podczas gdy dla $j=i$,
$\det(A_1,\dots,\overbrace{A_j}^i,\dots,A_n)=\det(A)$. Stąd natychmiast dostajemy, że

$$x_i=\frac{\det(A_{x_i})}{\det(A)}.$$

W praktyce twierdzenie Cramera można stosować tylko dla niewielkich układów równań, w związku z kłopotliwością obliczania wyznaczników dużych macierzy.