Obyčajné differenciálne rovnice/Odvodenie Runge-Kutta metód

Odvodenie Runge-Kutta metód

Runge-Kutta metódy sú konštruované s ohľadom na ich poradie konzistencie, t. j. matica koeficientov ${\textstyle A}$ a vektory ${\textstyle {\vec {b}},{\vec {c}}}$ sa hľadajú tak, aby lokálna chyba diskretizácie bola čo najmenšia.

Analogicky k definícii 3.2 lokálnej chyby ESV v kapitole 3 možno definovať aj lokálnu chybu skrátenia (chybu diskretizácie) a potom konzistenciu Runge-Kutta metódy.

---

''Definícia 4.2. ("Poradie konzistencie RKV")

Nech ${\textstyle f(t,y)}$ je dostatočne často spojito diferencovateľná funkcia. Runge-Kutta metóda má konzistentný poriadok $p$, ak $\|h\tau (t;h)\|=:\|\varepsilon (t;h)\|=\|y(t+h)-y(t)-h\phi (t,y,f,h)\|\leq Ch^{p+1},\ C\in {\mathbb {R} },$$\qquad (4.3)$

kde ${\textstyle \varepsilon (t;h)}$ opisuje rozdiel medzi presným riešením a numerickým riešením, počnúc presným riešením, v bode ${\textstyle t+h}$. ${\textstyle \|\cdot \|}$ označuje Euklidovu normu na ${\textstyle {\mathbb {R} }^{n}}$ alebo absolútnu hodnotu.

---

Aby sme preskúmali poriadok konzistencie všeobecného RKV, budeme teraz uvažovať lokálnu diskretizáciu chyby ${\textstyle \tau (t;h)={\frac {1}{h}}(y(t+h)-y(t))-\phi (t,y,f,h)}$. Pre vopred daný poriadok konzistencie ${\textstyle p}$ použijeme Taylorov rad od ${\textstyle y(t+h)}$ a ${\textstyle \phi (t,y,f,h)}$ až po prvok s ${\textstyle h^{p}}$ v ${\textstyle \tau }$.

Prvý príklad demonštruje maximálny rád konzistencie, ktorý môže dvojstupňová explicitná Runge-Kutta metóda vo všeobecnosti dosiahnuť. Konvergencia a rád konvergencie RKV sa určuje pomocou definície 3.5 a kritéria konvergencie pre všeobecné jednostupňové metódy ( veta 3.1, t. j. v podstate dôkazom Lipschitzovej konzistencie funkcie metódy ${\textstyle \phi }$).

Príklad 4.2. Určte 2-stupňovú explicitnú Rungeho-Kuttovu metódu pre počiatočnú hodnotu úlohy (1.6) s ${\textstyle c_{1}=0}$.
. Keďže ide o eRKV, matica ${\textstyle A}$ je dolná trojuholníková matica. Preto ${\textstyle a_{11}=a_{12}=a_{22}=0}$ a treba určiť len štyri neznáme ${\textstyle a_{21},\ b_{1},\ b_{2}}$ a ${\textstyle c_{2}}$:

Predpokladajme, že ${\textstyle f\in C^{2}([0,T]\times D)}$ a teda ${\textstyle y\in C^{3}[0,T]}$. Určíme poradie konzistencie pomocou Taylorovho radu okolo ${\textstyle h=0}$:

• Taylorov rozvoj ${\textstyle y(t+h)}$: Podobne ako v príklade (3.5) dostaneme $$y(t+h)=y(t)+hy'(t)+{\frac {h^{2}}{2}}y''(t)+{\frac {h^{3}}{3!}}y'''(t)+{\frac {h^{4}}{4!}}y^{(IV)}(\theta ),\ \theta \in (t,t+h).$$ Použitím (3.14) a (3.15) tak dostaneme pre prvú časť lokálnej chyby
  

$${\begin{aligned}{\frac {y(t+h)-y(t)}{h}}&=y'(t)+{\frac {h}{2}}y''(t)+{\frac {h^{2}}{6}}y'''(t)+{\cal {O}}(h^{3})\\&=f(t,y(t))+{\frac {h}{2}}{\big (}f_{t}+ff_{y}{\big )}(t,y(t))\\&\quad +{\frac {h^{2}}{6}}{\big (}f_{tt}+2f_{ty}f+f_{y}f_{t}+f_{yy}f^{2}+(f_{y})^{2}f{\big )}(t,y(t))+{\cal {O}}(h^{3})\end{aligned}}$$

• Aplikujte Taylorov rozvoj v procesnej funkcii ${\textstyle \phi (t,y,h,f)}$: $${\begin{aligned}\phi (t,y,h,f)&=b_{1}k_{1}+b_{2}k_{2}=b_{1}f(t,y(t))+b_{2}f{\Big (}t+c_{2}h,y(t)+ha_{21}f{\big (}t,y(t){\big )}{\Big )}\\&{\stackrel {Taylor}{=}}b_{1}f(t,y)+b_{2}{\Big [}f(t,y)+{\big (}f_{t}(t,y)c_{2}h+f_{y}(t,y)a_{21}hf(t,y){\big )}\\&\quad +{\frac {1}{2!}}{\Big (}f_{tt}(t,y)c_{2}^{2}h^{2}+2f_{ty}(t,y)c_{2}h^{2}a_{21}f(t,y)+f_{yy}(t,y)h^{2}a_{21}^{2}f^{2}(t,y){\Big )}{\Big ]}+{\cal {O}}(h^{3})\end{aligned}}$$

Po dosadení Taylorovho radu (rozdielového kvocientu ${\textstyle y(t)}$ a v ${\textstyle \phi }$) do výrazu ${\textstyle \tau (t;h)}$ a po dosadení príslušných mocnín ${\textstyle h}$ dostaneme pre lokálnu chybu $${\begin{aligned}\tau (t;h)&=(1-b_{1}-b_{2})f(t,y)+{\frac {h}{2}}{\big (}{\big (}1-2c_{2}b_{2})f_{t}(t,y)+{\big (}1-2a_{21}b_{2})ff_{y}(t,y){\big )}\\&+{\frac {h^{2}}{6}}{\Big (}(1-3c_{2}^{2}b_{2})f_{tt}(t,y)+2(1-3c_{2}a_{21}b_{2})f_{ty}f(t,y)+(1-3a_{21}^{2}b_{2})f_{yy}f^{2}(t,y)\\&+(f_{y})^{2}f(t,y)+f_{t}f_{y}(t,y){\Big )}+{\cal {O}}(h^{3}).\end{aligned}}$$

Vhodnou voľbou koeficientov ${\textstyle a_{21},\ b_{1},\ b_{2}}$ a ${\textstyle c_{2}}$ dostaneme výrazy pre mocniny ${\textstyle h^{0},\ h^{1}}$ a čiastočne pri ${\textstyle h^{2}}$ zaniknú v diskretizácii chyby ${\textstyle \tau }$. Zistili sme nasledovné:

• Dôsledné eRKV, t. j. s ${\textstyle \tau \to 0}$ pre ${\textstyle h\to 0}$ vedie k voľbe ${\textstyle b_{1},b_{2}}$ s ${\textstyle b_{1}+b_{2}=1}$.
• Pre posledné dva členy pri ${\textstyle h^{2}}$ všeobecne platí, že ${\textstyle (f_{y})^{2}f(t,y)\neq 0,\ f_{t}f_{y}(t,y)\neq 0}$, preto tretím rádom konzistencie nie je možné touto metódou dosiahnuť.

Ukázali sme, že maximálny rád konzistencie pre explicitnú RKV druhej úrovne je dva. Pre prvý alebo druhý rád konzistencie musia byť pre koeficienty metódy splnené nasledujúce podmienky: $${\begin{aligned}&&\ \ \ b_{1}+b_{2}=1\quad \}\quad {\mbox{Konzistencia 1. rádu}}\\&&\left.{\begin{matrix}1-2c_{2}b_{2}&=0\\1-2a_{21}b_{2}&=0\end{matrix}}\quad \right\}\quad {\mbox{ 2. rádu}}.\end{aligned}}$$ Táto sústava troch rovníc obsahuje štyri neznáme, takže existuje nespočetné množstvo možností pre procesné koeficienty 2-stupňového eRKV druhého rádu konzistencie. Ak ako parameter vyberiete ${\textstyle b_{2}}$, dostanete $$b_{1}=1-b_{2},\quad c_{2}=a_{21}={\frac {1}{2b_{2}}}.$$

1. Voľba ${\textstyle b_{2}=1}$ vedie k explicitnému pravidlu stredového bodu (tzv. vylepšená Eulerova metóda).
2. V prípade ${\textstyle b_{2}={\frac {1}{2}}}$ dostaneme explicitné lichobežníkové pravidlo (tzv. Heunova metóda 2. rádu).
3. Pri voľbe ${\textstyle b_{2}={\frac {3}{4}}}$ si rýchlo uvedomíme, že dass für die ersten drei Terme bei ${\textstyle h^{2}}$ mit den Koeffizienten (da ${\textstyle c_{2}=a_{21}}$) $$1-3c_{2}^{2}b_{2}=1-3c_{2}a_{21}b_{2}=1-3a_{21}^{2}b_{2}\equiv 0$$ gilt. To znamená, že hlavný chybový koeficient je obsiahnutý v lokálnej diskretizovanej chybe tejto metódy (tu je to koeficient pri ${\textstyle h^{2}}$), a preto je aj chyba minimálna. Platí tu $$\tau (t,h)={\frac {h^{2}}{6}}{\Big (}(f_{y})^{2}f(t,y)+f_{t}f_{y}(t,y){\Big )}+{\cal {O}}(h^{3}){\stackrel {}{=}}{\frac {h^{2}}{6}}{\Big (}(f_{y})^{2}f(\theta ,y(\theta ))+f_{t}f_{y}(\theta ,y(\theta )){\Big )}$$ für ein ${\textstyle \theta \in (t,t+h)}$. Podľa predpokladov sú derivácie ${\textstyle f}$ rovnomerne obmedzené na ${\textstyle [0,t]\times D}$ a týmto dostávame optimálnu - v zmysle najmenšej lokálnej chyby - metódu druhého rádu konzistencie s $$\tau (t,h)\leq Ch^{2},\quad {\mbox{kde}}\ C:=\max _{t}{\frac {|f_{t}f_{y}|+|f(f_{y})^{2}|}{6}}.$$

S cieľom zaručiť Rád konvergencie 2 dvojstupňového eRKV, Lipschitzova spojitosť funkcie procesu vzhľadom na ${\textstyle y}$ byť splnené. Nasledujúci výpočet dokazuje, že je to dôsledok Lipschitzovej spojitosti ${\textstyle f}$. Toto tvrdenie sa dá zovšeobecniť. Lipschitzovu spojitosť funkcie metódy ${\textstyle \phi }$ možno odvodiť z ${\textstyle L}$ spojitosti ${\textstyle f}$ pre všetky explicitné a implicitné Runge-Kutta metódy.

Predpokladajme, že ${\textstyle m=1}$ a ${\textstyle \eta _{i}^{(1)\ (2)}}$ sú dve numerické riešenia AWA (1.6) v ${\textstyle t_{i}}$.
Pre rozdiel v procesnej funkcii analyzovanej dvojstupňovej eRKV platí: $$\diamond {\begin{aligned}&&k_{1}=f(t_{i},\eta _{i}^{(r)}),\ r=1,2\\&&k_{2}=f{\big (}t_{i}+c_{2}{h},\eta _{i}^{(r)}+a_{21}hk_{1}{\big )}\quad i=0,1\ldots N_{h}-1\\&&{\big |}\Phi (t_{i},\eta _{i}^{(1)},\ldots )-\Phi (t,\eta _{i}^{(2)},\ldots ){\big |}={\Big |}b_{1}f(t_{i},\eta _{i}^{(1)})+b_{2}f(t_{i}+c_{2}h,\eta _{i}^{(1)}+a_{21}h\underbrace {f(t_{i},\eta _{i}^{(1)})} _{k_{1}})\\&&\qquad \qquad \qquad \qquad \qquad \qquad \qquad -b_{1}f(t_{i},\eta _{i}^{(2)})-b_{2}f(t_{i}+c_{2}h,\eta _{i}^{(2)}+a_{21}hf\underbrace {(t_{i},\eta _{i}^{(2)})} _{k_{1}}){\Big |}\\&&\qquad \qquad (f(t,\eta )\ {\mbox{-L-stetig in }}\eta \ {\mbox{mit Konstante }}L)\\&&\qquad \leq |b_{1}|L|\eta _{i}^{(1)}-\eta _{i}^{(2)}|+|b_{2}|L{\Big |}\eta _{i}^{(1)}+a_{21}hf(t_{i},\eta _{i}^{(1)})-\eta _{i}^{(2)}-a_{21}hf(t_{i},\eta _{i}^{(2)}){\Big |}\\&&\qquad \leq (|b_{1}|+|b_{2}|)L|\eta _{i}^{(1)}-\eta _{i}^{(2)}|+|b_{2}a_{21}|Lh\underbrace {|f(t_{i},\eta _{i}^{(1)})-f(t_{i},\eta _{i}^{(2)})|} _{f\ L-stetig\ in\ \eta }\\&&\qquad \qquad (f(t,\eta )\ {\mbox{ist L-stetig in }}\eta )\\&&\qquad \leq (|b_{1}|+|b_{2}|)L|\eta _{i}^{(1)}-\eta _{i}^{(2)}|+|b_{2}a_{21}|LhL|\eta _{i}^{(1)}-\eta _{i}^{(2)})|\\&&\qquad \leq {\Big [}\underbrace {(|b_{1}|+|b_{2}|)L+|b_{2}a_{21}|hL^{2}} _{:=M}{\Big ]}|\eta _{i}^{(1)}-\eta _{i}^{(2)})|=M|\eta _{i}^{(1)}-\eta _{i}^{(2)})|,\end{aligned}}$$, kde bola pre absolútnu hodnotu niekoľkokrát použitá trojuholníková nerovnosť.

Vo výpočte vyššie sme ukázali, že procesná funkcia ${\textstyle \phi }$ analyzovaného eRKV je Lipschitzovo spojitá vzhľadom na ${\textstyle \eta }$, kde Lipschitzova konštanta ${\textstyle M=(|b_{1}|+|b_{2}|)L+|b_{2}a_{21}|hL^{2}<\infty }$ je odvodená od ${\textstyle L}$ konštanty funkcie ${\textstyle f}$. Explicitná 2-kroková Runge-Kutta metóda je teda konvergentná s rádom konvergencie 2 a vyšší rád konvergencie sa nedá dosiahnuť. ${\textstyle \diamond }$ V predchádzajúcom príklade sme videli, že 2-krokovou explicitnou Runge-Kutta metódou možno dosiahnuť druhý rád konzistencie a konvergencie. Táto analógia však všeobecne neplatí pre všetky eRKV. Neplatí, že rád konzistencie ${\textstyle s}$ možno dosiahnuť pomocou ${\textstyle s}$ úrovní. Na to sa neskôr odvoláme pomocou vety. V prípade implicitného RKV je situácia iná, pretože matica ${\textstyle A}$ môže byť plne naplnená, a teda existuje niekoľko možností, ako koeficientmi postupu dosiahnuť vyšší rád konzistencie.

Poznámka 4.2.

Pre koeficienty eRKV platí nasledovné:

1. Poradie konzistencie ${\textstyle p}$ je všeobecne opísané ${\textstyle s\geq p}$ možno dosiahnuť úrovne.
2. Pri pevnom poradí konzistencie existujú možnosti výberu koeficientov ${\textstyle A,{\vec {b}},{\vec {c}}}$. To znamená, že existuje niekoľko eRKV s rovnakým poradím konzistencie alebo rovnakým počtom úrovní.

Podobne ako v príklade 4.2 možno odvodiť nasledujúcu sústavu rovníc pre koeficienty eRKV s ${\textstyle s=4}$ úrovňami a ${\textstyle c_{1}=0}$, ${\begin{aligned}b_{1}+b_{2}+b_{3}+b_{4}&=1\quad \}\quad {\mbox{Konzistencia 1. rádu,}}\\c_{2}b_{2}+c_{3}b_{3}+c_{4}b_{4}&={\frac {1}{2}}\quad \}\quad \quad {\mbox{ 2. poradie,}}\\&\left.{\begin{matrix}c_{2}^{2}b_{2}+c_{3}^{2}b_{3}&={\frac {1}{3}}\\b_{3}c_{2}a_{32}+b_{4}c_{2}a_{42}+b_{4}c_{3}a_{43}&={\frac {1}{6}}\end{matrix}}\quad \right\}\quad \quad {\mbox{ 3. rádu}}\end{aligned}}$ $\qquad (4.4)$