Mehrschrittverfahren

Verfahren zur numerischen Lösung von Anfangswertproblemen
(Weitergeleitet von Adams-Bashforth-Verfahren)

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.

Es sei ein Anfangswertproblem

 

für   mit einer Anfangsbedingung   gegeben. Ein lineares Mehrschrittverfahren (LMV) erzeugt zu einer gegebenen Schrittweite   eine Folge   von Näherungen zu den Funktionswerten

 .

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

 .

Die Koeffizienten   sowie   bestimmen das Mehrschrittverfahren, dabei gilt  .

Man nennt das lineare Mehrschrittverfahren implizit, falls   ist, und explizit, falls   ist. Implizite Verfahren können bei gleicher Länge   der Koeffiziententupel eine um 1 höhere Konsistenzordnung als explizite Verfahren haben. Ihr Nachteil besteht jedoch darin, dass bei der Berechnung von   bereits   benötigt wird. Dies führt zu nichtlinearen Gleichungssystemen. Für explizite Verfahren kann man die lineare Rekursionsgleichung in die explizite Form

 

umstellen.

Zum Start benötigen  -Schrittverfahren   Startwerte  . Diese werden im Rahmen einer sogenannten Anlaufrechnung durch Anwendung anderer Näherungsverfahren bestimmt. Im einfachsten Fall werden die Startwerte linear extrapoliert

 .

Im Allgemeinen lassen sich die benötigten Startwerte auch durch sukzessive Anwendung von Mehrschrittverfahren mit steigender Schrittzahl gewinnen: Man startet dazu mit einem beliebigen Einschrittverfahren für den ersten Wert  , verwendet dann höchstens ein 2-Schritt-Verfahren für den zweiten Wert   und berechnet schließlich den Wert   durch ein aus maximal   Schritten bestehendes Mehrschrittverfahren.

Ein lineares Mehrschrittverfahren ist konvergent, wenn es konsistent und stabil für die Gleichung   ist (diese Eigenschaft heißt auch 0-Stabilität). Konvergenz besagt, dass durch Verkleinern der Schrittweite   die Differenz   zwischen Näherungswert und Wert der exakten Lösung für   für jedes fixierte   beliebig klein gehalten werden kann.

Konsistenz

Bearbeiten

Sei   eine beliebige, in einer Umgebung eines Punktes   definierte und einmal stetig differenzierbare Funktion. Diese erfülle die triviale Differentialgleichung  . Für diese kann der Fehler erster Ordnung des Mehrschrittverfahrens als

 

bestimmt werden. Man definiert dann:

Ein lineares Mehrschrittverfahren heißt konsistent, falls

 

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

 

gilt, das heißt   immer nach oben beschränkt ist.

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

 

wobei   die  -te Ableitung an der Stelle   bezeichnet. Dies führt man für alle im linearen Mehrschrittverfahren auftretenden Terme durch und setzt dies in   ein. Es ist ausreichend, dies für die Exponentialfunktion und ihre Differentialgleichung zu untersuchen.

Stabilität

Bearbeiten

Man definiert zwei sogenannte assoziierte Polynome  

 
 

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

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

  • sie liegt entweder im Innern des Einheitskreises,   oder
  • auf dem Rand des Einheitskreises,  , 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 lineare Mehrschrittverfahren ist die  -Schritt-Adams-Bashforth-Methode (nach John Couch Adams und Francis Bashforth). Diese hat die Form:

 

mit

 

z. B.:

 
 
 
 

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   auf. Eine bekannte Klasse von impliziten Mehrschrittverfahren sind die Adams-Moulton-Verfahren (nach Forest Ray Moulton und John Couch Adams). Diese haben die Form:

 

mit

 

z. B.:

 
 

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  -stabil, ab BDF-7 allerdings instabil.

Startwerte

Bearbeiten

Oftmals hat man es in der Praxis mit Problemen der Art

 

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

Prädiktor-Korrektor-Methode

Bearbeiten

Mit dem Gedanken, die im Vergleich um 1 höhere Konsistenzordnung der impliziten linearen Mehrschrittverfahren 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   durch eine explizite Methode berechnet, wonach durch Iteration der Wert für   zu verbessern versucht wird. Dazu gibt es verschiedene Verfahren, die geläufigsten sind:

Beim   (P = predict, E = evaluate, C = correct) wird der durch das explizite Prädiktorverfahren gewonnene Wert   für   wieder in das implizite Korrektorverfahren eingesetzt, wodurch man einen neuen Wert für  , nämlich   erhält. Dies wird so lange iteriert, bis   kleiner als eine festgelegte Fehlertoleranz ist, oder  -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).