View source for Obyčajné differenciálne rovnice/Implicitné Runge-Kutta metódy

= 4.3 Implicitné Runge-Kutta metódy =
Ak je matica koeficientov <math display=„inline“>A</math> v Butcherovej tabuľke Rungeho-Kuttovej metódy plne vyplnenou maticou, výpočet ohodnotení funkcie <math display=„inline“>k_j</math> pre každé <math display=„inline“>j=1, \ldots , s</math> závisí od ostatných <math display=„inline“>k_1, \dots k_s</math>, najmä tiež od <math display=„inline“>k_j, k_{j+1}, \dots k_s</math> , pozri (4. 1). Najjednoduchšou iRKV je už známa implicitná Eulerova metóda, ďalšími príkladmi sú implicitný stredový bod a lichobežníkové pravidlo:<br />
<br />
Implicitné pravidlo stredového bodu, <math display=„inline“>s=1</math>:<br />
<br />

[[file:Butcher Tab 13.png|left]]
<br />
<math display=„block“>\begin{aligned}
 k_1&=& f\big(t_i+\frac{h}{2},\eta_i+\frac{h}{2} k_1\big)\\
\eta_{i+1}&=&\eta_i+h k_1 \qquad \qquad \quad 
\end{aligned}</math><br />
<br />
Implicitné lichobežníkové pravidlo, <math display=„inline“>s=2</math>:<br />
<br />

[[file:Butcher Tab 14.png|left]]


<br />
<math display=„block“>\begin{aligned}
 k_1&=& f(t_i,\eta_i)\qquad \quad \quad\quad \quad\quad \quad\\
k_2&=& f\big(t_i+h,\underbrace{\eta_i+\frac{h}{2} (k_1+k_2)}_{\eta_{i+1}}\big) \qquad\\
\eta_{i+1}&=&\eta_i+\frac{h}{2} (k_1+k_2)\qquad \quad \qquad \qquad \\ 
&\equiv& \eta_i+\frac{h}{2}  \Big( f(t_i,\eta_i) +f (t_{i +1},\eta_{i+1}) \Big).     
 \end{aligned}</math>

Dôležitou podmnožinou iRKV sú tzv. gaussovské metódy, ktoré umožňujú čo najväčší poriadok vzhľadom na počet krokov. Tieto metódy patria medzi takzvané <span>''kolokačné metódy''</span> a sú odvodené od Gaussovej kvadratúry, ktorej vďačia za svoj názov. Gaussove metódy, ako aj iné (ale nie všetky) iRKV, majú dobré stabilizačné vlastnosti, ktoré sú dôležité najmä pri „tuhých“ problémoch.

<span id=„steife-probleme“></span>

=== Stiff problémy ===


Pojem tuhý problém vznikol pri použití numerických metód na riešenie diferenciálnej rovnice, keď sa na získanie použiteľného konvergentného riešenia vyžadujú veľmi malé veľkosti krokov alebo menšie a menšie veľkosti krokov s postupom metódy. V takýchto prípadoch explicitné metódy, ako napríklad Eulerova metóda alebo eRKV vyššieho rádu s pevnou veľkosťou kroku, zlyhávajú; metódy s riadením veľkosti kroku vytvárajú stále menšie veľkosti kroku až po nulu (v rámci presnosti počítača), čo znamená, že v určitom bode sa už nepohybujú, zastavia sa - odtiaľ pochádza termín „tuhý“.

Medzi tuhé problémy patria diferenciálne rovnice s riešeniami s vysokou rýchlosťou zmien alebo systémy so zložkami riešenia, ktoré rastú veľmi rozdielnou rýchlosťou. Tu explicitná metóda generuje aproximáciu riešenia v ďalšom časovom kroku na základe predchádzajúcich, vo vysoko dynamických systémoch už nie aktuálnych, sklonov/informácií náchylných na chyby, a tak explicitná metóda rýchlo prekročí cieľ.

Príkladom tuhých problémov sú systémy lineárnych diferenciálnych rovníc, ktorých matica má veľmi rozdielne vlastné hodnoty, alebo diferenciálne rovnice opisujúce chemické reakcie s látkami, ktoré reagujú rôznymi rýchlosťami. Vďaka dobrým stabilizačným vlastnostiam implicitných jednokrokových metód, ktoré svoj priebeh v aktuálnom kroku prispôsobujú budúcemu (ešte silnejšiemu) gradientu, a tak poskytujú dobré výsledky aj pre väčšie veľkosti krokov <math display=„inline“>h</math>, sú iRKV vhodné najmä pre tuhé problémy.



<div id=„Obr:S“ class=„obrázok“>
[[File:Abb4.1 Lösungskomponenten eines streiffen Differentialgleichungssystems.png|center|500px ]]
Obrázok 4.1: Komponenty riešenia systému tuhej diferenciálnej rovnice, presné riešenie <math display=„inline“>y_1(t)=e^{10t}, \ y_2=1000 e^{-10t}</math> a aproximácia explicitnou Eulerovou metódou, <math display=„inline“>h=0.125</math>.

</div>
Pri implicitných Runge-Kutta metódach sa kroky <math display=„inline“>k_j</math> počítajú riešením sústavy rovníc (4.1). Existencia riešenia tejto prípadne nelineárnej sústavy rovníc nie je vždy zaručená alebo dosiahnuteľná pomocou iteračných metód. Postačujúcou podmienkou existencie takéhoto riešenia a konvergencie iteračnej metódy pevného bodu je dostatočne malá veľkosť kroku <math display=„inline“>h</math>:
<div class=„theorem“>
----
'''Nastavenie 4.2''' 
(Butcher 1964)<br />

Nech <math display=„inline“>f</math> je spojitý na <math display=„inline“>{\mathbb R}\times {\mathbb R}^m</math> a Lipschitzovo spojitý vzhľadom na <math display=„inline“>y</math> s Lipschitzovou konštantou <math display=„inline“>L</math>. Pre prírastok <math display=„inline“>h</math> platí <math display=„block“>
h<\frac{1}{L\|| A\||_\infty}=\frac{1}{L \mathrm{max}_{i} \sum_{j=1,\ldots s}|a_{ij}|}.\qquad (4.12)</math> 


Potom sústava rovníc (4.1), <math display=„block“>k_j=f\Big(t_i+h c_j , \eta_i+h\sum_{\nu=1}^{s}a_{jm}k_\nu\Big) \quad \ j=1,\ldots,s</math> 

je jedinečné riešenie, ktoré sa dá vypočítať postupnou substitúciou (iteráciou pevného bodu). Ak <math display=„inline“>f\in C^p ({\mathbb R}\times {\mathbb R}^m)</math>, potom <math display=„inline“>k_j</math> ako funkcie <math display=„inline“>h</math> sú tiež <math display=„inline“>p</math>-krát spojito diferencovateľné.


</div>

</div>
<div class=„proof“>

'''Dôkaz.''' Pre jednoduchosť nech <math display=„inline“>m=1</math>. Riešenie (nelineárnej) sústavy rovníc (4.1) pre <math display=„inline“>k_1, \ldots k_s</math> možno určiť iteračne: <math display=„block“>
k_j^{(m+1)}=f\Big(t_i+h c_j , \eta_i+h\sum_{\nu=1}^{s}a_{j\nu}k_\nu ^{(m)}\Big) \quad \ j=1,\ldots,s.\qquad (4.13)</math> 


Ak sústavu rovníc (4.1) prevedieme do vektorového tvaru, <math display=„block“>\vec{K}=F(\vec{K}),</math> 

pričom <math display=„inline“>\vec{K}=(k_1, \ldots k_s)^T \in {\mathbb R}^s, \ F: {\mathbb R}^s \to {\mathbb R}^s,</math> <math display=„block“>\begin{aligned}
  F_j (\vec{K}):= f\Big(t_i+h c_j , \eta_i+h\sum_{\nu=1}^{s}a_{j\nu}k_\nu \Big)=
 f\Big(t_i+h c_j , \eta_i+h A_{j}\cdot \vec{K}\Big) \quad \ j=1,\ldots,s
\end{aligned}</math> 

namiesto (4.13) dostaneme iteračné pravidlo <math display=„block“>
\vec{K}^{(m+1)}=F\big( \vec{K}^{(m)}   \big)\qquad (4.14)</math> 


s počiatočným vektorom <math display=„inline“>K^{(0)}.</math>


Podľa Banachovej vety o pevnom bode, pozri vetu 2.1, kapitola 2, existuje jedinečné riešenie, pevný bod <math display=„inline“>\vec{K}=F(\vec{K})</math>, ak <math display=„inline“>F</math> je samomapovanie a kontrahovanie. Pre funkciu <math display=„inline“>F: {\mathbb R}^s \to  {\mathbb R}^s</math> platí, že <math display=„inline“>F({\mathbb R}^s ) \subseteq {\mathbb R}^s</math>, t. j. vždy je samomapovanie.<br />
Teraz skúmame, či <math display=„inline“>F</math> je kontrakcia. Odhadneme Lipschitzovu spojitosť funkcie <math display=„inline“>f</math> a trojuholníkovú nerovnosť pre absolútnu hodnotu v maximálnej norme: <math display=„block“>\begin{aligned}
  \|F (\vec{K})^1-F (\vec{K}^2)\|_\infty=
\max_{j=1,..., s}\Big| f\Big(t_i+h c_j , \eta_i+h\sum_{\nu=1}^{s}a_{j\nu}k_\nu ^1\Big)-f\Big(t_i+h c_j , \eta_i+h\sum_{\nu=1}^{s}a_{j\nu}k_\nu ^2\Big)\Big|
\\ \stackrel{L-stetig} {\leq} \max_{j}hL \Big|\sum_{\nu=1}^{s}a_{j\nu}(k_\nu ^1-k_\nu ^2)\Big| \leq hL \max_{j}\sum_{\nu=1}^{s}|a_{j\nu}| \max_{\nu}|k_\nu ^1-k_\nu ^2| \\
= hL \|| A\||_{\infty}\| K^1-K^2\|_\infty.
\end{aligned}</math> 

Z tohto odhadu vyplýva, že <math display=„inline“>F</math> je kontrakcia v Banachovom priestore <math display=„inline“>{\mathbb R}^s, \|\cdot \|_\infty</math>, ak <math display=„inline“>hL \| A\||_{\infty}\| < 1</math>. Z toho vyplýva, že mapovanie <math display=„inline“>F</math> pre <math display=„inline“>h<1/(L\||A\||_\infty)</math> v <math display=„inline“>{\mathbb R}^s</math> má jedinečný pevný bod, <math display=„block“>\vec{K}^\star=F(\vec{K}^\star),</math> 

Tvrdenie (4.13), (4.14) konverguje k tomuto pevnému bodu. Tvrdenie o p-násobnej spojitej diferencovateľnosti <math display=„inline“>k_j</math> ponecháme bez dôkazu. ◻


</div>
----
<span> ''''Poznámka o riešiteľnosti iRKV'''</span> <span> '''Remark on the solvability of the iRKV'''</span>


# Obmedzenie veľkosti kroku <math display=„inline“>h</math> môže byť veľmi obmedzujúce pre veľké <math display=„inline“>L</math> konštanty (t. j. pre <math display=„inline“>f</math> s vysokými hodnotami derivácie <math display=„inline“>\frac{\partial f }{\partial y} \approx L</math>) môžu byť veľmi obmedzujúce a viesť k pomalej konvergencii metódy pevného bodu. Východiskom v týchto prípadoch je použitie inej iteračnej metódy s vyššou rýchlosťou konvergencie na výpočet <math display=„inline“>k_j</math>, napríklad Newtonovej, sekantovej alebo kvázi-Newtonovej metódy. Tieto metódy konvergujú aj pre väčšie <math display=„inline“>h</math>, pretože majú superlineárnu rýchlosť konvergencie, ak je počiatočná hodnota zvolená priaznivo, v rámci tzv. konvergenčného intervalu.
# Ak je funkcia <math display=„inline“>f</math> len lokálne Lipschitzovo spojitá v <math display=„inline“>y</math>, t. j. len v okolí <math display=„inline“>K^{(0)}</math>, potom vyplývajú ďalšie obmedzenia na veľkosť kroku <math display=„inline“>h</math>, aby sa zaručila vlastnosť samomapovania.
# Lipschitzova spojitosť procesnej funkcie <math display=„inline“>\Phi</math> eRKV, ako aj iRKV vzhľadom na <math display=„inline“>y</math> vyplýva z Lipschitzovej spojitosti <math display=„inline“>f</math>. To znamená, že iRKV s rádom konzistencie p sú tiež konvergentné s rádom konvergencie p. (pozri vetu 3.1)

[[Category:Obyčajné differenciálne rovnice]]