Einige ältere Bücher, die ich gesehen habe, sagen, dass die Mindestanzahl von Stufen einer expliziten Runge-Kutta-Methode einer bestimmten Reihenfolge für Bestellungen unbekannt ist . Ist das noch wahr?$\geq 9$

Welche Bibliotheken gibt es, um automatisch mit Runge-Kutta-Methoden hoher Ordnung zu arbeiten?

Grenzen

Das ist immer noch wahr. In Butchers Buch , Seite 196, heißt es: In einem Artikel von 1985 hat Butcher gezeigt, dass Sie 11 Stufen benötigen, um Ordnung 8 zu erhalten , und das ist scharf. Für Ordnung 10 hat Hairer eine Familie von 17-stufigen Methoden abgeleitet , aber es ist nicht bekannt, ob man es besser machen kann. Die gleichen Informationen finden sich in Abschnitt II.5 von Hairer, Norsett & Wanner vol. Ich . Die letztere Referenz geht auch einige der Techniken zum Entwickeln von Paaren höherer Ordnung (bis zur Ordnung 8) durch.

Es gibt eine Obergrenze für die Mindestanzahl von Stufen, die für eine Bestellung erforderlich sind, da Sie diese durch Extrapolation erstellen können. Dies ist seit sehr langer Zeit bekannt; Eine Erklärung finden Sie in meinem jüngsten Artikel . Diese Grenze ist jedoch in der Reihenfolge quadratisch und sicherlich ziemlich pessimistisch. Die unten diskutierte Nodepy-Software kann genaue Koeffizienten für diese Methoden und auch für verzögerte Korrekturmethoden (die Runge-Kutta-Methoden sind) beliebiger Ordnung erzeugen.

Ich glaube, @Etienne hat Recht, wenn er sagt, dass die von Hand konstruierten Methoden höchster Ordnung Terry Feagin zu verdanken sind. In Bezug auf seinen anderen Kommentar enthält dieses Papier etwa 9 (8) Paare:

JH Verner, Explizite Runge-Kutta-Paare hoher Ordnung mit niedriger Stufenordnung, Angewandte Numerische Mathematik, Band 22, Ausgaben 1–3, November 1996, Seiten 345–357

$N$$p$

p | N
-----
1 | 1
2 | 2
3 | 4
4 | 8
5 | 17
6 | 37
7 | 85
8 | 200
9 | 486
10| 1205
11| 3047
12| 7813
13| 20300
14| 53264

Software

Bei Methoden sehr hoher Ordnung ist es unmöglich, die Anzahl und Komplexität der Bestellbedingungen von Hand zu behandeln. Einige symbolische Pakete (zumindest Mathematica) können Runge-Kutta-Bestellbedingungen generieren. Es gibt wahrscheinlich einige andere Pakete da draußen, aber mir ist Folgendes bekannt (beide habe ich geschrieben):

• nodepy : Ein Python-Paket, das symbolische Ausdrücke und Code für die Bestellbedingungen in beliebiger Reihenfolge generieren kann. Es enthält auch Python-Code zum Überprüfen dieser Bedingungen, Berechnen von Fehlerkoeffizienten usw.
• RK-Opt : Ein MATLAB-Paket, das unter anderem Runge-Kutta-Methoden hoher Ordnung mit für einige verschiedene Zwecke optimierten Koeffizienten finden kann. Es konnte derzeit keine explizite RK 9. Ordnung verarbeiten (es geht bis zur 8. Ordnung für Methoden der ersten Stufe, zehnte Ordnung für Methoden mit höherer Stufenordnung). Wenn Sie daran interessiert sind, könnte ich die Bedingungen 9. Ordnung (und höher) ziemlich einfach hinzufügen.

Ein weiterer interessanter Hinweis zu den Bestellbedingungen, der bei so hohen Aufträgen von Bedeutung ist, besteht darin, dass es zwei Möglichkeiten gibt, sie abzuleiten, und dass Sie unterschiedliche (aber kollektiv gleichwertige) Bedingungen erhalten: eine stammt von Butcher, die andere von Albrecht .

@ DavidKetchesons Antwort trifft die großen Punkte: Sie können immer Methoden mit ausreichend hoher Ordnung durch Extrapolation konstruieren, das ist eine sehr pessimistische Grenze und Sie können immer viel besser machen, alle guten werden von Hand abgeleitet (mit Hilfe eines Computers) Algebra-Werkzeuge) ist keine Untergrenze bekannt, und die Methoden höchster Ordnung sind auf Feagin zurückzuführen. Angesichts einiger Kommentare wollte ich die Antwort mit einer Diskussion über die aktuellen Tableaus auf dem Gebiet abrunden.

Wenn Sie ein Kompendium von RK-Tableaus wünschen, finden Sie eines in diesem Julia-Code . Zitate für das Papier, aus dem sie stammen, befinden sich in den Dokumenten für die Tableau-Konstrukteure. In der Entwicklerdokumentation für DifferentialEquations.jl sind alle diese Tableaus als zur Verwendung verfügbar aufgeführt. Hier können Sie sehen, dass alle Tablets mit Travis und AppVeyor Continuous Integration Suites getestet wurden, um sicherzustellen, dass nicht nur die Bestellbedingungen erfüllt sind, sondern auch die tatsächlichen die gewünschte Konvergenz erreichen (Verifikationstest). An diesen können Sie sehen, dass es gibt:

• 5 bestellen 9 Methoden
• 6 10 Methoden bestellen
• 2 12 Methoden bestellen
• 1 Ordnung 14 Methode

(dass ich finden konnte, dass veröffentlicht wurden). Wieder alles von Hand abgeleitet.

Die Konvergenztests zeigen , dass einige der Ableitungen wurden nicht für mehr als 64-Bit - Zahlen zu hoch genug Präzision durchgeführten Arbeiten (sie werden kommentiert wie folgt ). Das ist also eine interessante Besonderheit: Bei diesen hohen Ordnungen erhalten Sie normalerweise nur Koeffizienten, die "zu einem Fehler x" die Ordnungsbedingungen erfüllen, aber wenn Sie Arithmetik mit beliebiger Genauigkeit verwenden, können Sie diese Grenzen tatsächlich erkennen. Die Genauigkeit, mit der Sie die Koeffizienten ausführen, spielt also eine Rolle, und Sie sollten sie auswählen, um die Genauigkeit abzudecken, die Sie testen möchten (/ natürlich verwenden).

Wenn Sie eine Reihe von Stabilitätsdiagrammen wünschen, können Sie einfach plot(tableau)das Rezept Plots.jl verwenden. Eine gute Reihe von Notizen, in denen viel davon aufgeschrieben ist, finden Sie auf der Website von Peter Stone (klicken Sie unten auf "Bestellen Sie 10 Schemata" und Sie erhalten eine Reihe von PDFs). Bei der Entwicklung von DifferentialEquations.jl habe ich diese Tableaus erstellt, um sie systematisch bei Testproblemen durchzugehen / anhand der Analyseindikatoren festzustellen, welche in die Hauptbibliothek aufgenommen werden sollten. Ich habe hier ein paar kurze Notizen gemacht . Wie Sie den in der Hauptbibliothek enthaltenen Algorithmen entnehmen könnenIch fand die Methoden Verner und Feagin lohnenswert. Die Verner-Methode 9. Ordnung ist die Methode höchster Ordnung mit einem Interpolanten, der ebenfalls der Ordnung entspricht. Das ist etwas zu erkennen: Die Feagin-Methoden haben keine passende Interpolation (obwohl Sie Hermite booten können, aber das ist wirklich ineffizient).

Da sie alle mit sehr effizienten Implementierungen implementiert sind, können Sie selbst damit herumspielen und sehen, wie wichtig die verschiedenen Funktionen tatsächlich sind. Hier ist ein Jupyter-Notizbuch, das die verwendeten Feagin-Methoden zeigt . Beachten Sie, dass das Konvergenzdiagramm tatsächlich 1e-48fehlerhaft sein wird. Methoden höherer Ordnung sind nur dann effizienter als Methoden niedrigerer Ordnung, wenn Sie wirklich eine sehr sehr geringe Toleranz benötigen. Einige Benchmarks, die einige davon verwenden , finden Sie unter DiffEqBenchmarks.jl . Wenn sie jedoch verwendet werden, handelt es sich normalerweise um die Verner-Methode 9. Ordnung, die normalerweise zeigt, dass sich der Benchmark nicht in dem Bereich befindet, in dem diese hohe Ordnung effizient ist.

Wenn Sie also herumspielen und mit Methoden höherer Ordnung arbeiten möchten, ist RK-Opt ein gutes Werkzeug, um einige abzuleiten (wie @DavidKetcheson erwähnt), und DifferentialEquations.jl verfügt über alle veröffentlichten Methoden (glaube ich? ) implementiert, damit Sie sie leicht testen / vergleichen können. Wenn Sie jedoch keine Annahme finden, die fallengelassen werden kann, konnte ich aus meinen Tests nichts finden, das die Methoden Verner (Befehle 6-9) und Feagin (Befehle 10+) übertrifft. YMMV, und ich würde gerne mehr Forschung in diesem Bereich sehen.