mini|Einschrittverfahren nähern die Lösung (blau) eines Anfangswert­problems an, indem vom gegebenen Startpunkt aus nacheinander Punkte , usw. bestimmt werden Einschrittverfahren sind in der numerischen Mathematik neben den Mehrschrittverfahren eine große Gruppe von Rechenverfahren zur Lösung von Anfangswertproblemen. Diese Aufgabenstellung, bei der eine gewöhnliche Differentialgleichung zusammen mit einer Startbedingung gegeben ist, spielt in allen Natur- und Ingenieurwissenschaften eine zentrale Rolle und gewinnt beispielsweise auch in den Wirtschafts- und Sozialwissenschaften immer mehr an Bedeutung. Anfangswertprobleme werden verwendet, um dynamische Vorgänge zu analysieren, zu simulieren oder vorherzusagen.

Die namensgebende Grundidee der Einschrittverfahren ist, dass sie ausgehend von dem gegebenen Anfangspunkt Schritt für Schritt entlang der gesuchten Lösung Näherungspunkte berechnen. Dabei verwenden sie jeweils nur die zuletzt bestimmte Näherung für den nächsten Schritt, im Gegensatz zu den Mehrschrittverfahren, die auch weiter zurückliegende Punkte in die Rechnung miteinbeziehen. Die Einschrittverfahren lassen sich grob in zwei Gruppen einteilen: in die expliziten Verfahren, die die neue Näherung direkt aus der alten berechnen, und in die impliziten Verfahren, bei denen dazu eine Gleichung gelöst werden muss. Letztere eignen sich auch für sogenannte steife Anfangswertprobleme.

Das einfachste und älteste Einschrittverfahren, das explizite Euler-Verfahren, wurde 1768 von Leonhard Euler veröffentlicht. Nachdem 1883 eine Gruppe von Mehrschrittverfahren vorgestellt worden war, entwickelten um 1900 Carl Runge, Karl Heun und Wilhelm Kutta deutliche Verbesserungen des eulerschen Verfahrens. Aus diesen ging die große Gruppe der Runge-Kutta-Verfahren hervor, die die wichtigste Klasse von Einschrittverfahren bildet. Weitere Entwicklungen des 20. Jahrhunderts sind beispielsweise die Idee der Extrapolation, vor allem aber Überlegungen zur Schrittweitensteuerung, also zur Wahl geeigneter Längen der einzelnen Schritte eines Verfahrens. Diese Konzepte bilden die Grundlage, um schwierige Anfangswertprobleme, wie sie in modernen Anwendungen auftreten, effizient und mit der benötigten Genauigkeit durch Computerprogramme lösen zu können.

Einführung Gewöhnliche Differentialgleichungen Die Entwicklung der Differential- und Integralrechnung durch den englischen Physiker und Mathematiker Isaac Newton und unabhängig davon durch den deutschen Universalgelehrten Gottfried Wilhelm Leibniz im letzten Drittel des 17. Jahrhunderts war ein wesentlicher Impuls für die Mathematisierung der Wissenschaft in der frühen Neuzeit. Diese Methoden bildeten den Startpunkt des mathematischen Teilgebiets der Analysis und sind in allen Natur- und Ingenieurwissenschaften von zentraler Bedeutung. Während Leibniz von dem geometrischen Problem, Tangenten an gegebene Kurven zu bestimmen, zur Differentialrechnung geführt wurde, ging Newton von der Fragestellung aus, wie sich Änderungen einer physikalischen Größe zu einem bestimmten Zeitpunkt bestimmen lassen.

Zum Beispiel ergibt sich bei der Bewegung eines Körpers dessen Durchschnittsgeschwindigkeit einfach als die zurückgelegte Strecke dividiert durch die dafür benötigte Zeit. Um jedoch die Momentangeschwindigkeit des Körpers zu einem bestimmten Zeitpunkt mathematisch zu formulieren, ist ein Grenzübergang notwendig: Man betrachtet kurze Zeitspannen der Länge , die dabei zurückgelegten Wegstrecken und die zugehörigen Durchschnittsgeschwindigkeiten . Wenn man nun die Zeitspanne gegen null konvergieren lässt und wenn sich dabei die Durchschnittsgeschwindigkeiten ebenfalls einem festen Wert annähern, dann wird dieser Wert die (Momentan-)Geschwindigkeit zu dem gegebenen Zeitpunkt genannt. Bezeichnet die Position des Körpers zur Zeit , dann schreibt man und nennt die Ableitung von .

Der entscheidende Schritt in die Richtung der Differentialgleichungsmodelle ist nun die umgekehrte Fragestellung: Im Beispiel des bewegten Körpers sei also zu jedem Zeitpunkt die Geschwindigkeit bekannt und daraus soll seine Position bestimmt werden. Es ist anschaulich klar, dass zusätzlich die Anfangsposition des Körpers zu einem Zeitpunkt bekannt sein muss, um dieses Problem eindeutig lösen zu können. Es ist also eine Funktion mit gesucht, die die Anfangsbedingung mit gegebenen Werten und erfüllt.

Im Beispiel der Bestimmung der Position eines Körpers aus seiner Geschwindigkeit ist die Ableitung der gesuchten Funktion explizit gegeben. Meist liegt jedoch der wichtige allgemeine Fall gewöhnlicher Differentialgleichungen für eine gesuchte Größe vor: Aufgrund der Naturgesetze oder der Modellannahmen ist ein Funktionszusammenhang bekannt, der angibt, wie die Ableitung der zu bestimmenden Funktion aus und aus dem (unbekannten) Wert berechnet werden kann. Zusätzlich muss wieder eine Anfangsbedingung gegeben sein, die beispielsweise aus einer Messung der gesuchten Größe zu einem fest gewählten Zeitpunkt erhalten werden kann. Zusammengefasst liegt also der folgende allgemeine Aufgabentyp vor: Man finde die Funktion , die die Gleichungen

erfüllt, wobei eine gegebene Funktion ist.

mini|Die dargestellte Lösung der Differentialgleichung des Lorenz-Attraktors ist eine sehr komplizierte Kurve im dreidimensionalen Raum Ein einfaches Beispiel ist eine Größe , die exponentiell wächst. Das bedeutet, dass die momentane Änderung, also die Ableitung proportional zu selbst ist. Es gilt also mit einer Wachstumsrate und beispielsweise einer Anfangsbedingung . Die gesuchte Lösung lässt sich in diesem Fall bereits mit elementarer Differentialrechnung finden und mithilfe der Exponentialfunktion angeben: Es gilt .

Die gesuchte Funktion in einer Differentialgleichung kann vektorwertig sein, das heißt, für jedes kann ein Vektor mit Komponenten sein. Man spricht dann auch von einem -dimensionalen Differentialgleichungssystem. Im Anschauungsfall eines bewegten Körpers ist dann seine Position im -dimensionalen euklidischen Raum und seine Geschwindigkeit zur Zeit . Durch die Differentialgleichung ist also in jedem Zeit- und Raumpunkt die Geschwindigkeit der gesuchten Bahnkurve mit Richtung und Betrag vorgegeben. Daraus soll die Bahn selbst berechnet werden.

Grundidee der Einschrittverfahren Bei der oben als Beispiel betrachteten einfachen Differentialgleichung des exponentiellen Wachstums ließ sich die Lösungsfunktion direkt angeben. Das ist bei komplizierteren Problemen im Allgemeinen nicht mehr möglich. Man kann dann zwar unter gewissen Zusatzvoraussetzungen an die Funktion zeigen, dass eine eindeutig bestimmte Lösung des Anfangswertproblems existiert; diese kann aber dann nicht mehr durch Lösungsverfahren der Analysis (wie beispielsweise Trennung der Variablen, einen Exponentialansatz oder Variation der Konstanten) explizit berechnet werden. In diesem Fall können numerische Verfahren verwendet werden, um Näherungen für die gesuchte Lösung zu bestimmen.

Die Verfahren zur numerischen Lösung von Anfangswertproblemen gewöhnlicher Differentialgleichungen lassen sich grob in zwei große Gruppen einteilen: die Einschritt- und die Mehrschrittverfahren. Beiden Gruppen ist gemeinsam, dass sie schrittweise Näherungen für die gesuchten Funktionswerte an Stellen berechnen. Die definierende Eigenschaft der Einschrittverfahren ist dabei, dass zur Bestimmung der folgenden Näherung nur die „aktuelle“ Näherung verwendet wird. Bei Mehrschrittverfahren gehen im Gegensatz dazu zusätzlich bereits zuvor berechnete Näherungen mit ein; ein Dreischrittverfahren würde also beispielsweise außer auch noch und zur Bestimmung der neuen Näherung verwenden.

mini|Zwei Schritte des expliziten Euler-Verfahrens Das einfachste und grundlegendste Einschrittverfahren ist das explizite Euler-Verfahren, das der Schweizer Mathematiker und Physiker Leonhard Euler 1768 in seinem Lehrbuch Institutiones Calculi Integralis vorstellte. Die Idee dieser Methode ist es, die gesuchte Lösung durch eine stückweise lineare Funktion anzunähern, bei der in jedem Schritt von der Stelle zur Stelle die Steigung des Geradenstücks durch gegeben ist. Genauer betrachtet: Durch die Problemstellung ist bereits ein Wert der gesuchten Funktion gegeben, nämlich . Aber auch die Ableitung an dieser Stelle ist bekannt, denn es gilt . Damit kann die Tangente an den Graphen der Lösungsfunktion bestimmt und als Näherung verwendet werden. An der Stelle ergibt sich mit der Schrittweite . Dieses Vorgehen kann nun in den folgenden Schritten fortgesetzt werden. Insgesamt ergibt sich damit für das explizite Euler-Verfahren die Rechenvorschrift

mit den Schrittweiten .

Das explizite Euler-Verfahren ist der Ausgangspunkt für zahlreiche Verallgemeinerungen, bei denen die Steigung , durch Steigungen ersetzt wird, die das Verhalten der Lösung zwischen den Stellen und genauer annähern. Eine zusätzliche Idee für Einschrittverfahren bringt das implizite Eulerverfahren, das als Steigung verwendet. Diese Wahl erscheint auf den ersten Blick wenig geeignet, da ja unbekannt ist. Als Verfahrensschritt erhält man aber nun die Gleichung

aus der (gegebenenfalls durch ein numerisches Verfahren) berechnet werden kann. Wählt man beispielsweise als Steigung das arithmetische Mittel aus den Steigungen des expliziten und des impliziten Euler-Verfahrens, so erhält man das implizite Trapez-Verfahren. Aus diesem lässt sich wiederum ein explizites Verfahren gewinnen, wenn man zum Beispiel das unbekannte auf der rechten Seite der Gleichung durch die Näherung des expliziten Euler-Verfahrens nähert, das sogenannte Heun-Verfahren. All diesen Verfahren und allen weiteren Verallgemeinerungen ist die Grundidee der Einschrittverfahren gemeinsam: der Schritt

mit einer Steigung , die von , und sowie (bei impliziten Verfahren) von abhängen kann.

Definition Mit den Überlegungen aus dem Einführungsabschnitt dieses Artikels kann der Begriff des Einschrittverfahrens wie folgt definiert werden: Gesucht sei die Lösung des Anfangswertproblems , . Dabei werde vorausgesetzt, dass die Lösung

auf einem gegebenen Intervall existiert und eindeutig bestimmt ist. Sind

Zwischenstellen im Intervall und die zugehörigen Schrittweiten, dann heißt das durch , gegebene Verfahren Einschrittverfahren mit Verfahrensfunktion . Wenn nicht von abhängt, dann nennt man es explizites Einschrittverfahren. Anderenfalls muss in jedem Schritt eine Gleichung für gelöst werden, und das Verfahren wird implizit genannt.

Konsistenz und Konvergenz Konvergenzordnung mini|Globaler Fehler bei verschiedenen Schrittweiten für drei Einschritt­verfahren. In doppelt-logarithmischer Auftragung erscheint der Zusammen­hang jeweils ungefähr linear, die Steigungen entsprechen dabei den Konvergenz­ordnungen 1, 2 und 4. Für ein praxistaugliches Einschrittverfahren sollen die berechneten gute Näherungen für die Werte der exakten Lösung an der Stelle sein. Da im Allgemeinen die Größen -dimensionale Vektoren sind, misst man die Güte dieser Näherung mit einer Vektornorm als , dem Fehler an der Stelle . Es ist wünschenswert, dass diese Fehler für alle schnell gegen null konvergieren, falls man die Schrittweiten gegen null konvergieren lässt. Um auch den Fall nicht konstanter Schrittweiten zu erfassen, definiert man dazu genauer als das Maximum der verwendeten Schrittweiten und betrachtet das Verhalten des maximalen Fehlers an allen Stellen im Vergleich zu Potenzen von . Man sagt, das Einschrittverfahren zur Lösung des gegebenen Anfangswertproblems habe die Konvergenzordnung , wenn die Abschätzung

für alle hinreichend kleinen mit einer von unabhängigen Konstante gilt.