Optimale ODE-Methode für eine feste Anzahl von RHS-Bewertungen

In der Praxis ist die Laufzeit der numerischen Lösung eines IVP x ( t 0 ) = x 0 wird oft von der Auswertungsdauer der rechten Seite (RHS)dominiert. Nehmen wir daher an, dass alle anderen Operationen sofort ausgeführt werden (dh ohne Rechenaufwand). Wenn die Gesamtlaufzeit zum Lösen des IVP begrenzt ist, ist dies gleichbedeutend mit der Begrenzung der Anzahl der Auswertungen vonauf einige.

Uns interessiert nur der Endwert .$x(t_1)$

Ich suche nach theoretischen und praktischen Ergebnissen, die mir bei der Auswahl der besten ODE-Methode in einem solchen Umfeld helfen.

Wenn zum Beispiel ist, können wir den IVP mit zwei expliziten Euler-Schritten der Breite ( t 1 - t 0 ) / 2 oder einem Schritt der Breite t 1 - t 0 mit der Mittelpunktmethode lösen . Mir ist nicht sofort klar, welches man bevorzugt. Für größere N kann man natürlich auch über Mehrschrittmethoden, iterierte Runge-Kutta-Schemata usw. nachdenken.$N = 2$$(t_1 - t_0)/2$$t_1 - t_0$$N$

Was ich suche, sind Ergebnisse ähnlich denen, die zum Beispiel für Quadraturregeln existieren: Wir können Gewichte { w i } und zugehörige Punkte { x i } so auswählen, dass die Quadraturregel ∑ n i = 1 w i ist g ( x i ) ist für alle Polynome g genau, so dass d e g ( g ) ≤ 2 n - 1 ist .$n$$\{w_i\}$$\{x_i\}$$\sum_{i = 1}^n w_i g(x_i)$$g$$deg(g) \le 2n - 1$

Aus diesem Grund suche ich nach einer Ober- oder Untergrenze für die globale Genauigkeit von ODE-Methoden bei einer begrenzten Anzahl zulässiger Bewertungen der RHS . Es ist in Ordnung, wenn die Grenzen nur für einige RHS-Klassen gelten oder zusätzliche Einschränkungen für die Lösung x darstellen (genau wie das Ergebnis für die Quadraturregel, die nur für Polynome bis zu einem bestimmten Grad gilt).$f$$x$

EDIT: Einige Hintergrundinformationen: Dies ist für harte Echtzeitanwendungen, dh das Ergebnis muss vor einem bekannten Termin verfügbar sein. Daher die Begrenzung der Anzahl der RHS-Bewertungen N als dominierender Kostenfaktor. Typischerweise sind unsere Probleme steif und vergleichsweise klein.$x(t_1)$$N$

EDIT2: Leider habe ich nicht die genauen Timing-Anforderungen, aber es ist sicher anzunehmen, dass eher klein sein wird (definitiv <100, wahrscheinlich näher an 10). In Anbetracht der Echtzeitanforderungen müssen wir einen Kompromiss zwischen der Genauigkeit der Modelle (wobei bessere Modelle zu längeren Ausführungszeiten der RHS und damit zu einem niedrigeren N führen ) und der Genauigkeit der ODE-Methode (wobei bessere Methoden höhere Werte erfordern) finden Werte von N ).$N$$N$$N$

Ich denke, ein wichtiger Hinweis zur Beantwortung Ihrer Frage ist dieses Papier von Hosea und Shampine . Jetzt werde ich einige Hintergrundinformationen geben.

Im Allgemeinen kann die Schrittgröße, die Sie bei der numerischen Integration eines IVP verwenden können, durch Stabilität oder Genauigkeit eingeschränkt sein. Wenn Sie den hinsichtlich der Stabilität besten Löser auswählen möchten, müssen Sie den Bereich der absoluten Stabilität berücksichtigen . Bei einer einstufigen Methode ist dies

Hier ist die Stabilitätsfunktion des Verfahrens; siehe zB den Text von Hairer et. al. Eine notwendige Bedingung für die Stabilität ist, dass λ h ∈ S ist, wobei λ über den Eigenwerten des Jacobians von f liegt und h die Schrittgröße ist. Dies ist nicht immer eine ausreichende Bedingung für nichtlineare Probleme, ist jedoch normalerweise eine gute Faustregel und wird in der Praxis angewendet.$P(z)$$\lambda h \in S$$\lambda$$f$$h$

Eine ausführliche Beschreibung des Problems, (explizite) Methoden zu finden, die große stabile Schrittgrößen ermöglichen, finden Sie in meinem Artikel über Stabilitätspolynome und in diesem Artikel über die Optimierung von Runge-Kutta-Methoden für Simulationen komprimierbarer Flüssigkeiten .

Stabilität ist das relevante Problem, wenn Sie feststellen, dass die größte stabile Schrittgröße bereits eine ausreichende Genauigkeit bietet. Andererseits kann die Schrittweite durch Ihre Genauigkeitsanforderungen eingeschränkt sein. In der Regel wird eine lokale Fehlerkontrolle durchgeführt. Die Lösung wird mit zwei Methoden berechnet, und ihre Differenz wird als Schätzung des Fehlers in der weniger genauen verwendet. Die Schrittweite wird adaptiv gewählt, um die vorgeschriebene Toleranz möglichst genau zu erreichen.

Zwei theoretische Maßnahmen sind der Schlüssel zur Vorhersage der Genauigkeitseffizienz. Die erste ist die Genauigkeitsreihenfolge des Verfahrens, die die Rate beschreibt, mit der sich der Fehler Null nähert, wenn die Schrittgröße verringert wird. Der zweite ist der Genauigkeits-Effizienz-Index (siehe das oben im ersten Satz aufgeführte Paper von Hosea und Shampine), der die in den Fehlerbegriffen auftretenden Konstanten berücksichtigt und Vergleiche zwischen Methoden derselben Reihenfolge ermöglicht.

Genauigkeit und Stabilitätseffizienz einer Vielzahl von Methoden können mit NodePy auf einfache und automatisierte Weise berechnet werden (Haftungsausschluss: NodePy wurde von mir entwickelt).

In dieser Richtung gibt es nicht viele Ergebnisse, da es schwieriger ist, als nur die Genauigkeit zu korrigieren, da Sie aus Stabilitätsgründen häufig Zeitschritte auswählen müssen, die kleiner sind, als Sie für die gewünschte Genauigkeit benötigen würden. Die Ergebnisse werden also zwischen steifen und nicht steifen Fällen aufgeteilt. Im ersteren Fall werden die Anforderungen an Zeitschritte und RHS-Bewertungen im Allgemeinen nicht von der Genauigkeit bestimmt, und im letzteren Fall sind sie es.

Ich werde mich auf explizite Methoden konzentrieren, da der implizite Fall weitaus weniger offensichtlich ist, wie viele RHS-Bewertungen Sie verwenden müssen. Dies hängt ganz davon ab, wie Sie sich für die Lösung des resultierenden Systems entscheiden.

Für nicht steife Systeme:

Es gibt Stufenbeschränkungen für explizite Runge-Kutta-Methoden, für die angegeben ist, wie viele Stufen (RHS-Bewertungen) erforderlich sind, um eine bestimmte Genauigkeitsreihenfolge zu erreichen. Nach der vierten Ordnung übersteigt die Anzahl der Stufen die Genauigkeitsordnung und die Ungleichheit wächst weiter. Das große ODE-Buch von Butcher: http://books.google.com/books/about/Numerical_Methods_for_Ordinary_Different.html?id=opd2NkBmMxsC

leistet gute Arbeit bei der Erklärung einiger dieser 'Nichtexistenz'-Beweise.

Ihr Beispiel für eine Quadraturregel führt entweder zu einer mehrstufigen Methode wie Adams-bashforth oder zu sogenannten spektralverzögerten Korrekturmethoden. Für adams-bashforth benötigen Sie nur eine RHS-Bewertung pro Schritt, aber da die Stabilitätsbereiche für diese Methoden im Allgemeinen so klein sind, erledigen Sie im Allgemeinen den gleichen Arbeitsaufwand hinsichtlich der RHS-Bewertungen wie für eine Runge-Kutta-Methode mit denselben bestellen.

Hier ist ein Artikel zur spektralen verzögerten Korrektur:

https://www.google.com/search?q=spectral+deferred+correction&aq=f&oq=spectral+deferred+correction&aqs=chrome.0.57j0l2j62.3336j0&sourceid=chrome&ie=UTF-8

Ich bin mir nicht sicher, wie sich diese Integrationsmethoden gegenüber expliziten Standardmethoden verhalten. Sie erfordern häufig viel mehr Speicher, um Lösungszustände an Quadraturknoten zu speichern, und deshalb habe ich sie selbst nie verwendet.

Für steife Systeme:

$S$$2S^2$$S-1$$S$

$10^{-14}$$f(x)$

Es gibt natürlich Ausnahmen (sehr große Systeme, sehr steife Systeme), aber ein allgemeines Gefühl in der Community ist, dass die Frage des Entwurfs von ODE-Solvern für "Standard" -Systeme gelöst ist. Aus diesem Grund denke ich, dass die von Ihnen gestellte Frage nicht sehr interessant ist - sie befasst sich mit einer Komponente des ODE-Solver-Designs, die nicht mehr von Bedeutung ist. Dies kann auch den Mangel an Literatur zu diesem Thema erklären.

$O(\mathit{dim}^3)$$O(\mathit{dim}^2)$

Der erste Punkt ist also, sicherzustellen, dass Ihre RHS wirklich teurer ist als die zugrunde liegende lineare Algebra.

Der zweite Punkt: Aus der Literatur ist bekannt, dass Löser, die auf "teuren" Methoden (dh expliziten RK-Methoden) basieren, manchmal schneller sind als "billigere" Methoden (explizite Mehrschrittmethoden).

Zusammenfassend denke ich, dass Sie nicht nur die RHS-Bewertungen berücksichtigen sollten.