Allgemeine lineare Verfahren

Die wichtigsten Verfahrensklassen für gewöhnliche Differentialgleichungen sind die Runge-Kutta-Verfahren, welche $s$ interne Stufen in jedem Zeitschritt verwenden, und die Mehrschrittverfahren, welche auf eine bestimmte Anzahl früherer Lösungsapproximationen zurückgreifen, also mit zwei anscheinend vollkommen unterschiedlichen Strukturen. Zur Vereinheitlichung schlug John C. Butcher die Klasse der allgemeinen linearen Verfahren (engl. General Linear Methods = GLM) vor auch in der Erwartung, dass in der allgemeineren Struktur neue, bessere Verfahren zu finden sind. Außerdem müssen damit grundlegende Aussagen wie Konsistenz oder Stabilitätseigenschaften nur einmal formuliert werden.

Runge-Kutta- und Mehrschritt-Verfahren

Beide Verfahrensklassen approximieren die Lösung $y(t)\in {ℝ}^d$ des autonomen Anfangswertproblems $y^{\prime }(t)=f(y(t)),y(t_0)=y_0,$ in Zeitschritten und erzeugen Näherungen $y_n\approx y(t_n)$ an Stellen $t_n=t_{n-1}+h$. Zur Motivation werden die Verfahren in einer etwas anderen Form als im Artikel Runge-Kutta-Verfahren, aber äquivalent damit, geschrieben:

$Y_i=y_{n-1}+h\sum _{j=1}^s{a}_{ij}f(Y_j),i=1,\dots ,s,$

$y_n=y_{n-1}+h\sum _{j=1}^s{b}_{j}f(Y_j).$

Für ein allgemeines lineares $m$-Schritt-Verfahren mit ${\alpha }_0=1$ lautet die Vorschrift so:

$y_n=-\sum _{j=1}^m{\alpha }_j{y}_{n-j}+h\sum _{j=0}^m{\beta }_{j}f(y_{n-j}).$

Hier stammen nur die Werte $y_{n-1},f(y_{n-1}),f(y_n)$ aus dem aktuellen Zeitschritt, alle anderen aus früheren.

Struktur der allgemeinen linearen Verfahren

Durch Zusammenfassung der älteren Informationen in einem Vektor $y^{[n-1]}$ mit $r$ Alt-Informationen erhält man das allgemeine lineare Verfahren mit $s$ internen Stufen $Y_j$:

$Y_i=h\sum _{j=1}^s{a}_{ij}f(Y_j)+\sum _{j=1}^r{u}_{ij}{y}_j^{[n-1]},i=1,\dots ,s,$

$y_i^{[n]}=h\sum _{j=1}^s{b}_{ij}f(Y_j)+\sum _{j=1}^r{v}_{ij}{y}_j^{[n-1]},i=1,\dots ,r.$

Im Rahmen dieser Verfahrensstruktur wird das Verfahren vollständig durch seine Koeffizienten beschrieben, welche man in Matrizen $A=(a_{ij})\in {ℝ}^{s\times s},B=(b_{ij})\in {ℝ}^{r\times s},U=(u_{ij})\in {ℝ}^{s\times r},V=(v_{ij})\in {ℝ}^{r\times r}$ zusammenfassen kann. Daher ist das Verfahren wieder in kompakter Form festgelegt durch sein Butcher-Tableau

$\left[\begin{array}{cc}A& U\\ B& V\end{array}\right].$

Zur Stabilität dieser Verfahren kann man ihre Stabilitätsfunktion betrachten.

Runge-Kutta-Verfahren als allgemeine lineare Verfahren

Dass die klassischen Verfahren in diesen Rahmen passen, sieht man bei Runge-Kutta-Verfahren einfach. Hier ist $r=1$, die Matrix $U$ entspricht dem Einsvektor $e$ bestehend aus lauter Einsen und das Butcher-Tableau des Runge-Kutta-Verfahrens ist

$\left[\begin{array}{cc}A& U\\ B& V\end{array}\right]=\left[\begin{array}{cc}A& e\\ b^T& 1\end{array}\right].$

Mehrschrittverfahren als allgemeine lineare Verfahren

Eine günstige Schreibweise bei Mehrschrittverfahren hängt davon ab, wie viele der Koeffizienten ${\alpha }_j,{\beta }_j$ wirklich von Null verschieden sind. Bei den einfach aufgebauten impliziten BDF-Verfahren ist nur ${\beta }_0=0$, die Vorschrift ist $\sum _{j=0}^m{\alpha }_j{y}_{n-1}=h{\beta }_{0}f(y_n)$, etwa mit ${\alpha }_0=1$. Hier setzt man $s=1$ und $r=m$ und definiert $y^{[n-1]}=(y_{n-1},\dots ,y_{n-m})$. Die neue Näherung $y_n$ muss sowohl als $y_n=Y_1$ als auch als $y_n=y_1^{[n]}$ eingeführt werden. Daher sind auch die beiden ersten Zeilen im Tableau des BDF-Verfahrens gleich:

$\left[\begin{array}{cc}A& U\\ B& V\end{array}\right]=\left[\begin{array}{ccccc}{\beta }_0& -{\alpha }_1& \dots & -{\alpha }_{m-1}& -{\alpha }_m\\ {\beta }_0& -{\alpha }_1& \dots & -{\alpha }_{m-1}& -{\alpha }_m\\ 0& 1& \dots & 0& 0\\ ⋮& & \ddots & & ⋮\\ 0& & & 1& 0\end{array}\right]$

Der untere Teil des Matrixblocks $V$ entspricht der Verschiebung der Altwerte im Vektor $y$. Daher hat diese Matrix $V$ die Form einer Begleitmatrix (bzw. ihre Transponierte).

Bei Adams-Bashforth-Verfahren ist dagegen nur ${\alpha }_1=0$ (nämlich −1). Hier wählt man $s=1$ und $r=m+1$, sowie $y^{[n-1]}=(y_{n-1},hf(y_{n-1}),\dots ,hf(y_{n-m}))$. Das Tableau ist hier

$\left[\begin{array}{cc}A& U\\ B& V\end{array}\right]=\left[\begin{array}{cccccc}0& 1& {\beta }_1& \dots & {\beta }_{m-1}& {\beta }_m\\ 0& 1& {\beta }_1& \dots & {\beta }_{m-1}& {\beta }_m\\ 1& 0& 0& \dots & 0& 0\\ 0& 0& 1& & 0& 0\\ ⋮& & & \ddots & & ⋮\\ 0& & & & 1& 0\end{array}\right]$

Mit der dritten Zeile des Tableaus wird der neue Funktionswert $y_2^{[n]}=f(y_1^{[n]})=f(Y_1)=f(y_n))$ berechnet. An dieser Mehrfachdarstellung sieht man, dass diese Formulierung nicht unbedingt für eine effiziente Implementierung geeignet ist, sondern vor allem der einheitlichen Beschreibung theoretischer Aussagen dient.

Bei allgemeinen linearen Mehrschrittverfahren muss man aber dann bis zu $r=2m$ Altwerte mitführen.

Literatur

• J.C. Butcher: Numerical methods for ordinary differential equations, John Wiley & Sons, 2. Aufl., 2008, ISBN 978-0-470-75375-0.
• E. Hairer, G. Wanner: Solving Ordinary Differential Equations II, Stiff problems, Springer Verlag, 1996, ISBN 978-3-540-60452-5.
• Z. Jaciewicz: General linear methods for ordinary differential equations, John Wiley & Sons, 2009, ISBN 978-0-470-52215-8.
• K. Strehmel, R. Weiner, H. Podhaisky: Numerik gewöhnlicher Differentialgleichungen - Nichtsteife, steife und differential-algebraische Gleichungen, Springer Spektrum, 2012, ISBN 978-3-8348-1847-8.