Einschrittverfahren

In der numerischen Mathematik ist ein Einschrittverfahren eine Methode zur näherungsweisen Lösung von Anfangswertproblemen. Im Gegensatz zu Mehrschrittverfahren werden hier zur Berechnung der Näherung an die Lösung keine Daten von vorhergehenden Zeitpunkten benutzt. Die wichtigste Klasse von Einschrittverfahren sind die Runge-Kutta-Verfahren.

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 physikalischen Fragestellung aus, wie sich Änderungen einer Größe zu einem bestimmten Zeitpunkt bestimmen lassen. So ergibt sich zum Beispiel 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 ${\displaystyle v(t)}${\displaystyle v(t)} des Körpers zu einem bestimmten Zeitpunkt ${\displaystyle t}${\displaystyle t} mathematisch zu formulieren, ist ein Grenzübergang notwendig: Man betrachtet kurze Zeitspannen der Länge ${\displaystyle \Delta t}${\displaystyle \Delta t}, die dabei zurückgelegten Wegstrecken ${\displaystyle \Delta x}${\displaystyle \Delta x} und die zugehörigen Durchschnittsgeschwindigkeiten ${\displaystyle {\tfrac {\Delta x}{\Delta t}}}${\displaystyle {\tfrac {\Delta x}{\Delta t}}}. Lässt man nun die Zeitspanne ${\displaystyle \Delta t}${\displaystyle \Delta t} gegen null konvergieren und nähern sich dabei die Durchschnittsgeschwindigkeiten ebenfalls einem festen Wert an, dann wird dieser Wert die (Momentan-)Geschwindigkeit ${\displaystyle v(t)}${\displaystyle v(t)} zu dem gegebenen Zeitpunkt ${\displaystyle t}${\displaystyle t} genannt. Bezeichnet ${\displaystyle x(t)}${\displaystyle x(t)} die Position des Körpers zur Zeit ${\displaystyle t}${\displaystyle t}, dann schreibt man ${\displaystyle v(t)=x'(t)}${\displaystyle v(t)=x'(t)} und nennt ${\displaystyle v}${\displaystyle v} die Ableitung von ${\displaystyle x}${\displaystyle x}.

Der entscheidende Schritt in die Richtung der Differentialgleichungsmodelle ist nun die umgekehrte Fragestellung: Im Beispiel des bewegten Körpers sei also zu jeden Zeitpunkt ${\displaystyle t}${\displaystyle t} die Geschwindigkeit ${\displaystyle v(t)}${\displaystyle v(t)} bekannt und daraus soll seine Position ${\displaystyle x(t)}${\displaystyle x(t)} bestimmt werden. Es ist anschaulich klar, dass zusätzlich die Anfangsposition des Körpers zu einem Zeitpunkt ${\displaystyle t_{0}}${\displaystyle t_{0}} bekannt sein muss, um dieses Problem eindeutig lösen zu können. Es ist also eine Funktion ${\displaystyle x(t)}${\displaystyle x(t)} mit ${\displaystyle x'(t)=v(t)}${\displaystyle x'(t)=v(t)} gesucht, die die Anfangsbedingung ${\displaystyle x(t_{0})=x_{0}}${\displaystyle x(t_{0})=x_{0}} mit gegebenen Werten ${\displaystyle t_{0}}${\displaystyle t_{0}} und ${\displaystyle x_{0}}${\displaystyle x_{0}} erfüllt. In diesem einfachsten Fall eines Anfangswertproblems ist die Ableitung der gesuchten Funktion explizit gegeben. Meist liegt jedoch der wichtige allgemeine Fall gewöhnlicher Differentialgleichungen vor: Für eine gesuchte Funktion ${\displaystyle y}${\displaystyle y} ist aufgrund der Naturgesetze oder der Modellannahmen ein Funktionszusammenhang bekannt, der angibt, wie die Ableitung ${\displaystyle y'(t)}${\displaystyle y'(t)} aus ${\displaystyle t}${\displaystyle t} und aus dem (unbekannten) Wert ${\displaystyle y(t)}${\displaystyle y(t)} berechnet werden kann. Zusammen mit der Anfangsbedingung liegt also der folgende allgemeine Aufgabentyp vor: Man finde die Funktion ${\displaystyle y}${\displaystyle y}, die die Gleichungen

${\displaystyle y'(t)=f(t,y(t)),\quad y(t_{0})=y_{0}}${\displaystyle y'(t)=f(t,y(t)),\quad y(t_{0})=y_{0}}

erfüllt, wobei ${\displaystyle f}${\displaystyle f} eine gegebene Funktion ist. Ein einfaches Beispiel ist eine Größe ${\displaystyle y}${\displaystyle y}, die exponentiell wächst. Das bedeutet, dass die momentane Änderung, also die Ableitung ${\displaystyle y'(t)}${\displaystyle y'(t)} proportional zu ${\displaystyle y(t)}${\displaystyle y(t)} selbst ist. Es gilt also ${\displaystyle y'(t)=\lambda \cdot y(t)}${\displaystyle y'(t)=\lambda \cdot y(t)} mit einer Wachstumsrate ${\displaystyle \lambda }${\displaystyle \lambda } und beispielsweise einer Anfangsbedingung ${\displaystyle y(0)=y_{0}}${\displaystyle y(0)=y_{0}}. Die gesuchte Lösung ${\displaystyle y}${\displaystyle y} lässt sich in diesem Fall leicht mit elementarer Differentialrechnung finden und mithilfe der Exponentialfunktion angeben: Es gilt ${\displaystyle y(t)=y_{0}\cdot e^{\lambda \cdot t}}${\displaystyle y(t)=y_{0}\cdot e^{\lambda \cdot t}}.

Die gesuchte Funktion ${\displaystyle y}${\displaystyle y} in einer Differentialgleichung kann auch vektorwertig sein, das heißt, für jedes ${\displaystyle t}${\displaystyle t} kann ${\displaystyle y(t)=(y_{1}(t),\dotsc ,y_{d}(t))}${\displaystyle y(t)=(y_{1}(t),\dotsc ,y_{d}(t))} ein Vektor mit ${\displaystyle d}${\displaystyle d} Komponenten sein. Man spricht dann auch von einem ${\displaystyle d}${\displaystyle d}-dimensionalen Differentialgleichungssystem. Im Anschauungsfall eines bewegten Körpers ist dann ${\displaystyle y(t)}${\displaystyle y(t)} seine Position im ${\displaystyle d}${\displaystyle d}-dimensionalen euklidischen Raum und ${\displaystyle y'(t)}${\displaystyle y'(t)} seine Geschwindigkeit zur Zeit ${\displaystyle t}${\displaystyle t}. 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.

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 ${\displaystyle f}${\displaystyle f} 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 Differentialgleichung lassen sich grob in zwei große Gruppen einteilen: die Einschritt- und die Mehrschrittverfahren. Beiden Gruppen ist gemeinsam, dass sie schrittweise Näherungen ${\displaystyle y_{0},y_{1},y_{2}\dotsc }${\displaystyle y_{0},y_{1},y_{2}\dotsc } für die gesuchten Funktionswerte ${\displaystyle y(t_{0}),y(t_{1}),y(t_{2})\dotsc }${\displaystyle y(t_{0}),y(t_{1}),y(t_{2})\dotsc } an Stellen ${\displaystyle t_{0}<t_{1}<t_{2}<\ldots }${\displaystyle t_{0}<t_{1}<t_{2}<\ldots } berechnen. Die definierende Eigenschaft der Einschrittverfahren ist dabei, dass zur Bestimmung der folgenden Näherung ${\displaystyle y_{j+1}}${\displaystyle y_{j+1}} nur die „aktuelle" Näherung ${\displaystyle y_{j}}${\displaystyle y_{j}} verwendet wird. Bei Mehrschrittverfahren gehen im Gegensatz dazu zusätzlich bereits zuvor berechnete Näherungen mit ein; ein 3-Schrittverfahren würde also beispielsweise außer ${\displaystyle y_{j}}${\displaystyle y_{j}} auch noch ${\displaystyle y_{j-1}}${\displaystyle y_{j-1}} und ${\displaystyle y_{j-2}}${\displaystyle y_{j-2}} zur Bestimmung der neuen Näherung ${\displaystyle y_{j+1}}${\displaystyle y_{j+1}} verwenden.

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 ${\displaystyle t_{j}}${\displaystyle t_{j}} zur Stelle ${\displaystyle t_{j+1}}${\displaystyle t_{j+1}} die Steigung des Geradenstücks durch ${\displaystyle f(t_{j},y_{j})}${\displaystyle f(t_{j},y_{j})} gegeben ist. Genauer betrachtet: Durch die Problemstellung ist bereits ein Wert der gesuchten Funktion gegeben, nämlich ${\displaystyle y(t_{0})=y_{0}}${\displaystyle y(t_{0})=y_{0}}. Aber auch die Ableitung an dieser Stelle ist bekannt, denn es gilt ${\displaystyle y'(t_{0})=f(t_{0},y_{0})}${\displaystyle y'(t_{0})=f(t_{0},y_{0})}. Damit kann die Tangente an den Graphen der Lösungsfunktion bestimmt und als Näherung verwendet werden. An der Stelle ${\displaystyle t_{1}>t_{0}}${\displaystyle t_{1}>t_{0}} ergibt sich mit der Schrittweite ${\displaystyle h_{0}:=t_{1}-t_{0}}${\displaystyle h_{0}:=t_{1}-t_{0}}

${\displaystyle y(t_{1})\approx y_{0}+h_{0}\cdot f(t_{0},y_{0})=:y_{1}}${\displaystyle y(t_{1})\approx y_{0}+h_{0}\cdot f(t_{0},y_{0})=:y_{1}}.

Dieses Vorgehen kann nun in den folgenden Schritten fortgesetzt werden. Insgesamt ergibt sich damit für das explizite Euler-Verfahren die Rechenvorschrift

${\displaystyle y_{j+1}=y_{j}+h_{j}\cdot f(t_{j},y_{j}),\quad j=0,1,2\dotsc }${\displaystyle y_{j+1}=y_{j}+h_{j}\cdot f(t_{j},y_{j}),\quad j=0,1,2\dotsc }

mit den Schrittweiten ${\displaystyle h_{j}=t_{j+1}-t_{j}}${\displaystyle h_{j}=t_{j+1}-t_{j}}.^[1]

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

${\displaystyle y_{j+1}=y_{j}+h_{j}\cdot f(t_{j+1},y_{j+1})}${\displaystyle y_{j+1}=y_{j}+h_{j}\cdot f(t_{j+1},y_{j+1})}

aus der ${\displaystyle y_{j+1}}${\displaystyle y_{j+1}} (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 diesen lässt sich wiederum ein explizites Verfahren gewinnen, wenn man zum Beispiel das unbekannte ${\displaystyle y_{j+1}}${\displaystyle y_{j+1}} auf der rechten Seite der Gleichung durch die Näherung des expliziten Euler-Verfahren nähert, das sogenannte Heun-Verfahren. All diesen Verfahren und allen weiteren Verallgemeinerungen ist die Grundidee der Einschrittverfahren gemeinsam: der Schritt

${\displaystyle y_{j+1}=y_{j}+h_{j}\cdot \Phi _{f}}${\displaystyle y_{j+1}=y_{j}+h_{j}\cdot \Phi _{f}}

mit einer Steigung, die von ${\displaystyle t_{j}}${\displaystyle t_{j}}, ${\displaystyle y_{j}}${\displaystyle y_{j}} und ${\displaystyle h_{j}}${\displaystyle h_{j}} sowie (bei impliziten Verfahren) von ${\displaystyle y_{j+1}}${\displaystyle y_{j+1}} abhängen kann.

Gesucht sei die Lösung ${\displaystyle y}${\displaystyle y} des Anfangswertproblems

${\displaystyle y'(t)=f(t,y(t))}${\displaystyle y'(t)=f(t,y(t))}, ${\displaystyle \quad y(t_{0})=y_{0}}${\displaystyle \quad y(t_{0})=y_{0}}.

Dabei werde vorausgesetzt, dass die Lösung

${\displaystyle y\colon I\to \mathbb {R} ^{d}}${\displaystyle y\colon I\to \mathbb {R} ^{d}}

auf einem gegebenen Intervall ${\displaystyle I=[t_{0},T]}${\displaystyle I=[t_{0},T]} existiert und eindeutig bestimmt ist. Sind

${\displaystyle t_{0}<t_{1}<t_{2}<\ldots <t_{n}=T}${\displaystyle t_{0}<t_{1}<t_{2}<\ldots <t_{n}=T}

Zwischenstellen im Intervall ${\displaystyle I}${\displaystyle I} und ${\displaystyle h_{j}=t_{j+1}-t_{j}}${\displaystyle h_{j}=t_{j+1}-t_{j}} die zugehörigen Schrittweiten, dann heißt das durch

${\displaystyle y_{j+1}=y_{j}+h_{j}\Phi _{f}(t_{j},y_{j},y_{j+1},h_{j})}${\displaystyle y_{j+1}=y_{j}+h_{j}\Phi _{f}(t_{j},y_{j},y_{j+1},h_{j})}, ${\displaystyle \quad j=0,\dotsc ,n-1}${\displaystyle \quad j=0,\dotsc ,n-1}

gegebene Verfahren Einschrittverfahren mit Verfahrensfunktion ${\displaystyle \Phi _{f}}${\displaystyle \Phi _{f}}. Wenn ${\displaystyle \Phi _{f}}${\displaystyle \Phi _{f}} nicht von ${\displaystyle y_{j+1}}${\displaystyle y_{j+1}} abhängt, dann nennt man es explizites Einschrittverfahren. Anderenfalls muss in jedem Schritt ${\displaystyle j}${\displaystyle j} eine Gleichung für ${\displaystyle y_{j+1}}${\displaystyle y_{j+1}} gelöst werden, und das Verfahren wird implizit genannt.

Für ein praxistaugliches Einschrittverfahren sollen die berechneten ${\displaystyle y_{j}}${\displaystyle y_{j}} gute Näherungen für Werte ${\displaystyle y(t_{j})}${\displaystyle y(t_{j})} der exakten Lösung ${\displaystyle y}${\displaystyle y} an der Stelle ${\displaystyle t_{j}}${\displaystyle t_{j}} sein. Da im Allgemeinen die Größen ${\displaystyle d}${\displaystyle d}-dimensionale Vektoren sind, misst man die Güte dieser Näherung mit einer Vektornorm als Fehler ${\displaystyle \|y_{j}-y(t_{j})\|}${\displaystyle \|y_{j}-y(t_{j})\|}. Es ist wünschenswert, dass diese Fehler für alle ${\displaystyle j}${\displaystyle j} 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 ${\displaystyle h}${\displaystyle h} als das Maximum der verwendeten Schrittweiten und betrachtet das Verhalten des maximalen Fehlers an allen Stellen ${\displaystyle t_{j}}${\displaystyle t_{j}} im Vergleich zu Potenzen von ${\displaystyle h}${\displaystyle h}. Man sagt, das Einschrittverfahren zur Lösung des gegebenen Anfangswertproblems habe die Konvergenzordnung ${\displaystyle p\geq 1}${\displaystyle p\geq 1}, wenn die Abschätzung

${\displaystyle \max _{j=0,\dotsc ,n}\|y_{j}-y(t_{j})\|\leq Ch^{p}}${\displaystyle \max _{j=0,\dotsc ,n}\|y_{j}-y(t_{j})\|\leq Ch^{p}}

für alle hinreichend kleinen ${\displaystyle h}${\displaystyle h} mit einer von ${\displaystyle h}${\displaystyle h} unabhängigen Konstante ${\displaystyle C>0}${\displaystyle C>0} gilt.^[2]

Die Konvergenzordnung ist die wichtigste Kenngröße für den Vergleich verschiedener Einschrittverfahren.ref>Robert Plato: Numerische Mathematik kompakt. 4. Auflage. Vieweg+Teubner, Wiesbaden 2010, ISBN 978-3-8348-1018-2, S. 156. </ref> Ein Verfahren mit höherer Konvergenzordnung ${\displaystyle p}${\displaystyle p} liefert im Allgemeinen bei vorgegebener Schrittweite einen kleineren Gesamtfehler bzw. umgekehrt sind weniger Schritte nötig, um eine vorgegebene Genauigkeit zu erreichen. Bei einem Verfahren mit ${\displaystyle p=1}${\displaystyle p=1} ist zu erwarten, dass sich bei einer Halbierung der Schrittweite auch der Fehler nur ungefähr halbiert. Bei einem Verfahren der Konvergenzordnung ${\displaystyle p=4}${\displaystyle p=4} kann man hingegen davon ausgehen, dass sich dabei der Fehler ungefähr um den Faktor ${\displaystyle \left({\tfrac {1}{2}}\right)^{4}={\tfrac {1}{16}}}${\displaystyle \left({\tfrac {1}{2}}\right)^{4}={\tfrac {1}{16}}} verringert.

Die in der Definition der Konvergenzordnung betrachteten Fehler ${\displaystyle \|y_{j}-y(t_{j})\|}${\displaystyle \|y_{j}-y(t_{j})\|} setzen sich auf eine zunächst kompliziert erscheinende Weise aus zwei Einzelkomponenten zusammen: Natürlich hängen sie zum einen von dem Fehler ab, den das Verfahren in einem einzelnen Schritt macht, indem es die unbekannte Steigung der gesuchten Funktion durch die Verfahrensfunktion annähert. Zum anderen ist aber zusätzlich zu berücksichtigen, dass bereits der Startpunkt ${\displaystyle (t_{j},y_{j})}${\displaystyle (t_{j},y_{j})} eines Schrittes nicht von der exakten Stelle ${\displaystyle (t_{j},y(t_{j}))}${\displaystyle (t_{j},y(t_{j}))} aus erfolgt; der Fehler nach diesem Schritt hängt also auch von allen Fehlern ab, die bereits in der vorangegangenen Schritten gemacht wurden. Aufgrund der einheitlichen Definition der Einschrittverfahren, die sich nur in der Wahl der Verfahrensfunktion ${\displaystyle \Phi _{f}}${\displaystyle \Phi _{f}} unterscheiden, lässt sich aber beweisen, dass man (unter gewissen technischen Voraussetzungen an ${\displaystyle \Phi _{f}}${\displaystyle \Phi _{f}}) direkt von der Fehlerordnung in einem einzelnen Schritt, der sogenannten Konsistenzordnung, auf die Konvergenzordnung schließen kann.

Das Begriff der Konsistenz ist ein allgemeines und zentrales Konzept der modernen numerischen Mathematik. Während man bei der Konvergenz eines Verfahrens untersucht, wie gut die numerischen Näherungen zur exakten Lösung passen, stellt man sich bei der Konsistenz vereinfacht gesprochen die „umgekehrte" Frage: Wie gut erfüllt die exakte Lösung die Verfahrensvorschrift? In dieser allgemeinen Theorie gilt, dass ein Verfahren genau dann konvergent ist, wenn es konsistent und stabil ist. Um die Notation zu vereinfachen, soll in der folgenden Überlegung angenommen werden, dass ein explizites Einschrittverfahren

${\displaystyle y_{j+1}=y_{j}+h\Phi _{f}(t_{j},y_{j},h)}${\displaystyle y_{j+1}=y_{j}+h\Phi _{f}(t_{j},y_{j},h)}

mit konstanter Schrittweite ${\displaystyle h}${\displaystyle h} vorliegt. Mit der wahren Lösung ${\displaystyle t\mapsto y(t)}${\displaystyle t\mapsto y(t)} definiert man den lokalen Abschneidefehler (auch lokaler Verfahrensfehler genannt) ${\displaystyle \eta }${\displaystyle \eta } als^[3]

${\displaystyle \eta (t,h)=y(t)+h\Phi _{f}(t,y(t),h)-y(t+h)}${\displaystyle \eta (t,h)=y(t)+h\Phi _{f}(t,y(t),h)-y(t+h)}.

Man nimmt also an, dass die exakte Lösung bekannt ist, startet einen Verfahrensschritt an der Stelle ${\displaystyle (t,y(t))}${\displaystyle (t,y(t))} und bildet die Differenz zu exakten Lösung an der Stelle ${\displaystyle t+h}${\displaystyle t+h}. Damit definiert man: Ein Einschrittverfahren hat die Konsistenzordnung ${\displaystyle p\geq 1}${\displaystyle p\geq 1}, wenn die Abschätzung

${\displaystyle \|\eta (t,h)\|\leq Ch^{p+1}}${\displaystyle \|\eta (t,h)\|\leq Ch^{p+1}}

für alle hinreichend kleinen ${\displaystyle h}${\displaystyle h} mit einer von ${\displaystyle h}${\displaystyle h} unabhängigen Konstante ${\displaystyle C>0}${\displaystyle C>0} gilt.

Der auffällige Unterschied zwischen den Definitionen der Konsistenzordnung und der Konvergenzordnung ist die Potenz ${\displaystyle h^{p+1}}${\displaystyle h^{p+1}} anstelle von ${\displaystyle h^{p}}${\displaystyle h^{p}}. Das lässt sich anschaulich so deuten, dass beim Übergang vom lokalen zum globalen Fehler eine Potenz der Schrittweite „verlorengeht". Es gilt nämlich der folgende, für die Theorie der Einschrittverfahren zentrale Satz:

Ist die Verfahrensfunktion ${\displaystyle \Phi _{f}}${\displaystyle \Phi _{f}} Lipschitz-stetig und hat das zugehörige Einschrittverfahren die Konsistenzordnung ${\displaystyle p}${\displaystyle p}, dann hat es die auch die Konvergenzordnung ${\displaystyle p}${\displaystyle p}.

Die Lipschitz-Stetigkeit als Zusatzvoraussetzung für die Stabilität ist normalerweise leicht einzusehen, wenn die Funktion ${\displaystyle f}${\displaystyle f} aus der Differentialgleichung Lipschitz-stetig ist. Diese Forderung ist im Allgemeinen sowieso vorausgesetzt, um die eindeutige Lösbarkeit des Anfangswertproblems zu garantieren. Nach dem Satz genügt es also, die Konsistenzordnung eines Einschrittverfahrens zu bestimmen. Das lässt sich prinzipiell durch Taylor-Entwicklung von ${\displaystyle \eta (t,h)}${\displaystyle \eta (t,h)} nach Potenzen von ${\displaystyle h}${\displaystyle h} erreichen. In der Praxis werden die entstehenden Formeln für höhere Ordnungen sehr kompliziert und unübersichtlich, sodass zusätzliche Konzepte und Notationen benötigt werden.

Wenn man die Steigungen ${\displaystyle f(t_{j},y_{j})}${\displaystyle f(t_{j},y_{j})} des expliziten Euler-Verfahrens und ${\displaystyle f(t_{j+1},y_{j+1})}${\displaystyle f(t_{j+1},y_{j+1})} des impliziten Euler-Verfahrens, wie sie an den beiden Endpunkten eines Schritts vorliegen, mittelt, kann man hoffen, eine bessere Näherung über das ganze Intervall zu erhalten. Tatsächlich lässt sich beweisen, dass das so erhaltene implizite Trapez-Verfahren

${\displaystyle y_{j+1}=y_{j}+{\frac {h}{2}}{\Big (}f(t_{j},y_{j})+f(t_{j+1},y_{j+1}){\Big )}}${\displaystyle y_{j+1}=y_{j}+{\frac {h}{2}}{\Big (}f(t_{j},y_{j})+f(t_{j+1},y_{j+1}){\Big )}}

die Konvergenzordnung 2 hat. Dieses Verfahren weist sehr gute Stabilitätseigenschaften auf, ist allerdings implizit, sodass in jedem Schritt eine Gleichung für ${\displaystyle y_{j+1}}${\displaystyle y_{j+1}} gelöst werden muss. Nähert man diese Größe auf der rechten Seite der Gleichung durch das explizite Euler-Verfahren an, so entsteht das explizite Verfahren von Heun

${\displaystyle y_{j+1}=y_{j}+{\frac {h}{2}}{\Big [}f(t_{j},y_{j})+f{\big (}t_{j+1},y_{j}+hf(t_{j},y_{j}){\big )}{\Big ]}}${\displaystyle y_{j+1}=y_{j}+{\frac {h}{2}}{\Big [}f(t_{j},y_{j})+f{\big (}t_{j+1},y_{j}+hf(t_{j},y_{j}){\big )}{\Big ]}},

das ebenfalls die Konvergenzordnung 2 besitzt. Ein weiteres einfaches explizites Verfahren der Ordnung 2, das verbesserte Euler-Verfahren, erhält man durch folgende Überlegung: Eine „mittlere" Steigung im Verfahrensschritt wäre die Steigung der Lösung ${\displaystyle y}${\displaystyle y} in der Mitte des Schritts, also an der Stelle ${\displaystyle t_{j}+{\tfrac {h}{2}}}${\displaystyle t_{j}+{\tfrac {h}{2}}}. Da die Lösung aber unbekannt ist, nähert man sie durch einen expliziten Euler-Schritt mit halber Schrittweite an. Es ergibt sich die Verfahrensvorschrift

${\displaystyle y_{j+1}=y_{j}+hf{\big (}t_{j}+{\tfrac {h}{2}},y_{j}+{\tfrac {h}{2}}f(t_{j},y_{j}){\big )}}${\displaystyle y_{j+1}=y_{j}+hf{\big (}t_{j}+{\tfrac {h}{2}},y_{j}+{\tfrac {h}{2}}f(t_{j},y_{j}){\big )}}.

Die erwähnten Ideen für einfache Einschrittverfahren führen bei weiterer Verallgemeinerung zur wichtigen Klasse der Runge-Kutta-Verfahren. Zum Beispiel lässt sich das Verfahren von Heun übersichtlicher so präsentieren: Zuerst wird eine Hilfssteigung ${\displaystyle k_{1}=f(t_{j},y_{j})}${\displaystyle k_{1}=f(t_{j},y_{j})} berechnet, nämlich die Steigung des expliziten Euler-Verfahrens. Damit wird eine weitere Hilfssteigung bestimmt, hier ${\displaystyle k_{2}=f(t_{j}+h,y_{h}+hk_{1})}${\displaystyle k_{2}=f(t_{j}+h,y_{h}+hk_{1})}. Die tatsächlich verwendete Steigung, also ${\displaystyle \Phi _{f}}${\displaystyle \Phi _{f}} ergibt sich anschließend als ein gewichtetes Mittel der Hilfssteigungen, im Verfahren von Heun also ${\displaystyle {\tfrac {1}{2}}k_{1}+{\tfrac {1}{2}}k_{2}}${\displaystyle {\tfrac {1}{2}}k_{1}+{\tfrac {1}{2}}k_{2}}. Dieses Vorgehen lässt sich auf mehr als zwei Hilfssteigungen verallgemeinern. Ein ${\displaystyle s}${\displaystyle s}-stufiges Runge-Kunge-Kutta-Verfahren berechnet zunächst Hilfssteigungen ${\displaystyle k_{1},\dotsc ,k_{s}}${\displaystyle k_{1},\dotsc ,k_{s}} durch Auswertung von ${\displaystyle f}${\displaystyle f} an geeigneten Stellen und anschließend ${\displaystyle \Phi _{f}}${\displaystyle \Phi _{f}} als gewichtetes Mittel. Bei einem expliziten Runge-Kutta-Verfahren werden die Hilfssteigungen ${\displaystyle k_{1},k_{2},k_{3},\dotsc }${\displaystyle k_{1},k_{2},k_{3},\dotsc } der Reihe nach direkt berechnet, bei einem impliziten ergeben sie sich als Lösungen eines Gleichungsystems. Als typisches Beispiel sei das explizite klassische Runge-Kutta-Verfahren der Ordnung 4 angeführt, dass mitunter einfach als das Runge-Kutta-Verfahren bezeichnet wird: Dabei werden zunächst die vier Hilfssteigungungen ${\displaystyle k_{1}=f(t_{j},y_{j})}${\displaystyle k_{1}=f(t_{j},y_{j})}, ${\displaystyle k_{2}=f(t_{j}+{\tfrac {h}{2}},y_{j}+{\tfrac {h}{2}}k_{1})}${\displaystyle k_{2}=f(t_{j}+{\tfrac {h}{2}},y_{j}+{\tfrac {h}{2}}k_{1})}, ${\displaystyle k_{3}=f(t_{j}+{\tfrac {h}{2}},y_{j}+{\tfrac {h}{2}}k_{2})}${\displaystyle k_{3}=f(t_{j}+{\tfrac {h}{2}},y_{j}+{\tfrac {h}{2}}k_{2})} und ${\displaystyle k_{4}=f(t_{j}+h,y_{j}+hk_{3})}${\displaystyle k_{4}=f(t_{j}+h,y_{j}+hk_{3})} berechnet und dann als Verfahrenssteigung das gewichtete Mittel ${\displaystyle {\tfrac {1}{6}}k_{1}+{\tfrac {1}{3}}k_{2}+{\tfrac {1}{3}}k_{3}+{\tfrac {1}{6}}k_{4}}${\displaystyle {\tfrac {1}{6}}k_{1}+{\tfrac {1}{3}}k_{2}+{\tfrac {1}{3}}k_{3}+{\tfrac {1}{6}}k_{4}} verwendet.

• Wolfgang Dahmen, Arnold Reusken: Numerik für Ingenieure und Naturwissenschaftler. 2. Auflage. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-76492-2, Kap. 11: Gewöhnliche Differentialgleichungen. 
• Peter Deuflhard, Folkmar Bornemann: Numerische Mathematik 2 – Gewöhnliche Differentialgleichungen. 3. Auflage. Walter de Gruyter, Berlin 2008, ISBN 978-3-11-020356-1. 
• David F. Griffiths, Desmond J. Higham: Numerical Methods for Ordinary Differential Equations – Initial Value Problems. Springer, London 2010, ISBN 978-0-85729-147-9. 
• Robert Plato: Numerische Mathematik kompakt. 4. Auflage. Vieweg+Teubner, Wiesbaden 2010, ISBN 978-3-8348-1018-2, Kap. 7: Einschrittverfahren für Anfangswertprobleme. 
• Hans Rudolf Schwarz, Norbert Köckler: Numerische Mathematik. 8. Auflage. Vieweg+Teubner, Wiesbaden 2011, ISBN 978-3-8348-1551-4, Kap. 8: Anfangswertprobleme. 
• Karl Strehmel, Rüdiger Weiner, Helmut Podhaisky: Numerik gewöhnlicher Differentialgleichungen. 2. Auflage. Springer Spektrum, Wiesbaden 2012, ISBN 978-3-8348-1847-8. 

• Lars Grüne: Numerische Methoden für gewöhnliche Differentialgleichungen (Numerische Mathematik II). (PDF) 2008, abgerufen am 8. September 2017 (Vorlesungsskript der Universität Bayreuth). 
• Peter Spellucci: Numerik gewöhnlicher Differentialgleichungen. (PDF) 2007, abgerufen am 8. September 2017 (Vorlesungsskript der TU Darmstadt). 
• Hans U. Fuchs: Numerical Methods for Differential Equations. (PDF) 2007, abgerufen am 8. September 2017 (englisch, Vorlesungsskript der Zürcher Hochschule für Angewandte Wissenschaften). 

1. ↑ Wolfgang Dahmen, Arnold Reusken: Numerik für Ingenieure und Naturwissenschaftler. 2. Auflage. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-76492-2, S. 386 f. 
2. ↑ Robert Plato: Numerische Mathematik kompakt. 4. Auflage. Vieweg+Teubner, Wiesbaden 2010, ISBN 978-3-8348-1018-2, S. 157. 
3. ↑ Robert Plato: Numerische Mathematik kompakt. 4. Auflage. Vieweg+Teubner, Wiesbaden 2010, ISBN 978-3-8348-1018-2, S. 157. 

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Einschrittverfahren&oldid=169190888"

Kategorien:

• Numerische Mathematik
• Theorie gewöhnlicher Differentialgleichungen

Versteckte Kategorie:

• Wikipedia:Reviewprozess