Soustavy lineárních rovnic a Gaussova eliminace
Proč to potřebuji?
Soustavy rovnic potkáváš všude — od výpočtu proudů v elektrickém obvodu, přes ekonomické modely, až po počítačovou grafiku. Gaussova eliminační metoda (GEM) je univerzální algoritmus, kterým vyřešíš jakoukoli soustavu lineárních rovnic. Je to základ, na kterém stojí celá lineární algebra.
Předpoklady: Základní počítání s čísly (sčítání, násobení, zlomky). Nic víc nepotřebuješ.
Teorie
Co je soustava lineárních rovnic
Lineární algebraická rovnice o $n$ neznámých $x_1, x_2, \ldots, x_n \in \mathbb{R}$ je rovnice ve tvaru
$$a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b,$$kde $a_1, a_2, \ldots, a_n \in \mathbb{R}$ jsou koeficienty a $b \in \mathbb{R}$ je konstanta (pravá strana).
Jednoduše řečeno: v lineární rovnici se neznámé vyskytují jen v první mocnině a nejsou navzájem násobeny. Například $3x_1 - 2x_2 + x_3 = 5$ je lineární rovnice, ale $x_1 \cdot x_2 = 3$ nebo $x^2 = 4$ lineární nejsou.
Soustava $m$ lineárních algebraických rovnic o $n$ neznámých je:
$$\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &= b_2 \\ &\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &= b_m \end{aligned}$$Řešením soustavy je každá $n$-tice čísel $(s_1, s_2, \ldots, s_n)$, která splňuje všechny rovnice současně.
Soustava lineárních rovnic má vždy právě jednu z těchto možností:
- Právě jedno řešení — rovnice se protínají v jednom bodě
- Nekonečně mnoho řešení — řešení závisí na parametru (parametrech)
- Žádné řešení — rovnice si vzájemně odporují
Je-li $b_1 = b_2 = \cdots = b_m = 0$ (všechny pravé strany jsou nulové), nazýváme soustavu homogenní. Homogenní soustava má vždy alespoň jedno řešení — triviální řešení $x_1 = x_2 = \cdots = x_n = 0$.
Maticový zápis soustavy
Abychom nemuseli neustále opisovat neznámé, zapíšeme koeficienty do tabulky — matice.
Matice soustavy $\mathbf{A}$ obsahuje jen koeficienty u neznámých. Rozšířená matice soustavy $(\mathbf{A}|\vec{b})$ přidává navíc sloupec pravých stran:
$$\mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}, \qquad (\mathbf{A}|\vec{b}) = \left(\begin{array}{cccc|c} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{array}\right)$$Příklad zápisu: Soustava
$$\begin{aligned} x_1 + 2x_2 + x_3 &= 3 \\ 3x_1 - x_2 - 3x_3 &= -1 \\ 2x_1 + 3x_2 + x_3 &= 4 \end{aligned}$$se zapíše jako rozšířená matice:
$$\left(\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 3 & -1 & -3 & -1 \\ 2 & 3 & 1 & 4 \end{array}\right)$$Elementární řádkové úpravy
Klíčový nápad: na rozšířené matici smíme provádět operace, které nemění množinu řešení, ale zjednodušují matici.
Následující operace s řádky matice zachovávají množinu řešení soustavy:
- Výměna dvou řádků: $R_i \leftrightarrow R_j$
- Vynásobení řádku nenulovým číslem: $\alpha \cdot R_i \to R_i$, kde $\alpha \neq 0$
- Přičtení násobku jednoho řádku k jinému: $R_i + \alpha \cdot R_j \to R_i$
Řádek smíme násobit pouze nenulovým číslem. Vynásobením nulou bychom ztratili informaci a změnili množinu řešení.
Gaussova eliminační metoda (GEM)
GEM je postup, kterým převedeme rozšířenou matici na řádkově odstupňovaný tvar (schodovitý tvar). Pak snadno vyčteme řešení zpětnou substitucí.
Matice je v řádkově odstupňovaném tvaru, jestliže:
- Obsahuje-li $i$-tý řádek samé nuly, pak všechny řádky pod ním jsou také nulové.
- První nenulový prvek v každém nenulovém řádku (tzv. pivot) leží ve sloupci s vyšším indexem než pivot předchozího řádku.
Typická struktura ($\#$ = pivot, $*$ = libovolné číslo):
$$\begin{pmatrix} \# & * & * & * & * \\ 0 & \# & * & * & * \\ 0 & 0 & 0 & \# & * \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$Algoritmus GEM krok za krokem
- Začni v prvním sloupci. Najdi řádek s nenulovým prvkem (pokud je na pozici pivota nula, vyměň řádky).
- Pomocí operace „přičtení násobku" vynuluj všechny prvky pod pivotem v tomto sloupci.
- Přejdi na další sloupec a opakuj totéž pro menší podmatici.
- Pokračuj, dokud nezpracuješ všechny sloupce nebo řádky.
Výsledkem je matice v odstupňovaném tvaru. Řešení pak najdeš zpětnou substitucí — od posledního řádku nahoru.
Hodnost matice a existence řešení
Hodnost matice $\mathbf{A}$ (značíme $\text{hod}\,\mathbf{A}$ nebo $\text{rank}\,\mathbf{A}$) je počet nenulových řádků v jejím řádkově odstupňovaném tvaru. Ekvivalentně: počet pivotů.
Soustava $\mathbf{A}\vec{x} = \vec{b}$ má řešení právě tehdy, když:
$$\text{hod}\,\mathbf{A} = \text{hod}\,(\mathbf{A}|\vec{b})$$Navíc:
- Je-li $\text{hod}\,\mathbf{A} = n$ (počet neznámých) → právě jedno řešení
- Je-li $\text{hod}\,\mathbf{A} < n$ → nekonečně mnoho řešení (závisí na $n - \text{hod}\,\mathbf{A}$ parametrech)
Sloupce obsahující pivoty odpovídají bázovým proměnným (ty vyjádříme jednoznačně). Zbývající neznámé jsou volné proměnné — ty si můžeme zvolit libovolně (parametry řešení).
Homogenní a nehomogenní soustavy
Obecné řešení nehomogenní soustavy $\mathbf{A}\vec{x} = \vec{b}$ má tvar:
$$\vec{x} = \vec{p} + x_{f_1}\vec{h}_1 + x_{f_2}\vec{h}_2 + \cdots + x_{f_{n-r}}\vec{h}_{n-r}$$kde $\vec{p}$ je partikulární řešení (jedno konkrétní řešení), $\vec{h}_1, \ldots, \vec{h}_{n-r}$ jsou řešení přidružené homogenní soustavy $\mathbf{A}\vec{x} = \vec{0}$ a $x_{f_1}, \ldots, x_{f_{n-r}}$ jsou volné proměnné.
Řešené příklady
Řešte soustavu rovnic metodou GEM:
$$\begin{aligned} 3x_1 - 2x_2 - x_3 &= 5 \\ 2x_1 + 5x_2 - x_3 &= -4 \\ x_1 + 2x_2 + x_3 &= 3 \end{aligned}$$Koeficienty a pravé strany přepíšeme do rozšířené matice:
$$\left(\begin{array}{ccc|c} 3 & -2 & -1 & 5 \\ 2 & 5 & -1 & -4 \\ 1 & 2 & 1 & 3 \end{array}\right)$$Jednička v prvním sloupci třetího řádku se nám bude lépe pracovat jako pivot:
$$\xrightarrow{R_1 \leftrightarrow R_3} \left(\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 2 & 5 & -1 & -4 \\ 3 & -2 & -1 & 5 \end{array}\right)$$Vynulujeme prvky pod jedničkou v prvním sloupci:
$$\xrightarrow{\substack{R_2 - 2R_1 \to R_2 \\ R_3 - 3R_1 \to R_3}} \left(\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 1 & -3 & -10 \\ 0 & -8 & -4 & -4 \end{array}\right)$$Výpočet: $R_2$: $(2-2, 5-4, -1-2, -4-6) = (0, 1, -3, -10)$. $R_3$: $(3-3, -2-6, -1-3, 5-9) = (0, -8, -4, -4)$.
Výpočet $R_3$: $(0+0, -8+8, -4-24, -4-80) = (0, 0, -28, -84)$.
Matice je v odstupňovaném tvaru. Čteme od posledního řádku:
- $x_3 = 3$
- $x_2 = -10 + 3x_3 = -10 + 9 = -1$
- $x_1 = 3 - 2x_2 - x_3 = 3 - 2 \cdot (-1) - 3 = 2$
Řešení: $x_1 = 2, \; x_2 = -1, \; x_3 = 3$.
Najděte všechna řešení homogenní soustavy:
$$\left(\begin{array}{cccc|c} 1 & 1 & -2 & 3 & 0 \\ 4 & 3 & -1 & 5 & 0 \\ 2 & 1 & 3 & -1 & 0 \end{array}\right)$$Pivoty jsou ve sloupcích 1 a 2 → bázové proměnné: $x_1, x_2$.
Sloupce 3 a 4 nemají pivot → volné proměnné: $x_3, x_4$ (můžeme volit libovolně).
$\text{hod}\,\mathbf{A} = 2$, počet neznámých $n = 4$ → řešení závisí na $4 - 2 = 2$ parametrech.
Z druhé rovnice: $x_2 = 7x_3 - 7x_4$
Z první rovnice: $x_1 = -x_2 + 2x_3 - 3x_4 = -(7x_3 - 7x_4) + 2x_3 - 3x_4 = -5x_3 + 4x_4$
Obecné řešení zapíšeme vektorově:
$$\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = x_3 \begin{pmatrix} -5 \\ 7 \\ 1 \\ 0 \end{pmatrix} + x_4 \begin{pmatrix} 4 \\ -7 \\ 0 \\ 1 \end{pmatrix}, \quad x_3, x_4 \in \mathbb{R}$$Najděte všechna řešení soustavy:
$$\left(\begin{array}{cccc|c} 1 & -1 & 1 & -1 & 1 \\ 2 & 1 & -1 & 2 & 2 \\ 3 & 3 & -3 & 5 & 3 \\ 1 & 2 & -1 & 3 & 2 \end{array}\right)$$$\text{hod}\,\mathbf{A} = \text{hod}\,(\mathbf{A}|\vec{b}) = 3$. Počet neznámých $n = 4$ → řešení závisí na $4 - 3 = 1$ parametru.
Pivoty ve sloupcích 1, 2, 3 → bázové proměnné $x_1, x_2, x_3$. Volná: $x_4 = k, \; k \in \mathbb{R}$.
Z třetí rovnice: $x_3 = 1$
Z druhé: $3x_2 = 3x_3 - 4x_4 = 3 - 4k$ → $x_2 = 1 - \frac{4}{3}k$
Z první: $x_1 = 1 + x_2 - x_3 + x_4 = 1 + (1 - \frac{4}{3}k) - 1 + k = 1 - \frac{1}{3}k$
Položíme $x_4 = 3k$ (volba pro hezčí čísla):
$$\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \end{pmatrix} + k\begin{pmatrix} -1 \\ -4 \\ 0 \\ 3 \end{pmatrix}, \quad k \in \mathbb{R}$$Ukažte, že následující soustava nemá řešení:
$$\left(\begin{array}{cc|c} 1 & 1 & 1 \\ 1 & -1 & 3 \\ -1 & 2 & -2 \end{array}\right)$$Poslední řádek odpovídá rovnici:
$$0 \cdot x_1 + 0 \cdot x_2 = 2 \quad \Longrightarrow \quad 0 = 2$$To je spor! Žádné hodnoty $x_1, x_2$ tuto rovnici nesplní.
Formálně: $\text{hod}\,\mathbf{A} = 2$, ale $\text{hod}\,(\mathbf{A}|\vec{b}) = 3$. Hodnosti se nerovnají → soustava nemá řešení.
Jsou dány body $P[1, 6]$, $Q[-1, 8]$, $R[2, 11]$. Určete rovnici polynomu 2. stupně $y = ax^2 + bx + c$ procházejícího těmito body.
Dosadíme souřadnice bodů do $y = ax^2 + bx + c$:
$$\begin{aligned} P[1,6]: \quad a + b + c &= 6 \\ Q[-1,8]: \quad a - b + c &= 8 \\ R[2,11]: \quad 4a + 2b + c &= 11 \end{aligned}$$$-3c = -15 \Rightarrow c = 5$
$-2b = 2 \Rightarrow b = -1$
$a = 6 - b - c = 6 + 1 - 5 = 2$
Výsledek: $y = 2x^2 - x + 5$
Určete všechna řešení homogenní soustavy:
$$\left(\begin{array}{ccc|c} 1 & 1 & 1 & 0 \\ 2 & 2 & 2 & 0 \\ 1 & 2 & 3 & 0 \\ 3 & 4 & 5 & 0 \end{array}\right)$$$\text{hod}\,\mathbf{A} = 2$, neznámých $n = 3$ → volná proměnná: $x_3 = t$.
$x_2 = -2t$, $\;x_1 = -x_2 - x_3 = 2t - t = t$.
$$\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = t \begin{pmatrix} 1 \\ -2 \\ 1 \end{pmatrix}, \quad t \in \mathbb{R}$$Cvičení k procvičení
Cvičení 1: Řešte soustavu rovnic metodou GEM:
$$x_1 + x_2 - 2x_3 + 3x_4 = 4 \qquad 2x_1 + 3x_2 + 3x_3 - x_4 = 3 \qquad 5x_1 + 7x_2 + 4x_3 + x_4 = 5$$$x_1 = 1 + x_2 - 2x_3 + 3x_4 - \text{...}$ Řešení: $x_1 + 2x_3 - 3x_3 - 2x_4 + 4x_5 = 1$. Nekonečně mnoho řešení závisejících na volných proměnných.
Cvičení 2: Určete všechna řešení homogenní soustavy (zapište jako rozšířenou matici a použijte GEM):
$$\begin{aligned} x_1 + 2x_2 + 3x_3 &= 0 \\ 4x_1 + 7x_2 + 5x_3 &= 0 \\ x_1 + 6x_2 + 10x_3 &= 0 \\ x_1 + x_2 - 4x_3 &= 0 \end{aligned}$$Řešení: $(x_1, x_2, x_3)^T = (0, 0, 0)^T$ — pouze triviální řešení (hodnost = 3 = počet neznámých).
Cvičení 3: Řešte soustavu:
$$\begin{aligned} x_1 + x_2 - 2x_3 + 3x_4 &= 4 \\ 2x_1 + x_2 + 3x_3 + 3x_4 &= 3 \\ 5x_1 + 7x_2 + 4x_3 + x_4 &= 5 \end{aligned}$$Výsledek: nemá řešení (sporná rovnice $0 = c \neq 0$).
Cvičení 4: Homogenní soustava — najděte obecné řešení:
$$\left(\begin{array}{ccc|c} 1 & 1 & 1 & 0 \\ 2 & 2 & 2 & 0 \\ 1 & 2 & 3 & 0 \\ 3 & 4 & 5 & 0 \end{array}\right)$$$(x_1, x_2, x_3)^T = t(1, -2, 1)^T$, $t \in \mathbb{R}$.
Cvičení 5: Jsou dány body $P[-2, 0]$, $Q[1, 6]$, $R[-1, 6]$, $S[3, 30]$. Určete rovnici polynomu stupně 3 ($y = ax^3 + bx^2 + cx + d$) procházejícího těmito body.
$y = x^3 - x + 6$
Cvičení 6: Řešte soustavu, kde pravé strany nejsou nulové:
$$\begin{aligned} x_1 + x_2 + 2x_3 + 3x_4 &= 4 \\ 2x_1 + x_2 + 3x_3 - x_4 &= 3 \\ 5x_1 + x_2 + 7x_3 + x_4 &= 5 \end{aligned}$$Řešení závisí na 2 parametrech (hodnost = 2, neznámých = 4). Obecné řešení vyjádřete jako partikulární + lineární kombinaci vektorů.
Cvičení 7: Řešte soustavu s podíly — použijte substituci $u = \frac{1}{x+y}$, $v = \frac{1}{x-y}$:
$$\frac{1}{x+y} + \frac{1}{x-y} = 1 \qquad \frac{6}{x+y} + \frac{12}{x-y} = 7$$$(x, y)^T = (3, 6; -2, 4)^T$. Po substituci $u + v = 1$ a $6u + 12v = 7$, řešíme lineární soustavu pro $u, v$.
Cvičení 8: Soustava s absolutní hodnotou — rozepište na případy a řešte:
$$3(x-1)(x+2) - 2(y-2)(y+3) = 20 \qquad 2(x-1)(x+2) + 3(y-2)(y+3) = -4$$Substituujte $u = (x-1)(x+2) = x^2+x-2$ a $v = (y-2)(y+3) = y^2+y-6$. Pak $3u - 2v = 20$ a $2u + 3v = -4$. Řešení: $u = 4, v = -4$, odkud $x \in \{2, -3\}$, $y \in \{1, -2\}$.
Shrnutí
Klíčové vzorce a pojmy
- Rozšířená matice: $(\mathbf{A}|\vec{b})$ — koeficienty + pravé strany
- Elementární řádkové úpravy: výměna řádků, násobení řádku nenulovým číslem, přičtení násobku
- GEM: převedení na odstupňovaný tvar + zpětná substituce
- Hodnost: $\text{hod}\,\mathbf{A}$ = počet pivotů (nenulových řádků v odstupňovaném tvaru)
- Řešitelnost: $\text{hod}\,\mathbf{A} = \text{hod}\,(\mathbf{A}|\vec{b})$ → řešení existuje
- Jednoznačnost: $\text{hod}\,\mathbf{A} = n$ → právě jedno řešení
- Obecné řešení: $\vec{x} = \vec{p} + \sum x_{f_i}\vec{h}_i$ (partikulární + homogenní)
- Zapomeneš provést operaci i na sloupec pravých stran
- Numerická chyba při výpočtu — zapisuj si přesně, jakou úpravu provádíš
- Zaměníš bázovou a volnou proměnnou — pivoty určují bázové!
- U homogenní soustavy zapomeneš, že $\vec{0}$ je vždy řešení