Notice: Unexpected clearActionName after getActionName already called in /var/www/html/includes/context/RequestContext.php on line 338
Runge-Kutta-Verfahren – Wikipedia (Deutsch) – Lokale Kopie Zum Inhalt springen

Runge-Kutta-Verfahren

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Butcher-Tableau)
Datei:Runge-kutta.svg
Einige Runge-Kutta-Verfahren im Vergleich.

Die nach Carl Runge und Martin Wilhelm Kutta benannten <math>s</math>-stufigen Runge-Kutta-Verfahren 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.

Allgemeine Formulierung

Gegeben sei ein Anfangswertproblem:

<math>

y'(t) = f\left(t, y(t)\right), \quad y(t_0) = y_0, \quad y \colon \R \to \R^d </math>

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

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

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

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

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

Die <math>c_j</math> und <math>a_{jl}</math> sind weitere für das Verfahren charakteristische Koeffizienten und können als Knoten und Gewichte der Quadraturformeln zur Berechnung der <math>k_j</math> verstanden werden.

Ein allgemeines Runge-Kutta-Verfahren ist implizit, es müssen also zur Bestimmung der <math>k_j</math> (lineare oder nichtlineare, je nach Aufbau von <math>f</math>) Gleichungssysteme gelöst werden, weil in der Formel für <math>k_j</math> sowohl links wie auch rechts alle <math>k_.</math> vorkommen. Gilt aber <math>a_{jl}=0</math> für alle <math>l \ge j</math>, dann ist das Verfahren explizit, d. h. man muss kein Gleichungssystem lösen: Denn dann kann man jedes <math>k_j</math> aus den vorher bestimmten <math>k_l</math> mit <math>l < j</math> ermitteln.

Die Steuerung der Schrittweite <math>h</math> ist von besonderem Interesse. Man kann sich leicht vorstellen, dass die Funktion in Bereichen, in denen nur geringe Änderungen zwischen <math>y_{n+1}</math> und <math>y_n</math> vorliegen, mit weniger Rechenschritten auskommt als in solchen, in denen schnelle Änderungen vorliegen.

Beispiel

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

<math> k_1 = f (t_n, y_n )\quad </math>
<math> k_2 = f \left( t_n+\frac{h}{2}, y_n+\frac{h}{2}k_1 \right)\quad </math>
<math> k_3 = f (t_n+h, y_n-h k_1+2h k_2)\quad </math>

Butcher-Tableau

Man kann die charakteristischen Koeffizienten <math>c_j</math>, <math>b_j</math>, <math>a_{jl}</math> übersichtlich im 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 (Nilpotente Dreiecksmatrix).

<math>

\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}\; , </math>  <math> 

       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} \;. </math>

Konsistenzordnung und Konvergenzordnung

Eine wichtige Eigenschaft zum Vergleich von Verfahren ist die Konsistenzordnung, die auf dem Begriff des lokalen Diskretisierungsfehlers <math>\tau=y_{n+1}-y(t_{n+1})</math> beruht. Dabei ist <math>y_{n+1}</math> die numerische Lösung nach einem Schritt und <math>y(t_{n+1})</math> die exakte Lösung. Ein Einschrittverfahren heißt konsistent von der Ordnung <math>p</math> (hat Konsistenzordnung <math>p</math>), falls für den lokalen Diskretisierungsfehler gilt:

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

Die Konsistenzordnung kann durch Taylorentwicklung von <math>\tau</math> oder der exakten und numerischen Lösung bestimmt werden. Allgemein gilt:

Konsistenzordnung <math>p</math> und Stabilität <math>\Rightarrow</math> Konvergenzordnung <math>p</math>

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

Konsistenzordnung <math>p</math> <math>\Rightarrow</math> Konvergenzordnung <math>p</math>

Aus der Konsistenzbedingung (z. B. soll das Verfahren 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 <math>s</math>-stufiges Runge-Kutta-Verfahren hat höchstens Konvergenzordnung <math>s</math>, ein implizites dagegen bis zu <math>2s</math>.

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 <math>s</math> schneller wächst als die Ordnung <math>p</math>. Für <math>s \ge 5</math> existiert beispielsweise kein explizites <math>s</math>-stufiges Runge-Kutta-Verfahren der Konvergenzordnung <math>q=s</math>.<ref name="Butcher1965" details="Theorem 1, S. 410"/><ref name="Butcher2016" details="Theorem 324B, S. 201"/> Basierend auf Resultaten von Butcher ergibt sich folgende Übersicht<ref name="Schwarz" details="Tab. 9.5, S. 380"/> über die maximal erreichbare Konvergenzordnung <math>q</math> bei gegebener Anzahl der Stufen <math>s</math>:

Mit gegebener Stufenzahl maximal erreichbare Konvergenzordnung eines expliziten Runge-Kutta-Verfahrens
Anzahl Stufen <math>s</math> 1 2 3 4 5 6 7 8 9
maximale Ordnung <math>q</math> 1 2 3 4 4 5 6 6 7

Ein explizites Runge-Kutta-Verfahren der Ordnung <math>p</math> benötigt immer mindestens <math>s\geq p</math> Stufen.<ref name="Butcher2016" details="Theorem 324A, S. 200"/> Diese untere Schranke an <math>s</math> ist für <math>1\leq p\leq 4</math> größtmöglich, wie unten aufgeführte Beispiele klassischer Verfahren zeigen. Ist <math>p\geq 5</math>, dann benötigt man <math>s\geq p+1</math>,<ref name="Butcher1965" details="Theorem 1, S. 410"/><ref name="Butcher2016" details="Theorem 324B, S. 201"/><ref name="Butcher2016" details="S. 202, 1. Absatz"/> und diese Schranke ist für <math>5\leq p\leq 6</math> scharf (siehe z. B. das Verfahren von Kutta-Nyström von 5. Ordnung<ref name="Butcher2016" details="S. 205"/> unter Beispiele und weitere von Butcher angegebene Verfahren der Ordnung 6<ref name="Butcher2016" details="S. 208"/>). Ab <math>p\geq 7</math> folgt sogar <math>s\geq p+2</math>,<ref name="Butcher1965" details="Theorem 2, S. 410"/><ref name="Butcher2016" details="S. 202, 1. Absatz"/> und diese Schranke ist für <math>p=7</math> scharf (siehe z. B. das neunstufige Verfahren von Butcher<ref name="Butcher2016" details="S. 209"/> unter Beispiele). Ab <math>p\geq 8</math> folgt noch schärfer <math>s\geq p+3</math>,<ref name="Butcher1985" details="Theorem, S. 521">John C. Butcher: The non-existence of ten stage eighth order explicit Runge-Kutta methods. In: BIT Numerical Mathematics. Bd. 25, Nr. 3, 1985, S. 521–540. doi:10.1007/BF01935372</ref><ref name="Butcher2016" details="S. 202, 1. Absatz"/> und diese untere Schranke an <math>s</math> ist zumindest für <math>p=8</math> scharf<ref name="Butcher1985" details="Corollary, S. 521"/><ref name="Butcher2016" details="S. 210"/>. Dazu wurden bereits 1970 von Curtis<ref name="Curtis1970" details="S. 274—276">Alan R. Curtis: An eighth order Runge-Kutta process with eleven function evaluations per step. In: Numerische Mathematik. Bd. 16, Nr. 3, 1970, S. 268–277. doi:10.1007/BF02219778</ref> und 1972 von Cooper und Verner<ref name="CooperVerner1972" details="Tab. 1, S. 404">G. J. Cooper, James H. Verner: Some explicit Runge-Kutta methods of high order. In: SIAM Journal on Numerical Analysis. Bd. 9, Nr. 3, 1972, S. 389–405.</ref> explizite Verfahren von Konvergenzordnung <math>p=8</math> mit <math>s=11</math> Stufen konstruiert. Für die kleinstmögliche Stufenzahl gilt also:<ref name="Butcher1985" details="S. 521"/>

Minimal notwendige Anzahl an Stufen eines expliziten Runge-Kutta-Verfahrens von vorgegebener Konvergenzordnung
Konvergenzordnung <math>p</math> 1 2 3 4 5 6 7 8
minimale Stufenanzahl <math>s</math> 1 2 3 4 6 7 9 11

Nach Butcher ist für <math>p\in\{9,10\}</math> die optimale Anzahl an Stufen eines expliziten Runge-Kutta-Verfahrens mit Konvergenzordnung <math>p</math> aktuell (Publikationsjahr 2016) unbekannt.<ref name="Butcher2016" details="S. 210"/> Für <math>p=10</math> gab Ernst Hairer 1978 ein explizites Verfahren mit <math>s=17</math> Stufen an,<ref name="Hairer1978" details="S. 48, 2. Absatz; Tab. 3, S. 57—58>Ernst Hairer: A Runge-Kutta method of order 10. In: Journal of the Institute of Mathematics and its Applications. Bd. 21, Nr. 1, 1978, S. 47–59.</ref><ref name="Butcher2016" details="S. 210"/> d. h., die minimale Stufenanzahl liegt für <math>p=10</math> im Bereich <math>p+3=13\leq s\leq 17</math>.

Implizite Runge-Kutta-Verfahren

Explizite Verfahren haben den Vorteil, dass die Stufen durch sukzessives Einsetzen berechenbar sind, beim impliziten Verfahren muss dagegen je nach Form der rechten Seite <math>f \in \mathbb{R}^d</math> ein lineares oder nichtlineares Gleichungssystem mit <math>s \cdot d</math> 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 Anfangswertproblemen und differentiell-algebraischen Gleichungen interessant.

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

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

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

Schrittweitensteuerung: Eingebettete Verfahren

Wenn Probleme in der numerischen Approximation gefunden werden, wie zum Beispiel zusätzliche dissipative Effekte,<ref name=":0">{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Robert Collyer, Frank Womack|Robert Collyer, Frank Womack: }}{{#if:|{{#if:Double-well Forced Oscillator|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Double-well Forced Oscillator}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Double-well Forced Oscillator}}}}|[{{#invoke:URLutil|getNormalized|1=https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Double-well Forced Oscillator}}}}]}}{{#if:| ({{{format}}}{{#if:www.phys.lsu.edu{{#if: 2024-02-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html}}%7C%7C}}}}{{#if:Double-well Forced Oscillator|{{#if:{{#invoke:WLink|isValidLinktext|1=Double-well Forced Oscillator|lines=0}}||}}}}{{#if: www.phys.lsu.edu| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=www.phys.lsu.edu}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2024-02-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2024-02-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2024-02-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:62319||(?)}}}}}}{{#if: 2024-02-23|;}}}}{{#if: 2024-02-23| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2024-02-23 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2024-02-23|class=Zitationswartung}} }} {{#invoke:DateTime|format|2024-02-23|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:www.phys.lsu.edu{{#if: 2024-02-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2024-02-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html
      | {{#if:{{#invoke:URLutil|isWebURL|https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html
       | {{#if:{{#invoke:URLutil|isWebURL|https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html
      | {{#if:{{#invoke:URLutil|isWebURL|https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html
       | {{#if:{{#invoke:URLutil|isWebURL|https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://www.phys.lsu.edu/~fwomack/ProjectPage/project.html }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> kann die Schrittweite <math display="inline">h_i</math> auch automatisch an Schätzungen der lokalen Fehler <math>\epsilon</math> angepasst werden:

Beim Runge-Kutta-Verfahren kann der lokale Fehler <math>\epsilon</math> durch den Vergleich zweier verschiedener Sätze an Koeffizienten <math>b_j</math> und <math>\hat{b}_j</math> unterschiedlicher Ordnung abgeschätzt werden. Die Differenz der Vorhersagen mit den unterschiedlichen Koeffizienten

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

verwendet die bereits berechneten Zwischenschritte <math display="inline">k_j</math> wieder und wird zur Schätzung des lokalen Fehlers <math>\epsilon</math> verwendet. Die Schrittweite <math>h_i</math> wird entsprechend diesem lokalen Fehler <math>\epsilon</math> angepasst. Das führt je nach Algorithmus zur Wiederholung der Berechnung mit kleinerer Schrittweite.<ref name=":0" />

Die Bestimmung einer neuen Schrittweite aus dem Fehlerschätzer kann über verschiedene Schrittweitensteuerungen erfolgen. Die bekanntesten eingebetteten Verfahren sind das Runge-Kutta-Fehlberg-Verfahren sowie die Dormand-Prince-Formeln(DOPRI).

Geschichte

Die ersten Runge-Kutta-Verfahren wurden um 1900 von Karl Heun,<ref>K. Heun: Neue Methoden zur approximativen Integration der Differentialgleichungen einer unabhängigen Veränderlichen, Z. Math. Phys., Band 45, 1900, S. 23–38 (Heun-Verfahren)</ref> Martin Wilhelm Kutta,<ref>W. Kutta: Beitrag zur näherungsweisen Integration totaler Differentialgleichungen, Z. Math. Phys., Band 46, 1901, S. 435–453</ref> und Carl Runge<ref>C. Runge: Über die numerische Auflösung von Differentialgleichungen, Math. Annalen, Band 46, 1895, S. 167–178, Online</ref> entwickelt. In den 1960ern entwickelte John C. Butcher mit den vereinfachenden Bedingungen und dem Butcher-Tableau Werkzeuge, um (insbesondere explizite) Verfahren höherer Ordnung zu entwickeln. Durch Arbeiten bis in die 1970er Jahre wurde klar, dass gewisse der bis dahin entwickelten expliziten Verfahren von bis zu 7. Ordnung die kleinstmögliche Anzahl an Stufen aufwiesen. Ergebnisse von Butcher zeigten, dass dabei für <math>p\geq 7</math> mindestens <math>p+2</math> Stufen notwendig waren.<ref name="Butcher1965" details="Theorem 2, S. 410"/><ref name="Butcher1975">John C. Butcher: An order bound for Runge-Kutta methods. In: SIAM Journal on Numerical Analysis. Bd. 12, 1975, S. 304—315. doi:10.1137/0712025</ref> Für die Ordnung 8 wurden zu Beginn der 1970er Jahre von Curtis<ref name="Curtis1970"/> und Cooper und Verner<ref name="CooperVerner1972"/> Verfahren mit 11 Stufen vorgestellt, wobei die optimale Stufenanzahl solcher Verfahren noch 1978<ref name="Hairer1978" details="S. 47"/> mit 10 oder 11 unklar war. Curtis veröffentlichte 1975 ein Verfahren der Ordnung 10 mit 18 Stufen.<ref name="Curtis1975">A. R. Curtis: High-order explicit Runge-Kutta formulae, their uses, and limitations. In: Journal of the Institute of Mathematics and its Applications. Bd. 16, Nr. 1, 1975, S. 35–55.</ref> Ernst Hairer verbesserte dieses Ergebnis 1978 durch ein Verfahren 10. Ordnung mit nur 17 Stufen,<ref name="Hairer1978" details="S. 48, 2. Absatz; Tab. 3, S. 57—58/> wie Butcher schreibt, „using an ingenious combination of various simplifying assumptions“<ref name="Butcher2016" details="S. 210"/>. Die Optimalität der Stufenanzahl 17 ist für diesen Fall noch heute unbekannt (Publikationsjahr 2016);<ref name="Butcher2016" details="S. 210"/> die Optimalität der Verfahren 8. Ordnung von Curtis und Cooper—Verner in Bezug auf die Stufenanzahl wurde hingegen 1985 von Butcher schließlich bestätigt.<ref name="Butcher1985" details="Corollary, S. 521"/> 2006 wurde, basierend auf Hairers 17-stufigem Verfahren, von Ono ein 25-stufiges Verfahren der Ordnung 12 publiziert.<ref name="Ono2006">Hiroshi Ono: On the 25 stage 12th order explicit Runge–Kutta method. In: Journal of the Japanese Society of Applied Mathematics. Bd. 16, Nr. 3, 2006, S. 177—186. doi:10.11540/jsiamt.16.3_177</ref>

Beispiele

Das explizite Euler-Verfahren (Ordnung 1)<ref name="Schwarz" details="S. 359 (9.4)">Hans Rudolf Schwarz: Numerische Mathematik. 2., durchgesehene Auflage. B. G. Teubner, Stuttgart 1988, ISBN 3-519-12960-4</ref><ref name="Butcher2016" details="S. 185"/>:

<math>\begin{array}{c|c} 0 \\ \hline & 1 \end{array}</math>

Das implizite Euler-Verfahren (Ordnung 1):

<math>\begin{array}{c|c} 1 & 1 \\ \hline & 1 \end{array}</math>

Das Heun-Verfahren (Ordnung 2)<ref name="Schwarz" details="S. 371 (9.37)"/><ref name="Butcher2016" details="S. 193, c₂=1"/>:

<math>\begin{array}{c|cc} 0 \\ 1 & 1 \\ \hline & \frac{1}{2} & \frac{1}{2} \end{array}</math>

Das Runge-Kutta-Verfahren der Ordnung 2, auch verbesserte Polygonzugmethode<ref name="Schwarz" details="S. 367 (9.29)"/><ref name="Butcher2016" details="S. 193, c₂=½"/>:

<math>\begin{array}{c|cc} 0 \\ \frac{1}{2} & \frac{1}{2} \\ \hline & 0 & 1 \end{array}</math>

Das implizite Trapez-Verfahren der Ordnung 2<ref name="Schwarz" details="S. 368 (9.33)"/>:

<math>\begin{array}{c|cc} 0 \\ 

               1 & \frac{1}{2} & \frac{1}{2} \\

\hline & \frac{1}{2} & \frac{1}{2} \end{array}</math>

Das Runge-Kutta-Verfahren der Ordnung 3 (vgl. Simpsonregel), auch Methode von Kutta dritter Ordnung<ref name="Schwarz" details="S. 375 (9.47)"/>:

<math>\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}</math>

Das Heun-Verfahren 3. Ordnung<ref name="Schwarz" details="S. 375 (9.46)"/>:

<math>\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}</math>

Das klassische Runge-Kutta-Verfahren (Ordnung 4)<ref name="Schwarz" details="S. 379 (9.52)"/><ref name="Butcher2016" details="S. 194"/>:

<math>\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}</math>

Das Verfahren von Kutta 4. Ordnung (vgl. 3/8-Regel)<ref name="Schwarz" details="S. 379 (9.53)"/><ref name="Butcher2016" details="S. 193"/>:

<math>\begin{array}{c|cccc} 0 & & & & \\ 

               \frac{1}{3} & \frac{1}{3} & & & \\
               \frac{2}{3} & -\frac{1}{3} &1 & & \\
               1 & 1 & -1 & 1 &  \\

\hline & \frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8} \end{array}</math>

Das sechsstufige Verfahren von Kutta-Nyström der Ordnung 5<ref name="Butcher2016" details="S. 205"/> (die Anzahl der Stufen ist für diese Ordnung optimal<ref name="Butcher2016" details="Theorem 324B, S. 201"/><ref name="Butcher1965" details="Theorem 1, S. 410"/>):

<math>\begin{array}{c|cccccc} 

0 & & & & \\
\frac{1}{3} & \frac{1}{3} \\
\frac{2}{5} & \frac{4}{25}& \frac{6}{25} \\
1 & \frac{1}{4} & -3 & \frac{15}{4} \\
\frac{2}{3}&\frac{2}{27}&\frac{10}{9}&-\frac{50}{81}&\frac{8}{81}\\
\frac{4}{5}&\frac{2}{25}&\frac{12}{25}&\frac{2}{15}&\frac{8}{75}&0\\

\hline & \frac{23}{192} &0& \frac{125}{192}&0 & -\frac{27}{64} & \frac{125}{192} \end{array}</math>

Bei Butcher<ref name="Butcher2016" details="S. 209">John C. Butcher: Numerical Methods for Ordinary Differential Equations. 3. Auflage. John Wiley & Sons Ltd., Chichester 2016, ISBN 978-1-119-12150-3</ref> findet man auch das folgende explizite neunstufige Verfahren der Ordnung 7 (weniger Stufen sind nach einer Arbeit von Butcher aus dem Jahr 1965<ref name="Butcher1965" details="Theorem 2, S. 410">John C. Butcher: On the attainable order of Runge-Kutta methods. In: Mathematics of Computation. Bd. 19, Nr. 91, 1965, S. 408–417. doi:10.1090/S0025-5718-1965-0179943-X</ref> zur Erreichung dieser Ordnung nicht möglich<ref name="Butcher2016" details="S. 202, 1. Absatz"/>):

<math>\begin{array}{c|ccccccccc} 

0& & & & \\
\frac{1}{6} & \frac{1}{6} \\
\frac{1}{3} & 0& \frac{1}{3}\\
\frac{1}{2} & \frac{1}{8}& 0& \frac{3}{8}\\
\frac{2}{11}& \frac{148}{1331}& 0& \frac{150}{1331}& -\frac{56}{1331}\\
\frac{2}{3} & -\frac{404}{243}& 0&-\frac{170}{27}&\frac{4024}{1701}&\frac{10648}{1701}\\
\frac{6}{7} & \frac{2466}{2401}&0&\frac{1242}{343}&-\frac{19176}{16807}&-\frac{51909}{16807}&\frac{1053}{2401}\\
         0  & \frac{5}{154}&0&0&\frac{96}{539}&-\frac{1815}{20384}&-\frac{405}{2464}&\frac{49}{1144}\\
         1  & -\frac{113}{32}&0&-\frac{195}{22}&\frac{32}{7}&\frac{29403}{3584}&-\frac{729}{512}&\frac{1029}{1408}&\frac{21}{16}\\

\hline & 0&0&0&\frac{32}{105}&\frac{1771561}{6289920}&\frac{243}{2560}&\frac{16807}{74880}&\frac{77}{1440}&\frac{11}{270} \end{array}</math>

Literatur

  • Peter Albrecht: The Runge-Kutta Theory in a Nutshell. In: SIAM Journal on Numerical Analysis. 33, 5, October 1996, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0036-1429|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1 

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0 

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0036-1429}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, 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. Band 1: Anfangswertprobleme und lineare Randwertprobleme. Walter de Gruyter Verlag, Berlin und Boston 2017, ISBN 978-3-11-050036-3.
  • M. Sofroniou: Symbolic Derivation of Runge-Kutta Methods. In: Journal of Symbolic Computation. 18, 3, September 1994, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0747-7171|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1 

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0 

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0747-7171}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, 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

Einzelnachweise

<references />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Runge-Kutta-Verfahren&oldid=62319#Butcher-Tableau“