Runge–Kutta-módszer

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 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 aij (1 ≤ j < is), bi (i = 1, 2, ..., s) és a ci (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
 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(hp+1) lesz. Például egy kétlépcsős módszer másodrendű ha b1 + b2 = 1, b2c2 = 1/2, és b2a21 = 1/2.

Példák[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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_is újraszámolása érdekében f(t_i,k_1)-et használtunk.

Adaptív Runge–Kutta-módszer[szerkesztés | forrásszöveg szerkesztése]

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:

 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- és 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 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:

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[szerkesztés | forrásszöveg szerkesztése]

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 aij 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).