Runge–Kutta-módszer

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

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.

${\displaystyle 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 ${\displaystyle h}$ lépésköz esetén az ${\displaystyle n}$-edik lépésben a kezdetiérték-probléma ${\displaystyle y(t)}$ megoldásának egy olyan

${\displaystyle y(t_{n})\;\approx \;y_{n}}$

közelítését adja a

${\displaystyle 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 ${\displaystyle (1/3)^{4}=1/81}$-szeresre zsugorodik.

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

${\displaystyle {\begin{aligned}y_{n+1}&=y_{n}+h\cdot {a_{n}+2\cdot b_{n}+2\cdot c_{n}+d_{n} \over 6}\\{\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{aligned}}}$

Így, a ${\displaystyle t_{n+1}}$ helyhez tartozó ${\displaystyle y_{n+1}}$ közelítőérték egyenlő a ${\displaystyle t_{n}}$ helyhez tartozó ${\displaystyle y_{n}}$ közelítőérték, plusz a becsült meredekség szorozva az intervallum ${\displaystyle 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:

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

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

${\displaystyle {\begin{aligned}{\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) \over 6}\\&\;\approx \;{1\cdot a_{n}+2\cdot b_{n}+2\cdot c_{n}+1\cdot d_{n} \over 6}\end{aligned}}}$

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

${\displaystyle y_{n+1}=y_{n}+h\sum _{i=1}^{s}b_{i}k_{i},}$

ad meg, ahol

${\displaystyle k_{1}=f(t_{n},y_{n}),\,}$

${\displaystyle k_{2}=f(t_{n}+c_{2}h,y_{n}+a_{21}hk_{1}),\,}$

${\displaystyle k_{3}=f(t_{n}+c_{3}h,y_{n}+a_{31}hk_{1}+a_{32}hk_{2}),\,}$

${\displaystyle \vdots }$

${\displaystyle k_{s}=f(t_{n}+c_{s}h,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 egyéb 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 kerülnek be, ami a Butcher táblájaként ismert (Butcher tableau, John C. Butcher neve után):

	0
	${\displaystyle c_{2}}$	${\displaystyle a_{21}}$
	${\displaystyle c_{3}}$	${\displaystyle a_{31}}$	${\displaystyle a_{32}}$
	${\displaystyle \vdots }$	${\displaystyle \vdots }$		${\displaystyle \ddots }$
	${\displaystyle c_{s}}$	${\displaystyle a_{s1}}$	${\displaystyle a_{s2}}$	${\displaystyle \cdots }$	${\displaystyle a_{s,s-1}}$
		${\displaystyle b_{1}}$	${\displaystyle b_{2}}$	${\displaystyle \cdots }$	${\displaystyle b_{s-1}}$	${\displaystyle b_{s}}$

A Runge–Kutta-módszer konzisztens, ha

${\displaystyle \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ő:

Habár a legegyszerűbb Runga-Kutta-módszer az Euler-módszer maga, amelynek ${\displaystyle 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.

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

${\displaystyle 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:

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:

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

${\displaystyle 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:

${\displaystyle k_{1}=y_{n}}$

${\displaystyle k_{2}=y_{n}+{\tfrac {2}{3}}hf(t_{n},k_{1})}$

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

${\displaystyle t_{0}=1}$
	${\displaystyle y_{0}=1}$
${\displaystyle t_{1}=1.025}$
	${\displaystyle k_{1}=y_{0}=1}$	${\displaystyle f(t_{0},k_{1})=2.557407725}$	${\displaystyle k_{2}=y_{0}+2/3hf(t_{0},k_{1})=1.042623462}$
	${\displaystyle y_{1}=y_{0}+h(1/4*f(t_{0},k_{1})+3/4*f(t_{0}+2/3h,k_{2}))=1.066869388}$
${\displaystyle t_{2}=1.05}$
	${\displaystyle k_{1}=y_{1}=1.066869388}$	${\displaystyle f(t_{1},k_{1})=2.813524695}$	${\displaystyle k_{2}=y_{1}+2/3hf(t_{1},k_{1})=1.113761467}$
	${\displaystyle y_{2}=y_{1}+h(1/4*f(t_{1},k_{1})+3/4*f(t_{1}+2/3h,k_{2}))=1.141332181}$
${\displaystyle t_{3}=1.075}$
	${\displaystyle k_{1}=y_{2}=1.141332181}$	${\displaystyle f(t_{2},k_{1})=3.183536647}$	${\displaystyle k_{2}=y_{2}+2/3hf(t_{2},k_{1})=1.194391125}$
	${\displaystyle y_{3}=y_{2}+h(1/4*f(t_{2},k_{1})+3/4*f(t_{2}+2/3h,k_{2}))=1.227417567}$
${\displaystyle t_{4}=1.1}$
	${\displaystyle k_{1}=y_{3}=1.227417567}$	${\displaystyle f(t_{3},k_{1})=3.796866512}$	${\displaystyle k_{2}=y_{3}+2/3hf(t_{3},k_{1})=1.290698676}$
	${\displaystyle 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 ${\displaystyle y_{i}}$s újraszámolása érdekében ${\displaystyle 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 hibát minden egyes RK lépésben. Ezt úgy valósította meg, hogy két módszert tartalmaz a táblázat, egyet p-ed rendűvel és egyet p-1-ed rendűvel.

A kisebb rendű lépés adott:

${\displaystyle y_{n+1}^{*}=y_{n}+h\sum _{i=1}^{s}b_{i}^{*}k_{i},}$

ahol, a ${\displaystyle k_{i}}$ megegyezik a magasabb rendű módszerrel. Ekkor a hiba:

${\displaystyle e_{n+1}=y_{n+1}-y_{n+1}^{*}=h\sum _{i=1}^{s}(b_{i}-b_{i}^{*})k_{i},}$

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

	0
	${\displaystyle c_{2}}$	${\displaystyle a_{21}}$
	${\displaystyle c_{3}}$	${\displaystyle a_{31}}$	${\displaystyle a_{32}}$
	${\displaystyle \vdots }$	${\displaystyle \vdots }$		${\displaystyle \ddots }$
	${\displaystyle c_{s}}$	${\displaystyle a_{s1}}$	${\displaystyle a_{s2}}$	${\displaystyle \cdots }$	${\displaystyle a_{s,s-1}}$
		${\displaystyle b_{1}}$	${\displaystyle b_{2}}$	${\displaystyle \cdots }$	${\displaystyle b_{s-1}}$	${\displaystyle b_{s}}$
		${\displaystyle b_{1}^{*}}$	${\displaystyle b_{2}^{*}}$	${\displaystyle \cdots }$	${\displaystyle b_{s-1}^{*}}$	${\displaystyle b_{s}^{*}}$

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

Habár a legegyszerűbb adaptív Runge–Kutta-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:

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:

${\displaystyle {\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.

${\displaystyle y_{n+1}=y_{n}+h\sum _{i=1}^{s}b_{i}k_{i}\,}$

${\displaystyle k_{i}=f\left(t_{n}+c_{i}h,y_{n}+h\sum _{j=1}^{s}a_{ij}k_{j}\right).}$

Az ${\displaystyle a_{ij}}$ mátrix telítettsége miatt, az egyes ${\displaystyle k_{i}}$ becslése jelentékeny mértékben fog függeni az ${\displaystyle 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:

${\displaystyle y_{n+1}=y_{n}+hf(t_{n}+h,y_{n+1})\,}$

Ennek táblázata egyszerű:

${\displaystyle {\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:

${\displaystyle k_{1}=f(t_{n}+c_{1}h,y_{n}+ha_{11}k_{1})\rightarrow k_{1}=f(t_{n}+h,y_{n}+hk_{1}).}$

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

${\displaystyle y_{n+1}=y_{n}+hk_{1}\rightarrow hk_{1}=y_{n+1}-y_{n}\,}$

így hát

${\displaystyle 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:

${\displaystyle y_{n+1}=y_{n}+hf(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).

Algoritmus

Legyen mondjuk a ${\displaystyle y^{'}(x)=-2*y(x);y(0)=3}$ differenciálegyenlet, aminek a megoldása:${\displaystyle y(x)=3*e^{-2*x}}$

import math
import numpy as np
import matplotlib.pyplot as plt

x0=0
y0=3
h=0.8
def ypontos():
	x=np.linspace(0,10,100)
	y=3*np.exp(-2*x)
	plt.plot(x,y,"-b")
def f(x, y):
	return(-2*y)
def RungeKutta2nd(f, h, x0, y0):
	x=np.arange(0, 10, h)
	y=x*0
	y[0]=y0
	for i in range(10):
		k1=h*f(x[i],y[i])
		k2=h*f(x[i]+h/2,y[i]+k1/2)
		y[i+1]=y[i]+k2
	plt.plot(x,y, "--r")
	plt.text(-0.5, 3,'Masodrendu Runge-Kutta (h=0.8)',color='red', fontsize=10)
def RungeKutta4th(f, h, x0, y0):
	x=np.arange(0, 10, h)
	y=x*0
	y[0]=y0
	for i in range(10):
		k1=h*f(x[i],y[i])
		k2=h*f(x[i]+h/2,y[i]+k1/2)
		k3=h*f(x[i]+h/2,y[i]+k2/2)
		k4=h*f(x[i]+h,y[i]+k3)
		y[i+1]=y[i]+(k1+2*k2+2*k3+k4)/6
	plt.plot(x,y, "--g")
	plt.text(5, 3,'Negyedrendu Runge-Kutta (h=0.8)',color='green', fontsize=10)
ypontos()
RungeKutta2nd(f, h, x0, y0)
RungeKutta4th(f, h, x0, y0)
plt.show()

A program lefuttatása után egy grafikonon összehasonlíthatjuk a másodrendű illetve 4.-edrendű Runge-Kutta módszereket illetve a tényleges megoldást.