Runge-Kutta-Verfahren

Die $s$-stufigen Runge-Kutta-Verfahren (nach Carl Runge und Martin Wilhelm Kutta) sind Einschrittverfahren zur näherungsweisen Lösung von Anfangswert-Problemen in der Mathematik.

Allgemeines

Wenn vom Runge-Kutta-Verfahren gesprochen wird, ist oft das populäre klassische Runge-Kutta-Verfahren gemeint. Dieses bildet jedoch nur einen Spezialfall dieser Familie von Verfahren.

Gegeben sei ein Anfangswert-Problem

$y'(x)=f(x,y)\quad ,\quad y(0)=y_{0}\quad ,\quad y\colon \mathbb {R} \to \mathbb {R} ^{n}\colon x\mapsto y(x)$

mit exakter Lösung $y(x)$. Die exakte Lösung kann im allgemeinen nicht angegeben werden, weshalb man sich mit einer Näherung $\eta _{i}$ an diskreten Stellen $x_{i}$ begnügt. Es gibt verschiedene Methoden zur Berechnung dieser Näherung, z.B. Einschrittverfahren oder Mehrschrittverfahren.

Die s-stufigen Runge-Kutta-Verfahren sind Einschrittverfahren der Art:

${\begin{matrix}\eta _{i+1}&=&\eta _{i}+h\sum _{j=1}^{s}b_{j}k_{j}\quad ,\\k_{j}&=&f(x_{i}+hc_{j},\eta _{i}+h\sum _{l=1}^{s}a_{jl}k_{l})\quad .\end{matrix}}$

Die Anzahl der Stufen $s$ gibt an, wie viele Funktionsaufrufe pro Schritt (mit Schrittweite $h$) benötigt werden. Im allgemeinen ist die Rekursionsformel des Runge-Kutta-Verfahrens implizit; Für $a_{jl}=0\;\forall l\geq j$ ist das Verfahren explizit.

Man kann die charakteristischen Koeffizienten $c_{j}$, $b_{j}$, $a_{jl}$ übersichtlich im sog. Runge-Kutta-Tableau (auch engl. Butcher array genannt) anordnen:

${\begin{matrix}c&|&A\\-&-&-\\&|&b^{\top }\end{matrix}}\quad ,\quad c={\begin{bmatrix}c_{1}\\\vdots \\c_{j}\\\vdots \\c_{s}\end{bmatrix}}\quad ,\quad b={\begin{bmatrix}b_{1}\\\vdots \\b_{j}\\\vdots \\b_{s}\end{bmatrix}}\quad ,\quad A={\begin{bmatrix}a_{11}&\dots &a_{1l}&\dots &a_{1s}\\\vdots &\ddots &\vdots &\ddots &\vdots \\a_{j1}&\dots &a_{jl}&\dots &a_{js}\\\vdots &\ddots &\vdots &\ddots &\vdots \\a_{s1}&\dots &a_{sl}&\dots &a_{ss}\\\end{bmatrix}}\quad .$

Eine wichtige Eigenschaft zum Vergleich von Verfahren ist die Konsistenzordnung, die auf dem Begriff des lokalen Diskretisierungsfehlers $\tau$ beruht. Ein Einschrittverfahren heißt konsistent von der Ordnung $p$ (hat Konsistenzordnung $p$), falls gilt:

$\tau \leq {\mathcal {O}}(h^{p})\quad .$

Die Konsistenzordnung kann durch Taylorentwicklung von $\tau$ bestimmt werden.

Weil ein konsistentes Verfahren auch konvergent ist (globaler Diskretisierungsfehler erreicht im Grenzwert kleiner Schrittweiten Null), sind Runge-Kutta-Verfahren mit möglichst hoher Ordnung $p$ bei möglichst wenigen Funktionsauswertungen s von Interesse.

Aus der Konsistenzbedingung (z.B. das Verfahren soll Ordnung 4 haben) ergeben sich Konsistenzgleichungen (engl. oder conditions) für die Koeffizienten des Runge-Kutta-Verfahrens. Die Anzahl und die Gleichungen selbst können mit Hilfe der Theorie der Butcher-Bäume ermittelt werden. Mit zunehmender Ordnung wächst die Zahl der zu lösender (i.A. nicht-linearen) Konsistenzgleichung schnell an. Das Aufstellen der Konsistenzgleichungen ist bereits nicht einfach; Das Lösen ist dann noch schwieriger.

Beispiele

Das explizite Euler-Verfahren (Ordnung 1):

${\begin{matrix}0&|&&\\&|&&\\-&-&-&-\\&|&1&\end{matrix}}\quad .$

Das Heun-Verfahren (Ordnung 2):

${\begin{matrix}0&|&&\\1&|&1&\\-&-&-&-\\&|&{\frac {1}{2}}&{\frac {1}{2}}\end{matrix}}\quad .$

Das Runge-Kutta-Verfahren der Ordnung 2:

${\begin{matrix}0&|&&\\{\frac {1}{2}}&|&{\frac {1}{2}}&\\-&-&-&-\\&|&0&1\end{matrix}}\quad .$

Das Runge-Kutta-Verfahren der Ordnung 3 (vgl. Simpsonregel):

${\begin{matrix}0&|&&&\\{\frac {1}{2}}&|&{\frac {1}{2}}&&\\1&|&-1&2&\\-&-&-&-&-\\&|&{\frac {1}{6}}&{\frac {4}{6}}&{\frac {1}{6}}\end{matrix}}\quad .$

Das Heun-Verfahren 3. Ordnung:

${\begin{matrix}0&|&&&\\{\frac {1}{3}}&|&{\frac {1}{3}}&&\\{\frac {2}{3}}&|&0&{\frac {2}{3}}&\\-&-&-&-&-\\&|&{\frac {1}{4}}&0&{\frac {3}{4}}\end{matrix}}\quad .$

Das klassische Runge-Kutta-Verfahren (Ordnung 4):

${\begin{matrix}0&|&&&&\\{\frac {1}{2}}&|&{\frac {1}{2}}&&&\\{\frac {1}{2}}&|&0&{\frac {1}{2}}&&\\1&|&0&0&1&\\-&-&-&-&-&-\\&|&{\frac {1}{6}}&{\frac {1}{3}}&{\frac {1}{3}}&{\frac {1}{6}}\end{matrix}}\quad .$

Literatur

• J. C. Butcher: The Numerical Analysis of Ordinary Differential Equations: Runge-Kutta and General Linear Methods, 1987.
• E. Fehlberg: Klassische Runge-Kutta Formeln 5. und 7. Ordnung mit Schrittweitenkontrolle.
• Lambert Numerical Methods for Ordinary Differential Systems, The Initial Value Problem, 1991.
• Sofroniou Symbolic Derivation of Runge-Kutta Methods, 1994.
• M. Hermann: Numerik gewöhnlicher Differentialgleichungen, Anfangs- und Randwertprobleme, Oldenbourg Verlag, München und Wien, 2004, ISBN: 3-486-27606-9

Weblinks

• http://www.learn-line.nrw.de/angebote/modell/runge.htm