Kurs:Gewöhnliche Differentialgleichungen/Herleitung der Runge-Kutta Verfahren

Herleitung der Runge-Kutta-Verfahren

Die Runge-Kutta Verfahren werden im Hinblick auf ihre Konsistenzordnung konstruriert, d.h. die Koeffizientenmatrix ${\textstyle A}$ und die Vektoren ${\textstyle {\vec {b}},{\vec {c}}}$ werden so gesucht, dass der lokale Diskretisierungsfehler möglichst klein ist.

In Analogie zu Definition 3.2 des lokalen Fehlers des ESV im Kapitel 3, kann auch der lokale Abschneidefehler (Diskretisierungsfehler) und anschließend die Konsistenz der Runge-Kutta Verfahren definiert werden.

---

Definition 4.2. (Konsistenzordnung der RKV)

Sei ${\textstyle f(t,y)}$ eine hinreichend oft stetig differenzierbare Funktion. Ein Runge-Kutta Verfahren hat die Konsistenzordnung $p$, wenn $\|h\tau (t;h)\|=:\|\varepsilon (t;h)\|=\|y(t+h)-y(t)-h\phi (t,y,f,h)\|\leq Ch^{p+1},\ C\in {\mathbb {R} },$$\qquad (4.3)$

wobei hier ${\textstyle \varepsilon (t;h)}$ den Unterschied zwischen der exakten Lösung und der numerischen Lösung, ausgehend aus der exakten Lösung, an der Stelle ${\textstyle t+h}$ beschreibt. ${\textstyle \|\cdot \|}$ bezeichnet die Euklid Norm auf ${\textstyle {\mathbb {R} }^{n}}$, bzw. den Betrag.

---

Um die Konsistenzordnung eines allgemeinen RKV zu untersuchen, werden wir im Folgenden den lokalen Diskretisierungsfehler ${\textstyle \tau (t;h)={\frac {1}{h}}(y(t+h)-y(t))-\phi (t,y,f,h)}$ betrachten. Für eine vorher gegebene Konsistenzordnung ${\textstyle p}$ werden wir Taylorreihen von ${\textstyle y(t+h)}$ und ${\textstyle \phi (t,y,f,h)}$ bis zum Glied mit ${\textstyle h^{p}}$ in ${\textstyle \tau }$ einsetzen.

Im ersten Beispiel wird demonstriert, welche Konsistenzordnung generell ein zweistufiges explizites Runge-Kutta Verfahren maximal erreichen kann. Die Konvergenz und die Konvergenzordnung der RKV wird anhand der Definition 3.5 und des Kriteriums der Konvergenz für allgemeine Einschrittverfahren ( Satz 3.1, also im Wesetlichen durch den Nachweis der Lipschitz -Stetigkeit der Verfahrensfunktion ${\textstyle \phi }$) bestimmt.

Beispiel 4.2. Bestimmen Sie ein 2-stufiges explizites Runge-Kutta Verfahren für die Anfangswertaufgabe (1.6) mit ${\textstyle c_{1}=0}$.
Da es sich um ein eRKV handelt, ist die Matrix ${\textstyle A}$ eine untere Dreiecksmatrix. Somit ist ${\textstyle a_{11}=a_{12}=a_{22}=0}$ und es sind lediglich vier Unbekannte ${\textstyle a_{21},\ b_{1},\ b_{2}}$ und ${\textstyle c_{2}}$ zu bestimmen:

Angenommen, ${\textstyle f\in C^{2}([0,T]\times D)}$ und damit ${\textstyle y\in C^{3}[0,T]}$. Die Konsistenzordnung bestimmen wir mithilfe der Taylorreihen um ${\textstyle h=0}$:

• Taylorentwicklung von ${\textstyle y(t+h)}$: Ähnlich wie im Beispiel (3.5) erhalten wir
  $$y(t+h)=y(t)+hy'(t)+{\frac {h^{2}}{2}}y''(t)+{\frac {h^{3}}{3!}}y'''(t)+{\frac {h^{4}}{4!}}y^{(IV)}(\theta ),\ \theta \in (t,t+h).$$
  Mit Anwendung von (3.14) und (3.15) erhalten wir somit für den ersten Teil des lokalen Fehlers
  

$${\begin{aligned}{\frac {y(t+h)-y(t)}{h}}&=y'(t)+{\frac {h}{2}}y''(t)+{\frac {h^{2}}{6}}y'''(t)+{\cal {O}}(h^{3})\\&=f(t,y(t))+{\frac {h}{2}}{\big (}f_{t}+ff_{y}{\big )}(t,y(t))\\&\quad +{\frac {h^{2}}{6}}{\big (}f_{tt}+2f_{ty}f+f_{y}f_{t}+f_{yy}f^{2}+(f_{y})^{2}f{\big )}(t,y(t))+{\cal {O}}(h^{3})\end{aligned}}$$

• Taylorentwicklung in Verfahrensfunktion ${\textstyle \phi (t,y,h,f)}$ anwenden:
  $${\begin{aligned}\phi (t,y,h,f)&=b_{1}k_{1}+b_{2}k_{2}=b_{1}f(t,y(t))+b_{2}f{\Big (}t+c_{2}h,y(t)+ha_{21}f{\big (}t,y(t){\big )}{\Big )}\\&{\stackrel {Taylor}{=}}b_{1}f(t,y)+b_{2}{\Big [}f(t,y)+{\big (}f_{t}(t,y)c_{2}h+f_{y}(t,y)a_{21}hf(t,y){\big )}\\&\quad +{\frac {1}{2!}}{\Big (}f_{tt}(t,y)c_{2}^{2}h^{2}+2f_{ty}(t,y)c_{2}h^{2}a_{21}f(t,y)+f_{yy}(t,y)h^{2}a_{21}^{2}f^{2}(t,y){\Big )}{\Big ]}+{\cal {O}}(h^{3})\end{aligned}}$$

Nach dem Einsetzen der Taylorreihen (des Differenzenquotienten von ${\textstyle y(t)}$ und in ${\textstyle \phi }$) in den Ausdruck von ${\textstyle \tau (t;h)}$, und nach dem Einordnen der entsprechenden Potenzen von ${\textstyle h}$, erhalten wir für den lokalen Fehler

$${\begin{aligned}\tau (t;h)&=(1-b_{1}-b_{2})f(t,y)+{\frac {h}{2}}{\Big (}{\big (}1-2c_{2}b_{2})f_{t}(t,y)+{\big (}1-2a_{21}b_{2})ff_{y}(t,y){\Big )}\\&+{\frac {h^{2}}{6}}{\Big (}(1-3c_{2}^{2}b_{2})f_{tt}(t,y)+2(1-3c_{2}a_{21}b_{2})f_{ty}f(t,y)+(1-3a_{21}^{2}b_{2})f_{yy}f^{2}(t,y)\\&+(f_{y})^{2}f(t,y)+f_{t}f_{y}(t,y){\Big )}+{\cal {O}}(h^{3}).\end{aligned}}$$

Durch eine geeignete Wahl der Koeffizienten ${\textstyle a_{21},\ b_{1},\ b_{2}}$ und ${\textstyle c_{2}}$ können die Ausdrücke bei den Potenzen ${\textstyle h^{0},\ h^{1}}$ und zum Teil bei ${\textstyle h^{2}}$ im Diskretisierungsfehler ${\textstyle \tau }$ verschwinden. Wir stellen Folgendes fest:

• Ein konsistentes eRKV, d. h. mit ${\textstyle \tau \to 0}$ für ${\textstyle h\to 0}$ ergibt sich bei der Wahl von ${\textstyle b_{1},b_{2}}$ mit ${\textstyle b_{1}+b_{2}=1}$.
• Für die letzten zwei Terme bei ${\textstyle h^{2}}$ gilt im Allgemeinen, dass ${\textstyle (f_{y})^{2}f(t,y)\neq 0,\ f_{t}f_{y}(t,y)\neq 0}$, daher ist die dritte Konsistenzordnung bei diesem Verfahren nicht möglich.

Wir haben gezeigt, dass bei einem expliziten RKV zweiter Stufe die maximale Konsistenzordnung zwei ist. Für die erste bzw. die zweite Konsistenzordnung müssen folgende Bedingungen an die Verfahrenskoeffizienten erfüllt werden:

$${\begin{aligned}&&\ \ \ b_{1}+b_{2}=1\quad \}\quad {\mbox{Konsistenz, 1. Ordnung}}\\&&\left.{\begin{matrix}1-2c_{2}b_{2}&=0\\1-2a_{21}b_{2}&=0\end{matrix}}\quad \right\}\quad {\mbox{ 2. Ordnung}}.\end{aligned}}$$

Dieses System von drei Gleichungen enthält vier Unbekannte, es existieren also unzählige Möglichkeiten für die Verfahrenskoeffizienten eines 2-stufigen eRKV zweiter Konsistenzordnung. Wählt man ${\textstyle b_{2}}$ als Parameter, erhält man

$$b_{1}=1-b_{2},\quad c_{2}=a_{21}={\frac {1}{2b_{2}}}.$$

1. Die Wahl ${\textstyle b_{2}=1}$ führt zur expliziten Mittelpunktregel (sog. verbesserters Eulerverfahren).
2. Im Fall ${\textstyle b_{2}={\frac {1}{2}}}$ erhalten wir die explizite Trapezregel (sog. Verfahren von Heun 2. Ordnung).
3. Bei der Wahl ${\textstyle b_{2}={\frac {3}{4}}}$ stellt man schnell fest, dass für die ersten drei Terme bei ${\textstyle h^{2}}$ mit den Koeffizienten (da ${\textstyle c_{2}=a_{21}}$)
   $$1-3c_{2}^{2}b_{2}=1-3c_{2}a_{21}b_{2}=1-3a_{21}^{2}b_{2}\equiv 0$$
   gilt. Damit ist der führende Fehlerkoeffizient im lokalen Diskretisierungsfehler dieses Verfahrens (hier der Koeffizient bei ${\textstyle h^{2}}$) enthalten und somit auch der Fehler minimal. Dies ist
   $$\tau (t,h)={\frac {h^{2}}{6}}{\Big (}(f_{y})^{2}f(t,y)+f_{t}f_{y}(t,y){\Big )}+{\cal {O}}(h^{3}){\stackrel {}{=}}{\frac {h^{2}}{6}}{\Big (}(f_{y})^{2}f(\theta ,y(\theta ))+f_{t}f_{y}(\theta ,y(\theta )){\Big )}$$
   für ein ${\textstyle \theta \in (t,t+h)}$. Nach Voraussetzungen sind die Ableitungen von ${\textstyle f}$ gleichmäßig beschränkt auf ${\textstyle [0,t]\times D}$ und wir erhalten hiermit ein - im Sinne des kleinesten lokalen Fehlers - optimales Verfahren zweiter Konsistenzordnung mit
   $$\tau (t,h)\leq Ch^{2},\quad {\mbox{wobei}}\ C:=\max _{t}{\frac {|f_{t}f_{y}|+|f(f_{y})^{2}|}{6}}.$$

Um die Konvergenzordnung 2 des zweistufigen eRKV zu garantieren, muss noch die
Lipschitz-Stetigkeit der Verfahrensfunktion bezüglich ${\textstyle y}$ erfüllt werden. In folgender Rechnung wird nachgewiesen, dass dies eine Folgerung aus der Lipschitz-Stetigkeit von ${\textstyle f}$ ist. Diese Aussage lässt sich verallgemeinern. Man kann die Lipschitz-Stetigkeit der Verfahrensfunktion ${\textstyle \phi }$ für alle expliziten wie auch impliziten Runge-Kutta Verfahren aus der ${\textstyle L}$-Stetigkeit von ${\textstyle f}$ herleiten.

Angenommen, ${\textstyle m=1}$ und ${\textstyle \eta _{i}^{(1)\ (2)}}$ sind zwei numerische Lösungen der AWA (1.6) in ${\textstyle t_{i}}$.
Für den Unterschied der Verfahrensfunktion des untersuchten zweistufigen eRKV gilt:

$${\begin{aligned}&&k_{1}=f(t_{i},\eta _{i}^{(r)}),\ r=1,2\\&&k_{2}=f{\big (}t_{i}+c_{2}{h},\eta _{i}^{(r)}+a_{21}hk_{1}{\big )}\quad i=0,1\ldots N_{h}-1\\&&{\big |}\Phi (t_{i},\eta _{i}^{(1)},\ldots )-\Phi (t,\eta _{i}^{(2)},\ldots ){\big |}={\Big |}b_{1}f(t_{i},\eta _{i}^{(1)})+b_{2}f(t_{i}+c_{2}h,\eta _{i}^{(1)}+a_{21}h\underbrace {f(t_{i},\eta _{i}^{(1)})} _{k_{1}})\\&&\qquad \qquad \qquad \qquad \qquad \qquad \qquad -b_{1}f(t_{i},\eta _{i}^{(2)})-b_{2}f(t_{i}+c_{2}h,\eta _{i}^{(2)}+a_{21}hf\underbrace {(t_{i},\eta _{i}^{(2)})} _{k_{1}}){\Big |}\\&&\qquad \qquad (f(t,\eta )\ {\mbox{-L-stetig in }}\eta \ {\mbox{mit Konstante }}L)\\&&\qquad \leq |b_{1}|L|\eta _{i}^{(1)}-\eta _{i}^{(2)}|+|b_{2}|L{\Big |}\eta _{i}^{(1)}+a_{21}hf(t_{i},\eta _{i}^{(1)})-\eta _{i}^{(2)}-a_{21}hf(t_{i},\eta _{i}^{(2)}){\Big |}\\&&\qquad \leq (|b_{1}|+|b_{2}|)L|\eta _{i}^{(1)}-\eta _{i}^{(2)}|+|b_{2}a_{21}|Lh\underbrace {|f(t_{i},\eta _{i}^{(1)})-f(t_{i},\eta _{i}^{(2)})|} _{f\ L-stetig\ in\ \eta }\\&&\qquad \qquad (f(t,\eta )\ {\mbox{ist L-stetig in }}\eta )\\&&\qquad \leq (|b_{1}|+|b_{2}|)L|\eta _{i}^{(1)}-\eta _{i}^{(2)}|+|b_{2}a_{21}|LhL|\eta _{i}^{(1)}-\eta _{i}^{(2)})|\\&&\qquad \leq {\Big [}\underbrace {(|b_{1}|+|b_{2}|)L+|b_{2}a_{21}|hL^{2}} _{:=M}{\Big ]}|\eta _{i}^{(1)}-\eta _{i}^{(2)})|=M|\eta _{i}^{(1)}-\eta _{i}^{(2)})|,\end{aligned}}$$

wobei hier die Dreiecksungleichung für den Betrag mehrfach verwendet wurde.

In der obigen Rechnung haben wir gezeigt, dass die Verfahrensfunktion ${\textstyle \phi }$ des untersuchten eRKV Lipschitz-Stetig bezüglich ${\textstyle \eta }$ ist, wobei hier die Lipschitz-Konstante ${\textstyle M=(|b_{1}|+|b_{2}|)L+|b_{2}a_{21}|hL^{2}<\infty }$ abgeleitet von der ${\textstyle L}$-Konstanten der Funktion ${\textstyle f}$ ist. Somit ist das explizite 2-stufige Runge-Kutta Verfahren konvergent mit der Konvergenzordnung 2 und es kann keine höhere Konvergenzordnung erreicht werden. ${\textstyle \diamond }$ In vorherigen Beispiel haben wir gesehen, dass die zweite Konsistenz - und Konvergenzordnung bei einem 2-stufigen expliziten Runge-Kutta Verfahren erreichbar ist. Diese Analogie gilt allerdings im Allgemeinen nicht für alle eRKV. Es gilt nicht, dass mit ${\textstyle s}$ Stufen die Konsistenzordnung ${\textstyle s}$ erreichbar ist. Dies wird später mit einem Satz referenziert. Für implizite RKV ist die Situation anders, da Matrix ${\textstyle A}$ voll besetzt werden kann und somit gibt es mehrere Möglichkeiten für die Verfahrenskoeffizienten, um eine höhere Konsistenzordnung zu erreichen.

Bemerkung 4.2.

Für die Koeffizienten eines eRKV gilt Folgendes:

1. Die Konsistenzordnung ${\textstyle p}$ ist allgemein mit ${\textstyle s\geq p}$ Stufen erreichbar.
2. Für die feste Konsistenzordnung besteht die Möglichkeiten für die Wahl der Koeffizienten ${\textstyle A,{\vec {b}},{\vec {c}}}$. Somit existieren mehrere eRKV mit gleicher Konsistenzordnung oder gleicher Stufenanzahl.

Analog wie im Beispiel 4.2 lässt sich folgendes Gleichungssystem für die Koeffizienten eines eRKV mit ${\textstyle s=4}$ Stufen und ${\textstyle c_{1}=0}$ herleiten, ${\begin{aligned}b_{1}+b_{2}+b_{3}+b_{4}&=1\quad \}\quad {\mbox{Konsistenz, 1. Ordnung,}}\\c_{2}b_{2}+c_{3}b_{3}+c_{4}b_{4}&={\frac {1}{2}}\quad \}\quad \quad {\mbox{ 2. Ordnung,}}\\&\left.{\begin{matrix}c_{2}^{2}b_{2}+c_{3}^{2}b_{3}&={\frac {1}{3}}\\b_{3}c_{2}a_{32}+b_{4}c_{2}a_{42}+b_{4}c_{3}a_{43}&={\frac {1}{6}}\end{matrix}}\quad \right\}\quad \quad {\mbox{ 3. Ordnung.}}\end{aligned}}$ $\qquad (4.4)$