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}\).
    Zobraziť 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). \]
    Zobraziť 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ú.
    Zobraziť 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ú.
    Zobraziť 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.
    Zobraziť 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}).
    Zobraziť 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}).
    Zobraziť 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}).
    Zobraziť 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}).
    Zobraziť 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}\)
    Zobraziť 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}\)
    Zobraziť 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}\)
    Zobraziť 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}\)
    Zobraziť 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}\)
    Zobraziť výsledok
comments powered by Disqus