Runge–Kutta-módszer

A Runge–Kutta-módszerek családja a differenciálegyenletek numerikus analízisének széles körben ismert és alkalmazott közelítő eljárása, amelyet Carl Runge és Martin Kutta német matematikusok dolgoztak ki 1900 körül.

A közönséges negyedrendű Runge–Kutta-módszer

A Runge–Kutta-módszercsalád közönséges negyedrendű tagja annyira elterjedten használatos, hogy egyszerűen csak „a Runge–Kutta-módszer”-ként hivatkoznak rá. E módszer az alábbi kezdetiérték-probléma egy negyedrendű közelítő megoldását adja.

$y'(t) = f(\;t\;,\;y(t)\;) \qquad y(t_0) = y_0$

Azaz tetszőlegesen rögzített pozitív valós, tipikus esetben kicsiny $h$ lépésköz esetén az $n$-edik lépésben a kezdetiérték-probléma $y(t)$ megoldásának egy olyan

$y(t_n) \;\approx\; y_n$

közelítését adja a

$t_n = t_0 + n\cdot h$

helyen, amely közelítés hibája negyedrendű. E negyedrendűség azt jelenti, hogy a választott lépésköz zsugorításakor annak negyedik hatványával zsugorodik a hibára adott felső becslés. Például a lépésköz harmadolása árán, azaz nagyjából háromszor annyi számolás árán a hibakorlát $(1/3)^4=1/81$-szeresre zsugorodik.

A $h$ lépésköz rögzítése után az alábbi, $n$-szerinti rekurziós lépésekkel kapjuk az $y(t)$ megoldásfüggvény közelítését.

$\begin{align} y_{n+1} &= y_n + h\cdot{a_n + 2\cdot b_n + 2\cdot c_n + d_n\over6} \\ \text{ahol} \\ a_n &= f(\;t_n\;,\;y_n\;) \\ b_n &= f(\;t_n + \tfrac{1}{2}h\;,\;y_n + \tfrac{1}{2}h\cdot a_n\;) \\ c_n &= f(\;t_n + \tfrac{1}{2}h\;,\;y_n + \tfrac{1}{2}h\cdot b_n\;) \\ d_n &= f(\;t_n + h\;,\;y_n + h\cdot c_n\;) \end{align}$

Így, a $t_{n+1}$ helyhez tartózó $y_{n+1}$ közelítőérték egyenlő a $t_n$ helyhez tartozó $y_n$ közelítőérték, plusz a becsült meredekség szorozva az intervallum $h$ hosszával. A meredekség becslése egy, most nem részletezett matematikai megfontolás alapján súlyozott középértéke az alábbi négy meredekségi becslésnek:

$\begin{align} a_n &= f(\;t_n\;,\;y_n\;) \\ &\approx f(\;t_n\;,\;y(t_n)\;) \\ &= y'(t_n) \\ b_n &= f(\;t_n + \tfrac{1}{2}h\;,\;y_n + \tfrac{1}{2}h\cdot a_n\;) \\ &\approx f(\;t_n + \tfrac{1}{2}h\;,\;y(t_n) + \tfrac{1}{2}h\cdot y'(t_n)\;) \\ &\approx f(\;t_n + \tfrac{1}{2}h\;,\;y(t_n+\tfrac{1}{2}h)\;) \\ &= y'(t_n+\tfrac{1}{2}h) \\ c_n &= f(\;t_n + \tfrac{1}{2}h\;,\;y_n + \tfrac{1}{2}h\cdot b_n\;) \\ &\approx f(\;t_n + \tfrac{1}{2}h\;,\;y(t_n) + \tfrac{1}{2}h\cdot y'(t_n+\tfrac{1}{2}h)\;) \\ &\approx f(\;t_n + \tfrac{1}{2}h\;,\;y(t_n+\tfrac{1}{2}h)\;) \\ &= y'(t_n+\tfrac{1}{2}h) \\ d_n &= f(\;t_n + h\;,\;y_n + h\cdot c_n\;) \\ &\approx f(\;t_n + h\;,\;y(t_n) + h\cdot y'(t_n+\tfrac{1}{2}h)\;) \\ &\approx f(\;t_n + h\;,\;y(t_n+h)\;) \\ &= y'(t_n+h) \end{align}$

E négy közelítés átlagolásánál a $t_n$ és $t_{n+1}$ szélekhez képest a $t_{n+0.5}$ felezőnél dupla súlyt alkalmazunk.

$\begin{align} \mbox{átlagos meredekség} &\;\approx\; {y'(t_n) + 2\cdot y'(t_n+\tfrac{1}{2}h) + 2\cdot y'(t_n+\tfrac{1}{2}h) + y'(t_n+h)\over6} \\ &\;\approx\; {1\cdot a_n + 2\cdot b_n + 2\cdot c_n + 1\cdot d_n\over6} \end{align}$

Mivel a megoldásfüggvény felvett értékeire csak additív műveleteket és a skalárral való szorzás műveletét alkalmazzuk, lényegében ezért a módszer nem csak skalár értékű megoldásfüggvények, hanem vektor értékűek esetén is alkalmazható. Ilyen például a Schrödinger-differenciálegyenlet, amelynek Hamilton-operátorát használjuk a fenti szerepében.

Explicit Runge–Kutta-módszer

A fent említett Runge–Kutta-módszercsalád általánosítása az Explicit Runge–Kutta-módszer, amit a

$y_{n+1} = y_n + h\sum_{i=1}^s b_i k_i,$

ad meg, ahol

$k_1 = f(t_n, y_n), \,$

$k_2 = f(t_n+c_2h, y_n+a_{21}hk_1), \,$

$k_3 = f(t_n+c_3h, y_n+a_{31}hk_1+a_{32}hk_2), \,$

$\vdots$

$k_s = f(t_n+c_sh, y_n+a_{s1}hk_1+a_{s2}hk_2+\cdots+a_{s,s-1}hk_{s-1}).$

(Megjegyzés: a fenti egyenletek különböző formákban is megjelenhetnek egyeb forrásokból, de jelentésük azonos).

Ahhoz hogy meghatározzunk egy bizonyos módszert,kell egy s egész változó (a szakaszok száma), illetve az a_ij (1 ≤ j < i ≤ s), b_i (i = 1, 2, ..., s) és a c_i (i = 2, 3, ..., s) együtthatók. Ezek az adatok általában egy mnemonik eszközbe kerulnek be, ami a Butcher táblájaként ismert (Butcher tableau, John C. Butcher neve után):

	0
	$c_2$	$a_{21}$
	$c_3$	$a_{31}$	$a_{32}$
	$\vdots$	$\vdots$		$\ddots$
	$c_s$	$a_{s1}$	$a_{s2}$	$\cdots$	$a_{s,s-1}$
		$b_1$	$b_2$	$\cdots$	$b_{s-1}$	$b_s$

A Runge-Kutta-módszer konzisztens, ha

$\sum_{j=1}^{i-1} a_{ij} = c_i\ \mathrm{ha}\ i=2, \ldots, s.$

Ugyanakkor vannak más követelmények, ha azt szeretnénk, hogy a módszernek legyen p fokszáma, így a kerekítési hiba O(h^p+1) lesz. Például egy kétlépcsős módszer másodrendű ha b₁ + b₂ = 1, b₂c₂ = 1/2, és b₂a₂₁ = 1/2.

Példák

A RK4 szerkezete a következő táblázat szerint értelmezhető:

	0
	1/2	1/2
	1/2	0	1/2
	1	0	0	1
		1/6	1/3	1/3	1/6

Habár a legegyszerűbb Runga-Kutta-módszer az Euler-módszer maga, amelynek $y_{n+1} = y_n + hf(t_n,y_n)$ képlet ad meg. Ez az egyetlen explicit Runge-Kutta-módszer egy lépcsővel.

	0
		1

Egy példa a másodrendű két lépcsős módszerre a középponti módszer:

$y_{n+1} = y_n + hf\left(t_n+\tfrac{1}{2}h,y_n+\tfrac{1}{2}hf(t_n, y_n)\right).$

Az erre megfelelő táblázat:

	0
	1/2	1/2
		0	1

Megjegyzendő, a középponti módszer nem a legmegfelelőbb RK-módszer. A Heun-módszer egy alternatív megoldást kínál,ahol a tábla 1/2 ei 1-re cserélődnek, és a b sora pedig [1/2,1/2] Ha valaki minimalizálni akarja a kerekítés által keletkezett hibákat, akkor az alábbi módszert kell használnia (Atkinson p. 423). Más fontos módszerek: Fehlberg, Cash-Karp és Dormand-Prince.

Használat

A következõ egy példa a kétlépcsős explicit Runge-Kutta módszerre:

	0
	2/3	2/3
		1/4	3/4

a kezdeti értéket meghatározó képlet

$y' = \tan(y)+1,\quad y(1)=1,\ t\in [1, 1.1]$

a h=0,025 lépésköz

A fenti táblát meghatározó egyenrangú számítások:

$k_1 = y_n$

$k_2 = y_n + \tfrac{2}{3}hf(t_n, k_1)$

$y_{n+1} = y_n + h\left(\tfrac{1}{4}f(t_n,k_1)+\tfrac{3}{4}f(t_n+\tfrac{2}{3}h,k_2)\right)$

$t_0=1$
	$y_0=1$
$t_1=1.025$
	$k_1 = y_0 = 1$	$f(t_0,k_1)=2.557407725$	$k_2 = y_0 + 2/3hf(t_0,k_1) = 1.042623462$
	$y_1=y_0+h(1/4*f(t_0, k_1) + 3/4*f(t_0+2/3h,k_2))=1.066869388$
$t_2=1.05$
	$k_1 = y_1 = 1.066869388$	$f(t_1,k_1)=2.813524695$	$k_2 = y_1 + 2/3hf(t_1,k_1) = 1.113761467$
	$y_2=y_1+h(1/4*f(t_1, k_1) + 3/4*f(t_1+2/3h,k_2))=1.141332181$
$t_3=1.075$
	$k_1 = y_2 = 1.141332181$	$f(t_2,k_1)=3.183536647$	$k_2 = y_2 + 2/3hf(t_2,k_1) = 1.194391125$
	$y_3=y_2+h(1/4*f(t_2, k_1) + 3/4*f(t_2+2/3h,k_2))=1.227417567$
$t_4=1.1$
	$k_1 = y_3 = 1.227417567$	$f(t_3,k_1)=3.796866512$	$k_2 = y_3 + 2/3hf(t_3,k_1) = 1.290698676$
	$y_4=y_3+h(1/4*f(t_3, k_1) + 3/4*f(t_3+2/3h,k_2))=1.335079087$

Az aláhúzott kifejezések jelzik a számszerû megoldásokat.Megjegyzendõ, az $y_i$s újraszámolása érdekében $f(t_i,k_1)$-et használtunk.

Adaptív Runge–Kutta-módszer

Az adaptív módszer arra volt tervezve,hogy megadja a becsült helyi kerekítési hibat minden egyes RK lépésben. Ezt úgy valósitotta meg h két módszert tartalmaz a táblázat, egyet p-ed rendűvel es egyet p-1-ed rendűvel.

A kisebb rendű lépés adott:

$y^*_{n+1} = y_n + h\sum_{i=1}^s b^*_i k_i,$

ahol, a $k_i$ megegyezik a magasabb rendű módszerrel. Ekkor a hiba:

$e_{n+1} = y_{n+1} - y^*_{n+1} = h\sum_{i=1}^s (b_i - b^*_i) k_i,$

ami $O(h^p)$. A Butcher-táblázat erre a módszerre ki van bővítve, így megadja a $b^*_i$ értékeit:

	0
	$c_2$	$a_{21}$
	$c_3$	$a_{31}$	$a_{32}$
	$\vdots$	$\vdots$		$\ddots$
	$c_s$	$a_{s1}$	$a_{s2}$	$\cdots$	$a_{s,s-1}$
		$b_1$	$b_2$	$\cdots$	$b_{s-1}$	$b_s$
		$b^*_1$	$b^*_2$	$\cdots$	$b^*_{s-1}$	$b^*_s$

A RK Fehlberg módszernek a két rendszere az ötöd- es negyedrendű. Ennek a kibővített Butcher-táblázata a következő:

	0
	1/4	1/4
	3/8	3/32	9/32
	12/13	1932/2197	−7200/2197	7296/2197
	1	439/216	−8	3680/513	-845/4104
	1/2	−8/27	2	−3544/2565	1859/4104	−11/40
		16/135	0	6656/12825	28561/56430	−9/50	2/55
		25/216	0	1408/2565	2197/4104	−1/5	0

Habár a legegyszerűbb adaptiv RK módszer a másodrendű Heun módszert és az elsőrendű Euler módszert foglalja magába. Ennek a kibővített Butcher-táblázata:

	0
	1	1
		1/2	1/2
		1	0

A hiba eredményét a lépték határozza meg.

Más adaptiv Runge-Kutta-módszerek a Bogacki-Shampine-módszer (harmad-és másodrendű), a Cash-Karp-módszer és a Dormand-Prince-módszer (mindkettő ötöd- és negyedrendű).

Implicit Runge-Kutta-módszer

Az implicit módszerek jóval általánosabbak az expliciteknél. Az eltérés a Butcher-táblázatnál merül fel: az implicit módszernél, a mátrix a_ij együtthatója nem feltétlenül alacsony háromszög:

$\begin{array}{c|cccc} c_1 & a_{11} & a_{12}& \dots & a_{1s}\\ c_2 & a_{21} & a_{22}& \dots & a_{2s}\\ \vdots & \vdots & \vdots& \ddots& \vdots\\ c_s & a_{s1} & a_{s2}& \dots & a_{ss} \\ \hline & b_1 & b_2 & \dots & b_s\\ \end{array} = \begin{array}{c|c} \mathbf{c}& A\\ \hline & \mathbf{b^T} \\ \end{array}$

A megközelítő megoldás a kezdeti érték problémára utal az együtthatók nagyobb számára.

$y_{n+1} = y_n + h \sum_{i=1}^s b_i k_i\,$

$k_i = f\left(t_n + c_i h, y_n + h \sum_{j = 1}^s a_{ij} k_j\right).$

Az $a_{ij}$ mátrix telítettsége miatt, az egyes $k_i$ becslése jelentékeny mértékben fog függeni az $f(t, y)$ függvénytől. A nehézségek ellenére, az implicit módszerek nagy jelentőséggel birnak az erősen stabil állapotuk miatt, ami különösen fontos a parciális differenciál egyenletek megoldásában. A legegyszerűbb példa egy implicit Runge-Kutta-módszerre fordított Euler-módszer:

$y_{n + 1} = y_n + h f(t_n + h, y_{n + 1})\,$

Ennek táblázata egyszerű:

$\begin{array}{c|c} 1 & 1 \\ \hline & 1 \\ \end{array}$

Még az egyszerűbb implicit módszer alkalmazása is bonyolulttá válhat, ami a ki kifejezésből látszik is:

$k_1 = f(t_n + c_1 h, y_n + h a_{11} k_1) \rightarrow k_1 = f(t_n + h, y_n + h k_1).$

Ebben az esetben, a fenti bonyolult kifejezés leegyszerűsíthető a következő képpen:

$y_{n+1} = y_n + h k_1 \rightarrow h k_1 = y_{n+1} - y_n\,$

így hát

$k_1 = f(t_n + h, y_n + y_{n+1} - y_n) = f(t_n + h, y_{n+1}).\,$

amiből következik, hogy:

$y_{n + 1} = y_n + h f(t_n + h, y_{n + 1})\,$

Noha egyszerűbb, mint a módosítások előtti „nyers” kifejezés, ez egy implicit összefüggés, tehát a konkrét megoldás problémafüggő. A többlépéses implicit módszert sikeresen használják a kutatók. Az egyensúly összeállítása (kombinációja), a magasabb rendpontosság kevesebb lépésben és a léphetőség (stepping) egyedül az előző értékben válik érdekessé, ugyanakkor a bonyolult példa jellegzetes kivitelezése, és a tény, hogy ki ismételt megközelítései mutatják hogy ezek hasonlóak (ugyanazok).