Stabilität (Numerik)

In der numerischen Mathematik heißt ein Verfahren stabil, wenn es unempfindlich ist gegenüber kleinen Störungen der Daten. Insbesondere bedeutet dies, dass sich Rundungsfehler (siehe auch Maschinengenauigkeit) nicht zu stark auf die Berechnung auswirken.

Bei der numerischen Lösung mathematischer Probleme unterscheidet man Kondition, Stabilität und Konsistenz. Stabilität ist dabei eine Eigenschaft des Algorithmus, Kondition eine Eigenschaft des Problems. Zwischen diesen Größen besteht folgende Beziehung:

Es sei

• $f(x)$ das mathematische Problem in Abhängigkeit von der Eingabe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde f} der numerische Algorithmus
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x} die gestörten Eingabedaten:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|f(\tilde x) - f(x)\|} Kondition: Wie stark schwankt das Problem bei Störung?

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|\tilde f(\tilde x) - \tilde f(x)\|} Stabilität: Wie stark schwankt der numerische Algorithmus bei Störung?

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|\tilde f(x) - f(x)\|} Konsistenz: Wie gut löst der Algorithmus (mit exakter Eingabe) tatsächlich das Problem?

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|\tilde f(\tilde x) - f(x)\|} Konvergenz: Wie gut löst der gestörte Algorithmus tatsächlich das Problem?

Also beschreibt die Stabilität die Robustheit des numerischen Verfahrens gegenüber Störungen in den Eingabedaten, insbesondere bedeutet dies, dass sich Rundungsfehler nicht summieren und zu Störungen in der Lösung führen. Die Quantifizierung des Begriffes ist jedoch nach Problem und verwendeter Norm unterschiedlich.

Im Regelfall folgt aus Stabilität und Konsistenz (manchmal noch mit einer kleinen Zusatzvoraussetzung) die Konvergenz der numerischen Lösung gegen die analytische Lösung, da sowohl die Fehler der Eingabedaten als auch die Fehler durch die Diskretisierung des Problems gedämpft werden.

Die beiden Analyseverfahren

Vorwärtsanalyse

Ein Verfahren heißt stabil, wenn es eine Konstante Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \sigma \in \mathbb {R} } und ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|\tilde x - x \| \leq \varepsilon} gibt, so dass gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|\tilde f(x) - \tilde f(\tilde x) \| \leq \kappa\sigma \varepsilon}

mit

• der relativen Kondition Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \kappa } des Problems
• der Maschinengenauigkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon }
• der Quantifizierung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma } der Stabilität im Sinne der Vorwärtsanalyse.

Rückwärtsanalyse

Das zweite gängige Analyseverfahren ist die von James Hardy Wilkinson eingeführte Rückwärtsanalyse.

Meistens kennt man eine sinnvolle obere Schranke Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} für den unvermeidbaren relativen Eingabefehler ${\frac {\|{\tilde {x}}-x\|}{\|x\|}}$ (problemabhängig kann das ein Messfehler oder auch ein Rundungsfehler sein). Um den durch den Algorithmus verursachten Fehler besser einschätzen zu können, rechnet man ihn bei der Rückwärtsanalyse rückwärts in einen äquivalenten Fehler in den Eingangsdaten des Problems um, der auch als Rückwärtsfehler bezeichnet wird.

Die formale Definition des Rückwärtsfehlers des Algorithmus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde f} für die (gerundeten) Eingabedaten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x} (mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|\tilde x\|\neq 0} ) lautet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon_{\text{R}}(\tilde x) := \inf\left\{\left.\frac{\|\hat x-\tilde x\|}{\|\tilde x\|}\right| \hat x \in\operatorname{Db} f\;\wedge\; f(\hat x)=\tilde f(\tilde x) \right\}} ,

wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{Db}} für Definitionsbereich steht.

Vereinfacht gesagt wird bei der Rückwärtsanalyse nicht direkt das Ergebnis der Durchführung / Anwendung des Algorithmus beurteilt, sondern indirekt wie groß der (relative) Eingabefehler sein darf, mit dem noch ein erträglich genaues Ergebnis herauskommt.

Der Algorithmus ist rückwärtsstabil, wenn der relative Rückwärtsfehler für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x \in \operatorname{Db} \tilde f} kleiner ist als der unvermeidbare relative Eingabefehler.

Für manche Anwendungen schwächt man diese Forderung ab und lässt noch eine dem Problem angemessene Konstante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C>1} zu, mit der gelten soll:

für alle ${\tilde {x}}\in \operatorname {Db} {\tilde {f}}\colon \varepsilon _{\text{R}}({\tilde {x}})\leq C\varepsilon .$

Manchmal interessiert man sich auch nur dafür, ob der relative Rückwärtsfehler überhaupt beschränkt ist.

Man kann zeigen, dass Rückwärtsstabilität die Vorwärtsstabilität impliziert.

Anwendungen

Addition

Da man zeigen kann, dass die relative Kondition der Addition bei zwei Zahlen im Falle der Auslöschung (Ergebnis ist nah an 0) beliebig schlecht sein kann, folgt aus der Definition der Vorwärtsanalyse, dass die Addition als numerisches Verfahren (im Computer) stabil ist.

Differentialgleichungen

Bei numerischen Lösern für Differentialgleichungen mit Anfangs- oder Randwerten bzw. mit rechter Seite Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} versucht man abzuschätzen, wie die entwickelte Lösung von den Eingabegrößen abhängt. Im Sinne der Vorwärtsanalyse gibt es in diesem Fall die Konstante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma} .

Gewöhnliche Differentialgleichungen

Für gewöhnliche Differentialgleichungen gilt der Äquivalenzsatz von Lax, nach dem Null-Stabilität und Konsistenz äquivalent zu Konvergenz des Verfahrens sind.

Zu konkreten Verfahren wird das Stabilitätsgebiet definiert als die Menge der komplexen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \xi = \Delta t \cdot \lambda} , für die das numerische Verfahren bei der Lösung der dahlquistschen Testgleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y' = \lambda y, \quad y(0) = 1}

bei fester Schrittweite Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta t} eine beschränkte Folge von Näherungen liefert.

Der beste Fall ist, wenn das Stabilitätsgebiet die komplette linke Halbebene enthält, dann heißt das Verfahren A-stabil.

Partielle Differentialgleichungen

Das Standardverfahren zur Stabilitätsanalyse numerischer Verfahren für partielle Differentialgleichungen ist die Von-Neumann-Stabilitätsanalyse. Sie macht

• für lineare Probleme notwendige und hinreichende Aussagen
• für nichtlineare Probleme jedoch nur notwendige.

Siehe auch

• Stabilitätstheorie

Literatur

• J. H. Wilkinson: Error Analysis of Direct Methods of Matrix Inversion. Journal of the ACM, Vol. 8(1961), No. 3, pp. 281–330
• Peter Deuflhard, Andreas Hohmann: Numerische Mathematik I, Eine algorithmisch orientierte Einführung. 3. Auflage. De Gruyter, 2002, ISBN 978-3-11-017182-2. 
• Martin Hermann: Numerische Mathematik. Oldenbourg Verlag, München und Wien 2001, ISBN 3-486-25558-4. 
• Martin Hermann: Numerik gewöhnlicher Differentialgleichungen, Anfangs- und Randwertprobleme. Oldenbourg Verlag, München und Wien 2004, ISBN 3-486-27606-9.