Wissenschaftliche Standards für numerische Fehler

40

In meinem Forschungsgebiet wird die Spezifizierung von experimentellen Fehlern allgemein akzeptiert, und Veröffentlichungen, die diese nicht liefern, werden stark kritisiert. Gleichzeitig stelle ich häufig fest, dass Ergebnisse numerischer Berechnungen ohne Berücksichtigung numerischer Fehler bereitgestellt werden, obwohl (oder vielleicht weil) häufig fragwürdige numerische Methoden am Werk sind. Ich spreche von Fehlern, die aus der Diskretisierung und endlichen Genauigkeit numerischer Berechnungen usw. resultieren. Sicher, diese Fehlerschätzungen sind nicht immer leicht zu erhalten, wie im Fall hydrodynamischer Gleichungen, aber sie scheinen oft aus Faulheit zu resultieren, obwohl ich glaube dass die Spezifikation von numerischen Fehlerschätzungen ebenso Standard sein sollte wie für experimentelle Ergebnisse. Daher meine Frage:

highsciguy
quelle

Antworten:

26

Ihre Frage bezieht sich auf die Modellüberprüfung. Sie finden zahlreiche Ressourcen zu Methoden und Standards bei der Suche nach Verification and Validation ( Roache 1997 , 2002 , 2004 , Oberkampf & Trucano 2002 , Salari & Knupp 2000 , Babuska & Oden 2004 ) sowie zum umfassenderen Thema Uncertainty Quantification . Anstatt auf Methoden einzugehen, möchte ich eine Community hervorheben, die sich zu diesem Thema entschieden hat.

Im Jahr 1986 gegründet Roache, Ghia und Weiß das Journal of Fluidtechnik Editorial Policy Statement über die Kontrolle der numerischen Genauigkeit , die mit eröffnet

Ein professionelles Problem besteht sowohl in der Computer-Fluid-Dynamics-Community als auch im weiteren Bereich der Computerphysik. Es besteht nämlich ein Bedarf an höheren Standards für die Steuerung der numerischen Genauigkeit.

[...] Das Problem ist sicherlich nicht auf die JFE beschränkt und wurde auf der AFOSRHTM-Stanford-Konferenz über komplexe turbulente Strömungen 1980-81 noch schärfer thematisiert. Das Bewertungskomitee dieser Konferenz gelangte zu dem Schluss, dass es in den meisten Beiträgen zu dieser Konferenz unmöglich war, die Genauigkeit verschiedener Turbulenzmodelle zu bewerten und zu vergleichen, da man physikalische Modellierungsfehler nicht von numerischen Fehlern im Zusammenhang mit dem Algorithmus und unterscheiden konnte Gitter. Dies gilt insbesondere für genaue Methoden erster Ordnung und für Hybridmethoden.

Sie schließen mit sehr direkten Richtlinien:

Das Journal of Fluids Engineering akzeptiert keine Artikel zur Veröffentlichung, in denen die numerische Lösung eines Problems im Bereich der Fluidtechnik gemeldet wird, das die Aufgabe der systematischen Prüfung von Kürzungsfehlern und der Genauigkeitsschätzung nicht erfüllt.

[...] müssen wir klarstellen, dass eine einzelne Berechnung in einem festen Raster nicht akzeptabel ist , da es unmöglich ist, aus einer solchen Berechnung eine Genauigkeitsschätzung abzuleiten. Die Redakteure betrachten eine angemessene Übereinstimmung mit experimentellen Daten auch nicht als ausreichenden Beweis für die Genauigkeit, insbesondere wenn einstellbare Parameter wie bei der Turbulenzmodellierung beteiligt sind.

Die aktuelle Version enthält eine umfassende Reihe von Kriterien und stellt einen Standard dar, den meines Erachtens andere Bereiche erfüllen sollten. Es ist beschämend, dass bis heute in so vielen Bereichen kein Bewusstsein für die Bedeutung der Modellverifikation vorhanden ist.

Jed Brown
quelle
1
Der letzte Punkt über einstellbare Parameter erinnert mich an ein Zitat von John von Neumann: "Mit vier Parametern kann ich einen Elefanten passen und mit fünf kann ich ihn dazu bringen, seinen Rüssel zu wackeln."
Jed Brown
Hiermit wird nur die Auswirkung von Diskretisierungsfehlern und nicht die Auswirkung von Rundungsfehlern angesprochen, die in Fluidsimulationen fast überall ignoriert werden, da sie in der Regel weniger zum Gesamtfehler beitragen. Bei Anwendungen ohne Differentialgleichungen oder Integrale tritt jedoch kein Diskretisierungsfehler auf. Bei diesen Problemen sind Rundungsfehler und Iterations-Kürzungsfehler die dominierende Fehlerquelle.
Arnold Neumaier
Glauben Sie, dass eine rigorose Schätzung nachträglich die Anforderung der Netzunabhängigkeit ersetzen könnte? Wie sehr verfeinern Sie das Raster, um die Unabhängigkeit zu gewährleisten? Ein guter A-posteriori-Schätzer sollte dagegen keinen Raum für Mehrdeutigkeiten lassen.
Reid.Atcheson
2
@ Reid.Atcheson "Yo dawg, ich habe gehört, Sie mögen Fehlerschätzungen, also habe ich Ihnen eine Fehlerschätzung für Ihre Fehlerschätzung, damit Sie den Fehler in Ihrem ... schätzen können." Worst-Case-Grenzen. Die verfügbaren Grenzen sind häufig pessimistisch und beruhen auf Annahmen, die für die meisten technischen Probleme nicht zutreffen. Auch mit dem höchsten Fehlerschätzer müssen Sie überprüfen, ob er korrekt implementiert wurde. Verwenden Sie auf jeden Fall einen Fehlerschätzer, wenn Sie einen haben, aber der Fehlerschätzer ist keine eigenständige Überprüfung.
Jed Brown
19

Es gibt keine solchen Standards, da zuverlässige Fehlerschätzungen oft viel mehr kosten als die ungefähren Berechnungen.

Grundsätzlich gibt es vier Arten von Fehlerschätzungen:

(i) Theoretische Analysen, die belegen, dass eine numerische Methode numerisch stabil ist. Dies ergibt keinen Fehlerbalken, da die Analyse nur garantiert, dass der gemachte Fehler nicht schlechter ist als ein quantifizierter Fehler in den Eingabeargumenten. Für die meisten wissenschaftlichen Berechnungen ist dies ausreichend, da die Eingaben ebenfalls nur ungefähre Werte sind, sodass der mit einer numerisch stabilen Methode gemachte Fehler nicht schlechter ist als die Verwendung einer geringfügig anderen (aber unbekannten) Eingabe. Die meisten hoch angesehenen numerischen Methoden werden von einer numerischen Stichprobenanalyse begleitet, obwohl man kaum eine Implementierung findet, die auf Anfrage den resultierenden sogenannten Rückwärtsfehler meldet.

(ii) Asymptotische Fehlerschätzungen. Diese setzen voraus, dass Produkte aller Fehler (Eingabefehler, Rundungsfehler oder Diskretisierungsfehler als häufigste Ursachen) vernachlässigt werden können (fraglich, wenn Funktionen sehr nichtlinear sind) und verwenden die Sensitivitätsanalyse, um Eingabefehler zu verbreiten. Zusammen mit einer numerischen Stabilitätsanalyse kann dies auch den Effekt von Rundungsfehlern oder Diskretisierungsfehlern erfassen. Die resultierenden Fehlerbalken sind ebenso realisierbar wie die Gültigkeit der zugrunde liegenden Annahmen. Bei Verwendung automatischer Differenzierungswerkzeuge sind die Kosten der Fehlerschätzung zusätzlich zu den Kosten für die Approximation in der Regel ein Faktor von 1 oder 2. Daher ist diese Art der Fehlerschätzung in der Praxis ziemlich häufig.

[Bearbeiten] Zum Beispiel liefert der Oettli-Prager-Satz leicht berechenbare Rückwärtsfehlerschätzungen für die Lösung linearer Systeme. Die Sensitivitätsanalyse zeigt, dass diese Fehler mit der Norm der inversen Matrix multipliziert werden müssen, die mit dem Hager-Schätzer (eingebaut in moderne Zustandszahlenschätzer) geschätzt werden kann.

(iii) Stochastische Fehleranalyse: (CESTAC, http://www.sciencedirect.com/science/article/pii/0378475488900705) Dies geschieht durch Überladen aller Operationen mit einer entsprechenden stochastischen Variante, die drei Sätze von Argumenten auswertet und anschließend einen künstlichen zufälligen Rundungsfehler hinzufügt. Die letzten drei Ergebnisse werden verwendet, um einen Mittelwert und eine Standardabweichung der Quadratwurzel von (Summe der Quadrate der Abweichungen vom Mittelwert geteilt durch 2 = 3-1) zu berechnen. Dies ergibt eine ziemlich nützliche Genauigkeitsschätzung des Rundungsfehlerteils. Dies berücksichtigt jedoch nicht den Diskretisierungsfehler, der typischerweise der dominierende Fehler bei ODE- und PDE-Berechnungen ist. Die Kosten hängen von der Programmiersprache ab, da bei der Ausführung überlasteter Vorgänge ein Mehraufwand entsteht. Vorausgesetzt (was so gut wie nie der Fall ist), dass die Überladung keine Zeitstrafe verursacht, sind die Kosten für Ergebnis plus Fehlerschätzung ein Faktor von 3 im Vergleich zur reinen Näherungsberechnung.

(iv) Intervallanalyse: Dies gibt strenge Grenzen für alle Fehlerquellen, wenn dies ordnungsgemäß durchgeführt wird. Mit Ausnahme einfacher Fälle erfordert dies jedoch viel Erfahrung (oder Software, die sie verkörpert), damit die Grenzen die wahren Fehler nicht ernsthaft überschätzen . Gute Intervall-Software gibt es unter anderem für die lineare Algebra (z. B. IntLab http://www.ti3.tu-harburg.de/rump/intlab/ ; Kosten Sie einen Faktor von etwa 6, wenn die Dimension groß ist) und für die globale Optimierung (z. B. , COCONUT http://www.mat.univie.ac.at/~coconut/coconut-environment/; kann weitaus teurer oder sogar billiger sein als die ungefähre globale Optimierung, abhängig von den Problemmerkmalen). Viele andere Problemklassen, die sich nur annähernd genau behandeln lassen (z. B. die Flugbahnen der großen Planeten des Sonnensystems über 10 Jahre), sind für die aktuelle Generation von Intervallmethoden völlig unzugänglich.

Arnold Neumaier
quelle
Vielen Dank. Ich würde gerne (ii) bei der Arbeit sehen. Können Sie ein Beispiel nennen, in dem Autoren Sensitivitätsanalyse und numerische Stabilitätsanalyse kombinieren, um globale Fehlerschätzungen zu ermitteln?
Highsciguy
@highsciguy: siehe meine Bearbeitung zu (ii)
Arnold Neumaier
Vielen Dank. Jacobian Matrix invers?
Highsciguy
@highsciguy: Verstehe deine letzte Frage nicht. Das Beispiel löste ein lineares Gleichungssystem, keine jakobianischen Zahlen.
Arnold Neumaier
1
Ich habe linear übersehen. Dann ist es klar. Gibt es Versuche, das Oettli-Prager-Theorem auf nichtlineare Systeme zu verallgemeinern?
Highsciguy
13

Art von. Es gibt theoretische Fehlergrenzen, die von numerischen Analysten abgeleitet wurden, die normalerweise überschätzt werden und in der Praxis möglicherweise nicht so nützlich sind, weil sie Informationen enthalten können, die für Probleme in der Praxis schwierig zu erhalten sind. Ein gutes Beispiel wären die Grenzen numerischer Fehler bei der Lösung gewöhnlicher Gleichungen, die Sie in den Büchern von Hairer und Wanner finden. Das Buch von Nick Higham, Genauigkeit und Stabilität numerischer Algorithmen (ich verstehe den Titel vielleicht etwas), enthält auch einige Fehlergrenzen für gängige numerische Operationen und lineare Algebra-Algorithmen. Die Literatur zur numerischen Analyse steckt voller solcher Grenzen.

Intervallanalysemethoden wurden auch verwendet, um Fehlergrenzen zu berechnen; Diese Methoden sind rigoros und liefern tendenziell stärkere Fehlergrenzen als theoretische Fehlergrenzen. Dennoch können diese Methoden den Fehler in einer numerischen Berechnung stark überschätzen. Diese Methoden wurden meines Wissens am besten für die globale Optimierung genutzt, finden aber auch bei der Quantifizierung von Unsicherheiten Verwendung. Arnold Neumaier hat mindestens ein Buch über Intervallanalysemethoden verfasst und kann dieses Thema ausführlicher kommentieren. Zusätzlich zu möglichen Überschätzungsproblemen erfordern Intervallanalysemethoden eine zusätzliche Recheninfrastruktur, die eine Nachrüstung bestehender großer numerischer Simulationspakete (wie PETSc, Trilinos, CLAWPACK / PyClaw usw.) erfordert. ) mit Intervallarithmetik und automatischer Differenzierung (für Taylor-basierte Methoden). Soweit ich gesehen habe, gibt es nicht viele freizügig lizenzierte Intervall-Arithmetik- und automatische Differenzierungspakete, obwohl es einige gibt. Selbst dann haben diese Bibliotheken manchmal eine eingeschränkte Funktionalität. Es war schwierig, eine zulassungspflichtige (LGPL- oder BSD-ähnliche) Intervall-Arithmetikbibliothek mit BLAS-ähnlicher Funktionalität zu finden.

A-posteriori- Fehlerschätzungen können einfacher erhalten werden, sind jedoch nicht streng. Ich kenne diese Schätzungen am besten aus der Arbeit mit gewöhnlichen Differentialgleichungen, aber sie gibt es auch für viele Methoden zur Berechnung von Lösungen für partielle Differentialgleichungen.

Im weiteren Sinne können Methoden aus der Quantifizierung von Unsicherheiten wie die Verwendung von Polynom-Chaos-Expansionen, Monte-Carlo-Methoden oder andere Abtastmethoden verwendet werden, um die Unsicherheit in Berechnungen aufgrund von Schwankungen der Eingabeparameter zu quantifizieren. Diese Methoden sollten in der Lage sein, aufgrund von Variationen in den Parametern eine Art heuristischen "Fehlerbalken" bereitzustellen, ohne jedoch strenge Grenzen zu setzen.

Ich bin der Meinung, dass Sie absolut Recht haben, wenn es um die Spezifikation numerischer Fehler geht: In der Informatik sollten die Ergebnisse genauso streng präsentiert werden wie in den experimentellen Naturwissenschaften. In diesem Bereich wird viel gearbeitet (unter den Oberbegriffen "Unsicherheitsquantifizierung" und "numerische Analyse"), und ich hoffe, dass Fehlerbalken bei der Erörterung der meisten Berechnungsergebnisse zu einem späteren Zeitpunkt berücksichtigt werden .

Geoff Oxberry
quelle
Haben Sie eine gute Referenz zu einem Übersichtsartikel über diese Polynom-Chaos-Erweiterungen? Ich habe den Begriff regelmäßig auftauchen sehen und würde gerne mehr darüber erfahren. Vielen Dank.
GertVdE
2
Dongbin Xiu schreibt im Allgemeinen barrierefreie Artikel über polynomiale Chaoserweiterungen. Hier ist eine der allgemeineren Übersichtsarbeiten, die er geschrieben hat: dam.brown.edu/scicomp/media/report_files/BrownSC-2003-07.pdf
Geoff Oxberry
7

Zusätzlich zu den anderen Antworten sind einige zusätzliche Punkte zu beachten.

  1. Numerische Diskretisierungsfehler oder zumindest die Reihenfolge der Schemata können analytisch bestimmt werden. Auf die Erörterung dieser Fehler kann in Veröffentlichungen verzichtet werden, wenn sie ein allgemein bekanntes Schema verwenden.
  2. Netzverfeinerungsstudien, bei denen dasselbe Problem, normalerweise etwas Einfaches, auf immer feineren Netzen ausgeführt wird. Diese werden mit einer exakten Lösung oder der Lösung auf einem lächerlich feinen Gitter verglichen, um die L-Norm zu finden, typischerweise L2. Die Steigung dieser Fehlerschätzung gibt die Reihenfolge der Genauigkeit an.
  3. Bei Problemen, bei denen verschiedene numerische Schemata verfügbar sind, aber keine Verfeinerung des Rasters oder keine exakten Lösungen vorliegen, wird eine andere Methode namens Richardson-Extrapolation die Fehlerbegriffe einschränken. Eine gute Übersicht über diese Methoden finden Sie in diesem Artikel
  4. Schließlich setzt jede Zeitschrift ihre eigenen Standards für die Akzeptanz. Einige sind streng, andere nicht. Zum Beispiel setzen die AIAA seine Standards heraus hier . Andere Zeitschriften haben ähnliche Informationen für Autoren.
tpg2114
quelle
Ich möchte nur auf Punkt 2 eingehen. Ich bin der Meinung, dass bei der numerischen Lösung eines Problems der realen Welt die Wahrscheinlichkeit sehr viel größer ist, dass die Norm den Unterschied zwischen zwei aufeinanderfolgenden Verfeinerungen vergleicht, als mit einem "lächerlich feinen Gitter". Wenn Sie das sehr feine Gitter lösen können, warum haben Sie es dann mit viel gröberen zu tun?
Godric Seer
Die Netzverfeinerungsstudien sind für echte Probleme in der Regel unpraktisch. Hier kommt Punkt 3 ins Spiel. Es ist viel einfacher, Fehlergrenzen durch Ändern der Schemareihenfolge zu bestimmen, als das Raster schrittweise zu verfeinern. Zum Beispiel validieren wir unsere Codes mit einem nichtlinearen Wirbel, aber wir können sehr feine "exakte" Lösungen ausführen, um die Genauigkeit zu überprüfen. Bei einer Vollwirbelbrennkammer können wir dies jedoch praktisch nicht tun, sodass wir unterschiedliche Schemata verwenden.
tpg2114
Beachten Sie auch, dass das Verfeinern des Rasters und das Überprüfen des Unterschieds in der Antwort die Rasterunabhängigkeit anzeigt, was eine andere Sache ist als das Überprüfen der Fehlergrenzen. Eine Verfeinerung des Rasters ist auch in praktischen Fällen noch erforderlich, obwohl eine Verfeinerung des Rasters für so etwas wie große Wirbelsimulationen eine ganze andere Dose Würmer öffnet.
tpg2114
Vielen Dank, ich habe die Netzunabhängigkeit fälschlicherweise mit Fehlergrenzen in Verbindung gebracht. Ich war wohl immer davon ausgegangen, dass die Netzunabhängigkeit ein gewisses Maß an qualitativer Garantie für Diskretisierungsfehler impliziert.
Godric Seer
3
Gitterunabhängigkeit bedeutet, dass ein feineres Gitter die Antwort nicht verbessert, aber es sagt Ihnen nicht, wie genau Ihre Antwort ist oder wie schnell eine Verfeinerung des Gitters die Genauigkeit verbessert.
tpg2114