Iteračné metódy

Pre ľahšie pochopenie tejto časti je vhodné oboznámiť sa so základnými poznatkami o iteračných metódach, ktoré sa nachádzajú v kapitole Reálne čísla, časti Algoritmy.
Tieto metódy sú užitočné pri riešení (spravidla) veľkých sústav lineárnych rovníc postupným približovaním sa k presnému riešeniu. Špeciálne iteračné metódy sa tiež používajú pre spresnenie riešenia získaného eliminačnou metódou. Princíp iteračnej metódy najskôr budeme ilustrovať na jednoduchom príklade:

Príklad 21. Iteračnou metódou chceme nájsť riešenie sústavy rovníc

$$\begin{array}{rrrrrrr} 11x_1 & + & 2x_2 & + & x_3 & = & 15 \... ...& = & 16 \\ 2x_1 & + & 3x_2 & - & 8x_3 & = & 1 \\ \end{array}$$

alebo

$${ { \left( \begin{array}{rrr} 11 & 2 & 1 \\ 1 & 10 & 2... ...n{array}{r} 15 \\ 16 \\ 1 \\ \end{array} \right) } . }$$

Riešenie: Sústavu musíme najskôr upraviť na tvar vhodný na vykonávanie iterácií. Urobíme to tak, že z každej rovnice vyčleníme jednu neznámu tak, aby sme na ľavej strane dostali celý vektor x a ostatné členy dáme na pravú stranu. Napríklad:

$$\begin{array}{rr} x_1 = &\frac{1}{11}( 15 - 2x_2 - x_3 ) \\ ... ... 2x_3) \\ x_3 = &\ \frac{1}{8} (-1 + 2x_1+ 3x_2 ) \end{array}$$

to jest

$${ { \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \... ... \frac{8}{5} \\ -\frac{1}{8} \\ \end{array} \right) } . }$$

Označme maticu tohto zápisu ${\bf H_J}$. Iná možnosť, ako upraviť pôvodnú sústavu na tvar vhodný pre iterácie, môže byť:

$$\begin{array}{rr} x_1 = & 15- 10 x_1- 2x_2 - x_3 \\ x_2 = & 16 - x_1 - 9x_2-2x_3 \\ x_3 = &-1 + 2x_1+ 3x_2-7x_3 \end{array}$$

to jest

$${ { \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \... ...{array}{r} 15 \\ 16 \\ -1 \\ \end{array} \right) } . }$$

Maticu tohto zápisu označíme ${\bf H_B}$. Týchto možností je nekonečne veľa, ale len niektoré vedú ku konvergentným postupnostiam. (Keďže pracujeme s postupnosťami vektorov, konvergenciu v tomto prípade chápeme po zložkách). Z týchto dvoch upravených sústav dostávame rekurentné vzťahy tak, že k neznámym na ľavej strane pripíšeme index $k+1$ a k neznámym na pravej strane zas index $k$. Máme

$$x_1^{(k+1)} = \frac{1}{11}( 15- 2x_2^{(k)} - x_3^{(k)} )$$

$$x_2^{(k+1)} = \frac{1}{10}(16 - x_1^{(k)} - 2x_3^{(k)})$$ (4.8)

$$x_3^{(k+1)} = \frac{1}{8} (-1 + 2x_1^{(k)}+ 3x_2^{(k)} )$$

to jest

$${\bf x}^{(k+1)} = {\bf H_J x}^{(k)} +{\bf g_J}$$

alebo

$$x_1^{(k+1)} = 15- 10 x_1^{(k)}- 2x_2^{(k)} - x_3^{(k)}$$

$$x_2^{(k+1)} = 16 - x_1^{(k)} - 9x_2^{(k)}-2x_3^{(k)}$$ (4.9)

$$x_3^{(k+1)} = -1 + 2x_1^{(k)}+ 3x_2^{(k)}-7x_3^{(k)}$$

to jest

$${\bf x}^{(k+1)} = {\bf H_B x}^{(k)} +{\bf g_B}.$$

Teraz zvolíme ${\bf x}^{(0)} =( x_1^{(0)},x_2^{(0)},x_3^{(0)})^T$, napríklad $(0,0,0)^T$. Dosadíme tieto počiatočné hodnoty do pravej strany odvodených rekurentných vzťahov (4.8) a vypočítame:

$${\bf x}^{(1)} =(\frac{15}{11},\ \frac{16}{10},\ -\frac{1}{8})^T.$$

Ak budeme takto ďalej pokračovať využívajúc opäť vzťahy (4.8), dostávame:

$${\bf x}^{(2)} =(1,0840;\ 1,4886;\ 0,81590)^T,$$

$${\bf x}^{(3)} =(1,0188;\ 1,3284;\ 0,70422)^T.$$

Po vykonaní niekoľkých ďalších iterácií dospejeme k približnému riešeniu

$${\bf x_c} =(1,056;\ 1,364;\ 0,651)^T.$$

Ak budeme počítať analogicky podľa rekurentných vzťahov (4.9), dostávame:

$${\bf x}^{(1)} =(15,\ 16,\ -1)^T,$$

$${\bf x}^{(2)} =(-166 ;\ -145;\ 84)^T,$$

$${\bf x}^{(3)} =(1881;\ 16551;\ -1990)^T.$$

Tu sú jednotlivé zložky vektorov značne rozptýlené a je pravdepodobné, že postupnosť iterácií diverguje. $\clubsuit$

Z tohoto príkladu vidíme, že nie každý ľubovoľne vytvorený rekurentný vzťah je vhodný pre výpočet, pretože nie každá postupnosť ním získaných iterácii konverguje. Pozrime sa preto na problém hľadania vhodných iteračných metód trochu všeobecnejšie.

Uvažujme lineárnu sústavu rovníc s regulárnou reálnou maticou sústavy

$${ \bf Ax = b }$$ (4.10)

a predpokladajme, že existuje jediné riešenie tejto sústavy: ${\bf r = A^{-1} b}$. Rovnicu (4.10) prepíšeme na tvar vhodný pre iterácie

$${\bf x}={\bf H x} +{\bf g }$$ (4.11)

tak, aby jej riešením bol tiež vektor ${\bf r = A^{-1} b}$ . Maticu H nazývame iteračnou maticou.
Zostrojíme postupnosť iterácií ${\bf x}^{(k)}=(x_1^{(k)}, x_2^{(k)},\dots,x_n^{(k)})^T$ podľa vzorca

$${\bf x}^{(k+1)} = {\bf H x}^{(k)} + {\bf g}, \ \ k=0,1,2\dots$$ (4.12)

Ak existuje $\lim_{k\rightarrow \infty} { \bf x}^{(k)} ={ \bf x}^{*}$, (definíciu limity pozri kapitola Limita funkcie), potom prechodom k limite vo vzťahu (4.12) dostaneme ${ \bf x}^{*}={ \bf H}{ \bf x}^* +{ \bf g}$, a teda ${ \bf x}^*$ je riešením rovnice (4.11). Z nášho predpokladu vyplýva, že ${ \bf x}^* ={ \bf r}$ a iterácia ${ \bf x}^{(k)}$ je aproximáciou ${ \bf r}$.
Okrem predpísania iteračného vzťahu musíme ešte pripojiť inštrukciu, ako iteračný proces zahájiť, t.j. voľbu ${ \bf x}^{(0)}$ (viď časť Algoritmy v kapitole Reálne čísla) a ako ho ukončiť. Ukončenie procesu zabezpečíme splnením jednej z nasledujúcich podmienok:

1. stanovíme počet iterácií, ktoré chceme vypočítať
2. stanovíme podmienku zastavenia: zvolíme číslo $\delta >0$ (dostatočne malé) a výpočet ukončíme, ak bude splnená napríklad podmienka:
   
   $$\sqrt{\sum_{i=1}^n \vert x^{(k)}_i -x^{(k-1)}_i\vert^2} <\delta.$$
   
   

Jacobiho metóda
Pri vysvetlení tejto metódy pôjde o zovšeobecnenie postupu z predchádzajúceho príkladu. Napíšeme $i$-tu rovnicu sústavy ${\bf Ax = b }$:

$$a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n =b_i, \ \ i=1,2,\dots,n.$$ (4.13)

Ak je $a_{ii} \ne 0$, dostávame

$$x_i = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1,\ j \ne i}^n a_{ij} x_j \right) ,\ i=1,2,\dots,n$$ (4.14)

Teda z $i$-tej rovnice sme vypočítali neznámu $x_i$. Jacobiho iteračná formula je tvaru:

$$x^{(k+1)}_i = \frac{1}{a_{ii}}\left( b_i - \sum_{j=1,\ j \ne i}^n a_{ij} x^{(k)}_j \right) ,\ k=0,1,\dots,\ \ i=1,2,\dots,n$$ (4.15)

alebo maticovo

$${ \bf x}^{(k+1)} = { \bf H}_{{\bf J}} { \bf x}^{(k)} + { \bf g}_{{\bf J}},\ \ k=0,1,2,\dots,$$ (4.16)

kde

$${ { \bf H}_{{\bf J}} = { \left( \begin{array}{rrrrr} 0,... ... .... \\ \frac{b_n}{a_{nn}} \\ \end{array} \right) }. }$$

Príklad 22. Riešme sústavu ${\bf Ax = b }$ Jacobiho metódou, ak

$${ {\bf A} = { \left( \begin{array}{rrrr} 4 & -1 & -1& 0 ... ...ay}{r} 1 \\ 2 \\ 0 \\ 1 \\ \end{array} \right) }. }$$

Riešenie: Výsledky zapíšeme do tabuľky. Vidíme, že iterácie konvergujú dosť pomaly. (Porovnajte s príkladom 6!)

${ \bf x}^{(0)}$	${ \bf x}^{(1)}$	${ \bf x}^{(3)}$	${ \bf x}^{(4)}$	${ \bf x}^{(5)}$	${ \bf x}^{(6)}$	${ \bf x}_t$
0	0,25	0,4375	0,46875	0,48438	0,49219	0,5
0	0,50	0,6875	0,71875	0,73438	0,74219	0,75
0	0,00	0,1875	0,21875	0,23438	0,24219	0,25
0	0,25	0,4375	0,46875	0,48438	0,49219	0,5

$\clubsuit$

Gauss-Seidelova metóda
Opäť použijeme rozpis $i$-tej rovnice (4.13) a (4.14), ale rozpíšeme ho do nasledujúcej podoby

$$x_i =\frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij} x_j - \sum_{j=i+1}^n a_{ij} x_j \right), \ i=1,2,\dots, n.$$ (4.17)

V tejto metóde využijeme fakt, že pri $i$-tej rovnici riešenia $(k+1)$-vej iterácie poznáme okrem celého vektora ${ \bf x}^{(k)}$ aj prvých $i-1$ zložiek vektora $k+1$ -vej iterácie. A teda tieto výpočty môžeme využiť. Preto iteračné indexy tejto metódy zapíšeme takto:

$$x^{(k+1)}_i =\frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} ... ...j - \sum_{j=i+1}^n a_{ij} x^{(k)}_j \right), \ i=1,2,\dots, n.$$ (4.18)

Gauss-Seidelova iteračná formula v maticovom tvare vyzerá nasledovne:

$${ \bf x}^{(k+1)} ={ \bf H}_{{\bf S}} { \bf x}^{(k)}+ { \bf g}_{{\bf S}},\ \ k=0,1,2,\dots$$ (4.19)

Konkrétna podoba matice ${ \bf H}_{{\bf S}}$ a vektora ${ \bf g}_{{\bf S}}$ sa dajú stanoviť pomocou prvkov $a_{ij}$ matice A.

Príklad 23. Sústavu z predchádzajúceho príkladu budeme riešiť Gauss -Seidelovou metódou.

Riešenie: Budeme mať iteračné vzorce:

$$\begin{array}{ll} x_1^{(k+1)} = &\frac{1}{4}( 1 + x_2^{(k)} ... ... = &\frac{1}{4} (1 + x_2^{(k+1)}+ x_3^{(k+1)} ) \\ \end{array}$$

Výsledky opäť zapíšeme do tabuľky. Vidíme, že iterácie konvergujú a v porovnaní s Jacobiho metódou, konvergujú rýchlejšie.

${ \bf x}^{(0)}$	${ \bf x}^{(1)}$	${ \bf x}^{(2)}$	${ \bf x}^{(3)}$	${ \bf x}^{(4)}$	${ \bf x}^{(5)}$	${ \bf x}_t$
0	0,25	0,40625	0,47656	0,49414	0,49854	0,5
0	0,5625	0,70312	0,73828	0,74707	0,74927	0,75
0	0,0625	0,20312	0,23828	0,24707	0,24927	0,25
0	0,40625	0,47656	0,49414	0,49854	0,49963	0,5

$\clubsuit$

Teraz sa budeme venovať konvergencii a odhadu chyby uvedených iteračných metód.
Označíme vektor chyby k-tej iterácie

$${ \bf e}^{(k)} = { \bf x}^{(k)} - { \bf r}.$$

Z doteraz povedaného vieme:

$${ \bf x}_t ={ \bf H}{ \bf x}_t + { \bf g}, \hbox{ a} \ { \bf x}^{(k)} ={ \bf H}{ \bf x}^{(k-1)} +{ \bf g},$$

po odčítaní týchto vzťahov dostaneme:

$${ \bf e}^{(k)} ={ \bf H}{ \bf e}^{(k-1)} = \dots = { \bf H}^k { \bf e}^{(0)}.$$

Pretože $\lim_{k\rightarrow \infty} { \bf x}^{(k)} ={ \bf r}$ práve keď $\lim_{k\rightarrow \infty}{ \bf e}_{(k)} ={ \bf0}$ (nulový vektor), musíme vyšetriť konvergenciu noriem mocnín ${ \bf H}^{k}$ matice ${ \bf H}$ k nule.

Veta 4.2 (Konvergenčná)   Iterácie ${ \bf x}^{(k)} = { \bf H}{ \bf x}^{(k-1)} +{ \bf g}$ konvergujú pre ľubovoľné ${ \bf x}^{(0)}$ teda
$\lim_{k\rightarrow \infty} { \bf H}^{k} { \bf e}^{(0)} = { \bf0}$, práve keď

$$\rho({ \bf H}) =\max_{i}\vert\lambda_i({ \bf H})\vert <1,$$ (4.20)

kde číslo $\rho({ \bf H})$ sa nazýva spektrálny polomer matice ${ \bf H}$ a $\lambda_i({ \bf H})$ sú vlastné čísla matice ${ \bf H}$. ^4.2

Poznámka. Pretože ${ \bf e}^{(k)}$ je lineárna funkcia ${ \bf e}^{(k-1)}$, hovoríme, že konvergencia uvedeného iteračného procesu je lineárna.

Veta 4.3 (Postačujúca podmienka konvergencie)   . Ak platí podmienka

$$\vert\vert{ \bf H}\vert\vert \leq q<1,$$ (4.21)

potom postupnosť $\{ { \bf x}^{(k)} \}_{k=0}^{\infty}$, určená formulou ${ \bf x}^{(k)} = { \bf H}{ \bf x}^{(k-1)} +{ \bf g}$, konverguje pri ľubovoľnej voľbe vektora ${ \bf x}^{(0)}$ a je

$$\lim_{k \rightarrow \infty}{ \bf x}^{(k)} = ({ \bf I}-{ \bf H})^{-1}{ \bf g}={ \bf x}_t,$$

kde ${ \bf I}$ je jednotková matica a $\vert\vert.\vert\vert$ označuje normu matice.

Norma matice je nezáporné reálne číslo napr. ak $\bf {A} = \{a_{ij}\}_{i,j=1}^n$, potom

$$\vert\vert A\vert\vert = \sqrt{\sum_{i,j=1}^n a_{ij}^2}.$$

Podmienky (4.20) a (4.21) sa v praxi dosť ťažko overujú, preto je vhodné sformulovať postačujúce podmienky konvergencie metód priamo vzhľadom k matici A.
Dajú sa ukázať nasledujúce kritériá konvergencie:

Veta 4.4   Ak má matica A vlastnosť ostrej diagonálnej dominantnosti, potom Jacobiho aj Gauss-Seidelova metóda konvergujú pre ľubovoľnú začiatočnú hodnotu vektora ${ \bf x}^{(0)}$.
Ak je matica A symetrická a kladne definitná, potom Gauss-Seidelova metóda konverguje pre ľubovoľný začiatočný vektor ${ \bf x}^{(0)}$.

Poznámka. Vlastnosti matíc uvedené vo vete pozri paragraf Gaussova eliminačná metóda.