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

4.3 Implicitné Runge-Kutta metódy

Ak je matica koeficientov $A$ v Butcherovej tabuľke Rungeho-Kuttovej metódy plne vyplnenou maticou, výpočet ohodnotení funkcie $k_{j}$ pre každé $j=1,\ldots ,s$ závisí od ostatných $k_{1},\dots k_{s}$, najmä tiež od $k_{j},k_{j+1},\dots k_{s}$ , 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:

Implicitné pravidlo stredového bodu, $s=1$:

${\begin{aligned}k_{1}&=&f{\big (}t_{i}+{\frac {h}{2}},\eta _{i}+{\frac {h}{2}}k_{1}{\big )}\\\eta _{i+1}&=&\eta _{i}+hk_{1}\qquad \qquad \quad \end{aligned}}$

Implicitné lichobežníkové pravidlo, $s=2$:

${\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}}$

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é kolokačné metódy 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.

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 $h$, sú iRKV vhodné najmä pre tuhé problémy.

Obrázok 4.1: Komponenty riešenia systému tuhej diferenciálnej rovnice, presné riešenie $y_{1}(t)=e^{10t},\ y_{2}=1000e^{-10t}$ a aproximácia explicitnou Eulerovou metódou, $h=0.125$.

Pri implicitných Runge-Kutta metódach sa kroky $k_{j}$ 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 $h$:

---

Nastavenie 4.2 (Butcher 1964)

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

Potom sústava rovníc (4.1), $k_{j}=f{\Big (}t_{i}+hc_{j},\eta _{i}+h\sum _{\nu =1}^{s}a_{jm}k_{\nu }{\Big )}\quad \ j=1,\ldots ,s$

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

Dôkaz. Pre jednoduchosť nech $m=1$. Riešenie (nelineárnej) sústavy rovníc (4.1) pre $k_{1},\ldots k_{s}$ možno určiť iteračne: $k_{j}^{(m+1)}=f{\Big (}t_{i}+hc_{j},\eta _{i}+h\sum _{\nu =1}^{s}a_{j\nu }k_{\nu }^{(m)}{\Big )}\quad \ j=1,\ldots ,s.\qquad (4.13)$

Ak sústavu rovníc (4.1) prevedieme do vektorového tvaru, ${\vec {K}}=F({\vec {K}}),$

pričom ${\vec {K}}=(k_{1},\ldots k_{s})^{T}\in {\mathbb {R} }^{s},\ F:{\mathbb {R} }^{s}\to {\mathbb {R} }^{s},$ ${\begin{aligned}F_{j}({\vec {K}}):=f{\Big (}t_{i}+hc_{j},\eta _{i}+h\sum _{\nu =1}^{s}a_{j\nu }k_{\nu }{\Big )}=f{\Big (}t_{i}+hc_{j},\eta _{i}+hA_{j}\cdot {\vec {K}}{\Big )}\quad \ j=1,\ldots ,s\end{aligned}}$

namiesto (4.13) dostaneme iteračné pravidlo ${\vec {K}}^{(m+1)}=F{\big (}{\vec {K}}^{(m)}{\big )}\qquad (4.14)$

s počiatočným vektorom $K^{(0)}.$

Podľa Banachovej vety o pevnom bode, pozri vetu 2.1, kapitola 2, existuje jedinečné riešenie, pevný bod ${\vec {K}}=F({\vec {K}})$, ak $F$ je samomapovanie a kontrahovanie. Pre funkciu $F:{\mathbb {R} }^{s}\to {\mathbb {R} }^{s}$ platí, že $F({\mathbb {R} }^{s})\subseteq {\mathbb {R} }^{s}$, t. j. vždy je samomapovanie.
Teraz skúmame, či $F$ je kontrakcia. Odhadneme Lipschitzovu spojitosť funkcie $f$ a trojuholníkovú nerovnosť pre absolútnu hodnotu v maximálnej norme: ${\begin{aligned}\|F({\vec {K}})^{1}-F({\vec {K}}^{2})\|_{\infty }=\max _{j=1,...,s}{\Big |}f{\Big (}t_{i}+hc_{j},\eta _{i}+h\sum _{\nu =1}^{s}a_{j\nu }k_{\nu }^{1}{\Big )}-f{\Big (}t_{i}+hc_{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}}$

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

Tvrdenie (4.13), (4.14) konverguje k tomuto pevnému bodu. Tvrdenie o p-násobnej spojitej diferencovateľnosti $k_{j}$ ponecháme bez dôkazu. ◻

---

'Poznámka o riešiteľnosti iRKV Remark on the solvability of the iRKV

1. Obmedzenie veľkosti kroku $h$ môže byť veľmi obmedzujúce pre veľké $L$ konštanty (t. j. pre $f$ s vysokými hodnotami derivácie ${\frac {\partial f}{\partial y}}\approx L$) 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 $k_{j}$, napríklad Newtonovej, sekantovej alebo kvázi-Newtonovej metódy. Tieto metódy konvergujú aj pre väčšie $h$, pretože majú superlineárnu rýchlosť konvergencie, ak je počiatočná hodnota zvolená priaznivo, v rámci tzv. konvergenčného intervalu.
2. Ak je funkcia $f$ len lokálne Lipschitzovo spojitá v $y$, t. j. len v okolí $K^{(0)}$, potom vyplývajú ďalšie obmedzenia na veľkosť kroku $h$, aby sa zaručila vlastnosť samomapovania.
3. Lipschitzova spojitosť procesnej funkcie $\Phi$ eRKV, ako aj iRKV vzhľadom na $y$ vyplýva z Lipschitzovej spojitosti $f$. To znamená, že iRKV s rádom konzistencie p sú tiež konvergentné s rádom konvergencie p. (pozri vetu 3.1)