Systémy lineárních rovnic

Kapitoly: Systémy rovnic, Cramerovo pravidlo, Homogenní systémy

Lineární soustava rovnic je množina m lineárních rovnic o n proměnných. Vyřešením rovnice získáme hodnoty, které můžeme dosadit za našich n proměnných tak, aby všechny rovnice dávaly smysl.

Definice systému lineárních rovnic

Už jste se určitě setkali s nějakou jednoduchou soustavou typu

$$ \begin{array}{ccccc} a_{11}x &+&a_{12}y &=& b_1\\ a_{21}x &+&a_{22}y &=&b_2\\ \end{array} $$

kde $a_{11},…,a_{22}, b_1, b_2$ jsou zadaná reálná čísla a x a y jsou proměnné. Tato soustava rovnic může mít různý počet řešení — žádné, jedno nebo nekonečně mnoho, podobně jako klasická lineární rovnice. V případě soustavy lineárních rovnic je otázka počtu řešení a jejich nalezení složitější než v případě jednoduché lineární rovnice.

Definice systému lineárních rovnic:

$$ \begin{array}{ccccccccc} a_{11}x_1&+&a_{12}x_2&+&\ldots&+&a_{1n}x_n&=&b_1\\ a_{21}x_1&+&a_{22}x_2&+&\ldots&+&a_{2n}x_n&=&b_2\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ a_{m1}x_1&+&a_{m2}x_2&+&\ldots&+&a_{mn}x_n&=&b_n\\ \end{array} $$

kde $a_{11}, …, a_{mn}, b_1, …, b_m$ jsou reálná čísla. Tato soustava se pak nazývá systém m lineárních rovnic o n neznámých x1, …, xn s koeficienty $a_{11}, …, a_{mn}$. Konkrétní příklad systému lineárních rovnic by mohl vypadat takto:

$$ \begin{array}{ccccccccc} 3x_1&+&-2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&+&4x_2&+&2x_3&+&-10x_4&=&2\\ 11x_1&+&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

Pokud je ale nějaké aij záporné, je zvykem psát to v tomto tvaru:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&+&4x_2&+&2x_3&-&10x_4&=&2\\ 11x_1&+&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

Stále ale platí, že a12 = −2 a a24 = −10.

Maticový zápis

Tuto soustavu můžeme převést do maticového tvaru. Definujeme celkem tři matice, jednu pro koeficienty, jednu pro pravou stranu rovnic a jednu pro samotné proměnné. Matice pak budou vypadat takto:

$$ A= \begin{pmatrix} a_{11}&a_{12}&…&a_{1n}\\ a_{21}&a_{22}&…&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&…&a_{mn} \end{pmatrix}, \quad b= \begin{pmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{pmatrix}, \quad x= \begin{pmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{pmatrix} $$

Matice A obsahuje koeficienty původních rovnic a nazýváme ji „matice systému“, matice b obsahuje pravé strany rovnic a matice x obsahuje proměnné. Potom můžeme celou soustavu rovnic zapsat jako rovnici

$$Ax,=,b$$

Tato rovnice dává smysl, protože na levé straně máme součin dvou matic a na pravé straně máme matici, přičemž jejich dimenze sedí. Můžeme si zkusit vynásobit levou stranu. Násobíme matici typu m × n maticí typu n × 1, takže výsledná matice bude typu m × 1, bude mít m řádků a jeden sloupec. Prozatím je to v pořádku.

Nyní provedeme klasický algoritmus násobení matic, začneme s prvním řádkem matice A a s prvním sloupcem matice x (jiný sloupec tam není). Dostaneme:

$$a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n$$

Tímto součtem jsme získali první prvek nové matice, tedy hodnotu b1. Když si to celé dosadíme do rovnice, máme:

$$a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n = b_1$$

Získali jsme přesně první rovnici z naší soustavy rovnic. Stejným způsobem bychom pokračovali pro ostatní řádky. Definujeme ještě rozšířenou matici systému, což je matice systému, ke které přidáme matici b takto:

$$ B=(A|b)= \begin{pmatrix} a_{11}&a_{12}&…&a_{1n}&b_1\\ a_{21}&a_{22}&…&a_{2n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{m1}&a_{m2}&…&a_{mn}&b_m \end{pmatrix} $$

Dále nás bude zajímat hodnost této rozšířené matice systému. Hodnost původní nerozšířená matice systému označíme rank(A), hodnost rozšířené rank(A|b). Jaký je vztah mezi těmito hodnostmi? Pokud k matici A přidáme sloupec b, mohou nastat dvě situace: pokud tento nový sloupec je lineární kombinací sloupců matice A, pak se hodnost nezmění. Pokud nebyl lineární kombinací, pak bude hodnost o jedna větší.

Frobeniova věta

Hodnost rozšířené matice pro nás bude důležitá, protože platí důležitá věta, Frobeniova věta: Systém rovnic Ax = B má řešení právě tehdy, když je hodnost matice systému rovna hodnosti rozšířené matice systému: rank(A) = rank(A|b).

Zkusíme si ukázat, že tato věta platí alespoň v jednom směru — pokud je x = β řešením rovnice Ax = b, pak rank(A) = rank(A|b). Pokud se tyto hodnosti rovnají, musí platit, že sloupec b je lineární kombinací sloupců matice A. Rozepíšeme si to. Matice β má tvar:

$$ \beta=\begin{pmatrix} \beta_1\\ \beta_2\\ \vdots\\ \beta_n \end{pmatrix} $$

A my tvrdíme, že pokud za x1 dosadíme β1 atd., tak všechny rovnice v systému rovnic budou platné:

$$ \begin{array}{ccccccccc} a_{11}\beta_1&+&a_{12}\beta_2&+&\ldots&+&a_{1n}\beta_n&=&b_1\\ a_{21}\beta_1&+&a_{22}\beta_2&+&\ldots&+&a_{2n}\beta_n&=&b_2\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ a_{m1}\beta_1&+&a_{m2}\beta_2&+&\ldots&+&a_{mn}\beta_n&=&b_m\\ \end{array} $$

Nyní rovnice trochu přepíšeme. Když se podíváme na první sloupeček, tak zjistíme, že tam vždy máme hodnoty $a_{11}, a_{21}, …, a_{m1}$, které násobíme stejnou hodnotou β1. Pokud osamostatníme sloupeček do samostatné matice, můžeme vytknout hodnou β1 před matici, čímž dostaneme:

$$ \begin{pmatrix} a_{11}\beta_1\\ a_{21}\beta_1\\ \vdots\\ a_{m1}\beta_1 \end{pmatrix} =\beta_1 \begin{pmatrix} a_{11}\\ a_{21}\\ \vdots\\ a_{m1} \end{pmatrix} $$

Nyní takto můžeme přepsat celou soustavu:

$$ \beta_1\begin{pmatrix} a_{11}\\ a_{21}\\ \vdots\\ a_{m1} \end{pmatrix} + \beta_2\begin{pmatrix} a_{12}\\ a_{22}\\ \vdots\\ a_{m2} \end{pmatrix} +…+ \beta_n\begin{pmatrix} a_{1n}\\ a_{2n}\\ \vdots\\ a_{mn} \end{pmatrix} \begin{pmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{pmatrix} $$

Aby tato rovnice platila, musí být sloupcové matice na levé straně lineární kombinací matice na pravé straně a hodnoty β1, …, βn musí být jejich koeficienty.

Tím jsme dokázali, že pokud má být matice β řešením soustavy rovnic, tak pravá strana soustavy, matice b, musí být lineární kombinací sloupců matice soustavy. A pokud je sloupec z matice b lineární kombinací sloupců matice A, pak musí mít matice A stejnou hodnot, jako matice (A|b).

Zároveň platí, že pokud rank(A) = rank(A|b) = k a k je rovno počtu neznámých, tedy k = n, pak má soustava právě jedno řešení. Pokud platí, že k < n, pak má soustava nekonečně mnoho řešení a k jeho zapsání budeme potřebovat n − k parametrů.

Elementární řádkové úpravy

Dále je z předchozí rovnice vidět, že pokud budeme v matici (A|b) provádět elementární řádkové úpravy, nezmění se řešení soustavy rovnic. Pokud bychom přičetli ke druhému řádku první řádek, dostali bychom rovnici:

$$ \beta_1\begin{pmatrix} a_{11}\\ a_{21}+a_{11}\\ \vdots\\ a_{m1} \end{pmatrix} + \beta_2\begin{pmatrix} a_{12}\\ a_{22}+a_{12}\\ \vdots\\ a_{m2} \end{pmatrix} +...+ \beta_n\begin{pmatrix} a_{1n}\\ a_{2n}+a_{1n}\\ \vdots\\ a_{mn} \end{pmatrix} \begin{pmatrix} b_1\\ b_2+b_1\\ \vdots\\ b_m \end{pmatrix} $$

Když si druhý řádek rozepíšeme, dostaneme:

$$\beta_1(a_{21}+a_{11})+\beta_2(a_{22}+a_{12})+\ldots+\beta_n(a_{2n}+a_{1n})=b_1+b_2$$

Roznásobíme závorky:

$$\beta_1a_{21}+\beta_1a_{11}+\beta_2a_{22}+\beta_2a_{12}+\ldots+\beta_na_{2n}+\beta_na_{1n}=b_1+b_2$$

Nyní to jen trochu přeházíme:

$$(\beta_1a_{11}+\beta_2a_{12}+\ldots+\beta_na_{1n})+(\beta_1a_{21}+\beta_2a_{22}+\ldots+\beta_na_{2n})=b_1+b_2$$

V první závorce máme ve skutečnosti první řádek a ve druhé závorce původní druhý řádek. My víme, že první řádek je rovný hodnotě b1 a druhý řádek je rovný hodnotě b2. To víme z původních rovnic. Takže za první závorku můžeme napsat b1 a za druhou b2:

$$b_1+b_2=b_1+b_2.$$

Podobně můžeme celý řádek vynásobit konstantou c ≠ 0 a nezměníme platnost soustavy rovnic. Pozor ale na to, že nemůžeme provádět sloupcové úpravy.

Soustava s jedním řešením

Na příkladu si ukážeme, jak vyřešit takovou soustavu, která má právě jedno řešení. Mějme takovou soustavu rovnic:

$$ \begin{array}{ccccccc} 2x_1&+&3x_2&+&7x_3&=&47\\ 3x_1&+&8x_2&+&x_3&=&50\\ &&3x_2&+&3x_3&=&27\\ \end{array} $$

Matice A bude vypadat takto:

$$ A=\begin{pmatrix} 2&3&7\\ 3&8&1\\ 0&3&3 \end{pmatrix} $$

Nyní spočítáme hodnost této matice:

$$ \begin{pmatrix} 2&3&7\\ 3&8&1\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 6&16&2\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&7&-19\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&21&-57\\ 0&21&21 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&21&-57\\ 0&0&78 \end{pmatrix} $$

Vidíme, že rank(A) = 3. Z toho také vyplývá, že rank(A|b) = 3, protože matice typu 3 × 4 může mít maximální hodnost tři. Systém má tři neznámé, takže celá soustava má právě jedno řešení. Jak ho nalezneme?

Gaussova eliminační metoda

Gaussova eliminace spočívá v úpravě rozšířené matice systému na schodovitý tvar. Tím, že převedeme matici na schodovitý tvar, budeme schopni zjistit hodnotu jedné proměnné. Poté, co nalezneme hodnotu jedné proměnné, můžeme začít dosazovat tuto hodnotu do dalších rovnic.

Matice (A|b) má tvar:

$$ (A|b)=\begin{pmatrix} 2&3&7&47\\ 3&8&1&50\\ 0&3&3&27 \end{pmatrix} $$

Převedeme ji na schodovitý tvar. Budeme provádět stejné úpravy jako v předchozím kroku, pouze je tentokrát budeme aplikovat i na čtvrtý sloupec:

$$\begin{eqnarray} \begin{pmatrix} 2&3&7&47\\ 3&8&1&50\\ 0&3&3&27 \end{pmatrix} &\sim& \begin{pmatrix} 6&9&21&141\\ 6&16&2&100\\ 0&3&3&27 \end{pmatrix} \\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&7&-19&-41\\ 0&3&3&27 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&21&-57&-123\\ 0&21&21&189 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&21&-57&-123\\ 0&0&78&312 \end{pmatrix}\\ \end{eqnarray}$$

Protože jsme prováděli elementární řádkové úpravy, popisuje tato matice ekvivalentní soustavu rovnic — soustavu, která má stejnou množinu řešení. Přepíšeme si soustavu z maticového zápisu do běžného, přičemž použijeme koeficienty z naší poslední matice:

$$ \begin{array}{ccccccc} 6x_1&+&9x_2&+&21x_3&=&141\\ &&21x_2&-&57x_3&=&-123\\ &&&&78x_3&=&312\\ \end{array} $$

Nyní vyjdeme z poslední rovnice. Ta nám říká, že 78x3 = 312. Jakou hodnotu musí mít x3? To je jednoduchá lineární rovnice, takže

$$\begin{eqnarray} 78x_3&=&312\\ x_3&=&\frac{312}{78}\\ x_3&=&4 \end{eqnarray}$$

Máme hodnotu první proměnné, x3. Tuto hodnotu dosadíme do druhé rovnice. Dostáváme rovnici:

$$\begin{eqnarray} 21x_2-57x_3&=&-123\\ 21x_2-57\cdot4&=&-123\\ 21x_2&=&-123+228\\ 21x_2&=&105\\ x_2&=&\frac{105}{21}\\ x_2&=&5 \end{eqnarray}$$

A nakonec obě spočítané hodnoty dosadíme do první rovnice:

$$\begin{eqnarray} 6x_1+9x_2+21x_3&=&141\\ 6x_1+9\cdot5+21\cdot4&=&141\\ 6x_1+45+84&=&141\\ 6x_1&=&12\\ x_1&=&2 \end{eqnarray}$$

Hodnota proměnné x1 je rovna dvěma. V tuto chvíli máme kompletní řešení. Můžeme napsat, že x = (x1, x2, x3) = (2, 5, 4). Jak je vidět, Gaussova eliminační metoda je jednoduchá, ale účinná metoda, jak vyřešit soustavu lineárních rovnic.

Nekonečně mnoho řešení

Pokud rank(A) = rank(A|b) = k a k je menší než počet neznámých, k < n, pak má soustava nekonečně mnoho řešení. Vezměme si jednoduchý příklad:

$$ \begin{array}{cccccc} 4x_1&+&x_2&=&5\\ 12x_1&+&3x_2&=&15\\ \end{array} $$

Vidíme, že druhá rovnice je rovna trojnásobku první rovnice. Pokud první rovnici vynásobíme minus třemi a přičteme k druhému řádku, získáme:

$$ \begin{array}{cccccc} 4x_1&+&x_2&=&5\\ 0x_1&+&0x_2&=&0\\ \end{array} $$

V tuto chvílí máme počet proměnných rovný dvěma, n = 2, hodnost matice systému rovnu jedné, rank(A) = 1 a hodnost rozšířené matice je také rovna jedné, rank(A|b) = 1. Platí, že k < n, takže systém má nekonečně mnoho řešení. Jak tato řešení nalezneme?

Podíváme se na rovnice. Druhá rovnice je splněna pro všechna x1, x2, takže nás bude zajímat jen první rovnice. Ve skutečnosti všechny dvojice x1, x2, které vyhovují první rovnici, budou tvořit množinu všech řešení daného systému rovnic. Takže vypočítáme řešení rovnice 4x1 + x2 = 5. Rovnici upravíme do podoby x2 = 5 − 4x1.

Dále si vypomůžeme parametrem. Zvolíme si parametr t. Teď se budeme snažit vyjádřit dvojici x1, x2 pomocí parametru t tak, abychom mohli napsat, že například všechny dvojice tvaru (t, t + 2) jsou řešením systému. Tedy dvojice jako (1, 3) nebo (14, 16). Smyslem je vyjádřit hodnotu jedné proměnné pomocí jiné proměnné tak, abychom věděli, že když hodnota x1 bude taková a maková, tak hodnota x2 bude třikrát větší, například. Jako startovací bod zvolíme x1.

Položíme tak rovnost t = x1. Pokud bude mít proměnná x1 hodnotu t, jakou hodnotu bude mít proměnná x2? To vidíme z předchozí rovnice, bude mít hodnotu x2 = 5 − 4x1. Tedy pokud x1 = t, pak x2 = 5 − 4t. Můžeme tak napsat, že všechny dvojice tvaru (t, 5 − 4t) jsou řešením systému rovnic.

Můžeme si to zkontrolovat. Pokud za t dosadíme jedna, máme: x1 = 1 a x2 = 5 − 4 · 1 = 1. Dosadíme tyto hodnoty do rovnice: 4 · 1 + 1 = 5, rovnice sedí.

Pokud za t dosadíme pět, máme: x1 = 5, x2 = 5 − 4 · 5 = −15. Po dosazení do rovnice máme: 4 · 5 − 15 = 5. Sedí.

Obecné a partikulární řešení

Řešení systému rovnic, které je zapsáno pomocí parametrů, nazýváme obecné řešení. Konkrétní řešení, tj. pokud za parametry dosadíme konkrétní čísla, nazýváme partikulární řešení.

Takže z předchozího příkladu: (x1, x2) = (t, 5 − 4t) je obecné řešení systému rovnic, (1, 1) a (5, −15) jsou partikulární řešení.

Máme-li matici systému A a rozšířenou matici systému (A|b) a jejich hodnosti jsou rovny, rank(A) = rank(A|b) = k, pak k vyjádření obecného řešení potřebujeme n − k parametrů. Všimněte si, že pokud n = k, pak potřebujeme nula parametrů. To je případ, kdy má soustava právě jedno řešení — žádný parametr pak není potřeba.

Příklad

Vyřešte následující systém lineárních rovnic:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&-&4x_2&+&2x_3&+&10x_4&=&2\\ 11x_1&-&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

Jako první si vypočítáme hodnost matic A a (A|b). Převedeme rozšířenou matici na schodovitý tvar, z čehož zjistíme hodnost obou matic. Jdeme upravovat. (První řádek vynásobíme dvěma, poté sečteme první a druhý řádek a tento výsledek odečteme od třetího řádku. Dále od druhého řádku odečteme první řádek a nakonec první řádek zpátky vydělíme dvěma.)

$$\begin{eqnarray} (A|b)=\begin{pmatrix} 3&-2&4&5&1\\ 5&-4&2&10&2\\ 11&-8&10&20&4 \end{pmatrix} &\sim& \begin{pmatrix} 6&-4&8&10&2\\ 5&-4&2&10&2\\ 11&-8&10&20&4 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&-4&8&10&2\\ 5&-4&2&10&2\\ 0&0&0&0&0 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&-4&8&10&2\\ -1&0&-6&0&0\\ 0&0&0&0&0 \end{pmatrix}\\ &\sim& \begin{pmatrix} 3&-2&4&5&1\\ -1&0&-6&0&0\\ 0&0&0&0&0 \end{pmatrix}\\ \end{eqnarray}$$

Z této poslední matice už vidíme, že rank(A) = rank(A|b) = k = 2. Počet neznámých je přitom n = 4, takže budeme potřebovat n − k = 2 parametry. Vyjádříme si rovnice podle poslední matice:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ -x_1&&&-&6x_3&&&=&0\\ \end{array} $$

Z druhé rovnice dostaneme

$$\begin{eqnarray} -x_1-6x_3&=&0\\ -x_1&=&6x_3\\ x_1&=&-6x_3 \end{eqnarray}$$

Zvolíme první parametr, t = x3. Pak můžeme napsat, že x1 = −6t. Toto můžeme dosadit do první rovnice:

$$\begin{eqnarray} 3(-6t)-2x_2+4t+5x_4&=&1\\ -18t-2x_2+4t+5x_4&=&1\\ -14t-2x_2+5x_4&=&1\\ -2x_2&=&1+14t-5x_4\\ x_2&=&-\frac12-7t+\frac52x_4 \end{eqnarray}$$

Zapojíme do hry druhý parametr, s = x4. Pak můžeme napsat, že

$$x_2=-\frac12-7t+\frac52s$$

Tím dostáváme obecné řešení systému:

$$(x_1, x_2, x_3, x_4) = (-6t, -\frac12-7t+\frac52s, t, s)$$

Můžeme si vyzkoušet nějaká partikulární řešení. Například s = t = 0. Pak dostáváme: $(x_1, x_2, x_3, x_4) = (0, -\frac12, 0, 0)$. Po dosazení do původních rovnic:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&-&4x_2&+&2x_3&+&10x_4&=&2\\ 11x_1&-&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

získáme rovnice:

$$ \begin{array}{ccccccccc} 0&-&2\frac12&+&0x_3&+&0x_4&=&1\\ 0x_1&-&4\frac12&+&0x_3&+&0x_4&=&2\\ 0x_1&-&8\frac12&+&0x_3&+&0x_4&=&4\\ \end{array} $$

Po odstranění nulových prvků a po vynásobení zlomků získáváme:

$$\begin{eqnarray} 1&=&1\\ 2&=&2\\ 4&=&4 \end{eqnarray}$$

Zkusíme další partikulární řešení: s = 2, t = 1. Pak dostáváme:

$$\begin{eqnarray} x_1&=&-6\\ x_2&=&-\frac12-7+5=-\frac52\\ x_3&=&1\\ x_4&=&2 \end{eqnarray}$$

Dosadíme do rovnic:

$$ \begin{array}{ccccccccc} -18&-&2(-\frac52)&+&4&+&10&=&1\\ -30&-&4(-\frac52)&+&2&+&20&=&2\\ -66&-&8(-\frac52)&+&10&+&40&=&4\\ \end{array} $$

Upravíme:

$$ \begin{array}{ccccccccc} -4&+&5&=&1\\ -8&+&10&=&2\\ -16&+&20&=&4\\ \end{array} $$

A nakonec dostáváme:

$$\begin{eqnarray} 1&=&1\\ 2&=&2\\ 4&=&4 \end{eqnarray}$$

Zdá se, že výsledné obecné řešení je správné.

Odkazy a zdroje