Mehrschrittverfahren
Mehrschrittverfahren sind Verfahren zur numerischen Lösung von gewöhnlichen Differentialgleichungen. Im Gegensatz zu Einschrittverfahren, wie etwa dem Eulerschen Polygonzugverfahren oder dem Runge-Kutta-Verfahren, nutzen Mehrschrittverfahren die Information aus den zuvor bereits errechneten Stützpunkten.
Theorie
Es sei ein Anfangswertproblem für mit einer Anfangsbedingung näherungsweise zu lösen. Ein lineares Mehrschrittverfahren erzeugt zu einer gegebenen Schrittweite h>0 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 LMV implizit, falls , und explizit, falls . 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 bereits benötigt wird. Dies führt zu nichtlinearen Gleichungssystemen. Für explizite Verfahren kann man die lineare Rekursionsgleichung in die explizite Form
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,
- , .
Diese Werte können aber auch mit einem beliebigen Runge-Kutta-Verfahren gewonnen werden.
Analyse
Man untersucht die LMV auf die Eigenschaften Konsistenz und Stabilität. Diese beiden Eigenschaften ergeben zusammen die Konvergenz des LMVs. Diese besagt, dass durch Verkleinern der Schrittweite die Differenz zwischen Näherungswert und Wert der exakten Lösung für für jedes fixierte t beliebig klein gehalten werden kann.
Konsistenz
Sei beliebige, in einer Umgebung eines Punktes x definierte und einmal stetig differenzierbare Funktion. Diese erfüllt die triviale Differentialgleichung . Für diese kann der Fehler erster Ordnung des Mehrschrittverfahrens als
- .
bestimmt werden. Man definiert dann:
Ein LMV heißt konsistent, falls
für beliebige Wahlen von x und der Funktion y. Es heißt konsistent der Ordnung p, falls in Landau-Notation
gilt, d.h. 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
wobei die l-te Ableitung an der Stelle bezeichnet. Dies führt man für alle im LMV auftretenden Terme durch und setzt dies in ein. Es ist ausreichend, dies für die Exponentialfunktion und ihre Differentialgleichung zu untersuchen.
Stabilität
Man definiert zwei Polynome
Ein LMV wird durch diese beiden Polynome vollständig charakterisiert, so dass man anstelle von obiger Schreibweise des LMVs auch von einem "LMV ()" spricht.
Sei eine Nullstelle von Ein LMV () ist stabil, wenn für jede Nullstellen gilt:
- sie liegt entweder im Innern des Einheitskreises, oder
- auf dem Rand des Einheitskreises, , wobei sie dann eine einfache Nullstelle sein muss.
Beispiele
Explizite Verfahren
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. Diese hat die Form:
- .
mit
z.B.:
usw.
Implizite Verfahren
Bei 'Impliziten Verfahren' wird zur Berechnung auch der zu berechnende Wert selbst benutzt. Im Beispiel taucht so auf beiden Seiten der Gleichung auf. Das seinerseits bekannteste implizite LMV ist die Adams-Moulton-Methode. Dieses hat die Form:
mit
z.B.:
Vorteile gegenüber Einschrittverfahren
Der offensichtliche Vorteil lineare Mehrschrittverfahren gegenüber Einschrittverfahren ist ihr Verhältnis zwischen Kosten und Konsistenzordnung. Dies liegt daran, dass bei einem LMV jeweils nur ein Wert aus bereits vorhandenem Datenmaterial berechnet werden muss.
Praxis
Startwerte
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. dem klassischen Runge-Kutta-Verfahren) gewonnen.
Prädiktor-Korrektor-Methode
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 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 m-mal iteriert wurde.