9. Soustavy lineárních rovnic#

Motivace

  • Pro popis přírodních dějů je ideální jazyk derivací, protože umožňuje pracovat s okamžitými rychlostmi změn fyzikálních veličin. Pokud mechanismus děje známe, je snadné naformulovat pomocí derivací příslušný matematický model, poté ovšem přijde fáze řešení. Tady málokdy vystačíme s analytickými metodami, které jsme si ukázali v přednášce věnované diferenciálním rovnicím. Často se uchylujeme k numerickému řešení. V naprosté většině případů se toto řešení redukuje na řešení soustav lineárních rovnic. Tyto soustavy ovšem bývají obrovské, řádově obsahující tisíce rovnic a neznámých a proto středoškolské metody nejsou použitelné (například nejsou dostatečně rychlé, nebo mohou být numericky nestabilní). Z tohoto důvodu je nutné se problematice soustav rovnic věnovat podrobněji.

  • Nalezení vlastních směrů matice je zásadní pro zjednodušení popisu anizotropního materiálu, protože díky tomu, že matice má v soustavě respektující vlastní směry diagonální tvar, se redukuje počet materiálových konstant. Hledání těchto směrů je vlastně řešení soustavy lineárních rovnic. Situace je relativně jednoduchá, protože soustava má dimenzi dva nebo tři a k tomu nekonečně mnoho řešení, což výpočty urychluje. (Například ve dvourozměrném případě to znamená, že jedna rovnice je násobkem druhé a nemusíme ji uvažovat.)

  • Podrobněji viz zde. Numerický výpočet vlastních čísel zde

9.1. Varianty zápisu soustavy lineárních rovnic#

Uvažujme následující tři problémy:

  1. Najděte všechna reálná čísla \(\displaystyle x_1\), \(\displaystyle x_2\), splňující dvojici rovnic

    \[\begin{split} \begin{aligned} 4x_1&+5x_2=7\\ \phantom{4}x_1&-2x_2=4 \end{aligned} \end{split}\]

  2. Najděte všechna reálná čísla \(\displaystyle x_1\), \(\displaystyle x_2\), splňující vektorovou rovnici

    \[\begin{split} \begin{aligned} \begin{pmatrix} 4\\1 \end{pmatrix} x_1 + \begin{pmatrix} 5\\-2 \end{pmatrix} x_2 = \begin{pmatrix} 7\\4 \end{pmatrix} \end{aligned}\end{split}\]

  3. Najděte všechna reálná čísla \(\displaystyle x_1\), \(\displaystyle x_2\), splňující maticovou rovnici

    \[\begin{split}\begin{aligned} \begin{pmatrix} 4&5\\1&-2 \end{pmatrix} \begin{pmatrix} x_1\\x_2 \end{pmatrix} = \begin{pmatrix} 7\\4 \end{pmatrix} \end{aligned} \end{split}\]

Všechny problémy jsou ekvivalentní a jedná se o jiný zápis téhož. Jednou však používáme soustavu rovnic, vektory a jejich lineární kombinaci a jednou matice a maticový součin!

9.2. Soustava lineárních rovnic#

Definice (Soustava lineárních rovnic)

Soustavou \(\displaystyle m\) lineárních rovnic o \(\displaystyle n\) neznámých nazýváme soustavu rovnic

(9.1)#\[\begin{split} \begin{gathered} a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1n}x_n=b_1 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3+\cdots+a_{2n}x_n=b_2 \\ a_{31}x_1+a_{32}x_2+a_{33}x_3+\cdots+a_{3n}x_n=b_3 \\ \vdots \\ a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\cdots+a_{mn}x_n=b_m \end{gathered} \end{split}\]

Proměnné \(\displaystyle x_1\), \(\displaystyle x_2\), …, \(\displaystyle x_n\) nazýváme neznámé. Reálná čísla \(\displaystyle a_{ij}\) nazýváme koeficienty levých stran, reálná čísla \(\displaystyle b_i\) koeficienty pravých stran soustavy rovnic. Řešením soustavy rovnic rozumíme uspořádanou \(\displaystyle n\)-tici reálných čísel \(\displaystyle [t_1, t_2, \ldots, t_n]\) po jejichž dosazení za neznámé (v tomto pořadí) do soustavy dostaneme ve všech rovnicích identity.

Definice (Matice soustavy)

Matici

\[\begin{split} A=\left( \begin{matrix} a_{11}& a_{12}& a_{13}& \cdots{}& a_{1n}\\ a_{21}& a_{22}& a_{23}& \cdots{}& a_{2n}\\ \vdots{} &\vdots{}& {} &\ddots{}& \vdots{}\\ a_{m1}& a_{m2}& a_{m3}& \cdots{}& a_{mn}\\ \end{matrix}\right) \end{split}\]
nazýváme maticí soustavy (9.1). Matici
\[\begin{split} A_r=\left( \begin{array}{ccccc|c} a_{11}& a_{12}& a_{13}& \cdots{}& a_{1n}&b_1\\ a_{21}& a_{22}& a_{23}& \cdots{}& a_{2n}&b_2\\ \vdots{} &\vdots{}& {} &\ddots{}& \vdots{}&\vdots\\ a_{m1}& a_{m2}& a_{m3}& \cdots{}& a_{mn}&b_m\\ \end{array} \right) \end{split}\]
nazýváme rozšířenou maticí soustavy (9.1).

9.3. Vektorový zápis soustavy lineárních rovnic#

Soustavu (9.1) lze ekvivalentně přepsat do vektorového tvaru

\[\begin{split} \begin{pmatrix} a_{11}\\a_{21}\\\vdots\\a_{m1} \end{pmatrix} x_1+ \begin{pmatrix} a_{12}\\a_{22}\\\vdots\\a_{m2} \end{pmatrix} x_2+ \begin{pmatrix} a_{13}\\a_{23}\\\vdots\\a_{m3} \end{pmatrix} x_3+\cdots+ \begin{pmatrix} a_{1n}\\a_{2n}\\\vdots\\a_{mn} \end{pmatrix} x_n= \begin{pmatrix} b_{1}\\b_{2}\\\vdots\\b_{m} \end{pmatrix}. \end{split}\]
Vidíme tedy, že se vlastně jedná o problém, vyjádřit vektor složený z čísel na pravé straně soustavy rovnic jako lineární kombinaci vektorů, které tvoří sloupce matice soustavy.

9.4. Maticový zápis soustavy lineárních rovnic#

Soustavu (9.1) lze ekvivalentně přepsat do maticového tvaru pomocí maticového součinu

\[\begin{split} \left( \begin{matrix} 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{matrix}\right) \left( \begin{matrix} x_1\\x_2\\ \vdots \\x_n \end{matrix} \right) = \left( \begin{matrix} b_1\\b_2\\ \vdots \\b_m \end{matrix} \right). \end{split}\]
Tento tvar se používá často v inženýrských výpočtech pro úspornost. Symbolicky zpravidla píšeme soustavu lineárních rovnic ve tvaru
\[ A\vec x=\vec b, \]
nebo
\[AX=B\]
kde \(\displaystyle A\) je matice soustavy a \(\displaystyle \vec b\) resp. \(\displaystyle B\) je vektor pravých stran.

9.5. Využití inverzní matice pro řešení soustavy lineárních rovnic#

../_images/matrix.jpg

Obr. 9.1 Inverzní matice umožní zapsat elegantně řešení i neuvěřitelně komplexní a složité soustavy rovnic. Pro praktické počítání se však tato metoda moc nehodí a budeme ji muset ještě o něco vylepšit na iterační metodu. Zdroj: pixabay.com.#

Z úvodní přednášky o lineární algebře víme, že pomocí maticového násobení je možné soustavu lineárních rovnic zapsat ve tvaru

\[AX=B,\]
kde \(\displaystyle A\) je matice soustavy, \(\displaystyle X\) je sloupcový vektor neznámých a \(\displaystyle B\) je vektor pravých stran. Pokud má matice \(\displaystyle A\) inverzní matici, můžeme pomocí této matice soustavu vyřešit. Po vynásobení rovnice inverzní maticí zleva dostáváme
\[A^{-1}(AX)=A^{-1}B\]
a po uplatnění asociativního zákona
\[(A^{-1}A)X=A^{-1}B.\]
Protože výraz v závorce je součinem matice s maticí inverzní, je tento součin roven jednotkové matici, která je neutrálním prvkem při násobení a proto okamžitě dostáváme řešení soustavy ve tvaru
\[X=A^{-1}B.\]
Jako přirozený důsledek vidíme, že řešení je určeno jednoznačně. Známe-li inverzní matici, můžeme řešení dokonce vypočítat pro libovolnou pravou stranu velmi pohodlně a rychle pomocí maticového násobení. Bohužel, výpočet inverzní matice je zpravidla velmi drahý (vyžaduje velké množství operací) a numericky málo stabilní. Proto je tento postup užitečným teoretickým nástrojem, ale v praxi postupujeme poněkud odlišně.

9.6. Inverzní matice k diagonální matici#

Diagonální matice (tj. matice, které mají nenulové prvky jenom na hlavní diagonále) se vzhledem k násobení chovají velice hezky: součinem je taková matice, která je diagonální a na hlavní diagonále má prvky vytvořené jako součin odpovídajících prvků násobených matic.

\[\begin{split}\begin{pmatrix} 2&0&0 \\ 0&3&0 \\ 0&0&12 \end{pmatrix}\begin{pmatrix} 5&0&0 \\ 0&7&0 \\ 0&0&1 \end{pmatrix}=\begin{pmatrix} 10&0&0 \\ 0&21&0 \\ 0&0&12 \end{pmatrix}\end{split}\]

Proto je snadné zařídit, aby v hlavní diagonále vyšly jedničky. Stačí uvažovat podobně jako v následujícím příkladě.

\[\begin{split}\begin{pmatrix} 2&0&0 \\ 0&3&0 \\ 0&0&12 \end{pmatrix}\begin{pmatrix} \frac 12&0&0 \\ 0&\frac 13&0 \\ 0&0&\frac1{12} \end{pmatrix}=\begin{pmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{pmatrix}\end{split}\]
a tedy
\[\begin{split}\begin{pmatrix} 2&0&0 \\ 0&3&0 \\ 0&0&12 \end{pmatrix}^{-1}=\begin{pmatrix} \frac 12&0&0 \\ 0&\frac 13&0 \\ 0&0&\frac1{12} \end{pmatrix}.\end{split}\]

9.7. Iterační metoda řešení soustav lineárních rovnic#

Výše jsme viděli, že je jednoduché najít inverzní matici k matici diagonální. Toho využijeme pro řešení soustavy lineárních rovnic iterační metodou. Představíme si nejjednodušší, přesto však velmi mocnou metodu, Jacobiho metodu.

V úvodní přednášce z lineární algebry jsme modelovali rozložení teploty ve dvourozměrné desce pomocí soustavy rovnic

\[\begin{split}\begin{pmatrix} \phantom{-}4&-1& \phantom{-}0&-1\\ -1& \phantom{-}4&-1& \phantom{-}0\\ \phantom{-}0 &-1& \phantom{-}4&-1\\ -1& \phantom{-}0&-1& \phantom{-}4\end{pmatrix}\begin{pmatrix} x_1\\x_2\\x_3\\x_4\end{pmatrix}=\begin{pmatrix} 30\\60\\70\\40\end{pmatrix}.\end{split}\]
Pro
\[\begin{split}A=\begin{pmatrix} \phantom{-}4&-1& \phantom{-}0&-1\\ -1& \phantom{-}4&-1& \phantom{-}0\\ \phantom{-}0 &-1& \phantom{-}4&-1\\ -1& \phantom{-}0&-1& \phantom{-}4\end{pmatrix}, \quad X=\begin{pmatrix} x_1\\x_2\\x_3\\x_4\end{pmatrix},\quad B=\begin{pmatrix} 30\\60\\70\\40\end{pmatrix}\end{split}\]
tedy

(9.2)#\[AX=B.\]

Rozdělíme matici \(\displaystyle A\) na součet diagonální matice a matice s nulami v hlavní diagonále, tj. na součet matic

\[\begin{split}D=\begin{pmatrix} 4&0&0&0\\ 0& 4&0&0\\0 &0& 4&0\\ 0&0&0& 4\end{pmatrix}\quad \text{a}\quad T=\begin{pmatrix} \phantom{-}0&-1& \phantom{-}0&-1\\ -1& \phantom{-}0&-1& \phantom{-}0\\ \phantom{-}0 &-1& \phantom{-}0&-1\\ -1& \phantom{-}0&-1& \phantom{-}0\end{pmatrix}\end{split}\]
Potom můžeme psát rovnici ve tvaru
\[(D+T)X=B\]
a odsud
\[\begin{split}\begin{aligned}DX+TX&=B\\ DX&=B-TX\end{aligned}\end{split}\]
a využitím inverzní matice

(9.3)#\[X=D^{-1}(B-TX).\]

Definujme nyní iterační vzorec

(9.4)#\[X_{k+1}=D^{-1}(B-TX_k).\]

Podobně jako u Markovových řetězců můžeme najít postupnými iteracemi z vhodného (nebo libovolného) počátečního stavu stacionární stav, kdy se \(\displaystyle X_k\) dalšími iteracemi nemění a tím dostaneme řešení rovnice (9.3), která je ekvivalentní rovnici (9.2). Protože inverzní matici počítáme pro matici diagonální, je tento výpočet velice rychlý a levný. Vlastně není vůbec nutné mít k dispozici maticový počet. Iterace dostaneme tak, že z první rovnice osamostatníme \(\displaystyle x_1\), z druhé rovnice \(\displaystyle x_2\) atd. Výchozí odhad dosadíme do pravých stran a obdržíme zpřesněný odhad. Postup opakujeme, dokud nejsou dvě následující iterace dostatečně blízké.

Poznámka. Předchozí postup je možné použít jenom v případě, že iterační proces (9.4) konverguje. Pokud by nekonvergoval, není možné o řešení rovnice nic říct, pouze to, že Jacobiho metoda nefunguje. Postačující podmínka, kdy Jacobiho metoda konverguje, je aby každý řádek měl v hlavní diagonále číslo, které je v absolutní hodnotě větší než je součet absolutních hodnot zbylých čísel v tomto řádku. Matice, která splňuje tuto podmínku se nazývá řádkově ostře diagonálně dominantní matice a pro takovou matici Jacobiho metoda konverguje. Podobně je možné uvažovat sloupcově ostře diagonálně dominantní matice porovnáním absolutních hodnot diagonálních prvků se součty absolutních hodnot ostatních prvků v daných sloupcích a i pro sloupcově ostře diagonálně dominantní matice metoda konverguje. I přes jednoduchost tohoto kriteria se s diagonálně dominantními maticemi setkáváme v aplikacích poměrně často. Podíváme-li se, jak byla odvozena soustava popisující rozložení teploty na tepelně vodivé desce (konec minulé přednášky), není to až takové překvapení.

Online výpočet.

Podobnými iteračními metodami je možné efektivně řešit soustavy o tisících rovnic a neznámých. Výpočty probíhají rychle a nejsou náročné na paměť jako u přímých metod, známých například ze střední školy. Tímto způsobem se řeší soustavy rovnic při modelování namáhání konstrukcí, vedení tepla, proudění vody apod.

9.8. Gaussova-Seidelova iterační metoda#

Gaussova-Seidelova iterační metoda je modifikace Jacobiho iterační metody. Postupujeme jako v Jacobiho metodě, ale všechny zpřesněné hodnoty použijeme okamžitě, když jsou k dispozici. Nikoliv až v další iteraci jako u Jacobiho metody. Metoda konverguje za stejných podmínek jako Jacobiho metoda, ale rychleji a přesto nevznikají vyšší nároky na výpočetní výkon.

Použijeme příklad z Wikipedie. Soustavu

\[\begin{split}\begin{array}{rrrrl} 10x_1 &- x_2 &+ 2x_3 & & = 6, \\ -x_1 &+ 11x_2 &- x_3 &+ 3x_4 & = 25, \\ 2x_1 &- x_2 &+ 10x_3 &- x_4 & = -11, \\ & 3x_2 &- x_3 &+ 8x_4 & = 15. \end{array}\end{split}\]
s diagonálně dominantní maticí převedeme na iterační tvar
\[\begin{split} \begin{aligned} x_1 & = x_2/10 - x_3/5 + 3/5, \\ x_2 & = x_1/11 + x_3/11 - 3x_4/11 + 25/11, \\ x_3 & = -x_1/5 + x_2/10 + x_4/10 - 11/10, \\ x_4 & = -3x_2/8 + x_3/8 + 15/8. \end{aligned} \end{split}\]
Poté vyjdeme z počátečního odhadu řešení a dosazujeme do pravých stran.

U Jacobiho metody pro počáteční odhad vypočteme nejprve všechny pravé strany a dosadíme do proměnných na levé straně jako zpřesnění počáteční aproximace. Tento postup opakujeme.

U Gaussovy-Seidelovy metody nejprve pomocí počátečního odhadu vypočteme z první rovnice \(\displaystyle x_1\) a tuto hodnotu ihned použijeme při výpočtu \(\displaystyle x_2\) z další rovnice. Obojí, \(\displaystyle x_1\) i \(\displaystyle x_2\) už využijeme při výpočtu \(\displaystyle x_3\) a tak dále. Po výpočtu \(\displaystyle x_4\) je první iterace dokončena a postup opět opakujeme, dokud dvě po sobě jdoucí iterace nejsou dostatečně blízké.

S nulovou počáteční aproximací dostáváme v prvním průchodu

\[\begin{split} \begin{aligned} x_1 & = 3/5 = 0.6, \\ x_2 & = 0.6/11 + 25/11 = 2.3272, \\ x_3 & = -0.6/5 +(2.3272)/10-11/10 = -0.9873,\\ x_4 & = -3(2.3272)/8 +(-0.9873)/8+15/8 = 0.8789. \end{aligned} \end{split}\]
Jak vidno, vypočtenou hodnotu \(\displaystyle x_1\) ihned použijeme pro výpočet \(\displaystyle x_2\). Obě tyto hodnoty ihned použijeme pro výpočet \(\displaystyle x_3\) a tak dále. V dalších iteracích postup opakujeme. Mimo jiné hodnoty v paměti přímo přepisujeme a nemusíme držet v paměti starou a novou hodnotu.

9.9. Využití soustav lineárních rovnic#

Viz případová studie věnovaná akustickému tomografu.

9.10. Shrnutí, hlavní myšlenky#

../_images/message.jpg

Obr. 9.2 A jaká je hlavní message? Zdroj: pixabay.com#

  • Řada numerických metod pro řešení modelů založených na matematickém modelování fyzikálních zákonů se v nějaké fázi redukuje na řešení soustav lineárních rovnic. Kromě toho se se soustavami lineárních rovnic setkáváme při hledání vlastních směrů matic, což je důležité pro matice reprezentující materiálové charakteristiky.

  • Ukázali jsme si tři různé formulace soustav lineárních rovnic, klasickou pomocí rovnic, vektorovou pomocí jedné vektorové rovnice a maticovou pomocí jediné maticové rovnice a jediné maticové operace, maticového součinu.

  • Ukázali jsme si, že v případě známé inverze k matici soustavy se řešení redukuje na součin inverzní matice s maticí pravých stran.

  • Kromě možnosti využít inverzní matici jsme si ukázali další metody řešení.