Banachova veta o konvergencii iteračných procesov

Ciele

1. Použiť Banachovu vetu na riešenie nelineárnej rovnice \(f(x)=0\) metódou prostej iterácie. \(\def\mbf#1{{#1}}\def\a{&}\)
2. Zoznámiť sa s pojmami riadkovo diagonálne dominantná matica a riadková norma matice.
3. Použiť Banachovu vetu na riešenie sústavy lineárnych rovníc Jacobiovou metódou.

Úvod

Pri riešení mnohých úloh sa na dôkaz existencie riešenia používa princíp kontraktívnych zobrazení.

Definícia kontraktívneho zobrazenia
Nech \((P,\rho)\) je metrický priestor. Hovoríme, že zobrazenie \(T: P\to P\) je kontraktívne na \(P\) práve vtedy, ak existuje \(\lambda \in \langle 0, 1)\) také, že platí \begin{equation}\label{kontraktivnost} \forall \ p, q \in P: \quad \rho(T(p),T(q)) \leqq \lambda \rho(p,q), \end{equation} kde \(\rho\) je metrika.

Banachova veta o pevnom bode
Nech \((P,\rho)\) je úplný metrický priestor a nech \(T: P \to P\) je na \(P\) kontraktívne.
Potom existuje práve jeden pevný bod \(p^* \in P\) zobrazenia \(T\), pre ktorý \(p^*=T(p^*)\).

Tento bod môžeme určiť takto: Zvolíme ľubovoľne \(p_0 \in P\) a definujeme postupnosť \((p_n)_{n =1}^\infty\) bodov \(p_n \in P\) vzorcom \begin{equation}\label{iteracie} p_{n + 1} = T(p_n) \quad\mbox{pre}\quad n = 0, 1, \dots \end{equation} Potom \[ \lim_{n \to \infty} p_n = p^*. \] Ak je \(T\) kontraktívne zobrazenie s konštantou \(\lambda \in (0,1)\), platia odhady \begin{equation}\label{qodhad} \rho(p^*,p_n) \leqq {\lambda^n \over 1-\lambda} \rho(p_0,p_1)\qquad\mbox{a}\qquad \rho(p^*,p_n) \leqq {\lambda \over 1-\lambda} \rho(p_{n-1},p_n). \end{equation}

Postup

1. Snáď najjednoduchší prípad kontraktívneho zobrazenia poskytujú funkcie jednej premennej, pričom metrika v \(\mathbb{R}\) je definovaná ako absolútna hodnota vzdialenosti čísel, t. j. \(\rho(x,y)=|x-y|\). Predpokladajme, že funkcia \(\varphi(x)\) je spojite diferencovateľná na intervale \((a;b)\) a spojitá na uzavretom intervale \(\langle a;b\rangle\), pričom pre každé \(x\in\langle a;b\rangle\) je \(\varphi(x)\in\langle a;b\rangle\). Uzavretý interval \(\langle a;b\rangle\) potom reprezentuje úplný metrický priestor. Ak pre každé \(x\in\langle a;b\rangle\) je \(|\varphi^{\prime}(x)|\leqq \lambda\lt1\), tak zobrazenie \(\varphi\) je kontraktívne na \(\langle a;b\rangle\).

   Príklad: Metódou prostých iterácií určme približné reálne riešenie nelineárnej rovnice \[ x^3+2x+4=0 \] s presnosťou \(\varepsilon=10^{-6}\).

   Riešenie: Ak prepíšeme rovnicu na nasledujúci tvar: \[ x^3=-2x-4, \] grafy funkcií \(h(x)=x^3\) (mocninová funkcia) a \(g(x)=-2x-4\) (lineárna funkcia – grafom je priamka) načrtneme celkom jednoducho. Znova si to najprv vyskúšajte sami a porovnajte svoje riešenie s grafmi uvedenými na nasledujúcom obrázku:

   

   Obr.: : Pomocné funkcie pre rovnicu \(x^3+2x+4=0\)

   Je zrejmé, že grafy funkcií \(h(x)\) a \(g(x)\) sa pretínajú práve v jednom bode, ktorého \(x\)-ovú súradnicu označíme \(x^*\). Navyše je evidentné, že bod \(x^*\) leží v intervale \(\langle-2;0\rangle\) a po kratšom uvažovaní môžeme interval separácie dokonca zúžiť na \(\langle-2;-1\rangle\) (zdôvodnite prečo). Správnosť našich nákresov a úvah, presnejšie povedané správnosť určenia intervalu separácie overíme dosadením krajných bodov intervalu do vzorca funkcie \(f(x)\): \[ f(-2)=-8-4+4=-8\lt 0, \qquad f(-1)=-1-2+4=1\gt 0 \qquad\Rightarrow\qquad f(-2)\cdot f(-1)\lt 0, \] t. j. je splnená jedna z podmienok intervalu separácie (v širšom zmysle slova) \(\langle a;b\rangle\): \(f(a)\cdot f(b)\lt 0\). Pripomeňme, že druhou podmienkou je spojitosť funkcie \(f(x)\).
   
   Ak prepíšme rovnicu \(f(x)=0\) na ekvivalentný tvar \(x=\varphi(x)\), potom riešenie \(x^*\) rovnice bude pevným bodom zobrazenia \(\varphi\), t. j. \(x^*=\varphi(x^*)\).
   
   1. Vyjadrime napríklad \(x\) z lineárneho člena danej rovnice: \[ x=\frac{x^3+4}{-2}=\varphi_1(x). \] Vypočítajme deriváciu \[ \varphi_1^{\prime}(x)=-\frac{3x^2}{2},\qquad\mbox{t. j.}\qquad \forall x\in\langle-2;-1\rangle: |\varphi_1^{\prime}(x)| \geqq \frac{3}{2}. \] Nie je teda splnená postačujúca podmienka kontraktívnosti zobrazenie \(\varphi_1\) (ale nie nutná!) , dokonca je narušená vo všetkých bodoch intervalu separácie, a preto sa dá očakávať divergencia iteračného procesu.
   
   2. Vyjadrime teda \(x\) z kubického člena: \[ x=-\sqrt[3]{2x+4}=\varphi_2(x). \] Vypočítajme deriváciu \[ \varphi_2^{\prime}(x)=-\frac{2}{3\sqrt[3]{(2x+4)^2}}. \] Je zrejmé, že ak sa na intervale \(\langle-2;-1\rangle\) bude \(x\) blížiť k hodnote \(-2\), bude absolútna hodnota \(|\varphi_2^{\prime}(x)|\) neohraničene narastať do nekonečna! Zdá sa, že situácia je ešte horšia, ako v prípade zobrazenia \(\varphi_1\). Avšak tento problém môžeme vyriešiť zúžením intervalu separácie. Uvažujme interval \(\langle-1{,}5;-1\rangle\). \(f(-1{,}5)=-2{,}375\lt0\), a keďže \(f(-1)=1\gt0\), platí \(f(-1{,}5)\cdot f(-1)\lt0\), a teda nový interval je intervalom separácie pre rovnicu \(f(x)=0\).
   
   Pre \(x\in\langle-1{,}5;-1\rangle\) je \(2x+4\in\langle1;2\rangle\), a preto na intervale \(\langle-1{,}5;-1\rangle\) platí: \[ |\varphi_2^{\prime}(x)|\leqq \frac{2}{3}=\lambda\lt1. \] Zobrazenie \(\varphi_2\) je teda na intervale separácie \(\langle-1{,}5;-1\rangle\) kontraktívne a podľa Banachovej vety má na tomto intervale jediný pevný bod, ktorý s požadovanou presnosťou určíme pomocou nasledujúceho postupu (pouvažujte, ktorú podmienku sme v úvahách vynechali a ako môže ovplyvniť naše predchádzajúce závery).
   
   Približné riešenie s požadovanou presnosťou určíme nasledujúcim postupom: zvolíme ľubovoľný štartovací bod \(x_0\), najlepší bude zrejme stred intervalu separácie \(x_0=-1{,}25\). Ďalšie hodnoty \(x_n\) získame na základe iteračného pravidla \[ x_{n+1}=-\sqrt[3]{2\cdot x_n+4},\qquad n=0, 1, 2, \dots \] Po každej iterácii odhadneme odchýlku od pevného bodu \(x^*\) – uvažovaného riešenia nelineárnej rovnice – na základe vzťahu (\ref{qodhad}). Keďže \(\lambda=2/3\), bude \(\lambda /(1-\lambda)=2\), teda bude platiť \[ |x_{n}-x^*|\leqq 2|x_{n}-x_{n-1}|. \] Výpočet ukončíme, keď sa pravá strana získanej nerovnosti stane menšou ako hodnota požadovanej presnosti \(\varepsilon\).
   
   Výsledky výpočtov sú zhrnuté v nasledujúcej tabuľke: \[ \begin{array}{|r|l|l|} \hline n \a x_n \a 2|x_{n}-x_{n-1}| \\ \hline 0 \a -1{,}25 \a - \\ \hline 1 \a -1{,}14471424 \a 0{,}210571515 \\ \hline 2 \a -1{,}19595199 \a 0{,}102475492 \\ \hline 3 \a -1{,}17157652 \a 0{,}048750937 \\ \hline 4 \a -1{,}18329800 \a 0{,}023442967 \\ \hline 5 \a -1{,}17769059 \a 0{,}011214830\\ \hline 6 \a -1{,}18037976 \a 0{,}005378334 \\ \hline 7 \a -1{,}17909163 \a 0{,}002576244\\ \hline 8 \a -1{,}17970900 \a 0{,}001234734 \\ \hline 9 \a -1{,}17941319 \a 0{,}000591618 \\ \hline 10 \a -1{,}17955495 \a 0{,}000283508 \\ \hline 11 \a -1{,}17948702 \a 0{,}000135851 \\ \hline 12 \a -1{,}17951957 \a 0{,}000065099 \\ \hline 13 \a -1{,}17950397 \a 0{,}000031194 \\ \hline 14 \a -1{,}17951145 \a 0{,}000014948 \\ \hline 15 \a -1{,}17950786 \a 0{,}000007163 \\ \hline 16 \a -1{,}17950958 \a 0{,}000003432 \\ \hline 17 \a -1{,}17950876 \a 0{,}000001645 \\ \hline 18 \a -1{,}17950915 \a 0{,}000000788 \\ \hline \end{array} \] Na záver môžeme konštatovať, že približným riešením danej rovnice s presnosťou \(\varepsilon=10^{-6}\) je číslo \(x_{18}= -1{,}17950915\).

   Poznámka: Konvergencia metódy prostých iterácií je pomalšia ako v prípade Newtonovej metódy. Na zlepšenie presnosti o jednu desatinnú hodnotu boli potrebné zhruba 3 iterácie. Nevýhodou tejto metódy je tiež zložitý a často neúspešný výber kontraktívnej funkcie \(\varphi(x)\). Výhodou je však jednoduchá realizácia na kalkulačke – výpočet jednotlivých iterácií býva rýchlejší ako v metóde bisekcie i v Newtonovej metóde (túto však s kalkulačkou s možnosťou zadávania vzorcov už tiež dokážeme efektívne riešiť).

   Zobraziť riešenieSkryť riešenie

   Poznámka: Výpočty v Matlabe/Octave sa dajú realizovať nastavením štartovacej hodnoty
   
   x=-1.25
   
   a následným opakovaním trojice príkazov umiestnených do jedného riadku:
   
   xn=-(2*x+4)^(1/3), 2*abs(x-xn), x=xn;
   
   Podobne efektívne sa však dá v Matlabe/Octave realizovať aj výpočet pomocou Newtonovej metódy.

   Poznámka: Dá sa ukázať, že ak je \(|\varphi^{\prime}(x)|\leqq \lambda\lt1\) na intervale separácie \(\langle a;b\rangle\) , tak iteračný proces skonverguje z bodu \(x_0=a\) alebo \(x_0=b\) aj bez overenia podmienky \(\varphi(x)\in\langle a;b\rangle\).
2. Predtým ako pristúpime k riešeniu sústav lineárnych algebrických rovníc Jacobiovou iteračnou metódou, je dobré precvičiť pojmy riadková norma matice a matica riadkovo diagonálne dominantná.

   Príklad: Určme riadkové normy nasledujúcich matíc: \[ \mbf{x}=(\begin{array}{rrr}1\a -2\a 3\end{array}), \qquad \mbf{y}=\left(\begin{array}{r}-4 \\5\\-6 \end{array}\right), \qquad \mbf{A}=\left(\begin{array}{rrr}7 \a -8 \a 9 \\-10 \a 11 \a -12 \end{array}\right). \]

   Riešenie: Definícia riadkovej normy matice \(\mbf{A}\) typu \(m\times k\) (obsahujúcej \(m\) riadkov a \(k\) stĺpcov je: \[ \Vert\mbf{A}\Vert_{\mathrm{r}} = \max_{1\leqq i\leqq m} \sum_{j=1}^k |a_{ij}|, \] t. j. v každom riadku spočítame absolútne hodnoty prvkov matice a za normu prehlásime maximálny z týchto súčtov (v prípade jediného riadku je, samozrejme, súčet v tomto riadku maximálny). Teda riešením našej úlohy sú nasledujúce normy: \[ \Vert\mbf{x}\Vert_{\mathrm{r}}=6, \qquad \Vert\mbf{y}\Vert_{\mathrm{r}}=6, \qquad \Vert\mbf{A}\Vert_{\mathrm{r}}=\max\{24;33\}=33. \]

   Zobraziť riešenieSkryť riešenie

   Poznámka: Riadková norma sa zvykne označovať tiež ako tzv. nekonečno-norma: \(\Vert\mbf{A}\Vert_{\mathrm{r}}=\Vert\mbf{A}\Vert_{\mathrm{\infty}}\). Táto maticová norma je zosúladená s riadkovou normou stĺpcového vektora \(\Vert\mbf{x}\Vert_{\infty}=\max\limits_{1\leqq i\leqq m}|x_i|\).

   Poznámka: Ak použijeme riadkové normy na výpočet metriky \(\rho\) vo vektorovom priestore \(\mathbb{R}^k\), pričom vektory budeme chápať ako stĺpcové vektory, tak pre zobrazenie \(T(\mbf{x})=\mbf{G}\mbf{x}+\mbf{c}\) platí: \[ \Vert T(\mbf{x})-T(\mbf{y}) \Vert_r=\Vert \mbf{G}\mbf{x}+\mbf{c}-(\mbf{G}\mbf{y}+\mbf{c}) \Vert_r \leqq \Vert\mbf{G}\Vert_r\cdot \Vert\mbf{x}-\mbf{y}\Vert_r, \] t. j. ak bude platiť \(\Vert\mbf{G}\Vert_r\leqq\lambda\lt1\), bude zobrazenie \(T\) kontraktívne s konštantou \(\lambda\) v metrickom priestore \(\mathbb{R}^k\) s metrikou určenou riadkovou normou stĺpcových vektorov, t. j. max-normou.

   Pred riešením nasledujúcich úloh si najprv pripomeňme definíciu matice riadkovo diagonálne dominantnej.
   
   Matica \(\mbf{A}\) typu \(k\times k\) sa nazýva riadkovo diagonálne dominantnou práve vtedy, ak platí: \[ \forall i=1, 2, \dots k:\qquad |a_{ii}| \gt \sum_{\scriptsize\begin{array}{c} j=1\\j\ne i\end{array}}^k |a_{ij}|. \]

   Príklad: Overme, či je matica \[ \mbf{A}=\left(\begin{array}{rrr}7 \a -8 \a 9 \\-10 \a 11 \a -12\\ 13 \a -14 \a 15 \end{array}\right) \] riadkovo diagonálne dominantná, prípadne či sa dá výmenami riadkov pretransformovať na riadkovo diagonálne dominantnú.

   Riešenie: V každom riadku si všimneme prvok, ktorého absolútna hodnota je maximálna (môžeme ho nazvať hlavným prvkom v riadku, pričom diagonálne dominantná matica má v každom riadku hlavný prvok na hlavnej diagonále). V prípade zadanej matice sú všetky hlavné prvky umiestnené v treťom stĺpci. Preto matica nie je diagonálne dominantná.
   
   Pri výmene riadkov sa hlavné prvky nedostanú mimo tretieho stĺpca, preto matica nebude riadkovo diagonálne dominantná ani po výmenách riadkov.

   Zobraziť riešenieSkryť riešenie

   Poznámka: Pri riešení predchádzajúcej úlohy sme nepotrebovali na zdôvodnenie využiť presnejšie definíciu diagonálnej dominantnosti. Keďže \(9\not\gt7+8\), \(12\not\gt10+11\) a \(15\not\gt13+14\), žiaden riadok nemá dominantný hlavný prvok, a teda matica nie je diagonálne dominantná a nemôže sa takou stať len výmenou riadkov. Iné riadkové úpravy teraz nebudeme uvažovať.

   Príklad: Overme, či je matica \[ \mbf{A}=\left(\begin{array}{rrr}3 \a -4 \a 9 \\5 \a 2 \a 1\\ -3 \a -10 \a 6 \end{array}\right) \] riadkovo diagonálne dominantná, prípadne či sa dá výmenami riadkov pretransformovať na riadkovo diagonálne dominantnú.

   Riešenie: V každom riadku si znova všimneme prvok, ktorého absolútna hodnota je maximálna, ale budeme súčasne posudzovať aj jeho dominantnosť: \[ \begin{array}{r} 9\gt 3+4,\\ 5\gt 2+1,\\ 10\gt 3+6. \end{array} \] Teda v každom riadku sa nachádza dominantný hlavný prvok. Keďže všetky dominantné prvky sa nachádzajú v rôznych stĺpcoch, výmenami riadkov môžeme získať diagonálne dominantnú maticu: \[ \mbf{B}=\left(\begin{array}{rrr}\mathbf{5} \a 2 \a 1\\ -3 \a \mathbf{-10} \a 6\\3 \a -4 \a \mathbf{9} \end{array}\right). \]

   Zobraziť riešenieSkryť riešenie
3. Iteračné metódy riešenia sústav lineárnych algebrických rovníc poskytujú ďalší príklad praktického použitia Banachovej vety o pevnom bode. Z celej škály rôznych metód sa budeme venovať len tej najjednoduchšej – Jacobiovej metóde.

   Príklad: Sústavu lineárnych algebrických rovníc \[ \begin{array}{rcr} 2x-3y+7z\a=\a-11\\ 10x-2y+\phantom{1}z\a=\a5\\ -3x+8y-2z\a=\a15 \end{array} \] riešme Jacobiovou iteračnou metódou. Najprv overme splnenie postačujúcich podmienok konvergencie, potom uskutočnime 3 iterácie a odhadnime chybu.

   Riešenie: Overíme najprv, či je matica sústavy riadkovo diagonálne dominantná. Vidíme, že v každom riadku sa nachádza dominantný prvok: \[ \mbf{A}=\left[\begin{array}{rrr} 2\a-3\a \mathbf{7}\\ \mathbf{10}\a-2\a1\\ -3\a\mathbf{8}\a-2 \end{array}\right] \] Matica \(\mbf{A}\) však nie je riadkovo diagonálne dominantná. Keď prvý riadok sústavy prehodíme za tretí riadok, získame ekvivalentnú sústavu (s tou istou množinou riešení) s riadkovo diagonálne dominantnou maticou: \[ \begin{array}{rcr} 10x-2y+\phantom{1}z\a=\a5\\ -3x+8y-2z\a=\a15\\ 2x-3y+7z\a=\a-11 \end{array} \] \[ \begin{array}{r} 10\gt 2+1,\\ 8\gt3+2,\\ 7\gt2+3. \end{array} \] Pre túto sústavu je splnená postačujúca podmienka konvergencie Jacobiovej iteračnej metódy – riadková diagonálna dominantnosť matice sústavy.
   
   Ďalej z každej rovnice vyjadríme diagonálnu premennú: \[ \begin{array}{rcl} x\a=\a\dfrac{5+2y-z}{10}\\[3ex] y\a=\a\dfrac{15+3x+2z}8\\[3ex] z\a=\a\dfrac{-11-2x+3y}7 \end{array} \] Vzorce iteračného procesu získame tak, že premenným na pravej strane pripíšeme index \(n\) (stará, aktuálna premenná) a premenným na ľavej strane pripíšeme index \(n+1\): \[ \begin{array}{rcl} x_{n+1}\a=\a\dfrac{5+2y_{n}-z_{n}}{10}\\[3ex] y_{n+1}\a=\a\dfrac{15+3x_{n}+2z_{n}}8\\[3ex] z_{n+1}\a=\a\dfrac{-11-2x_{n}+3y_{n}}7 \end{array} \] Tento iteračný proces môžeme zapísať aj v nasledujúcom maticovom tvare: \[ \mbf{x}_{n+1}=\mbf{G}\mbf{x}_n+\mbf{c} \qquad\Leftrightarrow\qquad \left[\begin{array}{r} x_{n+1}\\ y_{n+1}\\ z_{n+1} \end{array}\right]= \left[\begin{array}{rrr} 0\a\dfrac{2}{10}\a-\dfrac{1}{10}\\[3ex] \dfrac{3}8\a0\a\dfrac{2}8\\[3ex] -\dfrac{2}7\a\dfrac{3}7\a0\end{array}\right]\cdot \left[\begin{array}{r} x_{n}\\ y_{n}\\ z_{n} \end{array}\right]+ \left[\begin{array}{r} \dfrac{5}{10}\\[3ex] \dfrac{15}8\\[3ex] -\dfrac{11}7 \end{array}\right] \] Riadková norma matice \(\mbf{G}\) je rovná \[ \Vert\mbf{G}\Vert_{\mathrm{r}}=\max\left\{\frac{2+1}{10};\frac{3+2}8;\frac{2+3}7\right\}=\max\left\{\frac{3}{10};\frac{5}8;\frac{5}7\right\}=\frac{5}7=\lambda\lt1. \] Týmto sme dokázali, že zobrazenie určujúce iteračný proces je kontraktívne s parametrom \(\lambda=\frac57\). Iterácie budú konvergovať z ľubovoľného začiatočného bodu \(\mbf{x}_0\) a na odhad [ne]presnosti môžeme použiť vzťah (\ref{qodhad}), pričom v tomto prípade bude \(\lambda /(1-\lambda)=\frac57/\frac27=\frac52\). Iteračný proces začneme zo začiatočného vektora \(\vec{x}_0=(0;0;0)^T\). V nasledujúcej tabuľke sú znázornené hodnoty jednotlivých iterácií a tiež zmien jednotlivých zložiek vektorov \(\mbf{x}_n\) (čísla sú zaokrúhlené na \(10\) desatinných miest). \[ \begin{array}{|r|c|c|c|c|} \hline n\a x_n \a y_n \a z_n \a \\ \a x_{n}-x_{n-1} \a y_{n}-y_{n-1} \a z_{n}-z_{n-1} \a \frac52\cdot\Vert \mbf{x}_{n}-\mbf{x}_{n-1}\Vert_{\infty} \\\hline 0\a 0 \a 0 \a 0 \a \\ \a - \a - \a - \a -\\\hline 1\a \frac{5}{10} \a \frac{15}{8} \a -\frac{11}{7} \a \\ \a 0{,}5 \a 1{,}875 \a -1{,}5714285714 \a 4{,}6875\phantom{000000}\\\hline 2\a \phantom{-}1{,}0321428571 \a \phantom{-}1{,}6696428571 \a -0{,}9107142857\a \\ \a \phantom{-}0{,}5321428571 \a -0{,}2053571429 \a \phantom{-}0{,}6607142857 \a 1{,}6517857143\\\hline 3\a \phantom{-}0{,}9250000000 \a \phantom{-}2{,}0343750000 \a -1{,}1507653061\a \\ \a -0{,}1071428571 \a \phantom{-}0{,}3647321429 \a -0{,}2400510204 \a 0{,}9118303571\\\hline \cdots \a \cdots \a\cdots \a\cdots \a\cdots\\ \hline 10\a \phantom{-}1{,}0005413588 \a \phantom{-}1{,}9990562805 \a -0{,}9989840495\a \\ \a \phantom{-}0{,}0016363207 \a -0{,}0025842961 \a \phantom{-}0{,}0031483856\a 0{,}0078709640\\\hline \cdots \a \cdots \a\cdots \a\cdots \a\cdots\\ \hline 24\a \phantom{-}1{,}0000000566 \a \phantom{-}1{,}9999999071 \a -0{,}9999998921\a \\ \a \phantom{-}0{,}0000001657 \a -0{,}0000002719 \a \phantom{-}0{,}0000003159\a 0{,}0000007897\\\hline \end{array} \] Presné riešenie danej sústavy je \((x;y;z)^T=(1;2;-1)^T\). Z tabuľky je vidieť, že odhad nepresnosti je dosť pesimistický, ale správny. Napríklad po troch iteráciách je maximálna absolútna odchýlka od presného riešenia rovná \(0{,}1507653061\), pričom jej horný odhad je rovný \(0{,}9118303571\), čo je 6-krát väčšia hodnota.

   Poznámka: Ak by sme chceli riešiť úlohu s požadovanou presnosťou, napríklad \(\varepsilon=0{,}01\), museli by sme uskutočniť \(10\) iterácií Jacobiovej metódy na to, aby sme mali istotu dosiahnutej presnosti. Pritom by sme dosiahli presnosť približne \(0{,}00102\). Na dosiahnutie presnosti \(\varepsilon=10^{-6}\) by sme potrebovali uskutočniť \(24\) iterácií, pričom skutočná nepresnosť by bola približne \(10^{-7}\).

   Zobraziť riešenieSkryť riešenie

   Poznámka: V prípade menších rozmerov (systémov s rádovo desiatkami alebo stovkami rovníc) je zrejme lepšie použiť na riešenie sústav lineárnych algebrických rovníc Gaussovu eliminačnú metódu. Iteračné metódy sú však neoceniteľné pri riešení veľkých sústav, napríklad s počtom neznámych rádovo milión (také sústavy sa v reálnej praxi skutočne riešia). Úspešne sa pritom dajú využiť aj špeciálne vlastnosti systémov (napríklad riedke matice sústav).

   Poznámka: Výpočty v Matlabe/Octave sa dajú realizovať nastavením štartovacej hodnoty, zadaním matíc a pomocných parametrov:
   
   x=[0;0;0]; G=[0,2/10,-1/10;3/8,0,2/8;-2/7,3/7,0]; c=[5/10;15/8;-11/7]; q=5/2; iter=0;
   
   a následným opakovaním pätice príkazov umiestnených do jedného riadku:
   
   iter=iter+1, xn=G*x+c, xn-x, q*norm(xn-x,inf), x=xn;
   
   

Zdroje

1. Buša, Pirč, Schrötter: Numerické metódy, pravdepodobnosť a matematická štatistika, 2006, ISBN 80-8073-632-4. Môžete stiahnuť obrazovkovú alebo tlačovú verziu.
2. Daňo, Ostertagová: Vybrané kapitoly z numerických metód, pravdepodobnosti a matematickej štatistiky, Equilibria s.r.o., Košice, 2012, ISBN 978-80-8143-012-1.

Doplňujúce úlohy

Úloha: Metódou prostej iterácie určte približné reálne riešenie rovnice \(\mathrm{e}^{x}+x=0\) s presnosťou \(\varepsilon=0{,}0001\). Overte, že navrhnuté zobrazenie \(\varphi\) je kontraktívne a dosiahnutú presnosť overte na základe vzťahu (\ref{qodhad}).
Výsledok: \(\varphi(x)=-\mathrm{e}^x\); \(\ \alpha\doteq -0{,}567163011515522\).
Zobraziť výsledokSkryť výsledok
Úloha: Metódou prostej iterácie určte všetky približné reálne riešenia rovnice \(5\cdot x\cdot \mathrm{e}^{x}+1=0\) s presnosťou \(\varepsilon=0{,}001\). Pre každý koreň overte, že navrhnuté zobrazenie \(\varphi\) je kontraktívne a dosiahnutú presnosť overte na základe vzťahu (\ref{qodhad}).
Výsledok: \(\varphi_1(x)=-\dfrac{\mathrm{e}^{-x}}{5}\); \(\ \alpha_1\doteq -0{,}260459390043382\); \(\qquad\varphi_2(x)=-\ln(-5x)\); \(\ \alpha_2\doteq -2{,}54223453548100\).
Zobraziť výsledokSkryť výsledok
Úloha: Metódou prostej iterácie určte približné reálne riešenie rovnice \(\sin(x)+2x/2=0\) s presnosťou \(\varepsilon=0{,}0001\). Overte, že navrhnuté zobrazenie \(\varphi\) je kontraktívne a dosiahnutú presnosť overte na základe vzťahu (\ref{qodhad}).
Výsledok: \(\varphi(x)=1-\dfrac{\sin x}{2}\); \(\ \alpha\doteq 0{,}684021994027646\).
Zobraziť výsledokSkryť výsledok
Úloha: Metódou prostej iterácie určte približné reálne riešenie rovnice \(2\cdot\ln x-\dfrac1x=0\) s presnosťou \(\varepsilon=0{,}0001\). Overte, že navrhnuté zobrazenie \(\varphi\) je kontraktívne a dosiahnutú presnosť overte na základe vzťahu (\ref{qodhad}).
Výsledok: \(\varphi(x)=\mathrm{e}^{1/(2x)}\); \(\ \alpha\doteq 1{,}4215321058904\).
Zobraziť výsledokSkryť výsledok
Úloha: S presnosťou \(0{,}001\) riešte sústavu rovníc \(\begin{array}[t]{rcr} 2 x_2 - 4 x_3 + 2 x_4 \a = \a 5,\\ 5 x_1 - 4 x_2 + 3 x_3 + 6 x_4 \a = \a - 2, \\ x_1 + 4 x_2 - 2 x_3 + 3 x_4 \a = \a 6, \\ 3 x_1 - 5 x_2 + x_3 + 4 x_4 \a = \a 7.\\ \end{array}\)
Výsledok: \(x_1 = -35{,}5; x_2 = -2{,}4; x_3 = 9{,}1; x_4 = 23{,}1 \)
Zobraziť výsledokSkryť výsledok
Úloha: S presnosťou \(0{,}001\) riešte sústavu rovníc \(\begin{array}[t]{rcr} 2 x_1 - 4 x_2 + 5 x_3 + 6 x_4 \a =\a -7,\\ 3 x_1 - 6 x_2 + 4 x_3 - 3 x_4 \a =\a 5,\\ 4 x_1 + 2 x_2 - 2 x_3 + 5 x_4 \a =\a 3,\\ 2 x_1 - x_2 + 3 x_3 - 4 x_4 \a =\a 6.\\ \end{array}\)
Výsledok: \(x_1 = 1{,}7503; x_2 = 0{,}2080; x_3 = -0{,}5903; x_4 = -1{,}1195\)
Zobraziť výsledokSkryť výsledok
Úloha: S presnosťou \(0{,}001\) riešte sústavu rovníc \(\begin{array}[t]{rcr} x_1 - 2 x_2 + 3 x_3 - 12 x_4 \a =\a -4, \\ 9 x_1 - x_2 + 3 x_3 + 2 x_4 \a =\a 6,\\ -9 x_1 + 10 x_2 - 2 x_3 + x_4 \a =\a -2, \\ 2 x_1 - x_2 + 8 x_3 - x_4 \a =\a 5 . \\ \end{array}\)
Výsledok: \(x_1 = 0{,}3771; x_2 = 0{,}2146; x_3 = 0{,}6180; x_4 = 0{,}4835\)
Zobraziť výsledokSkryť výsledok
Úloha: S presnosťou \(0{,}001\) riešte sústavu rovníc \(\begin{array}[t]{rcr} 2 x_1 - 3 x_2 + x_3 - 12 x_4 \a =\a 24,\\ x_1 + 10 x_2 - 2 x_3 + 3 x_4 \a =\a 8,\\ 13 x_1 - x_2 + 3 x_3 - 4 x_4 \a =\a -5,\\ 2 x_1 - 2 x_2 + 10 x_3 + x_4 \a =\a -7 .\\ \end{array}\)
Výsledok: \(x_1 = -1{,}0795; x_2 = 1{,}7109; x_3 = 0{,}1179; x_4 = - 2{,}5978 \)
Zobraziť výsledokSkryť výsledok
Úloha: S presnosťou \(0{,}001\) riešte sústavu rovníc \(\begin{array}[t]{rcr} 15 x_1 - 2 x_2 + 3 x_3 + 2 x_4 \a =\a 10,\\ x_1 + 12 x_2 - x_3 + 2 x_4 \a =\a -13,\\ 2 x_1 - x_2 + 17 x_3 - 3 x_4 \a =\a 12, \\ -3 x_1 + x_2 + 2 x_3 -13 x_4 \a =\a 14 .\\ \end{array}\)
Výsledok: \(x_1 = 0{,}6399; x_2 = -0{,}9003; x_3 = 0{,}3591; x_4 = -1{,}2386\)
Zobraziť výsledokSkryť výsledok