Runge-Kutta-Verfahren

Runge-Kutta-Verfahren
Einige Runge-Kutta-Verfahren im Vergleich.

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 von dem Runge-Kutta-Verfahren gesprochen wird, ist in der Regel das klassische Runge-Kutta-Verfahren gemeint. Dieses bildet jedoch nur einen Spezialfall dieser Familie von Verfahren.

Inhaltsverzeichnis

Allgemeine Formulierung

Gegeben sei ein Anfangswertproblem


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

mit exakter Lösung y(t). Die exakte Lösung kann im Allgemeinen nicht oder nicht effizient angegeben werden, weshalb man sich mit einer Näherung yn an diskreten Stellen tn begnügt. Es gibt verschiedene Methoden zur Berechnung dieser Näherung, z. B. Einschrittverfahren (wie diese Runge-Kutta-Verfahren) oder Mehrschrittverfahren.

Die s-stufigen Runge-Kutta-Verfahren sind Einschrittverfahren, die durch Ausdrücke der folgenden Art gegeben sind:

y_{n+1} = y_n + h \sum_{j=1}^s b_j k_j.

Dabei bezeichnet h die Schrittweite zwischen den aufeinanderfolgenden Stützstellen tn und tn + 1. Die Koeffizienten bj definieren das jeweilige Verfahren und können als Quadraturformel für das Integral \int_{t_n}^{t_{n+1}}f(t, y(t))dt interpretiert werden. Die Größen kj bezeichnet man als Zwischenschritte, sie entsprechen Auswertungen der rechten Seite f an bestimmten Knoten:

 k_j = f\left(t_n + h c_j, y_n + h \sum_{l=1}^s a_{jl} k_l \right),\,j=1,...,s.

Die cj und ajl sind weitere für das Verfahren charakteristische Koeffizienten und können als Quadraturformeln zur Berechnung der kj verstanden werden.

Ein allgemeines Runge-Kutta-Verfahren ist implizit, es müssen also zur Bestimmung der kj lineare beziehungsweise nichtlineare Gleichungssysteme gelöst werden. Gilt aber ajl = 0 für alle l \ge j, so ist das Verfahren explizit.

Die Steuerung der Schrittweite h ist von besonderem Interesse. Man kann sich leicht vorstellen, dass die Funktion in Bereichen, in denen nur geringe Änderungen zwischen yn + 1 und yn vorliegen, mit weniger Rechenschritten auskommt, als in solchen, in denen schnelle Änderungen vorliegen.

Beispiel

Ein Beispiel ist das dreistufige Runge-Kutta-Verfahren:  y_{n+1} = y_n + h \cdot \bigg( \frac{1}{6}k_1 + \frac{4}{6}k_2 + \frac{1}{6}k_3 \bigg) mit den Zwischenstufen

 k_1 = f (t_n, y_n )\quad
 k_2 = f (t_n+\frac{1}{2}h, y_n+\frac{h}{2}k_1)\quad
 k_3 = f (t_n+h, y_n-h k_1+2h k_2)\quad

Runge-Kutta-Tableau

Man kann die charakteristischen Koeffizienten cj, bj, ajl übersichtlich im sogenannten Runge-Kutta-Tableau (auch Butcher-Schema, -Tableau oder engl. Butcher array genannt) anordnen. Hierbei ist die Matrix A bei einem expliziten Verfahren eine strikte untere Dreiecksmatrix.


\begin{array}{c|c}
    \mathbf{c} & A\\
    \hline     & \mathbf{b^T} \\
\end{array}
=
\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}\; ,
  
        c = \begin{bmatrix}
			c_1 \\ \vdots \\ c_j \\ \vdots \\ c_s
		\end{bmatrix} \;, \quad 
	b = \begin{bmatrix}
			b_1 \\ \vdots \\ b_j \\ \vdots \\ b_s
		\end{bmatrix} \;, \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} \;.

Konsistenzordnung und Konvergenzordnung

Eine wichtige Eigenschaft zum Vergleich von Verfahren ist die Konsistenzordnung, die auf dem Begriff des lokalen Diskretisierungsfehlers τ = yn + 1y(tn + 1) beruht. Dabei ist yn + 1 die numerische Lösung nach einem Schritt und y(tn + 1) die exakte Lösung. Ein Einschrittverfahren heißt konsistent von der Ordnung p (hat Konsistenzordnung p), falls für den lokalen Diskretisierungsfehler gilt:

\tau \le \mathcal{O}(h^{p+1}) (Zur Notation, siehe Landau-Symbole).

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

Konsistenzordnung p und Stabilität \Rightarrow Konvergenzordnung p

Bei Einschrittverfahren, wie den Runge-Kutta-Verfahren gilt sogar, sofern f und die Verfahrensvorschrift Lipschitz-stetig sind:

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 Gleichungen und ihre Anzahl 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 allerdings noch schwieriger und bedarf Erfahrung und Fingerspitzengefühl, um „gute“ Koeffizienten zu erhalten.

Ein explizites s-stufiges Runge-Kutta-Verfahren hat höchstens Konvergenzordnung s, ein implizites dagegen bis zu 2s.

Um die Genauigkeit eines Ergebnisses zu verbessern gibt es zwei Möglichkeiten:

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

Welche Strategie die bessere ist, hängt von der konkreten Problemstellung ab, die Erhöhung der Konvergenzordnung ist allerdings nur bis zu einer bestimmten Grenze sinnvoll, da wegen der Butcher-Schranken die Stufenzahl s schneller wächst als die Ordnung p. Für s \ge 5 existiert beispielsweise kein explizites s-stufiges RKV der Konvergenzordnung q = s.

Implizite Runge-Kutta-Verfahren

Explizite Verfahren haben den Vorteil, dass die zu lösenden Gleichungssysteme durch sukzessives Einsetzen lösbar sind, beim impliziten Verfahren muss dagegen je nach Form der rechten Seite f \in \mathbb{R}^n ein lineares oder nichtlineares Gleichungssystem mit s \cdot n Unbekannten gelöst werden, was pro Zeitschritt einen wesentlich höheren Aufwand darstellt. Der Grund, warum implizite Verfahren überhaupt in Betracht gezogen werden, ist, dass explizite Runge-Kutta-Verfahren stets ein beschränktes Stabilitätsgebiet haben, während implizite Runge-Kutta-Verfahren für praktisch beliebig hohe Ordnungen A-stabil sein können und damit Einschränkungen an den Zeitschritt nur aufgrund von Genauigkeitsüberlegungen und nicht aufgrund von Stabilitätsbeschränkungen notwendig sind. Dies ist insbesondere bei steifen Differentialgleichungen und Differentiell-algebraischen Gleichungen interessant.

Die maximale Ordnung eines s-stufigen Runge-Kutta-Verfahrens ist 2s. Diese wird ausschließlich durch die so genannten Gauß-Legendre-Verfahren erzielt, bei denen die Quadraturformeln zur Konstruktion des Runge-Kutta-Verfahren den Gauß-Legendre-Formeln entsprechen. Ordnung 2s-1 wird etwa mittels Radau-Formeln erzielt, die Runge-Kutta-Verfahren heißen dann Radau-Verfahren, während Ordnung 2s-2 über Lobatto-Formeln erzielt wird, die Verfahren heißen dann Lobatto-Verfahren.

Um die Lösung eines Gleichungssystems mit s \cdot n Unbekannten zu umgehen, werden häufig so genannte Diagonal implizite Runge-Kutta-Verfahren (kurz DIRK) genutzt. Dabei ist die Matrix A im Butcher-Array diagonal, alle Einträge rechts oberhalb der Diagonalen sind also Null. Dies entkoppelt das große Gleichungssystem in eine Sequenz von s Gleichungssystemen. Ist darüber hinaus der Koeffizient auf der Diagonalen konstant, spricht man von einem SDIRK-Verfahren (für singly diagonal). Sind die Koeffizienten in der letzten Zeile von A identisch mit denen des Vektors b, so wird etwas Aufwand gespart, insbesondere sind die Verfahren dann aber auch L-stabil. Diese Vereinfachung geschieht auf Kosten der maximalen Ordnung: s-stufige DIRK-Verfahren haben maximal Ordnung s+1, wobei dieses Maximum nicht für beliebige Stufen erreicht werden kann. Die in der Praxis verwandten Verfahren haben in der Regel Ordnung s oder weniger.

Als Alternative zu DIRK-Verfahren haben sich noch die so genannten linear impliziten Verfahren etabliert, insbesondere die Rosenbrock-Verfahren, bei denen die nichtlinearen Gleichungen durch lineare angenähert werden.

Zeitschrittweitensteuerung: Eingebettete Verfahren

Um die Effizienz der Verfahren zu erhöhen ist es sinnvoll, den Zeitschritt einer Fehlertoleranz anzupassen. Runge-Kutta-Verfahren bieten hierzu über so genannte eingebettete Verfahren eine relative einfache Möglichkeit. Diese bestehen aus einem zweiten Satz an Koeffizienten \hat{b} für ein zweites Verfahren:

\hat{y}_{n+1} = y_n + h \sum_{j=1}^s \hat{b}_j k_j,

wobei die Koeffizienten so gewählt werden, dass sich ein schlechteres Verfahren, konkret ein Verfahren von niedrigerer Ordnung ergibt als das ursprüngliche. Dann ist die Differenz

y_{n+1}-\hat{y}_{n+1} = \sum_{j=1}^s (b_j-\hat{b}_j) k_j

eine Schätzung des lokalen Fehlers des ursprünglichen Verfahrens von der Ordnung wie das eingebettete Verfahren. Zur Berechnung sind keine neuen Funktionsauswertungen notwendig, sondern nur Linearkombinationen der bereits berechneten kj. Die Bestimmung einer neuen Zeitschrittweite aus dem Fehlerschätzer kann über verschiedene Steuerungen erfolgen.

Im expliziten Fall sind die bekanntesten eingebetteten Verfahren die Runga-Kutta-Fehlberg- sowie die Dormand-Prince-Formeln (DOPRI).

Geschichte

Die ersten Runge-Kutta-Verfahren wurden um 1900 von Karl Heun, Martin Wilhelm Kutta und Carl Runge entwickelt. In den 1960ern entwickelte John C. Butcher mit den vereinfachenden Bedingungen und dem Butcher-Tableau Werkzeuge, um Verfahren höherer Ordnung zu entwickeln. Ernst Hairer fand 1978 ein Verfahren 8. Ordnung mit 10 Stufen.

Beispiele

Das explizite Euler-Verfahren (Ordnung 1):

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

Das Heun-Verfahren (Ordnung 2):

\begin{array}{c|cc}
		0 \\
		1 & 1 \\
		\hline & \frac{1}{2} & \frac{1}{2}
\end{array}

Das Runge-Kutta-Verfahren der Ordnung 2:

\begin{array}{c|cc}
		0 \\
		\frac{1}{2} & \frac{1}{2} \\
		\hline & 0 & 1
\end{array}

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

\begin{array}{c|ccc}
		0 \\
                \frac{1}{2} & \frac{1}{2} \\
		1 & -1 & 2 \\
		\hline & \frac{1}{6} & \frac{4}{6} & \frac{1}{6}
\end{array}

Das Heun-Verfahren 3. Ordnung:

\begin{array}{c|ccc}
		0 \\
                \frac{1}{3} & \frac{1}{3} \\
                \frac{2}{3} & 0 & \frac{2}{3} \\
		\hline & \frac{1}{4} & 0 & \frac{3}{4}
\end{array}

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

\begin{array}{c|cccc}
		0 \\
                \frac{1}{2} & \frac{1}{2} \\
                \frac{1}{2} & 0 & \frac{1}{2} \\
                1 & 0 & 0 & 1 \\
		\hline & \frac{1}{6} & \frac{1}{3} & \frac{1}{3} & \frac{1}{6}
\end{array}

Das implizite Trapez-Verfahren der Ordnung 2:

\begin{array}{c|cc}
		0 \\
                1 & \frac{1}{2} & \frac{1}{2} \\
		\hline & \frac{1}{2} & \frac{1}{2}
\end{array}

Literatur

  • Peter Albrecht: The Runge-Kutta Theory in a Nutshell. In: SIAM Journal on Numerical Analysis. 33, 5, October 1996, ISSN 0036-1429, S. 1712–1735.
  • John C. Butcher: The Numerical Analysis of Ordinary Differential Equations. Runge-Kutta and General Linear Methods. Wiley, Chichester u. a. 1987, ISBN 0-471-91046-5 (A Wiley-Interscience publication).
  • Peter Deuflhard, Folkmar Bornemann: Numerische Mathematik. Band 2: Gewöhnliche Differentialgleichungen. 2. vollständige überarbeitete und erweiterte Auflage. de Gruyter, Berlin 2002, ISBN 3-11-017181-3.
  • Ernst Hairer, Gerhard Wanner: Solving Ordinary Differential Equations. Band 1: Nonstiff Problems. 2. revised edition. Springer Verlag, Berlin u. a. 1993, ISBN 3-540-56670-8 (Springer series in computational mathematics 8), (Auch Nachdruck: ebenda 2008, ISBN 978-3-642-05163-0).
  • E. Hairer, G. Wanner: Solving Ordinary Differential Equations. Band 2: Stiff and differential-algebraic problems. 2. revised edition. Corrected 2. print. Springer Verlag, Berlin u. a. 2002, ISBN 3-540-60452-9 (Springer series in computational mathematics 14), (Auch Nachdruck: ebenda 2010, ISBN 978-3-642-05220-0).
  • Martin Hermann: Numerik gewöhnlicher Differentialgleichungen. Anfangs- und Randwertprobleme. Oldenbourg, München u. a. 2004, ISBN 3-486-27606-9.
  • M. Sofroniou: Symbolic Derivation of Runge-Kutta Methods. In: Journal of Symbolic Computation. 18, 3, September 1994, ISSN 0747-7171, S. 265–296.
  • Karl Strehmel, Rüdiger Weiner: Linear-implizite Runge-Kutta-Methoden und ihre Anwendung. Teubner, Stuttgart u. a. 1992, ISBN 3-8154-2027-X (Teubner-Texte zur Mathematik 127).

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Runge-Kutta-Verfahren — Runge s ir Kutt o metodas statusas T sritis automatika atitikmenys: angl. Runge Kutta method vok. Runge Kutta Verfahren, n rus. метод Рунге Кутта, m pranc. méthode de Runge Kutta, f ryšiai: sinonimas – Rungės ir Kuto metodas …   Automatikos terminų žodynas

  • Runge-Kutta-Verfahren — Rụnge Kụtta Verfahren   [nach C. D. T. Runge und dem Mathematiker M. Wilhelm Kutta, * 1867, ✝ 1944], Näherungsmethode zur Lösung gewöhnlicher Differenzialgleichungen, mit der die gesuchte Funktion auf einem diskreten Punktgitter approximativ… …   Universal-Lexikon

  • Klassisches Runge-Kutta-Verfahren — Das klassische Runge Kutta Verfahren (nach Carl Runge und Martin Wilhelm Kutta) ist ein spezielles explizites 4 stufiges Runge Kutta Verfahren zur numerischen Lösung von Anfangswertproblemen (Gewöhnliche Differentialgleichungen). Runge hat als… …   Deutsch Wikipedia

  • Runge-Kutta method — Runge s ir Kutt o metodas statusas T sritis automatika atitikmenys: angl. Runge Kutta method vok. Runge Kutta Verfahren, n rus. метод Рунге Кутта, m pranc. méthode de Runge Kutta, f ryšiai: sinonimas – Rungės ir Kuto metodas …   Automatikos terminų žodynas

  • Runge-Kutta — Einige Runge Kutta Verfahren im Vergleich. 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… …   Deutsch Wikipedia

  • Runge-Kutta-Methode — Einige Runge Kutta Verfahren im Vergleich. 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… …   Deutsch Wikipedia

  • méthode de Runge-Kutta — Runge s ir Kutt o metodas statusas T sritis automatika atitikmenys: angl. Runge Kutta method vok. Runge Kutta Verfahren, n rus. метод Рунге Кутта, m pranc. méthode de Runge Kutta, f ryšiai: sinonimas – Rungės ir Kuto metodas …   Automatikos terminų žodynas

  • Runge's ir Kutt'o metodas — statusas T sritis automatika atitikmenys: angl. Runge Kutta method vok. Runge Kutta Verfahren, n rus. метод Рунге Кутта, m pranc. méthode de Runge Kutta, f ryšiai: sinonimas – Rungės ir Kuto metodas …   Automatikos terminų žodynas

  • Runge — ist eine seitliche Haltestange bei Langguttransportern (Holz, Rohre), siehe auch Rungenwagen eine Stadt in Texas, siehe Runge (Texas) Runge ist der Familienname folgender Personen: Alfred Runge (1881–1946), deutscher Architekt Annelie Runge (*… …   Deutsch Wikipedia

  • Kutta — Martin Wilhelm Kutta (* 3. November 1867 in Pitschen, Oberschlesien; † 25. Dezember 1944 in Fürstenfeldbruck) war ein deutscher Mathematiker. Von 1885 bis 1890 studierte er an der Universität Breslau, danach bis 1894 an der Universität München.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”