Wie identifiziere ich instabile Gleitkommaberechnungen?

15

In der Numerik ist es sehr wichtig, instabile Schemata zu identifizieren und ihre Stabilität zu verbessern. Wie identifiziere ich instabile Gleitkommaberechnungen?

Ich arbeite an einer sehr komplexen Simulation, bei der viele numerische Schemata zusammenarbeiten, und suche nach einer Methode, um ihre Schwachstellen zu identifizieren. Ich arbeite an einem physikalischen Modell mit Differentialgleichungen. Eine Vogelperspektive des Gesamtprozesses ist:

  1. (Preliminary Schritt) Sammle physikalischen Beobachtungen P .

  2. Bestimmen Sie die Anfangsparameter der Simulation. Dies verwendet einen Optimierungsalgorithmus, bei dem wir in einem Parameterraum nach Parametern C suchen, sodass eine Fehlerfunktion E (F (C), P) minimiert wird, wobei F eine abgeleitete Größe der Parameter ist.

  3. Stecken Sie C in die Simulationsmaschine. Dies ist ein Euler-Schema der EDV, sodass wir zu jedem Zeitpunkt die Terme berechnen, die die Dynamik antreiben (jede von ihnen ist eine komplexe Funktion, die möglicherweise Instabilität unterliegt), und das Euler-Schema mit diesen dynamischen Terms versorgen, um die nächste zu berechnen Zustand. Dies geht zu Tausenden von Zeitpunkten weiter.

  4. Am Ende der Simulation berechnen wir eine Funktion Proof (S) des Endzustand S und vergleichen , um einige Mengen erforderlich (P) aus den beobachteten Mengen abgeleitet. Dies ist kein formaler Nachweis des Ergebnisses, sondern eine Plausibilitätsprüfung.

Außerdem sehe ich einen Turm komplexer Operationen (Berechnung dynamischer Terme innerhalb des Euler-Schemas, innerhalb des Beweises ). Und möchte "schlechte Teile" erkennen und beheben.

Ich spekuliere, dass die Verwendung einer Softwareimplementierung von Gleitkommazahlen mit reduzierter Genauigkeit die Instabilität numerischer Schemata vergrößern und somit den Vergleich zwischen verschiedenen Implementierungen erleichtern würde. Ist dies eine übliche Technik, um diese Frage zu untersuchen? Ist es möglich, eine virtuelle Maschine wie Bochs zu verwenden, um dies zu erreichen, ohne das Programm zu ändern?

Um die Stabilitätsfrage angemessen zu behandeln, ist es manchmal akzeptabel, auf die typischen Eingaben der numerischen Prozedur abzustimmen, so dass sie für diese Eingaben gut und für andere gültige, aber unwahrscheinliche Eingaben möglicherweise weniger gut geeignet sind. Eine Probe von typischen Eingänge gegeben, ist es möglich, schnüffeln sie einige Zwischenergebnisse und bereiten ein statistisches Profil. Ist dies eine übliche Technik, um Stabilitätsprobleme zu untersuchen? Ist eine virtuelle Maschine dafür nützlich?

user40989
quelle
Vielleicht haben Sie interessantere Antworten auf math.stackexchange.com
Simon Bergot
@ Simon Sie haben vielleicht Recht, aber dies ist definitiv eine domänenübergreifende Frage. Ich vermute, Personen, die antworten können, sind sowohl für Mathematiker als auch für Programmierer registriert oder für niemanden. Warten wir ein bisschen und sehen, ob diese Frage hier ihre Antwort findet!
user40989
1
Intervallarithmetik?
SK-logic
2
Es ist nicht unbedingt böse, mit Euler den Staat zu verbreiten. Dies ist auch keine Optimierung, aber Sie müssen das Problem wirklich in Teilaufgaben aufteilen. Die numerische Instabilität ist möglicherweise das geringste Ihrer Probleme - die Konvergenz zu einem falschen Maximum und die Probleme im Zusammenhang mit der Steifheit der ODEs / PDEs sind größer. Und ja, niemals mit einfacher Präzision :)
Deer Hunter

Antworten:

6

Die Untersuchung der Stabilität der Gleitkommaberechnung ist Teil der numerischen Analyse. Wenn Sie wirklich ein solides Ergebnis erzielen möchten, möchten Sie, dass jemand, der sich in diesem Bereich auskennt, die Analyse der verwendeten Algorithmen durchführt.

Es gibt einige Dinge, die helfen können, instabile Algorithmen experimentell zu identifizieren. Laufen mit auf verschiedene Modi (auf / ab / zufällig) eingestellter Rundung oder mit unterschiedlicher Genauigkeit und Prüfen, ob das Ergebnis nicht zu stark variiert. Beantworten ist das zu viel? ist überhaupt nicht einfach und selbst wenn die Antwort nein ist , bedeutet das nicht, dass der Algorithmus stabil ist, nur dass er in dem von Ihnen verwendeten Datensatz nicht als instabil erkannt wurde.

In Kommentaren wurde eine Intervallarithmetik vorgeschlagen. Als ich es mir ansah, gab selbst der tollwütigste Befürworter der Intervallarithmetik zu, dass es gut mit Algorithmen funktioniert, die für die Intervallarithmetik entwickelt wurden, aber dass ein Wechsel zu ihm ohne Analyse des Algorithmus und ohne die Sicherstellung, dass Muster bekanntermaßen nicht gut funktionieren, nicht funktionieren würde nützlich sein (Gegner schienen der Meinung zu sein, dass die Voraussetzungen für die Intervallarithmetik nützlich sind, wenn sie zu restriktiv sind, um von praktischem Interesse zu sein)

Ein Programmierer
quelle
3

Das Entwerfen stabiler Gleitkomma-Algorithmen ist höchst unwesentlich. Diejenigen, die mathematisch versierter sind als ich, schlagen vor, nach Möglichkeit angesehene Bibliotheken zu verwenden, anstatt zu versuchen, Ihre eigenen zu rollen. Die Standardreferenz in diesem Bereich scheint zu sein:

NJ Higham. Genauigkeit und Stabilität numerischer Algorithmen. Gesellschaft für industrielle und angewandte Mathematik, Philadelphia, PA, USA, zweite Ausgabe, 2002. ISBN 0-89871-521-0

Wenn Sie nicht genau wissen, welche Arten von Berechnungen, Sprachen usw. Sie benötigen, ist es schwierig, eine konkrete Antwort zu geben. Es gibt hier einen guten Vortrag: http://introcs.cs.princeton.edu/java/91float/ Dies mag ein wenig grundlegend sein, aber es ist eine gute Einführung, wenn Sie Java verwenden.

WPrecht
quelle
1

Wie identifiziere ich instabile Gleitkommaberechnungen? Ist dies eine übliche Technik, um diese Frage zu untersuchen?

Ich denke, wenn Sie keine Statistiken zu Fehlern anzeigen müssen, müssen Sie keine Proben sammeln. Was Sie brauchen, ist die Numerische Analyse , die auch unter die Themen Numerische Methoden, Numerische Lineare Algebra usw. fällt. Und sie sind Teil der Informatik, sodass Sie möglicherweise auch in cs.stackexchange einige Antworten erhalten.

Wie dem auch sei, bei der allgemeinen Programmierung sind die meisten Probleme leicht zu erkennen, wenn ein grundlegendes Verständnis der Funktionsweise von Fließkommawerten und grundlegenden numerischen Methoden vorliegt. Aber noch komplexere Probleme sind heutzutage "einfacher" zu lösen, da 128-Bit-Floats zur Verfügung stehen und noch weniger Grund besteht, Fehlerbeispiele zu erstellen. Hier sind einige Beispielprobleme, um meinen Standpunkt zu verdeutlichen:

  1. Verwenden von Gleitkomma für die Berechnung von Geldwerten.
  2. Verwenden von Gleitkommazahlen für große Zahlen.
  3. Divisionen nicht vor anderen Operationen durchführen, wenn dies möglich ist. (um den Wert näher an 0 zu bringen).
  4. lange Berechnung ohne spezielle Behandlung für die Fehlerausbreitung.

Es gibt auch ein Beispiel für einen naiven Algorithmus und einen fehlerkompensierten Algorithmus zur Berechnung der Varianz . In dem Beispiel, in dem Sie die naive Version betrachten, können Sie nur riechen, dass das Berechnen in Schleifen einige Fehler mit sich bringt und nicht kompensiert wird.

imel96
quelle
Vielen Dank für Ihre Antwort, ich bin jedoch auf der Suche nach detaillierteren Informationen. Ich habe eine sehr große Berechnung und möchte ihre Schwachstellen identifizieren. Ich habe die Frage entsprechend bearbeitet.
user40989
Ich bin mir nicht ganz sicher, in welcher Situation Sie sich befinden, wenn Sie sagen, dass Sie über umfangreiche Berechnungen verfügen und Schwachstellen identifizieren möchten. Numerische Berechnungen enthalten von Natur aus Fehler, selbst eine einfache Additionsoperation. Sofern Ihre umfangreiche Berechnung nicht fehlerkompensiert ist, müssen sie insgesamt behoben werden. Schwächere Stellen zu verbessern ist möglicherweise nicht gut genug. Wenn Sie nun das "Epsilon" Ihres Gleitkommamodells angeben, zeigt eine einfache Analyse, wie groß der Fehler sein kann, wenn er sich durch die lange Berechnung ausbreitet.
Imel96
0

Sie können numerische Fehler vermeiden, indem Sie geeignete Datentypen verwenden (z. B. fortgesetzte Brüche). Wenn Sie Gleitkomma-Arithmetik benötigen oder verwenden möchten, müssen Sie numerisches Know-how anwenden, um die Fehler zu kennen.

Ingo
quelle
Ich möchte numerische Fehler nicht vermeiden, sondern herausfinden, welche Teile der Berechnung instabil sind. Dies ähnelt der Lokalisierung von Geschwindigkeitsengpässen bei der Geschwindigkeitsoptimierung. Ich möchte also die Präzision optimieren und möchte daher Präzisionsengpässe finden. (Fortgesetzte Brüche sind hier nicht nützlich.)
user40989
1
@ user40989, dann brauchst du auf jeden Fall Intervallarithmetik.
SK-logic