Rozdział 4 Układy równań liniowych

Opiszemy na przykładzie metodę eliminacji Gaussa pozwalającą sprowadzić dowolny układ do postaci schodkowej. Rozważmy układ równań (w ciele $ℝ$)

Wszystkie informacje o rozważanym układzie możemy wygodnie zakodować przy pomocy macierzy (tabeli):

W wierszach macierzy wypisujemy współczynniki i wyrazy wolne poszczególnych równań. Macierz $A$ nazywamy macierzą układu, a macierz jego macierzą rozszerzoną. Dozwolone operacje (I)-(III) mają swój odpowiednik w postaci dozwolonych operacji na wierszach macierzy:

DOZWOLONE OPERACJE NA WIERSZACH MACIERZY UKŁADU RÓWNAŃ LINIOWYCH (I) możemy dwa wiersze macierzy zamienić miejscami (permutacja); (II) możemy wiersz pomnożyć przez dowolną niezerową liczbę rzeczywistą (skalowanie); (III) możemy wiersz pomnożony przez dowolną liczbę rzeczywistą dodać do innego wiersza.

Zaczynamy od tego, że szukamy wiersza w którym pierwszy wyraz jest niezerowy. W naszym przypadku jest to wiersz pierwszy. Jeśli pierwszy niezerowy wyraz jest różny od $1$, to używamy skalowania (II), aby uzyskać $1$ na pierwszej pozycji.

• Jeżeli w pierwszym wierszu na pierwszej pozycji jest zero, to szukamy innego wiersza z niezerowym wyrazem na pierwszej pozycji. Jeśli taki istnieje, to używamy pierwszej operacji (I) i zamieniamy go miejscami z wierszem pierwszym. Może się zdarzyć, że wszystkie wiersze mają na pierwszej pozycji $0$. Wtedy powtarzamy procedurę szukając wiersza z niezerowym wyrazem na drugiej pozycji i iterujemy poprzednią procedurę.

W pierwszym kroku, używamy pierwszego wiersza i operacji (III) do wprowadzenia zer w pierwszej kolumnie pod jedynką w pierwszym wierszu. Dodając pierwszy wiersz do drugiego otrzymujemy macierz:

Następnie, pomnożony przez 2 pierwszy wiersz dodajemy do wiersza trzeciego

Kończymy ten krok odejmując pierwszy wiersz od wiersza piątego

W drugim kroku używamy analogicznie drugiego wiersza do eliminacji niezerowych elementów w trzeciej kolumnie i wierszach od trzeciego do piątego. W efekcie otrzymujemy

W ostatnim kroku używamy trzeciego wiersza do eliminacji jedynek w piątej kolumnie oraz czwartym i piątym wierszu. Otrzymujemy macierz:

Ostatnie dwa wiersze nie niosą ze sobą żadnej informacji, więc możemy je pominąć otrzymując w efekcie macierz

której odpowiada układ równań

Wstawiamy teraz $x_5=3$ do trzeciego równania i wyliczamy w nim $x_3$ otrzymując

Cofamy się teraz do pierwszego równania i wyliczamy $x_1$ po wstawieniu wartości za $x_3$ i $x_5$ otrzymując

$x_2$ i $x_3$ pełnią tu rolę parametrów. Zbiór rozwiązań jest dany przez

$$\{{[-x_2+4,x_2,-x_4-6,x_4,3]}^T:x_2,x_4\in ℝ\}.$$

Przykładowo, dla $x_2=x_4=0$ jednym z rozwiązań jest ${[4,0,-6,0,3]}^T$. Zbiór rozwiązań jest nieskończony, bo dowolnie wybranym $x_2$ i $x_4$ odpowiada jakieś rozwiązanie.

• Zredukowana postać schodkowa macierzy $A\in M_{m\times n}\left(𝔽\right)$ jest wyznaczona jednoznacznie. Uzasadnimy ten fakt stosując indukcję względem $n$, czyli liczby kolumn macierzy $A$. Dla $n=1$ jest to oczywiste. Niech $n>1$. Rozważmy macierz $A^{\prime }$ otrzymaną z $A$ przez skreślenie ostatniej kolumny. Każdy ciąg operacji elementarnych, który sprowadza $A$ do zredukowanej postaci schodkowej, sprowadza również macierz $A^{\prime }$ do zredukowanej postaci schodkowej. Z założenia indukcyjnego wynika więc, że jeśli $B$ i $C$ są zredukowanymi postaciami schodkowymi macierzy $A$, to $B$ i $C$ mogą się różnić jedynie ostatnią kolumną. Przypuśćmy, że $B\ne C$. Z definicji zredukowanej postaci schodkowej wynika, że na przykład $n$-ta kolumna $B$ jest niezerowa, a $n$-ta kolumna $C$ jest zerowa. Rozważmy taki wektor $x$, że $Bx=0$. Równoważnie $Cx=0$, bo dozwolone operacje nie zmieniają zbioru rozwiązań. Stąd również $\left(B-C\right)x=0$, czyli $x_n=0$, bo $n-1$-pierwszych kolumn macierzy $B-C$ jest zerowych, a $n$-ta jest niezerowa. Prowadzi to do sprzeczności, bo $n$-ta kolumna macierzy $C$ jest zerowa, więc $x_n$ w takim wektorze $x$, że $Cx=0$ może być dowolne.

ELIMINACJA GAUSSA – PODSUMOWANIE Jest to proces sprowadzania macierzy do postaci schodkowej. Możemy używać trzech dozwolonych operacji na wierszach: Permutacja wierszy – Skalowanie wierszy – Dodawanie wiersza do innego wiersza

POSTAĆ SCHODKOWA MACIERZY • jeśli wiersz jest niezerowy, to pierwszym wyrazem niezerowym (liderem) jest $1$ • jeśli wiersz $k$-ty jest niezerowy, to liczba wiodących wyrazów zerowych w wierszu $k+1$ jest większa niż w wierszu $k$-tym, • jeśli są wiersze zerowe, to są one poniżej wierszy niezerowych.

ZREDUKOWANA POSTAĆ SCHODKOWA MACIERZY • macierz ma postać schodkową, • pierwszy niezerowy element w wierszu jest jedynym niezerowym elementem w jego kolumnie.

Rząd macierzy: $\mathrm{rank}A=$ liczba niezerowych wierszy w postaci schodkowej macierzy $A$= liczba kolumna zawierających lidera.

ZBIÓR ROZWIĄZAŃ Dla $k\times n$-macierzy $A$ oraz $b\in {ℝ}^k$ mamy • układ ma dokładnie jedno rozwiązanie $\iff$ • układ jest sprzeczny $\iff$ • układ ma nieskończenie wiele rozwiązań $\iff$

Dla układu równań (4.1) wprowadzamy następujące oznaczenia: macierz

(4.2)

nazywamy macierzą główną układu, natomiast macierz

macierzą rozszerzoną układu. Macierz $A$ ma $k$ wierszy i $n$ kolumn. Przez $M_{k\times n}(𝔽)$ oznaczamy zbiór wszystkich macierzy $A$ postaci (4.2), gdzie wszystkie wyrazy macierzy $a_{ij}$ ($i=1,\mathrm{\dots }k$, $j=1,\mathrm{\dots },n$) są elementami ciała $𝔽$.

Kolumny macierzy $A$ oraz prawą stronę układu możemy interpretować jako wektory w ${𝔽}^k$:

$$a_1=\left[\begin{array}{c}\hfill a_{11}\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill a_{k1}\hfill \end{array}\right],a_2=\left[\begin{array}{c}\hfill a_{12}\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill a_{k2}\hfill \end{array}\right],\mathrm{\dots },a_n=\left[\begin{array}{c}\hfill a_{1n}\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill a_{kn}\hfill \end{array}\right],b=\left[\begin{array}{c}\hfill b_1\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill b_k\hfill \end{array}\right].$$

Będziemy wtedy pisali, że

Zauważmy, że wektor $x={[x_1,\mathrm{\dots },x_n]}^T$ jest rozwiązaniem układu (4.1) wtedy i tylko wtedy, gdy

$$x_1\cdot \left[\begin{array}{c}\hfill a_{11}\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill a_{k1}\hfill \end{array}\right]+\mathrm{\dots }+x_n\cdot \left[\begin{array}{c}\hfill a_{1n}\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill a_{kn}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill b_1\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill b_k\hfill \end{array}\right],$$

czyli

$x_1\cdot a_1+\mathrm{\dots }+x_n\cdot a_n=b.$

KONWENCJE MACIERZOWE ZAPISU UKŁADU RÓWNAŃ W konwencji wierszy W konwencji kolumn

UKŁAD RÓWNAŃ W ZAPISIE MACIERZOWYM $\{\begin{array}{c}\hfill a_{11}{x}_1+\mathrm{\dots }+a_{1n}{x}_n=b_1\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill a_{k1}{x}_1+\mathrm{\dots }+a_{kn}{x}_n=b_k\hfill \end{array}$ $\iff Ax=b$ $\iff x_1\cdot a_1+\mathrm{\dots }+x_n\cdot a_n=b$ $\iff b_1=(w_1^T|x),\mathrm{\dots },b_k=(w_k^T|x)$

Układ równań (4.1) będziemy zapisywać w skrócie jako $Ax=b$. Będziemy mówili, że układ $Ax=b$ ma rozwiązanie, jeśli zbiór jego rozwiązań jest niepusty. Powiemy, że ma on jednoznaczne rozwiązanie, jeśli zbiór jego rozwiązań składa się z jednego wektora.

Dla wektorów $a_1,\mathrm{\dots },a_n\in {𝔽}^k$ naturalnym więc jest rozważenie zbioru

$$\mathrm{Span}\{a_1,\mathrm{\dots },a_n\}=\{x_1\cdot a_1+\mathrm{\dots }+x_n\cdot a_n:x_1,\mathrm{\dots },x_n\in 𝔽\}$$

wszystkich możliwych kombinacji liniowych wektorów $a_1,\mathrm{\dots },a_n$.

Wektor zerowy $x=0$ jest zawsze jednym z rozwiązań układu jednorodnego $Ax=0$. Ciekawe jest pytanie o to kiedy układ jednorodny $Ax=0$ nie ma innych rozwiązań. Kiedy $Ax=0$ ma jednoznaczne rozwiązanie? Aby tak było musi zachodzić implikacja: jeśli $x_1\cdot a_1+\mathrm{\dots }+x_n\cdot a_n=0$ dla pewnych $x_i\in 𝔽$, to $x_1=\mathrm{\dots }=x_n=0$. Innymi słowy, jeśli kombinacja liniowa wektorów $a_1,\mathrm{\dots },a_n$ jest wektorem zerowym, to wszystkie jej współczynniki skalarne są równe $0$. Oznacza to liniową niezależność wektorów $a_1,\mathrm{\dots },a_n$.

Zajmiemy się teraz dokładniej układem dwóch równań liniowych (w ciele $ℝ$) z dwoma niewiadomymi

(4.3)

Skojarzone z nim macierze: główna i rozszerzona to odpowiednio

Przyglądnijmy się możliwym przypadkom.

Przypadek 1. Zakładamy, że

jest macierzą zerową. Układ (4.3) przyjmuje postać

Jeżeli któraś z liczb $b_1$ lub $b_2$ jest różna od zera, to układ jest sprzeczny, czyli jego zbiór rozwiązań jest zbiorem pustym. Jeśli $b_1=b_2=0$, to zbiorem rozwiązań jest cała płaszczyzna ${ℝ}^2$.

Przypadek 2. Zakładamy, że któryś z wierszy macierzy $A$, powiedzmy drugi jest zerowy (czyli $a_{21}=a_{22}=0$), a pierwszy jest niezerowy. Układ (4.3) ma wtedy postać

Jeśli $b_2\ne 0$, to układ jest sprzeczny. Dla $b_2=0$ redukuje się on do jednego równania

$$a_{11}{x}_1+a_{12}{x}_2=b_1$$

opisującego prostą na płaszczyźnie, bo założyliśmy, że $a_{11}^2+a_{12}^2>0$. W tym przypadku zbiorem rozwiązań układu jest więc prosta na płaszczyźnie.

Przypadek 3. Zakładamy, że obydwa wiersze macierzy $A$ są niezerowe. Wtedy obydwa równania opisują proste na płaszczyźnie. Szukamy więc punktów wspólnych dwóch prostych $l_1$ i $l_2$ na płaszczyźnie. Zachodzi jedna z trzech możliwości:

• (i)

  Proste są równe ($l_1=l_2$). Wtedy zbiorem rozwiązań jest prosta $l_1$.

• (ii)

  Proste $l_1$ i $l_2$ są równoległe, ale różne. Wtedy układ jest sprzeczny.

• (iii)

  Proste $l_1$ i $l_2$ nie są równoległe. Wtedy przecinają się w jednym punkcie. Zbiór rozwiązań układu jest jednoelementowy, czyli układ ma dokładnie jedno rozwiązanie.

• Dla niezerowego skalara $a\in 𝔽$ przez $\frac{1}{a}$ będziemy oznaczać element odwrotny $a^{-1}$ do $a$ względem mnożenia w ciele $𝔽$.

• Podamy pewną geometryczną interpretację wyznacznika na płaszczyźnie ${ℝ}^2$. Załóżmy, że wektory $e_1={[1,0]}^T$ i $u={[u_1,u_2]}^T$ są liniowo niezależne. Wtedy . Zauważmy, że

  • –

    wtedy i tylko wtedy, gdy $u_2>0$ wtedy i tylko wtedy, gdy najkrótszy kąt obrotu od wektora $e_1$ do wektora $u$ jest skierowany przeciwnie do ruchu wskazówek zegara;

  • –

    wtedy i tylko wtedy, gdy wtedy i tylko wtedy, gdy najkrótszy kąt obrotu od wektora $e_1$ do wektora $u$ jest skierowany zgodnie z ruchem wskazówek zegara.

PO CO NAM WYZNACZNIK? Dla macierzy poniższe warunki są równoważne: • $\det A\ne 0$, • kolumny $a_1$, $a_2$ są liniowo niezależne, • każdy wektor $b\in {ℝ}^2$ można jednoznacznie zapisać w postaci kombinacji liniowej $b=x_1{a}_1+x_2{a}_2$, • dla każdego wektora $b\in {ℝ}^2$ układ równań $Ax=b$ ma dokładnie jedno rozwiązanie.