Quelltext der Seite Explizites Euler-Verfahren

Das '''eulersche Polygonzugverfahren''' oder '''explizite Euler-Verfahren''' (auch '''Euler-Cauchy-Verfahren''' oder '''Euler-vorwärts-Verfahren''') ist das einfachste Verfahren zur [[Numerische Mathematik|numerischen]] Lösung eines [[Anfangswertproblem]]s.

Es wurde von [[Leonhard Euler]] 1768 in seinem Buch ''Institutiones Calculi Integralis'' vorgestellt. [[Augustin Louis Cauchy|Cauchy]] benutzte es, um einige Eindeutigkeitsresultate für [[gewöhnliche Differentialgleichung]]en zu beweisen.

Das Verfahren wird manchmal in der Physik als '''Methode der kleinen Schritte''' bezeichnet<ref>{{Literatur | Autor = Thomas Wilhelm | Datum = 2018 | Titel  =Zur Geschichte der mathematischen Modellbildung im Physikunterricht | Verlag =Verein zur Förderung des physikalischen und chemischen Unterrichts | Seiten =5 |Online=https://www.pluslucis.org/ZeitschriftenArchiv/2018-4_PL.pdf}}
</ref>.

== Das Verfahren ==
[[Datei:Euler two steps.svg|mini|Zwei Schritte des expliziten Euler-Verfahrens]]
Zur numerischen Lösung des Anfangswertproblems:

:<math> \dot{y}(t)=f(t,y), \quad \quad y(t_0)=y_0 </math>

für eine gewöhnliche Differentialgleichung wähle man eine Diskretisierungs-Schrittweite
<math> h>0 </math>, betrachte die diskreten Zeitpunkte

:<math> t_k=t_0+kh, \quad \quad k=0,1,2,\dots </math>

und berechne die Werte

:<math> y_{k+1}=y_k+hf(t_k,y_k),\quad k=0,1,2,\dots </math>

Die berechneten Werte <math> y_k</math> stellen Approximationen an die tatsächlichen Werte <math> y(t_k)</math> der exakten Lösung des Anfangswertproblems dar. Je kleiner die Schrittweite <math>h</math> gewählt ist, desto mehr Rechenarbeit ist nötig, aber desto genauer werden auch die approximierten Werte.

Eine Modifikation des Verfahrens besteht hier darin, dass man die Schrittweite variabel wählt. Eine sinnvolle Veränderung der Schrittweite setzt einen Algorithmus zur [[Schrittweitensteuerung]] voraus, der den Fehler im aktuellen Schritt abschätzt und dann die Schrittweite für den nächsten Schritt dementsprechend wählt.

Wird ein Verfahren über <math> y_{k+1}=y_k+hf(t_{k+1},y_{k+1})</math> definiert, erhält man das [[Implizites Euler-Verfahren|implizite Euler-Verfahren]].
Dieses ist [[A-Stabilität|A-stabil]] und daher für [[Steifes Anfangswertproblem|steife Anfangswertprobleme]] besser geeignet.

== Herleitung ==
Für die Herleitung von [[Einschrittverfahren]] wird das [[Anfangswertproblem]] meist in die dazu äquivalente [[Integralgleichung]] umgeformt<ref>{{Literatur |Autor=Arnold Reusken |Titel=Numerik für Ingenieure und Naturwissenschaftler |Verlag=Springer |Ort=Berlin |Datum=2006 |ISBN=3-540-25544-3 |Seiten=378}}</ref>
: <math>
\begin{align}
  \dot{y}&=f(t,y) \,, \qquad y(t_0)=y_0 \\
  \Longleftrightarrow \quad y(t) &= y_0 + \int_{t_0}^t f(s,y(s)) \, \mathrm ds \,.
\end{align}
</math>
Nun besteht die Idee, beim ''expliziten Euler-Verfahren'' eine simple [[Numerische Integration|Quadraturformel]] für das Integral zu benutzen: die [[Mittelpunktsregel#Boxregel|linksseitige Boxregel]]. Man wählt in jedem <math> k </math>-ten Schritt den Integranden als konstanten Wert an der linken Intervallgrenze<ref>{{Literatur |Autor=Arnold Reusken |Titel=Numerik für Ingenieure und Naturwissenschaftler |Verlag=Springer |Ort=Berlin |Datum=2006 |ISBN=3-540-25544-3 |Seiten=381}}</ref>
: <math>
y(t_{k+1})
  = y(t_k) + \int_{t_k}^{t_{k+1}} f(s,y(s)) \, \mathrm ds
  \approx y_k + \int_{t_k}^{t_{k+1}} f(t_k,y_k) \, \mathrm ds
  = y_k + h f(t_k,y_k)
  =: y_{k+1} \,.
</math>

== Eigenschaften ==
[[Datei:Stability region for Euler method.svg|mini|Stabilitätsgebiet des expliziten Euler-Verfahrens]]
Das explizite Euler-Verfahren hat [[Konsistenzordnung|Konsistenz-]] und [[Konvergenzordnung]] 1. Die [[Stabilitätsfunktion]] ist <math>R(z)=1+z</math> und sein [[Stabilitätsgebiet]] daher das Innere des Kreises um −1 mit Radius 1 in der [[Komplexe Zahlen|komplexen Zahlenebene]].

== Verbessertes explizites Euler-Verfahren ==
Anstatt die [[Mittelpunktsregel#Boxregel|Boxregel]] für die numerische Integration zu verwenden, kann man auch die [[Mittelpunktsregel]] anwenden.
:<math>
\int_{t_k}^{t_{k+1}} f(s,y(s)) \, \mathrm ds
  \approx h f\left(t_k +\frac{h}{2},y\left(t_k +\frac{h}{2}\right) \right) \,.
</math>
Nun wendet man wieder das explizite Euler-Verfahren zur Approximation von <math>y\left(t_k +\frac{h}{2}\right)</math> an
:<math>
y\left(t_k +\frac{h}{2}\right)
  \approx y_k + \frac{h}{2} f(t_k,y_k)
  =: y_{k+\frac{1}{2}} \,.
</math>
Zusammen führt dies auf das ''verbesserte explizite Euler-Verfahren'' (oder ''Euler-Verfahren mit kleinerer Schrittweite'')<ref>{{Literatur |Autor=Arnold Reusken |Titel=Numerik für Ingenieure und Naturwissenschaftler |Verlag=Springer |Ort=Berlin |Datum=2006 |ISBN=3-540-25544-3 |Seiten=382}}</ref>
:<math>
y_{k+1} = y_k + h f\left(t_k +\frac{h}{2},y_{k+\frac{1}{2}} \right)
  \quad \text{mit} \quad
  y_{k+\frac{1}{2}} = y_k + \frac{h}{2} f(t_k,y_k)
  \,.
</math>

== Verallgemeinerungen ==

Es lässt sich im Wesentlichen durch zwei verschiedene Ideen auf effizientere Verfahren verallgemeinern.

* Die erste Idee ist, bei der Berechnung des nächsten Schrittes mehr als nur einen der zuvor berechneten Werte mit einzubeziehen. Auf diese Weise erhält man Verfahren höherer Ordnung in der Klasse der linearen [[Mehrschrittverfahren]].

* Die zweite Idee ist, bei der Berechnung des nächsten Schrittes die Funktion <math> f(t,y)</math> auf dem Intervall <math> [t_k,t_{k+1}]</math> an mehreren Stellen auszuwerten. Auf diese Weise erhält man die Klasse der [[Runge-Kutta-Verfahren]].

Die Klasse der allgemeinen linearen Verfahren bezieht beide Ideen der
Verallgemeinerung mit ein und enthält die Klasse der linearen Mehrschrittverfahren sowie die Klasse der Runge-Kutta-Verfahren als
Spezialfall.

* Darüber hinaus gibt es auch eine Erweiterung des Euler-Verfahrens für [[stochastische Differentialgleichung]]en: das [[Euler-Maruyama-Verfahren]].

== Anwendungsbeispiel: Erdnaher freier Fall ==
In der Physik wendet man die ''Methode der kleinen Schritte'' beispielsweise bei der Bewegung eines Fallschirmspringers (im Fall) mit Luftwiderstand an.

=== Physikalischer Hintergrund ===
* Beim freien Fall in Erdnähe würde die Geschwindigkeit <math>v</math> eines fallenden Körpers –&nbsp;bei Vernachlässigung des Luftwiderstandes&nbsp;– um 9,81&nbsp;m/s pro Sekunde steigen. Dann wäre der freie Fall eine [[Bewegung (Physik)#Spezielle Formen der Bewegung einzelner Objekte|gleichmäßig beschleunigte Bewegung]]. Ein [[Fallschirmspringer]], der sich aus einem stationären Ballon fallen lässt, wird zunächst immer schneller, seine Geschwindigkeit nimmt stetig zu. Seine [[Beschleunigung]] entspricht dabei der Fallbeschleunigung g=9,81&nbsp;m/s² in der Nähe der Erdoberfläche und ist größer als die eines Autos: Nach einer Sekunde hat er theoretisch eine Geschwindigkeit von ''v'' = 9,81&nbsp;m/s (ca. 35&nbsp;km/h), nach zwei Sekunden 19,62&nbsp;m/s (ca. 71&nbsp;km/h), nach drei Sekunden 29,43&nbsp;m/s (ca. 106&nbsp;km/h). In einem echten ''freien Fall'', d.&nbsp;h. im [[Vakuum]], würde die Geschwindigkeit linear weiter entsprechend ansteigen.
* Tatsächlich wirkt auf den Fallschirmspringer jedoch auch der [[Luftwiderstand]], welcher quadratisch mit der Geschwindigkeit zunimmt. Die resultierende Beschleunigung entspricht daher nur am Anfang der Erdbeschleunigung, danach nimmt sie ab, bis sie nach wenigen Sekunden null wird – der Fallschirmspringer fällt ab diesem Zeitpunkt (je nach Wahl der Anfangsbedingungen) mit seiner Fallgrenzgeschwindigkeit  von z.&nbsp;B. ca. 55&nbsp;m/s (ca. 198&nbsp;km/h).

=== Anwendung einer Tabellenkalkulation ===
Mit Hilfe einer [[Tabellenkalkulation]] kann man derartige Probleme aber in viele einfache und vor allem ''lösbare'' Teilaufgaben zerlegen, deren Ergebnisse man durch das Computerprogramm zur Gesamtlösung zusammensetzen lässt. Die Vorteile liegen auf der Hand:
* Man benötigt keine Kenntnisse in höherer Mathematik
* Die Integration wird durch Summieren ersetzt. Das Ergebnis ist zwar nicht exakt, genügt aber den meisten praktischen Anforderungen.
* Anhand von Zwischenergebnissen erkennt man sofort kleine Irrtümer, die sich korrigieren lassen.
* Die vielen überprüfbaren Zwischenergebnisse steigern das Vertrauen in das Resultat.
* Durch Hinzufügen weiterer relevanter Formeln kann die Lösung schrittweise der Realität angepasst werden.

Die Vorgehensweise ist immer gleich: Mit elementaren Formeln werden relevante Größen wie Kraft, Beschleunigung oder Temperatur für einen gewissen Zeitpunkt berechnet – das sind die Anfangswerte für den nächsten Zeitpunkt. Die Ergebnisse sind nur dann korrekt, wenn sich von einem Zeitpunkt zum nächsten ''nur wenig'' ändert. Wie groß diese Änderungen und vor allem jeder Zeitschritt sein dürfen, kann man den Ergebnissen leicht entnehmen. Komplexe Formeln, wie sie beispielsweise bei der Wettervorhersage vorkommen, lassen sich gar nicht anders auswerten.

=== Einzelformeln des freien Falls mit Luftwiderstand ===
In der folgenden Berechnung wird angenommen, dass ein kugelförmiger Eisen-[[Meteor]] der Masse ''m''&nbsp;=&nbsp;4&nbsp;g und der Querschnittsfläche ''A''&nbsp;=&nbsp;1&nbsp;cm² mit der Geschwindigkeit ''v''&nbsp;=&nbsp;15&nbsp;km/s in die Atmosphäre eindringt und abgebremst wird. Gesucht sind Geschwindigkeit und Bremsverzögerung als Funktion der Höhe. Diese Werte werden in bekannte Formeln eingesetzt und für jeden Zeitschritt neu berechnet. Die Einzelergebnisse werden in der Tabelle zu den gesuchten Größen kombiniert und zum Schluss graphisch ausgegeben. Man startet das Verfahren in ausreichend großer Höhe ''h'', wo der Luftwiderstand noch vernachlässigbar ist.
* Die Gravitationsbeschleunigung der Erde wird mit zunehmendem Abstand ''h'' über der Erdoberfläche kleiner. Dafür gilt

:<math>a_\mathrm{gravi} = 9{,}81\, \frac{\mathrm{m}}{\mathrm{s}^2} \cdot \left( \frac{6370000\,\mathrm{m}}{6370000\,\mathrm{m} +h} \right)^2</math>

* In dieser Höhe ''h'' beträgt die Dichte der Luft nur noch ([[Barometrische Höhenformel]])

:<math> \rho(h) = \rho(\text{Boden}) \cdot e^{-\frac{h}{8400\,\mathrm{m}}}</math>

* Der [[Strömungswiderstand]] in Luft ''F''<sub>Luft</sub> bei der Geschwindigkeit ''v'' hängt auch von dieser Dichte ab

:<math>F_\text{Luft} = 0{,}5 \cdot \rho(h) \cdot C_w \cdot A \cdot v^2</math>

* Bei Flugrichtung zum Erdmittelpunkt ist die effektive Beschleunigung auf den Meteor der Masse ''m'' die Differenz von Gravitationsbeschleunigung und Bremsbeschleunigung

:<math>a_\mathrm{gesamt} = a_\mathrm{gravi} - \frac{F_\mathrm{Luft}}{m}</math>

* Mit diesem Zwischenergebnis lässt sich einen Zeitschritt ''dt'' später die dann gültige Geschwindigkeit errechnen

:<math>v_\mathrm{neu} = v_\mathrm{alt} + a_\mathrm{gesamt} \cdot dt</math>

* und daraus der Ort, an dem sich der Meteor dann befindet. Damit startet ein neuer Zyklus.

:<math>h_\mathrm{neu} = h_\mathrm{alt} - v_\mathrm{neu} \cdot dt</math>

Die Berechnung erfolgt schrittweise mit elementaren Mitteln und entspricht einer einfachen [[Integralrechnung#Numerische Verfahren|Integration]], die bei ausreichend kleinem ''dt'' brauchbare Ergebnisse liefert. Speziell für die letzten beiden Schritte existieren bessere, aber auch aufwendigere Verfahren, die in [[Numerische Integration]] beschrieben sind. Oft ist deren Anwendung übertrieben, wenn nur ein schneller Überblick gewünscht wird oder – wie in diesem Beispiel – die Formel für den Strömungswiderstand für Überschallgeschwindigkeit nicht exakt gilt.

=== Numerische Lösung ===
[[Datei:FreiFall Tabelle.gif|mini|Berechnungstabelle für freien Fall mit Luftwiderstand]]
[[Datei:Abbremsung eines Meteors.png|mini|Abbremsung eines Meteors in der Atmosphäre]]
Zunächst werden die Parameter in den Zellen J1 bis J5 und die Startwerte in A3, B3, C3 festgelegt, diese Werte werden fast überall in der Tabelle benötigt. In anderen Programmiersprachen würde man von „globalen Variablen“ sprechen. Die eben aufgezählten Formeln werden in benachbarten Spalten der Tabellenkalkulation programmiert, die Zwischenergebnisse werden im Regelfall in weiter rechts liegenden Spalten weiterverarbeitet. Die „Weiterschaltung“ in die folgende Zeile erfolgt dadurch, dass das Ergebnis der Zelle G3 verwendet wird, um den Inhalt der Zelle B4 nach dem folgenden Zeitschritt zu berechnen. Zum Schluss kopiert man die Formeln der 3. bzw. 4. Zeile in die nächsten 2000 Zeilen – gleichzeitig wird das Ergebnis berechnet.

Von ausschlaggebender Wichtigkeit für die physikalische Korrektheit der Ergebnisse ist die sinnvolle Wahl des Zeitschrittes ''dt'', der möglichst klein sein soll und in der nebenstehenden Tabelle den – für diese Aufgabenstellung – recht hohen Wert 0,2&nbsp;s hat. Das führt in der Umgebung der Zelle G20 zu gerade noch akzeptierbaren Wertesprüngen von etwa 40 %. Allerdings bewirkt auch eine Vergrößerung auf ''dt''&nbsp;=&nbsp;1&nbsp;s noch keine gravierenden Änderungen, was die Robustheit dieses Lösungsverfahrens demonstriert.

Im nebenstehenden Bild wird neben der Tabelle die Gesamtbeschleunigung in Abhängigkeit von der Höhe dargestellt. Die überraschenden Ergebnisse:
* Die Meteore werden fast unabhängig von ihrer Masse in etwa 40&nbsp;km Höhe am stärksten gebremst und können dabei in Bruchstücke zerlegt werden oder [[verglühen]].
* Die Geschwindigkeiten in den letzten Kilometern über der Erdoberfläche betragen stets etwa 40&nbsp;m/s – wenn die Bruchstücke bis dahin nicht verglüht sind. Der berechnete Geschwindigkeitsverlauf ist im unteren Bild dargestellt.

=== Weiterführende Untersuchungen ===
Das beschriebene Verfahren lädt dazu ein, Parameter wie Größe und Anfangsgeschwindigkeit zu variieren und deren Auswirkungen auf die berechneten Ergebnisse zu untersuchen. Diese Art von „[[Experimentelle Mathematik|experimenteller Mathematik]]“ kann zu größerem Verständnis der enthaltenen Physik führen als die Auswertung der komplexen Formeln im vorhergehenden Absatz.

== Weblinks ==
{{Wikibooks|Informationstechnische Grundlagen (ITG)/ Tabellenkalkulation#Projekt: Bewegung simulieren mit Tabellenkalkulation|Abschnitt zur Methode der kleinen Schritte in „Informationstechnische Grundlagen (ITG)“|suffix=-}}
* [https://www.leifiphysik.de/uebergreifend/allgemeines-und-hilfsmittel/ausblick/methode-der-kleinen-schritte Methode der kleinen Schritte bei konstant beschleunigter Bewegung] ([[LEIFI]])

== Literatur ==
* E. Hairer, S.P. Norsett, G. Wanner: ''Solving Ordinary Differential Equations I'', Springer Verlag
* M. Hermann: ''Numerik gewöhnlicher Differentialgleichungen, Anfangs- und Randwertprobleme'', Oldenbourg Verlag, München und Wien, 2004, ISBN 3-486-27606-9

== Einzelnachweise ==
<references />

[[Kategorie:Theorie gewöhnlicher Differentialgleichungen]]
[[Kategorie:Numerische Mathematik]]
[[Kategorie:Leonhard Euler als Namensgeber]]