next up previous
Next: 10. Przestrzenie euklidesowe Up: Algebra liniowa II Previous: 8. Diagonalizacja

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

\begin{displaymath}\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.\end{displaymath}

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.

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

gdzie

\begin{displaymath}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].\end{displaymath}

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

\begin{displaymath}X\in Z\iff F_A(X)=B\iff F_A(X)=F_A(X_0)\iff \end{displaymath}


\begin{displaymath}F_A(X-X_0)=0\iff X-X_0\in Ker(F_A)\iff X\in X_0+Ker(F_A).\end{displaymath}

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

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


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

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

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

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

\begin{displaymath}\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.\end{displaymath}

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


\begin{displaymath}\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}\end{displaymath}


\begin{displaymath}\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]\end{displaymath}

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ń

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


\begin{displaymath}\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}}.\end{displaymath}

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

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

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

\begin{displaymath}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}}.\end{displaymath}

Wektory

\begin{displaymath}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]\end{displaymath}

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ć

\begin{displaymath}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}}.\end{displaymath}

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

\begin{displaymath}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].\end{displaymath}

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)

\begin{displaymath}(*)  A\cdot X=B,\end{displaymath}

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

\begin{displaymath}A\cdot X= I\cdot Y\end{displaymath}

i we współrzędnych

\begin{displaymath}\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.\end{displaymath}

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

\begin{displaymath}I\cdot X=C\cdot Y\iff X=CY\end{displaymath}

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

\begin{displaymath}x_i=\frac{\det(A_{x_i})}{\det(A)}.\end{displaymath}

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

\begin{displaymath}B=x_1A_1+x_2A_2+\cdots+x_nA_n\end{displaymath}

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

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


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


\begin{displaymath}\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)\end{displaymath}


\begin{displaymath}=x_i\cdot \det(A),\end{displaymath}

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

\begin{displaymath}x_i=\frac{\det(A_{x_i})}{\det(A)}.\end{displaymath}

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.


next up previous
Next: 10. Przestrzenie euklidesowe Up: Algebra liniowa II Previous: 8. Diagonalizacja
Ludomir Newelski 2005-09-21