View source for Obyčajné differenciálne rovnice/Úvod do Runge-Kutta metód

= Runge-Kutta metódy =

Metódy Runge-Kutta (RKV) sú špeciálne jednokrokové metódy, ktoré vďaka svojej štruktúre umožňujú vyšší stupeň konzistencie, a tým aj vyššiu presnosť numerického riešenia. Tieto metódy vyvinul nemecký matematik Wilhelm Kutta v roku 1901 na základe článku Carla Rungeho z roku 1895.

Ak sa pozrieme na rovnicu <math display="inline">y'(t)=f(t,y(t))</math>, vyšší rád konzistencie metódy Runge-Kutta je spôsobený vyšším počtom vyhodnotení funkcie <math display="inline">f</math> (pravá strana rovnice) v bodoch medzi <math display="inline">t_i</math> und <math display="inline">t_{i+1}=t_i+h</math> dosiahnuté. Medziľahlé body <math display="inline">t_i+ch</math> voláme <span>''Kroky''</span>, oder <span>''Body podpory''</span>, pričom <math display="inline">c\in [0,1]</math> a <math display="inline">h</math> je prírastok.

V doteraz študovaných ESV, ako sú Eulerova metóda, lichobežníkové pravidlo, pravidlo stredového bodu (v explicitnej alebo implicitnej forme), sa v každom kroku použilo jedno alebo dve vyhodnotenia <math display="inline">f</math> v bodoch <math display="inline">t_i, t_{i+1/2}</math> alebo <math display="inline">t_{i+1}</math>. V RKV sa počet bodov mriežky zvyšuje a ich poloha sa určuje primerane, aby sa dosiahol čo najvyšší poriadok konzistencie. Die bisher bekannten ESV können als die einfachsten Runge-Kutta Verfahren einordnet werden.


----
''''Definícia 4.1. ("Runge-Kutta metóda").

'''Nech <math display="inline">s\in {\mathbb N}</math> je počet stupňov/podporných bodov, <math display="inline">A\in {\mathbb R}^{s\times s}</math> je koeficientová matica so zápismi <math display="inline">(A)_{j,m}=:a_{jm}</math>, nech <math display="inline">\vec{b} \in {\mathbb R}^{s}</math> vektor váh a <math display="inline">\vec{c} \in {\mathbb R}^{s}</math> vektor výberových bodov.<br />
Metóda s pravidlom <math display="block">\begin{align}
\eta_0&= y_0, \\
k_j&= f\Big(t_i+h c_j , \eta_i+h\sum_{m=1}^{s}a_{jm}k_m\Big) \quad \mbox{für} \ j=1,\ldots,s, \qquad \qquad (4.1) \\
\eta_{i+1}&= \eta_i+ h\sum_{j=1}^{s} k_j b_j \quad \mbox{für} \ i=0,1,\ldots,N_h-1
\end{align}\qquad (4.2)</math> sa nazýva s-kroková Runge-Kutta metóda.
----
</div>
Metódy Runge-Kutta sa dajú špecifikovať aj schematicky v takzvanej <span>''Butcherovej tabuľke''</span>:<br />

[[file:Butcher 4.0 1.png|180px|left]] oder kurz [[file:Butcher 4.0 2.png|120px|center]]


<math display="inline">\vec{c}=
\begin{pmatrix}
c_1 \\ \vdots \\ c_s
\end{pmatrix},
 \quad \vec{b}^{\,T}=(b_1, \ldots b_s)</math>.



'''Príklad 4.1.''' 

Ohodnotenie funkcie <math display="inline">k_j</math> RKV pre <math display="inline">j=2</math> je <math>k_2=f\Big( (t_i+h c_2, \eta_i+h\sum_{m=1}^{s}a_{2m}k_m\Big )= f\Big( (t_i+h c_2, \eta_i+h \vec{a}_2\cdot \vec{k}\Big ),</math> 
kde <math>\vec{a}_2=(a_{21},\ldots , a_{2s})</math> je druhý riadok matice <math>A</math> a <math>\vec{k}_2=(k_{1},\ldots , k_{s})</math> <math>\quad \diamond.</math>
</div>
Nová hodnota numerického riešenia po jednom kroku RKV (nazývanom aj Runge-Kutta aktualizácia) sa vypočíta podľa (4.2) ako <math>\eta_{i+1}=\eta_i+ h\sum_{j=1}^{s} k_j b_j.</math>
Porovnanie tejto rovnice s Volterrovou integrálnou rovnicou (2.1) na intervale <math>(t_i,t_{i+1})</math>, <math>y(t_i+h)=y(t_i)+\int_{t_i}^{t_{i+1}} f(s, y(s)) ds</math>
vedie k nasledujúcim úvahám: Ak integrál <math display="inline">\int_{t_i} ^{t_{i+1}}f (s,y(s))ds</math> zmysluplne nahradíme súčtom takým, že <math>h\sum_{j=1}^{s} k_j b_j \approx \int_{t_i} ^{t_{i+1}}f (s,y(s))ds,</math> 
na výpočet novej hodnoty <math display="inline">f</math> sa použije kvadratúra <math display="inline">\eta_{i+1}</math>. Tu <math display="inline">k_j</math> sú <math display="inline">s</math> uzly tejto kvadratúry v bodoch mriežky <math display="inline">t_i+hc_{j}</math> (pozri (4.1)) a <math display="inline">b_j</math> sú váhy kvadratúry. Skonštruovať RKV teda znamená nájsť vhodnú kvadratúru integrálu <math display="inline">\int_{t_i}^{t_{i+1}}f</math>. Najjednoduchšie RKV (ide o jednokrokové metódy uvedené v kapitole 3) zahŕňajú aplikáciu kvadratúr, ako je pravidlo obdĺžnika, stredového bodu a lichobežníka pre integrál <math display="inline">\int_{t_i} ^{t_{i+1}}f (s,y(s))ds</math> (pozri poznámku 3.1 bod iii) a obrázky 3.1, 3.2, 3.3, 3.4). Butcherovu tabuľku možno interpretovať takto: Vektor <math display="inline">\vec{c}</math> opisuje body mriežky a vektor <math display="inline">\vec{b}</math> opisuje váhy príslušnej kvadratúry <math display="inline">f</math> na intervale <math display="inline">(t_i,t_{i+1})</math>. Die Matrix <math display="inline">A</math> spiegelt in gewissem Sinne die Differentialgleichung zurück. Dies kann wie folgt begründet werden:<br />
Nach der Definition der Runge-Kutta Verfahren, siehe (4. 1), und mithilfe der Differentiagleichung <math display="inline">y'=f(t,y)</math> kann darauf geschlossen werden, dass die <math display="inline">k_j</math> die Ableitungen der gesuchten Funktion an den Stützstellen <math display="inline">t_i+h c_j</math> approximieren, sodass mit <math display="inline">j=1, \ldots s</math> und <math display="inline">i</math> - fest, <math display="block">k_j \approx y'(t_i+h c_j)</math> 

platí. Keďže na výpočet <math display="inline">A</math> sa používa matica <math display="inline">k_j</math>, automaticky sa tým vyjadruje diferenciálna rovnica vo vyššie opísanom zmysle.

<div class="remark">

Na rozlíšenie explicitných a implicitných metód RK možno použiť maticu <math display="inline">A</math>:



* <span>'''Explicitná Runge-Kutta metóda (eRKV):'''</span><br />
Ak je matica <math display="inline">A</math> dolná trojuholníková matica, ide o explicitnú RKV. V tomto prípade sa v každom <math display="inline">k_1, \ldots, k_{j-1}</math> kroku na výpočet <math display="inline">t_i</math> použije iba predtým vypočítaná <math display="inline">k_j, j=1, \ldots s</math>. V tomto prípade môžete explicitne vypočítať <math display="inline">k_j</math> vložením ako <math display="block">k_j=f\Big(t_i+h c_j , \eta_i+h\sum_{m=1}^{j-1}a_{jm}k_m\Big).</math>


* <span>''''Implicitná Runge-Kutta metóda (iRKV):<br /> <span>'''Implicitná Runge-Kutta metóda (iRKV):<br />
'''
</span> Ak je matica <math display="inline">A</math> plne vyplnená matica, potom <math display="inline">k_j</math> všeobecne závisí od všetkých <math display="inline">k_{1}, \ldots, k_{s}</math> pre každé <math display="inline">j=1, \ldots s</math>. Výpočet <math display="inline">k_j</math> sa potom vykoná riešením (lineárnej alebo prípadne nelineárnej) sústavy rovníc. V tomto prípade je výpočet <math display="inline">k_j</math> jednoduchší alebo lacnejší, ak <math display="inline">A</math> je trojuholníková matica. V tomto prípade sa rozlišuje medzi
** DIRK-metóda:<span> ''’diagonálna implicitná metóda RK’''</span>:<br />
Matrix <math display="inline">A</math> je trojuholníková matica s <math display="inline">diag (A)\neq {\bf 0}</math>,
** SDIRK-metóda:<span> ''’jednoducho diagonálna implicitná metóda RK’''</span>:<br />
matica <math display="inline">A</math> je trojuholníková matica s <math display="inline">diag (A)=\lambda diag (I)\neq {\bf 0}, \ \lambda \in {\mathbb R}, \ I</math> ist eine Einheitsmatrix,
** SIRK-metóda <span> ''’jednoducho implicitný postup RK’''</span>:<br />
matica <math display="inline">A</math> je plne vyplnená matica, pričom <math display="inline">diag (A)=\lambda diag (I)</math> a horná trojuholníková matica tiež pozostáva z <math display="inline">\lambda </math>'s.


</div>
Teraz uvedieme niekoľko konkrétnych príkladov Runge-Kutta metód:<br />
Explicitná Eulerova metóda, <math display="inline">s=1</math>:<br />
<br />

[[file:Butcher 4.0 3.png|100px|left]]
<br />
<math display="block">\begin{aligned}
\\
k_1&= f(t_i+0.h,\eta_i+0.h k_1)=f(t_i,\eta_i)\\
\eta_{i+1}&=\eta_i+hk_1\equiv \eta_i+hf\underbrace{(t_i,\eta_i)}_{=k_1}
\end{aligned}</math><br />
Implicitná Eulerova metóda, <math display="inline">s=1</math>:<br />
<br />

[[file:Butcher 4.0 4.png|left|100px]]
<br />
<math display="block">\begin{aligned}
\\
k_1&= f(t_i+1.h,\eta_i+1.h k_1)\\
\eta_{i+1}&=\eta_i+hk_1\equiv % \eta_i+hf\underbrace{(t_i +h,\eta_i +hk_1)}_{=k_1}=
\eta_i+hf(t_i+h, \underbrace{\eta_i +hk_1}_{=\eta_{i+1}})
\end{aligned}</math><br />
Vylepšená Eulerova metóda (explicitné pravidlo stredového bodu), <math display="inline">s=2</math>:<br />
<br />
[[file:Butcher 4.0 5.png|left|180px]]
<br />
<math display="block">\begin{aligned}
k_1&= f(t_i,\eta_i)\\
k_2&= f\big(t_i+\frac{h}{2},\eta_i+\frac{h}{2} k_1\big)\\
\eta_{i+1}&=\eta_i+h (0.k_1+1.k_2)\\&\equiv \eta_i+hf\underbrace{\Big(t_i +\frac{h}{2},\eta_i +\frac{h}{2}\underbrace{f(t_i,\eta_i)}_{=k_1}\Big)}_{=k_2}
\end{aligned}</math>

Klasický Runge-Kutta postup, <math display="inline">s=4</math>:<br />
<br />
[[file:Butcher 4.0 6.png|left|220px]]
<br />
<math display="block">\begin{aligned}
k_1&= f(t_i,\eta_i)\\
k_2&= f\big(t_i+\frac{h}{2},\eta_i+\frac{h}{2} k_1\big)\\
k_3&= f\big(t_i+\frac1{2}h,\eta_i+\frac{h}{2}k_2\big)\\
k_4&= f\big(t_i+h,\eta_i+h k_3\big)\\
\eta_{i+1}&=\eta_i+h \Big(\frac{k_1}{6}+\frac{k_2}{3}+ \frac{k_3}{3}+\frac{k_4}{6}\Big )
\end{aligned}</math>

<math display="inline">3/8</math>- Pravidlo, <math display="inline">s=4</math>:<br />
<br />
[[file:Butcher 4.0 7.png|left|220px]]
<br />
<math display="block">\begin{aligned} 
k_1&= f(t_i,\eta_i)\\
k_2&= f\big(t_i+\frac{h}{3},\eta_i+\frac{h}{3} k_1\big)\\
k_3&= f\big(t_i+\frac{2}{3}h,\eta_i-\frac{h}{3} k_1+ h k_2\big)\\
k_4&= f\big(t_i+h,\eta_i+h k_1 -h k_2+h k_3\big)\\
\eta_{i+1}&=\eta_i+h \Big(\frac{k_1}{8}+\frac{3}{8}k_2+ \frac{3}{8}k_3+\frac{k_4}{8}\Big )
\end{aligned}</math> 


Ďalšie dve explicitné 3-stupňové RKV sú dané nasledujúcimi Butcherovými tabuľkami:<br />
<br />

Heunova metóda, <math display="inline">s=3</math> (1900): <math> \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad </math>3-stupňová eRKV
[[file:Butcher 4.0 8.png|250px|left]]

[[file:Butcher 4.0 9.png|250px|center]]

[[Category:SK]]