Warum sind Runge-Kutta und Eulers Methode so unterschiedlich?

10

Ich löse ein lineares Gleichungssystem, , numerisch. Ich habe dies mit den populären Methoden von Euler und Runge-Kutta (RK) gemacht. Ich habe einen ziemlichen Unterschied zwischen den beiden in der Genauigkeit der analytischen Lösung festgestellt. Was ist der Grund dafür?x˙_=EIN_x_

Peter Mortensen
quelle
5
Im gleichen Zeitschritt weisen die beiden Methoden eine sehr unterschiedliche Genauigkeit und Stabilität auf. Leider ist dies meistens eine mathematische Frage, und es wäre besser, wenn Sie Ihr Verständnis für numerische Methoden erläutern.
Ja72
Mein Niveau mit diesem Thema ist sehr begrenzt. Aber danke, dass du deine Meinung geteilt hast.

Antworten:

18

Als erstes hätten Sie erwähnen können, welche RK-Methode Sie verwendet haben. Hier ist eine kurze Einführung in die RK-Methoden und die Euler-Methode, deren Funktionsweise und Nachteile.

Euler-Methode

Die Euler-Methode ist eine Methode erster Ordnung. Es ist eine einfache Methode, die den nächsten Punkt basierend auf der Änderungsrate am aktuellen Punkt schätzt und einfach zu codieren ist. Es ist eine Einzelschrittmethode. Insbesondere ist die Methode von Forward Euler für ungedämpfte oszillierende Systeme (wie ein Feder-Masse-System oder Wellengleichungen) bei der Raumdeskriptretierung bedingungslos instabil. Bei komplexen Problemen und / oder Randbedingungen kann dies fehlschlagen. Es kann für grundlegende numerische Analysen verwendet werden. Diese Methode wird nicht häufig für die räumliche Diskretisierung verwendet, sondern manchmal für die zeitliche Diskretisierung. Dieses Schema wird für die hyperbolische Differentialgleichung nicht empfohlen, da dies diffusiver ist. Die Reihenfolge der Konvergenz dieses Schemas mit der Netzverfeinerung ist sehr schlecht. Die Erweiterung der Euler-Methode auf eine Methode höherer Ordnung ist einfach und unkompliziert.

RK-Methoden:

Runge-Kutta-Methoden sind eigentlich eine Familie von Schemata, die in einem bestimmten Stil abgeleitet sind. Über diesen Link erhalten Sie eine grundlegende Vorstellung von RK-Methoden: http://web.mit.edu/10.001/Web/Course_Notes/Differential_Equations_Notes/node5.html

Die Vorwärts-Euler-Methode ist eigentlich die einfachste RK-Methode (1 Stufe, erste Ordnung). RK-Verfahren mit höherer Ordnung sind mehrstufig, da sie Steigungsberechnungen in mehreren Schritten bei oder zwischen dem aktuellen und dem nächsten diskreten Zeitwert beinhalten. Der nächste Wert der abhängigen Variablen wird berechnet, indem ein gewichteter Durchschnitt dieser mehreren Stufen basierend auf einer Taylorreihen-Näherung der Lösung genommen wird. Die Gewichte in diesem gewichteten Durchschnitt werden durch Lösen nichtlinearer algebraischer Gleichungen abgeleitet, die durch Aufheben der Fehlerterme in der Taylor-Reihe gebildet werden. Die Entwicklung von RK-Methoden höherer Ordnung ist mühsam und schwierig, ohne symbolische Werkzeuge für die Berechnung zu verwenden.

Die beliebteste RK-Methode ist RK4, da sie ein gutes Gleichgewicht zwischen der Reihenfolge der Genauigkeit und den Berechnungskosten bietet. RK4 ist die explizite Runge-Kutta-Methode höchster Ordnung, die die gleiche Anzahl von Schritten wie die Reihenfolge der Genauigkeit erfordert (dh RK1 = 1 Stufe, RK2 = 2 Stufen, RK3 = 3 Stufen, RK4 = 4 Stufen, RK5 = 6 Stufen ,. ..). Ab der vierten Ordnung werden die RK-Methoden relativ teurer in der Berechnung.

Antworten

  • Normalerweise ist der Fehler bei der Euler-Methode höher als bei der RK-Methode höherer Ordnung (RK2, RK3 usw.), da der Kürzungsfehler bei Methoden höherer Ordnung im Vergleich zur Euler-Methode geringer ist.

  • In einigen Literaturstellen für Anfänger in numerischen Methoden wird lose erwähnt, dass Methoden höherer Ordnung (z. B. RK4) weniger Fehler ergeben als Methoden niedrigerer Ordnung (z. B. Euler-Methode). Meistens ist dies wahr, aber nicht immer. Diese Eigenschaft hängt von der Netz- und Anfangsbedingung sowie den von Ihnen berücksichtigten Differentialgleichungen ab.

  • nn

  • Der anfängliche "absolute maximale Differenzfehler" bei der RK4-Methode ist gleich (oder) höher als bei der Euler-Methode für das Grobgitter und verringert sich mit dem Verfeinerungsgitter bei Problemen mit kürzeren Wellen im Verhältnis zum Gitter . Weil die Konvergenzrate der RK4-Methode höher ist als die von Euler. Bitte beachten Sie, dass die Grobheit oder Feinheit des Gitters vollständig auf der Differentialgleichung, dem Anfangszustand und dem numerischen Schema basiert. Weitere Informationen finden Sie unter folgendem Link . Obwohl dies auf Differenzierung basiert, können wir einen relativen Vergleich zwischen zeitlicher numerischer Integration und Differenzierung durchführen, solange die "numerische Integration" stabil ist.

Log(errÖr)Log(Grichd sichze)

AGN
quelle
6
Es ist großartig, andere Leute zu sehen, die erkennen, dass höhere Ordnung nicht immer einen geringeren Fehler bedeutet, sondern nur eine schnellere Konvergenz. Das ist so ein wichtiger Punkt, aber so viele scheinen ihn zu vermissen!
tpg2114
Ja, Sir, ich habe dies aus einer Vorlesung meiner Professoren erfahren und dies in einer meiner Aufgaben überprüft. Ich denke, es fehlt, weil wir die meiste Zeit in feinmaschigen und relativ nicht steifen Differentialgleichungen arbeiten.
AGN
Insgesamt sehr schöne Antwort. Ich habe einige Punkte korrigiert und einige Details hinzugefügt. Hoffentlich macht es dir nichts aus.
Doug Lipinski
1
@ Doug, Danke, dass du deine wertvolle Zeit damit verbracht hast. Mein Punkt ist einfach: Methoden niedrigerer Ordnung sind im Kursraster genau und Methoden höherer Ordnung sind im feinen Raster genau. Warum ich in meiner Antwort erwähnt habe (Bitte beachten Sie, dass die Grobheit oder Feinheit des Gitters vollständig auf der Differentialgleichung, der Anfangsbedingung und dem numerischen Schema basiert), hängt von der Gittergröße und der Größe der Reihenfolge der Ableitung der Funktion ab, die wir abgeschnitten haben ( Indirekt kann dies mit der Steifheit der ODE zusammenhängen.
AGN
Entschuldigung, ich habe Ihren Kommentar bis jetzt nicht gesehen. Personen erhalten nur dann Benachrichtigungen, wenn Sie @ auf ihren vollständigen Benutzernamen antworten (oder wenn sie der Postbesitzer sind). Beginnen Sie mit der Eingabe @Dou...und es sollte angeboten werden, die automatische Vervollständigung für Sie durchzuführen. Ich habe eine Antwort auf Ihre andere Frage gepostet .
Doug Lipinski
8

Bei der Euler-Methode wird die Krümmung der Lösung nicht berücksichtigt, sodass je nach Schrittgröße unterschiedliche Ergebnisse erzielt werden. RK berücksichtigt je nach Reihenfolge die Krümmung. Und das macht den geschätzten "nächsten Schritt" genauer. Wenn Sie so tun, als wäre eine gerade Linie eine gute Annäherung an eine Kurve (Euler), werden Sie Ihre Lösung grundsätzlich immer überschreiten. Wenn Sie jedoch die Krümmung (RK) berücksichtigen, können Sie der Kurve folgen.

Vergleichen Sie mit dem berühmten Hockey-Zitat (Gretzky): Euler läuft dorthin, wo der Puck ist; Runge-Kutta läuft dorthin, wo der Puck sein wird.

Ich empfehle Ihnen, über diese Algorithmen zu lesen. Sie können hier und hier mit Wikipedia-Artikeln beginnen .

Floris
quelle
5

Verzeihen Sie mir, dass ich eine Ich-zu-Antwort hinzugefügt habe, aber ich konnte einfach nicht widerstehen, diese Seite von Press ua aufzunehmen: "Numerische Rezepte in C":

Geben Sie hier die Bildbeschreibung ein

Mike Dunlavey
quelle
1
Sehr schön ergänzt die andere Antwort. Dieses Buch ist ein Klassiker. Obwohl es seine FORTRAN-Wurzeln zeigt, indem es manchmal Arrays mit einem Index von 1 startet.
Floris
2
@Floris: Ich habe einmal mit einem Mann aus Norditalien gearbeitet, der eine große Hakennase, schütteres blondes Haar und alles, namens Giuseppe. Ich habe darüber nachgedacht, warum Menschen nicht zu einer modernen Sprache wie C konvertiert sind :) Er rollt mit dieser tiefen, gebieterischen Stimme zu mir: "MIke, Fortran ist wie Rock and Roll. Es wird niemals sterben."
Mike Dunlavey
1
Ich passe ungefähr die Hälfte Ihrer Beschreibung von Giuseppe ... :-)
Floris
4

Grundsätzlich liegt der Grund für die unterschiedliche Genauigkeit in der Art und Weise, wie sie abgeleitet werden. Die (ich gehe davon aus, vorwärts) Euler-Methode ist erster Ordnung und kann auf verschiedene Arten abgeleitet werden. Am einfachsten aus Taylors Theroem. Bei diesem Verfahren wird nur der Term zweiter Ordnung beibehalten, wodurch der Fehler erster Ordnung wird.

Runge-Kutta-Methoden hingegen sind inszeniert und haben sehr spezifisch ausgewählte Koeffizienten, um mehrere Ordnungen von Fehlerausdrücken "aufzuheben". Rk4 ist vierte Ordnung, da sich die Fehlerterme nullter, erster, zweiter und dritter Ordnung durch die Wahl der Stufenkoeffizienten aufheben. Die Ableitung dieser Koeffizienten ist nicht sehr schwierig und kann wahrscheinlich auf Wikipedia gefunden werden, wenn Sie daran interessiert sind, sie zu sehen.

Alex
quelle