Runge-Kutta-Verfahren

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Die $s$ -stufigen Runge-Kutta-Verfahren (nach Carl Runge und Martin Wilhelm Kutta) sind Einschrittverfahren zur näherungsweisen Lösung von Anfangswertproblemen in der numerischen Mathematik. 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.

Inhaltsverzeichnis

1 Allgemeine Formulierung
2 Runge-Kutta-Tableau
3 Konsistenzordnung und Konvergenzordnung
4 Beispiele
5 Literatur
6 Weblinks

[Bearbeiten] Allgemeine Formulierung

Gegeben sei ein Anfangswertproblem

$y'(x) = f\left(x, y(x)\right), \quad y(0) = y_0, \quad y \colon \R \to \R^n$

mit exakter Lösung $y (x)$ . Die exakte Lösung kann im allgemeinen nicht angegeben werden, weshalb man sich mit einer Näherung η⁽ⁱ⁾ an diskreten Stellen x⁽ⁱ⁾ 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:

$\eta^{(i+1)} = \eta^{(i)} + h^{(i)} \sum_{j=1}^s b_j k^{(i)}_j$

h⁽ⁱ⁾ bezeichnet die Schrittweite zwischen den aufeinanderfolgenden Stützstellen x⁽ⁱ⁾ und x⁽ⁱ⁺¹⁾. Die Koeffizienten b_j sind charakteristisch für das jeweilige Verfahren. Die Koeffizienten k⁽ⁱ⁾_j bezeichnet man als Zwischenschritte. Sie werden bei jedem Berechnungsschritt neu berechnet:

$k^{(i)}_j = f\left(x^{(i)}_j, \eta^{(i)}_j \right)$

mit

$x^{(i)}_j = x^{(i)} + h^{(i)} \, c_j$

und

$\eta^{(i)}_j = \eta^{(i)} + h^{(i)} \, \sum_{l=1}^s a_{jl} k^{(i)}_l$

Die c_j und a_jl sind weitere für das Verfahren charakteristische Koeffizienten. Die Anzahl der Stufen s gibt an, wie viele Funktionsaufrufe pro Schritt benötigt werden.

Im Allgemeinen ist die Rekursionsformel zur Bestimmung der Zwischenschritte implizit. Gilt aber $a j l = 0$ für alle $l \ge j$ so ist das Verfahren explizit.

Die Steuerung der Schrittweite h⁽ⁱ⁾ ist auch von besonderem Interesse. Man kann sich leicht vorstellen, dass die Funktion in Bereichen, in denen nur geringe Änderungen zwischen η⁽ⁱ⁺¹⁾ und η⁽ⁱ⁾ vorliegen, mit weniger Rechenschritten auskommt, als in solchen, wo schnelle Änderungen vorliegen.

[Bearbeiten] Runge-Kutta-Tableau

Man kann die charakteristischen Koeffizienten $c j$ , $b j$ , $a j l$ ü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 .$

[Bearbeiten] Konsistenzordnung und Konvergenzordnung

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

$\tau \le \mathcal{O}(h^p) \quad .$ Je nach Definition des Diskretisierungsfehler kann allerdings auch $\tau \le \mathcal{O}(h^{p+1}) \quad .$ gefordert sein, je nachdem wie $τ$ definiert ist.

Ist $\tau=\frac{1}{h}(y_{i+1}-y(x_{i+1}))$ definiert so muss $\tau \le \mathcal{O}(h^p) \quad$ gelten.

Ist hingegen $τ = y i + 1 - y (x i + 1)$ definiert so muss $\tau \le \mathcal{O}(h^{p+1}) \quad$ gelten.

Beide Definitionen sind sinnvoll, und haben in verschiedenen Bereichen ihre Vorteile. Dabei ist $y i + 1$ die numerische Lösung nach einem Schritt und $y (x i + 1)$ die exakte Lösung.

Die Konsistenz von Ordnung kann durch Taylorentwicklung von $τ$ oder durch Taylorentwicklung der exakten Lösung und Taylorentwicklung der numerischen Lösung bestimmt werden. Allgemein gilt:

Konsistenzordnung p und Stabilität $\Rightarrow$ Konvergenzordnung p

Bei Einschrittverfahren, wie den Runge-Kutta Verfahren gilt aber sogar:

Konsistenzordnung p $\Rightarrow$ Konvergenzordnung p

Aus der Konsistenzbedingung (z.B. das Verfahren soll Ordnung 4 haben) ergeben sich Konsistenzgleichungen (engl. conditions) für die Koeffizienten des Runge-Kutta-Verfahrens. Die Anzahl und die Gleichungen selbst können mit Hilfe von Taylorentwicklung oder der Theorie der Butcher-Bäume ermittelt werden. Mit zunehmender Ordnung wächst die Zahl der zu lösenden nicht-linearen Konsistenzgleichungen schnell an. Das Aufstellen der Konsistenzgleichungen ist bereits nicht einfach; kann jedoch mit Hilfe der Butcher-Bäume von Computeralgebrasystemen erledigt werden. Das Lösen ist dann noch schwieriger und bedarf Erfahrung und Fingerspitzengefühl um "gute" Koeffizienten zu erhalten..

Im allgemeinen kann ein explizites s-stufiges Runge-Kutta-Verfahren höchstens Konvergenzordnung s haben, ein implizites dagegen idealerweise Konvergenzordnung 2s.

Explizite Verfahren haben allerdings den Vorteil, dass die zu lösenden Gleichungssysteme wesentlich einfacher sind, da sie durch sukzessives Einsetzen lösbar sind. Daher kommen Implizite Runge-Kutta-Verfahren meist nur bei steifen Differentialgleichungen oder Differentiell-algebraischen Gleichungen zum Einsatz.

Um die Genauigkeit eines Ergebnisses zu verbessern gibt es im Grunde zwei Möglichkeiten.

Man kann die Schrittweite verkleinern, das heißt, man erhöht die Anzahl der Diskretisierungspunkte.
Man kann Verfahren höherer Konvergenzordnung wählen

Welche Strategie die bessere ist, hängt von der konkreten Problemstellung ab, eine höhere Konvergenzordnung ist aber nur bis zu einer bestimmten Grenze sinnvoll, da

die Anzahl der zu lösenden Bestimmungsgleichungen exponentiell mit der Ordnung des Verfahrens wächst.
Wegen den Butcher-Schranken die Stufenzahl s schneller wächst als die Ordnung p.

[Bearbeiten] 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 .$

[Bearbeiten] 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. Computing, 4(2), 93-106, 1969.
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. München und Wien: Oldenbourg, 2004. ISBN 3-486-27606-9
Folkmar Bornemann Runge-Kutta Methods, Trees, and Maple Selçuk J. Appl. Math. 2, pp. 3-15 (2001). Version using Mathematica: E-print arXiv:math.NA/0211049
Peter Deuflhard, Folkmar Bornemann: Numerische Mathematik 2. ISBN 3110171813
Ernst Hairer, Gerhard Wanner: Solving Ordinary Differential Equations 1. Nonstiff Problems ISBN 3540566708
P. Albrecht: The Runge-Kutta Theory in a Nutshell, SIAM J. Numer. Anal.14, 1006-1021, 1977.