Lineare Mehrschrittverfahren

Lineare Mehrschrittverfahren berechnen jeden neuen Lösungswert aus einer Linearkombination mehrerer vorheriger Lösungswerte und Ableitungen, wobei vergangene Arbeit wiederverwendet wird, um eine hohe Ordnung bei geringen Kosten pro Schritt zu erzielen.

Definition

Ein lineares Mehrschrittverfahren ist ein Verfahren für gewöhnliche Differentialgleichungen, das den nächsten Lösungswert durch eine feste lineare Beziehung zwischen einer Reihe vorheriger Lösungswerte und Auswertungen der rechten Seite bestimmt.

Scope

Dieses Thema behandelt die Adams-Bashforth- (explizit) und Adams-Moulton-Familien (implizit), die Rückwärtsdifferenzierungsformeln für steife Probleme, die Prädiktor-Korrektor-Implementierung, die charakteristischen Polynome und die Wurzelbedingung, die die Null-Stabilität definieren, sowie Dahlquists Ordnungsschranken, die die Leistungsfähigkeit solcher Methoden begrenzen.

Core questions

• Wie nutzen Mehrschrittverfahren vergangene Werte wieder, um eine hohe Ordnung mit einer neuen Funktionsauswertung pro Schritt zu erreichen?
• Was ist Null-Stabilität, und wie drückt die Wurzelbedingung am charakteristischen Polynom diese aus?
• Wie kombinieren Prädiktor-Korrektor-Paare explizite und implizite Formeln in der Praxis?
• Was sagen Dahlquists Ordnungsschranken über die Grenzen der Mehrschrittgenauigkeit und -stabilität aus?

Key theories

Null-Stabilität und die Wurzelbedingung

Ein Mehrschrittverfahren ist genau dann null-stabil und somit konvergent, wenn es konsistent ist, wenn die Wurzeln seines ersten charakteristischen Polynoms im abgeschlossenen Einheitskreis liegen, wobei nur einfache Wurzeln auf dem Rand liegen; diese Wurzelbedingung ist das Mehrschritt-Analogon der Stabilität.

Dahlquist-Schranken

Dahlquists erste Schranke begrenzt die Ordnung eines null-stabilen k-Schritt-Verfahrens, und seine zweite Schranke zeigt, dass kein A-stabiles lineares Mehrschrittverfahren eine Ordnung größer als zwei haben kann, weshalb hochrangige steife Löser auf dem BDF-Kompromiss der relativen statt der absoluten Stabilität beruhen.

Mechanisms

Adams-Verfahren integrieren ein interpolierendes Polynom durch vergangene Ableitungswerte: Adams-Bashforth verwendet nur bekannte Werte (explizit), Adams-Moulton schließt den unbekannten neuen Wert (implizit) für größere Genauigkeit und Stabilität ein. In der Praxis werden die beiden als Prädiktor-Korrektor-Paar verwendet: Die explizite Formel prognostiziert, die implizite korrigiert, typischerweise in ein oder zwei Iterationen. Rückwärtsdifferenzierungsformeln differenzieren stattdessen vergangene Lösungswerte, um die Ableitung am neuen Punkt zu approximieren, was die steif-stabilen Methoden im Kern von Codes für steife gewöhnliche Differentialgleichungen (ODEs) ergibt. Da Mehrschrittverfahren mehrere Startwerte benötigen, werden sie durch ein Einschrittverfahren gebootstrappt.

Clinical relevance

Lineare Mehrschrittverfahren, insbesondere Rückwärtsdifferenzierungsformeln, sind die Grundlage für die in der chemischen Kinetik, der Simulation elektronischer Schaltungen und großen Differential-Algebraischen Systemen eingesetzten steifen ODE-Löser, bei denen die Auswertung der rechten Seite aufwendig ist und die Wiederverwendung vergangener Auswertungen durch Mehrschrittformeln erhebliche Effizienzgewinne erzielt.

History

Adams und Bashforth führten Mehrschrittformeln im neunzehnten Jahrhundert ein, wobei Moulton implizite Varianten hinzufügte; Dahlquists Analyse in den 1950er-60er Jahren etablierte die Stabilitätstheorie und Ordnungsschranken, die das Feld bestimmen, und C. William Gears Arbeit in den 1970er Jahren machte Rückwärtsdifferenzierungsformel-Codes zum Standard für steife Probleme.

Key figures

• John Couch Adams
• Francis Bashforth
• Forest Ray Moulton
• Germund Dahlquist
• C. William Gear

Seminal works

• hairer1993
• iserles2008

Frequently asked questions

Wie unterscheiden sich Mehrschrittverfahren von Runge-Kutta-Verfahren?

Runge-Kutta-Verfahren führen innerhalb jedes Schritts mehrere neue Ableitungsauswertungen durch, verwerfen diese aber danach, während Mehrschrittverfahren Ableitungswerte aus früheren Schritten wiederverwenden. Mehrschrittverfahren sind daher pro Schritt kostengünstiger, benötigen aber zusätzliche Startwerte und eine spezielle Handhabung von Schrittweitenänderungen.

Was ist die Wurzelbedingung?

Es ist die Anforderung, dass die Wurzeln des ersten charakteristischen Polynoms der Methode innerhalb oder auf dem Einheitskreis liegen, wobei Randwurzeln einfach sein müssen. Sie garantiert, dass kleine Fehler nicht akkumulativ verstärkt werden, wodurch die Methode null-stabil und somit konvergent ist.