Mehrschrittverfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Mehrschrittverfahren sind Verfahren zur numerischen Lösung von Anfangswertproblemen. Im Gegensatz zu Einschrittverfahren, wie etwa den Runge-Kutta-Verfahren, nutzen Mehrschrittverfahren die Information aus den zuvor bereits errechneten Stützpunkten.

Theorie[Bearbeiten]

Es sei ein Anfangswertproblem

 y'(x)= f(x,y(x))\,

für x\in [x_0,\infty) mit einer Anfangsbedingung y(x_0)=y_0\, gegeben. Ein lineares Mehrschrittverfahren (LMV) erzeugt zu einer gegebenen Schrittweite h>0\, eine Folge (y_n)_{n\in\N} von Näherungen zu den Funktionswerten

y_n\approx y(x_n)=y(x_0+n\,h).

Dabei besteht zwischen den Näherungswerten und der Differentialgleichung die lineare Rekursionsgleichung

\sum_{j=0}^{m}a_{j} \, y_{n-j} = h \sum_{j=0}^m b_{j} \, f(x_{n-j},y_{n-j}).

Die Koeffizienten a_0,\dots,a_m\, sowie b_0,\dots,b_m\, bestimmen das Mehrschrittverfahren, dabei gilt a_0=1\,.

Man nennt das LMV implizit, falls b_0 \neq 0\, ist, und explizit, falls b_0 = 0\, ist. Implizite Verfahren können bei gleicher Länge m der Koeffiziententupel eine um 1 höhere Konsistenzordnung als explizite Verfahren haben. Ihr Nachteil besteht jedoch darin, dass bei der Berechnung von y_{n+1}\, bereits f(x_{n+1},y_{n+1})\, benötigt wird. Dies führt zu nichtlinearen Gleichungssystemen. Für explizite Verfahren kann man die lineare Rekursionsgleichung in die explizite Form


    y_{n+1}=-\sum_{j=0}^{m-1}a_{1+j} \, y_{n-j}
            +h \sum_{j=0}^{m-1} b_{1+j} \, f(x_{n-j},y_{n-j})

umstellen.

In jedem Fall müssen die ersten m Glieder der Folge der Näherungswerte mit einem anderen Verfahren bestimmt werden, im einfachsten Fall wird linear extrapoliert,

y_k=y_0+k\,h\,f(x_0,y_0), \quad k=1,\dots,m-1.

Diese Werte können im Allgemeinen mit einem beliebigen Einschrittverfahren für den ersten Wert y_1\,, einem maximal 2-Schritt-Verfahren für den zweiten Wert y_2\,, usw. bis der Wert y_{m-1}\, durch ein maximal (m-1)-Schritt-Verfahren gewonnen werden. Diese Berechnung nennt man auch Anlaufrechnung für das Mehrschrittverfahren.

Analyse[Bearbeiten]

Ein lineares Mehrschritt-Verfahren ist konvergent, wenn es konsistent und stabil für die Gleichung y'(x)=0 ist (diese Eigenschaft heißt auch 0-Stabilität). Konvergenz besagt, dass durch Verkleinern der Schrittweite h> 0 die Differenz |y_k-y(x_k)| zwischen Näherungswert und Wert der exakten Lösung für x_k\approx t für jedes fixierte t beliebig klein gehalten werden kann.

Konsistenz[Bearbeiten]

Sei y(x) beliebige, in einer Umgebung eines Punktes x definierte und einmal stetig differenzierbare Funktion. Diese erfüllt die triviale Differentialgleichung y'(x)=f(x,y)=y(x). Für diese kann der Fehler erster Ordnung des Mehrschrittverfahrens als

T_h(x)=\frac{1}{h}\sum_{j=0}^{m}a_{j} \, y(x-j\,h) - \sum_{j=0}^m b_{j} \, y'(x-jh).

bestimmt werden. Man definiert dann:

Ein LMV heißt konsistent, falls

\lim_{h \to 0} |T_h(x)| = 0

für beliebige Wahlen von x und der Funktion y. Es heißt konsistent der Ordnung p, falls in Landau-Notation

|T_h(x)| = O(h^p)

gilt, d. h. h^{-p}\,|T_h(x)| immer nach oben beschränkt ist.

Man prüft dies unter Zuhilfenahme der Taylor-Entwicklung. So ist für eine p-fach differenzierbare Differentialgleichung die Lösung p+1 mal differenzierbar und es gilt

y(x_{k+j}) = y(x_k + j\, h) = y(x_k)+ jh \, y'(x_k)+ \frac{(jh)^2}{2}y''(x_k) + \dots + \frac{(jh)^p}{p!}\,y^{(p)}(x_k) + O(h^{p+1})

wobei y^{(l)}(x_k) die l-te Ableitung an der Stelle x_k bezeichnet. Dies führt man für alle im LMV auftretenden Terme durch und setzt dies in T_h(x_k) ein. Es ist ausreichend, dies für die Exponentialfunktion und ihre Differentialgleichung zu untersuchen.

Stabilität[Bearbeiten]

Man definiert zwei sogenannte assoziierte Polynome \rho, \sigma

\rho (\lambda) = \sum_{i=0}^ma_i \, \lambda^{m-i}
\sigma(\lambda) = \sum_{i=0}^mb_i \, \lambda^{m-i}

Ein LMV wird durch diese beiden Polynome vollständig charakterisiert, so dass man anstelle von obiger Schreibweise des linearen Mehrschrittverfahrens auch von einem „LMV (\rho,\sigma)“ spricht.

Sei \lambda_0 eine Nullstelle von \rho. Ein LMV (\rho, \sigma) ist nullstabil, wenn für jede Nullstelle \lambda_0 gilt:

  • sie liegt entweder im Innern des Einheitskreises, |\lambda_0| < 1 oder
  • auf dem Rand des Einheitskreises, |\lambda_0| = 1, wobei sie dann eine einfache Nullstelle sein muss. Ein allgemeinerer Fall wird im Artikel Stabilitätsfunktion diskutiert.

Bezüglich der A-Stabilität gilt die Zweite Dahlquist-Barriere, dass ein A-stabiles lineares Mehrschrittverfahren nicht mehr als Ordnung zwei haben kann.

Beispiele[Bearbeiten]

Explizite Verfahren[Bearbeiten]

Ein explizites Verfahren bedeutet in diesem Zusammenhang, dass zur Berechnung der Näherungswerte nur Werte herangezogen werden, die zeitlich vor dem zu Berechnenden liegen. Das wohl bekannteste explizite LMV ist die s+1–Schritt Adams-Bashforth-Methode (nach John Couch Adams und Francis Bashforth). Diese hat die Form:

y_{n+1}=y_n + h \sum_{j=0}^s b_{j} \, f(t_{n-j},y_{n-j}).

mit

b_j = {(-1)^j \over j!(s-j)!}\int_0^1 \prod_{i=0, i\ne j}^s (u+i) \,du,\quad j=0,\ldots, s.

z. B.:

s=1
y_{n+1} = y_n + h\left( {3\over 2} f(t_n, y_n) - {1 \over 2} f(t_{n-1}, y_{n-1})\right)
s=2
y_{n+1} = y_n + h\left( {23\over 12} f(t_n, y_n) - {16 \over 12} f(t_{n-1}, y_{n-1}) + {5\over 12}f(t_{n-2}, y_{n-2})\right)

usw.

Implizite Verfahren[Bearbeiten]

Bei impliziten Verfahren wird zur Berechnung auch der zu berechnende Wert selbst benutzt. Im Beispiel taucht so auf beiden Seiten der Gleichung y_{n+1} auf. Eine bekannte Klasse von impliziten Mehrschrittverfahren sind die Adams-Moulton-Verfahren (nach Forest Ray Moulton und John Couch Adams). Diese haben die Form:

y_{n+1} = y_n + h \sum_{j=-1}^{s-1} b_j f(t_{n-j}, y_{n-j}),\quad 0 \le s \le n

mit

b_j = {(-1)^{j+1} \over (j+1)!(s-j-1)!}\int_0^1 \prod_{i=-1, i\ne j}^{s-1} (u+i) \,du,\quad j=-1,0,\ldots,s-1

z. B.:

s=2
y_{n+1}=y_n+h\left({1 \over 12}\Big(5f(t_{n+1}, y_{n+1})+8f(t_n,y_n)-f(t_{n-1},y_{n-1})\Big) \right)

Darüber hinaus sind insbesondere die BDF-Verfahren für steife Anfangswertprobleme im Einsatz, da diese bessere Stabilitätseigenschaften haben. BDF-2 ist A-stabil, die weiteren noch A(\alpha )-stabil, ab BDF-7 allerdings instabil.

Praxis[Bearbeiten]

Startwerte[Bearbeiten]

Oftmals hat man es in der Praxis mit Problemen der Art:

y'(x)=f\left( x,y(x) \right) , \quad y(0)=y_0

zu tun. Hier fehlt es an Startwerten. Diese werden zunächst durch Einschrittverfahren (z. B. dem klassischen Runge-Kutta-Verfahren) gewonnen.

Prädiktor-Korrektor-Methode[Bearbeiten]

Mit dem Gedanken, die im Vergleich um 1 höhere Konsistenzordnung der impliziten LMVs zu nutzen, umgeht man das Lösen der nichtlinearen Gleichungen durch die sog. Prädiktor-Korrektor-Methode. Es wird der in der impliziten Methode benötigte Wert für y_{n+1} durch eine explizite Methode berechnet, wonach durch Iteration der Wert für y_{n+1} zu verbessern versucht wird. Dazu gibt es verschiedene Verfahren, die geläufigsten sind:

P(EC)^{m}E[Bearbeiten]

Beim P(EC)^{m}E (P=predict, E=evaluate, C=correct) wird der durch das explizite Prädiktorverfahren gewonnene Wert y_{n+1,alt} für y_{n+1} wieder in das implizite Korrektorverfahren eingesetzt, wodurch man einen neuen Wert für y_{n+1}, nämlich y_{n+1,neu} erhält. Dies wird so lange iteriert, bis |y_{n+1,neu} - y_{n+1,alt}| kleiner als eine festgelegte Fehlertoleranz ist, oder m-mal iteriert wurde.

Literatur[Bearbeiten]

  • Ernst Hairer, Gerhard Wanner: Solving Ordinary Differential Equations. Band 1: Nonstiff Problems. 2. revised edition. Springer Verlag, Berlin u. a. 1993, ISBN 3-540-56670-8 (Springer series in computational mathematics 8), (Auch Nachdruck: ebenda 2008, ISBN 978-3-642-05163-0).
  • E. Hairer, G. Wanner: Solving Ordinary Differential Equations. Band 2: Stiff and differential-algebraic problems. 2. revised edition. Corrected 2. print. Springer Verlag, Berlin u. a. 2002, ISBN 3-540-60452-9 (Springer series in computational mathematics 14), (Auch Nachdruck: ebenda 2010, ISBN 978-3-642-05220-0).