Kurs:Gewöhnliche Differentialgleichungen/4.3 Implizite Runge-Kutta Verfahren

4.3 Implizite Runge-Kutta Verfahren

Wenn die Koeffizientenmatrix $A$ im Butcher Tableau eines Runge-Kutta Verfahrens eine vollbesetzte Matrix ist, hängt die Berechnung der Funktionsauswertungen $k_j$ für jedes $j=1,\dots ,s$ von anderen $k_1,\dots k_s$ ab, insbesondere auch von den $k_j,k_{j+1},\dots k_s$ , siehe (4.1). Das einfachste iRKV ist das schon bekannte implizite Eulerverfahren, weitere Beispiele sind die implizite Mittelpunkt- und Trapezregel:

Implizite Mittelpunktregel, $s=1$:

$$\begin{array}{ccc}{k}_1& =& f(t_i+\frac{h}{2},{\eta }_i+\frac{h}{2}{k}_1)\\ {\eta }_{i+1}& =& {\eta }_i+h{k}_1\end{array}$$

Implizite Trapeztregel, $s=2$:

$$\begin{array}{ccc}{k}_1& =& f(t_i,{\eta }_i)\\ k_2& =& f(t_i+h,\underset{{\eta }_{i+1}}{\underbrace{{\eta }_i+\frac{h}{2}(k_1+k_2)}})\\ {\eta }_{i+1}& =& {\eta }_i+\frac{h}{2}(k_1+k_2)\\ & \equiv & {\eta }_i+\frac{h}{2}(f(t_i,{\eta }_i)+f(t_{i+1},{\eta }_{i+1})).\end{array}$$

Eine wichtige Untermenge der iRKV sind sogenannte Gauß-Verfahren, diese ermöglichen die größtmögliche Ordnung im Hinblick auf die Stufenzahl. Diese Verfahren gehören zu den sogenannten Kollokationsverfahren und werden von der Gauß-Quadratur abgeleitet, dieser Tatsache verdanken sie ihrem Namen. Die Gauß-Verfahren, wie auch andere (aber nicht alle) iRKV haben gute Stabilitätseigenschaften, die insbesondere für ’steife’ Probleme von großer Bedeutung sind.

Steife Probleme

Der Bergriff eines steifen Problems entstand bei der Anwendung der numerischen Methoden zur Lösung einer Differentialgleichung, wenn diese sehr kleine bzw. im Laufe des Verfahrensfortschritts immer kleinere Schrittweiten benötigt, um eine brauchbare, konvergente Lösung zu produzieren. Explizite Verfahren wie Eulerverfaren oder auch die eRKV höherer Ordnung mit fester Schrittweite versagen in solchen Fällen; Verfahren mit Schrittweitensteuerung generieren immer kleinere Schrittweiten bis zur Null (im Rahmen der Rechnergenauigkeit), demzufolge bewegen sie sich irgendwann nicht mehr von der Stelle, sie bleiben stehen - daher kommt der Begriff ’steif’.

Zu den steifen Problemen gehören Differentialgleichungen mit Lösungen mit hohen Veränderungsraten, oder Systeme mit sehr unterschiedlich schnell wachsenden Lösungskomponenten. Hierbei generiert ein explizites Verfahren die Lösungsapproximation im nächsten Zeitschritt anhand der vorherigen, in stark dynamischen Systemen nicht mehr aktueller, fehlerbehafteter Steigungen/Informationen und somit schießt das explizite Verfahren schnell über das Ziel hinaus.

Beispiele für steife Probleme sind lineare Differentialgleichungssysteme, deren Matrix sehr unterschiedliche Eigenwerte besitzt, oder etwa Differentialgleichungen, die chemische Reaktionen mit unterschiedlich schnell reagierenden Stoffen beschrieben. Durch die gute Stabilitätseigenschaften der impliziten Einschrittverfahren, die im aktuellem Schritt deren Verlauf an die zukunftige (noch stärkere) Steigung anpassen und somit auch für größere Schrittweiten $h$ gute Ergebnisse liefern, sind iRKV besonders für steiffe Probleme geeignet.

Abbildung 4.1: Lösungskomponenten eines steiffen Differentialgleichungssystems, exakte Lösung $y_1(t)=e^{10t},y_2=1000e^{-10t}$ und Approximation mit explizitem Eulerverfahren, $h=0.125$.

Bei impliziten Runge-Kutta Verfahren werden die Stufen $k_j$ durch die Lösung des Gleichungssystems (4.1) berechnet. Die Existenz der Lösung dieses ggf. nichtlinearen Gleichungssystems ist nicht immer garantiert oder durch iterative Methoden erreichbar. Eine hinreichende Bedingung für die Existenz einer solchen Lösung und der Konvergenz der iterativen Fixpunktmethode ist eine hineichend kleine Schrittweite $h$:

---

Satz 4.2 (Butcher 1964)

Sei $f$ stetig auf $ℝ\times {ℝ}^m$ und Lipschitz stetig bezüglich $y$ mit Lipschitz-Konstante $L$. Gelte für die Schrittweite $h$ $$h<\frac{1}{L\Vert |A\Vert {|}_{\mathrm{\infty }}}=\frac{1}{L{\mathrm{m}\mathrm{a}\mathrm{x}}_i\sum _{j=1,\dots s}|a_{ij}|}.(4.12)$$

Dann besitzt das Gleichungssystem (4.1), $$k_j=f(t_i+h{c}_j,{\eta }_i+h\sum _{\nu =1}^s{a}_{jm}{k}_{\nu })j=1,\dots ,s$$

eine eindeutige Lösung, die durch sukzessive Substitution (Fixpunktiteration) berechnet werden kann. Ist zudem $f\in C^p(ℝ\times {ℝ}^m)$, dann sind die $k_j$ als Funktionen von $h$ auch $p$-mal stetig differenzierbar.

Beweis. Sei einfachheitshalber $m=1$ an. Die Lösung des (nichtlinearen) Gleichungssystem (4.1) für $k_1,\dots k_s$ lässt sich iterativ bestimmen: $$k_j^{(m+1)}=f(t_i+h{c}_j,{\eta }_i+h\sum _{\nu =1}^s{a}_{j\nu }{k}_{\nu }^{(m)})j=1,\dots ,s.(4.13)$$

Schreibt man das Gleichungssystem (4.1) in die vektorielle Form um, $$\overrightarrow{K}=F(\overrightarrow{K}),$$

mit $\overrightarrow{K}=(k_1,\dots k_s{)}^T\in {ℝ}^s,F:{ℝ}^s\to {ℝ}^s,$ $$\begin{array}{c}{F}_j(\overrightarrow{K}):=f(t_i+h{c}_j,{\eta }_i+h\sum _{\nu =1}^s{a}_{j\nu }{k}_{\nu })=f(t_i+h{c}_j,{\eta }_i+h{A}_j\cdot \overrightarrow{K})j=1,\dots ,s\end{array}$$

so erhält man Anstelle von (4.13) die Iterationsvorschrift $${\overrightarrow{K}}^{(m+1)}=F\left({\overrightarrow{K}}^{(m)}\right)(4.14)$$

mit einem Startvektor $K^{(0)}.$

Nach dem Fixpunktsatz von Banach, siehe Satz 2.1, Kapitel 2, existiert eine eindeutige Lösung, ein Fixpunkt von $\overrightarrow{K}=F(\overrightarrow{K})$, wenn $F$ eine Selbstabbildung und kontrahierend ist. Für eine Funktion $F:{ℝ}^s\to {ℝ}^s$ ist $F({ℝ}^s)\subseteq {ℝ}^s$, also immer eine Selbtsabbildung.
Nun untersuchen wir, ob $F$ kontrahierend ist. Wir schätzen mihilfe der Lipschitz-Stetigkeit der Funktion $f$ und der Dreiecksungleichung für den Betrag inMaximumnorm: $$\begin{array}{c}\Vert F(\overrightarrow{K}{)}^1-F({\overrightarrow{K}}^2){\Vert }_{\mathrm{\infty }}=\underset{j=1,...,s}{\max }|f(t_i+h{c}_j,{\eta }_i+h\sum _{\nu =1}^s{a}_{j\nu }{k}_{\nu }^1)-f(t_i+h{c}_j,{\eta }_i+h\sum _{\nu =1}^s{a}_{j\nu }{k}_{\nu }^2)|\\ \stackrel{L-stetig}{\le }\underset{j}{\max }hL|\sum _{\nu =1}^s{a}_{j\nu }(k_{\nu }^1-k_{\nu }^2)|\le hL\underset{j}{\max }\sum _{\nu =1}^s|a_{j\nu }|\underset{\nu }{\max }|k_{\nu }^1-k_{\nu }^2|\\ =hL\Vert |A\Vert {|}_{\mathrm{\infty }}\Vert K^1-K^2{\Vert }_{\mathrm{\infty }}.\end{array}$$

Aus dieser Abschätzung folgt dass $F$ kontrahierend ist in Banach Raum ${ℝ}^s,\Vert \cdot {\Vert }_{\mathrm{\infty }}$, falls $hL\Vert |A\Vert {|}_{\mathrm{\infty }}\Vert <1$. Demzufolge hat die Abbildung $F$ für $h<1/(L\Vert |A\Vert {|}_{\mathrm{\infty }})$ in ${ℝ}^s$ einen eindeutigen Fixpunkt, $${\overrightarrow{K}}^{\star }=F({\overrightarrow{K}}^{\star }),$$

und die Iteration (4.13), (4.14) konvergiert gegen diesen Fixpunkt. Die Aussage über die p-fache stetige Differenzierbarkeit von $k_j$ belassen wir ohne Beweis. ◻

---

Bemerkung zur Lösbarkeit der iRKV

1. Die Einschränkung der Schrittweite $h$ kann bei großen $L$-Konstanen (d.h. bei $f$ mit hohen Werten der Ableitung $\frac{\partial f}{\partial y}\approx L$) sehr restriktiv sein und zur langsamen Konvergenz des Fixpunktverfahrens führen. Der Ausweg in diesen Fällen ist die Anwendung eines anderen iterativen Verfahren mit höherer Konvergenzgeschwindigkeit zur Berechnung nun von $k_j$, wie Newton-, Sekanten-, oder Quasi-Newton Verfahren. Diese Verfahren konvergieren auch für größere $h$, da sie superlineare Konvergenzgeschwindigkeit haben, wenn der Startwert günstig, innerhalb des sog. Konvergenzintervalls gewählt ist.
2. Ist die Funktion $f$ lediglich nur lokal Lipschitz stetig in $y$, d.h. nur in einer Umgebung von $K^{(0)}$, dann resultieren weitere Beschränkungen auf die Schrittweite $h$, um die Selbstabbildungs-Eigenschaft zu garantieren.
3. Die Lipschitz-Stetigkeit der Verfahrensfunktion $\mathrm{\Phi }$ eines eRKV, wie auch eines iRKV bezüglich $y$ folgt aus der Lipschitz-Stetigkeit von $f$. Damit sind auch die iRKV mit Konsistenzordnung p konvergent mit der Konvergenzordnung p. (siehe Satz 3.1)