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 $A$ und die Vektoren $\overrightarrow{b},\overrightarrow{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 $f(t,y)$ eine hinreichend oft stetig differenzierbare Funktion. Ein Runge-Kutta Verfahren hat die Konsistenzordnung $p$, wenn $\Vert h\tau (t;h)\Vert =:\Vert \epsilon (t;h)\Vert =\Vert y(t+h)-y(t)-h\varphi (t,y,f,h)\Vert \le C{h}^{p+1},C\in ℝ,$$(4.3)$

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

---

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

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

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

• Taylorentwicklung von $y(t+h)$: Ähnlich wie im Beispiel (3.5) erhalten wir $$y(t+h)=y(t)+h{y}^{\prime }(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{array}{cc}\frac{y(t+h)-y(t)}{h}& =y^{\prime }(t)+\frac{h}{2}{y}^{″}(t)+\frac{h^2}{6}{y}^{‴}(t)+𝒪(h^3)\\ & =f(t,y(t))+\frac{h}{2}(f_t+f{f}_y)(t,y(t))\\ & +\frac{h^2}{6}(f_{tt}+2f_{ty}f+f_y{f}_t+f_{yy}{f}^2+(f_y{)}^{2}f)(t,y(t))+𝒪(h^3)\end{array}$$

• Taylorentwicklung in Verfahrensfunktion $\varphi (t,y,h,f)$ anwenden: $$\begin{array}{cc}\varphi (t,y,h,f)& =b_1{k}_1+b_2{k}_2=b_{1}f(t,y(t))+b_{2}f(t+c_{2}h,y(t)+h{a}_{21}f(t,y(t)\left)\right)\\ & \stackrel{Taylor}{=}{b}_{1}f(t,y)+b_2[f(t,y)+(f_t(t,y)c_{2}h+f_y(t,y)a_{21}hf(t,y))\\ & +\frac{1}{2!}(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))]+𝒪(h^3)\end{array}$$

Nach dem Einsetzen der Taylorreihen (des Differenzenquotienten von $y(t)$ und in $\varphi$) in den Ausdruck von $\tau (t;h)$, und nach dem Einordnen der entsprechenden Potenzen von $h$, erhalten wir für den lokalen Fehler $$\begin{array}{cc}\tau (t;h)& =(1-b_1-b_2)f(t,y)+\frac{h}{2}\left(\right(1-2c_2{b}_2)f_t(t,y)+(1-2a_{21}{b}_2)f{f}_y(t,y))\\ & +\frac{h^2}{6}((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))+𝒪(h^3).\end{array}$$

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

• Ein konsistentes eRKV, d. h. mit $\tau \to 0$ für $h\to 0$ ergibt sich bei der Wahl von $b_1,b_2$ mit $b_1+b_2=1$.
• Für die letzten zwei Terme bei $h^2$ gilt im Allgemeinen, dass $(f_y{)}^{2}f(t,y)\ne 0,f_t{f}_y(t,y)\ne 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{array}{ccc}& & b_1+b_2=1\}\text{Konsistenz, 1. Ordnung}\\ & & \begin{array}{cc}1-2c_2{b}_2& =0\\ 1-2a_{21}{b}_2& =0\end{array}\}\text{ 2. Ordnung}.\end{array}$$

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 $b_2$ als Parameter, erhält man $$b_1=1-b_2,c_2=a_{21}=\frac{1}{2b_2}.$$

1. Die Wahl $b_2=1$ führt zur expliziten Mittelpunktregel (sog. verbesserters Eulerverfahren).
2. Im Fall $b_2=\frac{1}{2}$ erhalten wir die explizite Trapezregel (sog. Verfahren von Heun 2. Ordnung).
3. Bei der Wahl $b_2=\frac{3}{4}$ stellt man schnell fest, dass für die ersten drei Terme bei $h^2$ mit den Koeffizienten (da $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 $h^2$) enthalten und somit auch der Fehler minimal. Dies ist $$\tau (t,h)=\frac{h^2}{6}((f_y{)}^{2}f(t,y)+f_t{f}_y(t,y))+𝒪(h^3)\stackrel{}{=}\frac{h^2}{6}((f_y{)}^{2}f(\theta ,y(\theta ))+f_t{f}_y(\theta ,y(\theta )))$$ für ein $\theta \in (t,t+h)$. Nach Voraussetzungen sind die Ableitungen von $f$ gleichmäßig beschränkt auf $[0,t]\times D$ und wir erhalten hiermit ein - im Sinne des kleinesten lokalen Fehlers - optimales Verfahren zweiter Konsistenzordnung mit $$\tau (t,h)\le C{h}^2,\text{wobei}C:=\underset{t}{\max }\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 $y$ erfüllt werden. In folgender Rechnung wird nachgewiesen, dass dies eine Folgerung aus der Lipschitz-Stetigkeit von $f$ ist. Diese Aussage lässt sich verallgemeinern. Man kann die Lipschitz-Stetigkeit der Verfahrensfunktion $\varphi$ für alle expliziten wie auch impliziten Runge-Kutta Verfahren aus der $L$-Stetigkeit von $f$ herleiten.

Angenommen, $m=1$ und ${\eta }_i^{(1)(2)}$ sind zwei numerische Lösungen der AWA (1.6) in $t_i$.
Für den Unterschied der Verfahrensfunktion des untersuchten zweistufigen eRKV gilt: $$\begin{array}{ccc}& & k_1=f(t_i,{\eta }_i^{(r)}),r=1,2\\ & & k_2=f(t_i+c_{2}h,{\eta }_i^{(r)}+a_{21}h{k}_1)i=0,1\dots N_h-1\\ & & |\mathrm{\Phi }(t_i,{\eta }_i^{(1)},\dots )-\mathrm{\Phi }(t,{\eta }_i^{(2)},\dots )|=|b_{1}f(t_i,{\eta }_i^{(1)})+b_{2}f(t_i+c_{2}h,{\eta }_i^{(1)}+a_{21}h\underset{k_1}{\underbrace{f(t_i,{\eta }_i^{(1)})}})\\ & & -b_{1}f(t_i,{\eta }_i^{(2)})-b_{2}f(t_i+c_{2}h,{\eta }_i^{(2)}+a_{21}hf\underset{k_1}{\underbrace{(t_i,{\eta }_i^{(2)})}})|\\ & & (f(t,\eta )\text{-L-stetig in }\eta \text{mit Konstante }L)\\ & & \le |b_1|L|{\eta }_i^{(1)}-{\eta }_i^{(2)}|+|b_2|L|{\eta }_i^{(1)}+a_{21}hf(t_i,{\eta }_i^{(1)})-{\eta }_i^{(2)}-a_{21}hf(t_i,{\eta }_i^{(2)})|\\ & & \le (|b_1|+|b_2|)L|{\eta }_i^{(1)}-{\eta }_i^{(2)}|+|b_2{a}_{21}|Lh\underset{fL-stetigin\eta }{\underbrace{|f(t_i,{\eta }_i^{(1)})-f(t_i,{\eta }_i^{(2)})|}}\\ & & (f(t,\eta )\text{ist L-stetig in }\eta )\\ & & \le (|b_1|+|b_2|)L|{\eta }_i^{(1)}-{\eta }_i^{(2)}|+|b_2{a}_{21}|LhL|{\eta }_i^{(1)}-{\eta }_i^{(2)})|\\ & & \le \left[\underset{:=M}{\underbrace{(|b_1|+|b_2|)L+|b_2{a}_{21}|h{L}^2}}\right]|{\eta }_i^{(1)}-{\eta }_i^{(2)})|=M|{\eta }_i^{(1)}-{\eta }_i^{(2)})|,\end{array}$$ wobei hier die Dreiecksungleichung für den Betrag mehrfach verwendet wurde.

In der obigen Rechnung haben wir gezeigt, dass die Verfahrensfunktion $\varphi$ des untersuchten eRKV Lipschitz-Stetig bezüglich $\eta$ ist, wobei hier die Lipschitz-Konstante $M=(|b_1|+|b_2|)L+|b_2{a}_{21}|h{L}^2<\mathrm{\infty }$ abgeleitet von der $L$-Konstanten der Funktion $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. $\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 $s$ Stufen die Konsistenzordnung $s$ erreichbar ist. Dies wird später mit einem Satz referenziert. Für implizite RKV ist die Situation anders, da Matrix $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 $p$ ist allgemein mit $s\ge p$ Stufen erreichbar.
2. Für die feste Konsistenzordnung besteht die Möglichkeiten für die Wahl der Koeffizienten $A,\overrightarrow{b},\overrightarrow{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 $s=4$ Stufen und $c_1=0$ herleiten, $\begin{array}{cc}{b}_1+b_2+b_3+b_4& =1\}\text{Konsistenz, 1. Ordnung,}\\ c_2{b}_2+c_3{b}_3+c_4{b}_4& =\frac{1}{2}\}\text{ 2. Ordnung,}\\ & \begin{array}{cc}{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{array}\}\text{ 3. Ordnung.}\end{array}$ $(4.4)$