Konditionierung und numerische Stabilität

Die Konditionierung misst, wie empfindlich die Lösung eines Problems auf Störungen in seinen Daten reagiert, während die Stabilität misst, wie viele Fehler ein bestimmter Algorithmus bei der Gleitkommaarithmetik mit endlicher Genauigkeit hinzufügt; zusammen bestimmen sie die Genauigkeit eines berechneten Ergebnisses.

Definition

Konditionierung ist eine intrinsische Eigenschaft eines Problems, die beschreibt, wie seine exakte Lösung auf Störungen der Eingabe reagiert, während numerische Stabilität eine Eigenschaft eines Algorithmus ist, die beschreibt, wie zuverlässig er das Problem trotz Rundungsfehlern löst.

Scope

Dieses Thema behandelt die Gleitkommaarithmetik und den Maschinengenauigkeit (unit roundoff), die Konditionszahl von Problemen wie dem Lösen linearer Gleichungssysteme und der Funktionsauswertung, den Vorwärts- und Rückwärtsfehler, die Faustregel, dass der Vorwärtsfehler durch die Konditionszahl multipliziert mit dem Rückwärtsfehler begrenzt ist, sowie die Definitionen von Rückwärts- und Vorwärtsstabilität.

Core questions

• Wie wird die Gleitkommaarithmetik modelliert und welche Rolle spielt die Maschinengenauigkeit (unit roundoff)?
• Was quantifiziert die Konditionszahl eines Problems und wie ist sie für lineare Systeme und für die Funktionsauswertung definiert?
• Wie hängen Vorwärtsfehler, Rückwärtsfehler und Konditionierung zusammen?
• Was unterscheidet einen rückwärtsstabilen Algorithmus von einem vorwärtsstabilen und warum ist Rückwärtsstabilität das übliche Ziel?

Key theories

Konditionszahl

Die Konditionszahl ist der Faktor, um den relative Störungen in den Daten in der Lösung verstärkt werden können; für ein lineares System entspricht sie der Matrixnorm multipliziert mit der Norm der Inversen und setzt eine Grenze für die erreichbare Genauigkeit, unabhängig vom Algorithmus.

Rückwärtsfehleranalyse

Anstatt den Fehler in der Antwort direkt zu begrenzen, wird gezeigt, dass das berechnete Ergebnis die exakte Antwort auf ein nahegelegenes Problem ist; ein Algorithmus ist rückwärtsstabil, wenn dieses nahegelegene Problem vom Original um einen Betrag der Größenordnung der Maschinengenauigkeit abweicht.

Vorwärtsfehler gleich Konditionszahl mal Rückwärtsfehler

Die zentrale Faustregel der numerischen Analyse besagt, dass der Vorwärtsfehler (Lösungsfehler) annähernd durch die Konditionszahl des Problems multipliziert mit dem Rückwärtsfehler begrenzt ist, wodurch die Beiträge des Problems und des Algorithmus klar getrennt werden.

Mechanisms

Gleitkommazahlen stellen reelle Zahlen mit endlicher Genauigkeit dar, sodass jede elementare Operation einen relativen Fehler verursacht, der durch die Maschinengenauigkeit begrenzt ist. Die Rückwärtsfehleranalyse verfolgt diese Fehler, indem sie sie Störungen der Daten und nicht des Ergebnisses zuschreibt, wodurch Grenzen der Form erzeugt werden: berechnete Antwort gleich exakter Antwort einer gestörten Eingabe. Die Kombination einer Rückwärtsfehlergrenze mit der Konditionszahl des Problems ergibt eine Vorwärtsfehlerschätzung, die erklärt, warum ein stabiler Algorithmus bei einem schlecht konditionierten Problem immer noch an Genauigkeit verlieren kann.

Clinical relevance

Das Verständnis von Konditionierung und Stabilität ist unerlässlich, wann immer berechneten Ergebnissen vertraut werden muss: Es erklärt, warum einige Kleinste-Quadrate-Formulierungen an Genauigkeit verlieren, leitet die Wahl stabiler Algorithmen und gut gestellter Formulierungen in Simulation und Datenanalyse an und warnt, wenn ein schlecht konditioniertes Modell unabhängig von der verwendeten Methode keine zuverlässige Antwort liefern kann.

History

Der konzeptionelle Rahmen wurde von Wilkinson etabliert, dessen Rückwärtsfehleranalyse in den 1960er Jahren die praktische Zuverlässigkeit der Gauß-Elimination erklärte und später von Higham im gesamten Feld systematisiert und erweitert wurde; der IEEE 754 Gleitkommastandard stellte anschließend das Rundungsverhalten auf eine feste und portable Grundlage.

Key figures

• James H. Wilkinson
• Nicholas J. Higham
• Lloyd N. Trefethen
• William Kahan

Seminal works

• trefethen1997
• higham2002

Frequently asked questions

Wenn ein Algorithmus stabil ist, liefert er dann immer eine genaue Antwort?

Nein. Ein rückwärtsstabiler Algorithmus garantiert nur, dass seine Antwort für ein nahegelegenes Problem exakt ist; wenn das Problem selbst schlecht konditioniert ist, kann dieses nahegelegene Problem eine sehr unterschiedliche Lösung haben, sodass der Vorwärtsfehler immer noch groß sein kann.

Was ist die Maschinengenauigkeit (unit roundoff)?

Die Maschinengenauigkeit ist der maximale relative Fehler, der entsteht, wenn eine reelle Zahl auf die nächste Gleitkommazahl gerundet wird; sie legt die Granularität der Gleitkommaarithmetik fest und erscheint in praktisch jeder Stabilitätsgrenze.