Kurs:Gewöhnliche Differentialgleichungen/4.1 Ordnungsbedingungen für Runge-Kutta Verfahren

Ordnungsbedingungen für Runge-Kutta Verfahren

Bislang haben wir für explizite Runge-Kutta Verfahren immer vorausgesetzt, dass $c_1=0$. Diese Bedingung ist nicht willkürlich gewählt, sondern folgt aus einer bestimmten Forderung an die Zwischenstufen $k_j$. Wie wir in folgendem Absatz sehen werden, sichert eine solche Forderung die Exaktheit der RKV für lineare Funktionen $y(t)$. Das bedeutet, dass die numerische Lösung des RKV von $y^{\prime }=konst$, die an den Gitterpunkten vorliegt, mit keinem Diskretisierungsfehler behaftet ist. Somit ist sie exakt gleich der analytischen Lösung.

Im Hinblick auf die Konsistenzordnung stellen wir weitere (nichtlineare) Gleichungssysteme für die Runge-Kutta Koeffizienten auf (vergleiche (4.4)), sog. Ordnungsbedingungen. Die Ordnungsbedingungen werden auch in Matrixform anhand der Matrix $A$ und der Vektoren $\overrightarrow{b},\overrightarrow{c}$ im Allgemeinen und ohne Unterscheidung zwischen expliziten und impliziten RKV formuliert.

Zu diesem Zweck untersuchen wir eine einfache AWA $$\begin{array}{c}{y}^{\prime }(t)=1\\ y(t_0)=y_0\end{array}(4.5)$$

mit der analytischen Lösung als lineare Funktion $y(t)=t+y_0-t_0$.

Wir stellen folgende Forderungen an ein RKV:

(A) Ein RKV liefert für lineare Lösungen $y(t)$ exakte Ergebnisse.

Da in (4.5) für $k_i=f(t+c_{j}h,y+\dots )=1$ gilt, bedeuet es im Falle einer Differentialgleichung ($m=1$) nach dem Einsetzen der linearen Funktion $y(t)$: $$\begin{array}{cc}0& \stackrel{!}{=}|\epsilon (t,h)|=|h\tau (t,h)|=|y(t+h)-y(t)-h\varphi (t,y,h,f)|\\ & =|t+h-y_0-t_0-(t-y_0-t_0)-h\sum _{j=1}^s{b}_j{k}_j|=|h-h\sum _{j=1}^s{b}_{j}1|=h|1-\sum _{j=1}^s{b}_j|.\end{array}$$

Damit folgt aus der Bedingung (A) für lineare Lösungen die erste Bedingung an die Runge-Kutta Koeffizienten: $$\sum _{j=1}^s{b}_j=1.(4.6)$$

Hier weisen wir darauf hin, dass diese Bedingung im Falle einer allgemeinen Anfangswertaufgabe aus der Konsistenzforderung abgeleitet wurde, was in Beispiel 4.2 anhand der Taylorentwicklung demonstriert wurde. Daher gilt für RKV, dass die Konsisenzbedinung äquivalent zur Exakheit für lineare Funktionen ist.

(B) Forderung an die Zwischenstufen $k_j$ der RKV:

Wie am Anfang dieses Kapiels erwähnt, approximieren die $k_j$ die Ableitungen der gesuchten Funktion an den Stützstellen, $k_j\approx y^{\prime }(t_i+h{c}_j).$ Nun wird für lineare Funktionen gefordert, dass sie nicht nur die Ableitungen von $y$ an den Zwischenstufen $t+c_{j}h$ approximieren, sondern mit ihnen Übereinstimmen, also dass $$k_j=f(t+c_{j}h,y(t)+h\sum _{m=1}^s{a}_{jm}{k}_m)\stackrel{!}{=}{y}^{\prime }(t+c_{j}h)$$

gilt. Wegen $y^{\prime }=f(t,y)$ erhalten wir aus dieser Bedingung $$f(t+c_{j}h,y(t)+h\sum _{m=1}^s{a}_{jm}{k}_m)\stackrel{!}{=}f(t+c_{j}h,y(t+c_{j}h)),$$

und nach Vergleich der (zweiten) Argumente der Funktion $f$ folgt schließlich für die lineare Lösung $y(t)=t+y_0-t_0$ $$y(t)+h\sum _{m=1}^s{a}_{jm}{k}_m\stackrel{!}{=}y(t+c_{j}h)=t+c_{j}h+y_0-t_0.$$

Nachdem die lineare Funktion auf der linken Seite eingesetzt wurde, und mit Hilfe von $k_m=1$ (1.6), erhalten wird die zweite Bedingung, die an die Runge-Kutta Koeffizienten gestellt wird: $$\sum _{m=1}^s{a}_{jm}{k}_m=c_j.(4.7)$$

Diese Bedingung garaniert, dass auch die Ableitungen der gesuchten linearen Funktion an den Zwischenstellen exakt berechnet werden.

Bemerkung 4.3

Im Beispiel 4.2 haben wir gesehen, dass für ein zweistufiges explizites RKV diese Bedingung ($a_{21}=c_2$) automatisch erfüllt ist, um die zweite Konsistenzordnung zu ermöglichen. Daher wird (4.7) als eine sinnvolle Bedingung für die Runge-Kutta Koeffizienten betrachtet, und im Folgenden vorausgesetzt. Damit gilt für alle von uns untersuchten RKV, dass diese exakte Ergebnisse für lineare Funktionen liefern. Die Bedingung (4.7) bedeutet, dass die Summe der $j$-ten Zeile der Matrix $A$ des Butcher-Tableaus den $j$-ten Eintrag des Vektors $\overrightarrow{c}$ ergibt. Bei expliziten RKV folgt aus dieser Bedingung, dass $c_1=0$ ist, da die erste Zeile der Matrix $A$ eine Null-Zeile ist.

Die Bedingungen (4.6), (4.7), die aus den Forderungen (A), (B) resultieren, sind Bedingungen für ein konsistentes RKV erster Ordnung. Bezeichnet man $\mathrm{𝟏}=(1,\dots ,1{)}^T$, können die Ordnungsbedingungen für RKV höherer Ordnung in folgender Matrix-Vektor-Form dargestellt werden: $${\overrightarrow{b}}^T\mathrm{𝟏}=1,A\mathrm{𝟏}=\overrightarrow{c}.$$

Dazu muss die Anfangswertaufgabe (1.6) in ihre autonome Form von $m+1$ Differentalgleichungen umgestellt werden,

$$\begin{array}{c}Y:={\left(\begin{array}{c}t\\ y(t)\end{array}\right)}^{\prime }=\left(\begin{array}{c}1\\ f(t,y(t))\end{array}\right)=:f(Y),\text{mit der Anfangsbedingung}{Y}_0:=\left(\begin{array}{c}{t}_0\\ y_0\end{array}\right).\end{array}$$

und eine mehrdimensionale Analyse durch die Taylorentwicklung muss durchgeführt werden. In [1] ist dieser Vorgang genauer erläutert.

In folgender Übersicht geben wir die Ordnungsbedingungen bis zur Konsistenszordnung vier an. Die Bedingungen für eine bestimmte Konsistenzordnung ergeben sich aus den Bedingungen für die vorherige Ordnung durch Zugabe (Zeichen $⨁$) weiterer Bedingungen.

1. Ordnung:	${\overrightarrow{b}}^T\mathrm{𝟏}=1,A\mathrm{𝟏}=\overrightarrow{c}$
2. Ordnung:	$⨁$ ${\overrightarrow{b}}^{T}A\mathrm{𝟏}={\overrightarrow{b}}^T\overrightarrow{c}={\sum }_{j=1}^s{b}_j{c}_j=\frac{1}{2}$
3. Ordnung:	$\begin{array}{c}⨁{\overrightarrow{b}}^T{A}^2\mathrm{𝟏}={\overrightarrow{b}}^{T}A\overrightarrow{c}=\sum _{j=1}^s{b}_j{a}_{jk}{c}_k=\frac{1}{6}\\ \mathrm{u}\mathrm{n}\mathrm{d}{\overrightarrow{b}}^T(A\mathrm{𝟏}{)}^2={\overrightarrow{b}}^T(\overrightarrow{c}{)}^2=\sum _{j=1}^s{b}_j{c}_j^2=\frac{1}{3}\end{array}$
4. Ordnung:	$\begin{array}{c}⨁{\overrightarrow{b}}^T[(A\mathrm{𝟏})(A{}^2\mathrm{𝟏})]={\overrightarrow{b}}^T[(\overrightarrow{c})(A\overrightarrow{c})]=\frac{1}{8}\\ \mathrm{u}\mathrm{n}\mathrm{d}{\overrightarrow{b}}^T(A\mathrm{𝟏}{)}^3={\overrightarrow{b}}^T(\overrightarrow{c}{)}^3=\frac{1}{4}\\ \mathrm{u}\mathrm{n}\mathrm{d}{\overrightarrow{b}}^{T}A(A\mathrm{𝟏}{)}^2={\overrightarrow{b}}^{T}A(\overrightarrow{c}{)}^2=\frac{1}{12}\\ \mathrm{u}\mathrm{n}\mathrm{d}{\overrightarrow{b}}^T{A}^3\mathrm{𝟏}={\overrightarrow{b}}^T{A}^2\overrightarrow{c}=\frac{1}{24}\end{array}$

$(\star )$

Hier wurde für $r\in \mathbb{N}$ folgende Bezeichnung für die Potenzen oder Produkte von Vektoren verwendet:

$(\overrightarrow{v}{)}^r:=\left(\begin{array}{c}{v}_1^r\\ ⋮\\ v_s^r\end{array}\right)$ und $(\overrightarrow{v})(\overrightarrow{u}):=\left(\begin{array}{c}{v}_1{u}_1\\ ⋮\\ v_s{u}_s\end{array}\right)$

Die Ordnungsbedingungen $(\star )$ gelten für ein allgemeines RKV mit $s$ Stufen (implizit oder explizit). Wir beschränken uns im Folgenden auf explizite RKV. In der Herleitung der Koeffizienten eines eRKV dritter Ordnung, benötigt man nach den obigen Ordnungsbedingungen fünf (nichtlinerare) Gleichungen (vergleiche (4.4) ). Bei einem expliziten Verfahren vierter Ordnung erhält man acht Gleichungen. Setzt man als Matrix $A$ eine untere Dreiecksmatrix und $s=4$ in die Ordnungbedigungen, ergibt sich folgendes Gleichungssystem für die Koeffizienten eines expliziten RKV mit 4 Stufen $$\begin{array}{ccc}{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\mathrm{\&}=& 1/3\\ b_3{c}_2{a}_{32}+b_4{c}_2{a}_{42}+b_4{c}_3{a}_{43}& =& 1/6\end{array}\}\text{ 3. Ordnung,}\\ & & \begin{array}{cc}{c}_2^3{b}_2+c_3^3{b}_3+c_4^3{b}_4\mathrm{\&}=& 1/4\\ b_3{c}_3{c}_2{a}_{32}+b_4{c}_4{c}_2{a}_{42}+b_4{c}_4{c}_3{a}_{43}& =& 1/8\\ b_3{c}_2^2{a}_{32}+b_4{c}_2^2{a}_{42}+b_4{c}_3^2{a}_{43}\mathrm{\&}=& 1/12\\ b_4{c}_2{a}_{32}{a}_{43}& =& 1/24\end{array}\}\text{ 4. Ordnung.}\end{array}$$

Die Anzahl der Gleichungen in $(\star )$ steigt unproportional und nichtlinear mit der Konsistenzordnung. Auch gilt es, dass es nicht möglich ist eine beliebiege Konsistenzordnung mit gegebener Stufenzahl $s$ zu erreichen, die Stufenanzahl steigt auch unproportional mit der Konsistenzordnung. Tabelle 1 stellt eine Übersicht der Anzahl der Konsistenzordnungen und der Stufenzahl der eRK-Verfahren dar.

Ordnungsbedingungen und Stufenzahl bei expliziten Runge-Kutta Verfahren

Ordnung $p$	1	2	3	4	5	6	7	8	9	10
Stufen $s$	1	2	3	4	6	7	9	11	$\ge 13$	$\ge 15$
$\mathrm{\#}$ Ord-Bed.	1	2	4	8	17	37	85	200	486	1205

Es gilt folgender Satz über die Anzahl von Stufen und die Konsistenzordnung bei eRKV:

(Butcher Bariere)
Für die Konsistenzordnung $p\ge 5$ existiert kein explizites RKV mit $s=p$ Stufen.
Für die Konsistenzordnung $p\ge 7$ existiert kein explizites RKV mit $s=p+1$ Stufen.
Für die Konsistenzordnung $p\ge 8$ existiert kein explizites RKV mit $s=p+2$ Stufen.

Beweis. Ohne Beweis ◻

Das Verhältnis der zu erreichenden Konsistenzordnung $p$ zu der Stufenanzahl $s$ ist bei den impliziten RKV anders. Generell werden bei iRKV für höhere Ordnungen weniger Stufen benötigt. Allerdings wird die (implizite) Berechnung der Zwischenstufen $k_j$ deutlich komplizierter, da hier in jedem Schritt $t_i$, $s$ (eventuell nichtlineare) Gleichungen (4.1) gelöst werden müssen. Die Herleitung der Koeffizienten eines iRKV kann durch die Ordnungsbedingungen $(\star )$ erfolgen, jedoch existieren auch andere (ggf. einfachere) Ansätze, um ein möglichst genaues oder stabiles iRKV mit gegebener Stufenzahl zu erreichen. Diese werden im folgenden Abschnitten erläutet.