Stabilität (Numerik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der numerischen Mathematik heißt ein Verfahren stabil, wenn es gegenüber kleinen Störungen der Daten unempfindlich ist. Insbesondere bedeutet dies, dass sich Rundungsfehler nicht zu stark auf die Berechnung auswirken. Man unterscheidet in der Numerik hierbei Kondition, Stabilität und Konsistenz, die untereinander stark verwandt sind. Stabilität ist dabei eine Eigenschaft des Algorithmus und die Kondition eine Eigenschaft des Problems. Die Beziehung zwischen Kondition eines Problems und Stabilität lässt sich wie folgt beschreiben:

Es sei f(x) das mathematische Problem in Abhängigkeit von der Eingabe x, und es sei \tilde f der numerische Algorithmus, sowie \tilde x die gestörten Eingabedaten. So möchte man den folgenden Fehler abschätzen:

\|f(x) - \tilde f(\tilde x)\|.

Mit der Dreiecksungleichung gilt:

\|f(x) - \tilde f(\tilde x)\| = \|f(x) - f(\tilde x) + f(\tilde x) - \tilde f(\tilde x)\| \leq \|f(x) - f(\tilde x)\| + \|f(\tilde x) - \tilde f(\tilde x)\|.

Hierbei bezeichnet man mit \|f(x) - f(\tilde x)\| die Kondition des Problems und \|f(\tilde x) - \tilde f(\tilde x)\| die Stabilität.

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.

Stabilität und Konsistenz hängen im Regelfall derart zusammen, dass sie, manchmal noch mit einer kleinen Zusatzvoraussetzung, äquivalent zu Konvergenz der (numerischen) Lösung gegen die analytische sind.

Die beiden Analyseverfahren[Bearbeiten]

Vorwärtsanalyse[Bearbeiten]

Ein Verfahren heißt stabil, wenn es eine Konstante \sigma \in \mathbb{R} gibt, so dass gilt:

\|f(\tilde x) - \tilde f(\tilde x) \| \leq \kappa\sigma \varepsilon

wobei  \kappa die relative Kondition des Problems und  \varepsilon die Maschinengenauigkeit bezeichnet.  \sigma quantifiziert die Stabilität im Sinne der Vorwärtsanalyse.

Rückwärtsanalyse[Bearbeiten]

Das zweite gängige Analyseverfahren ist die von James Hardy Wilkinson eingeführte Rückwärtsanalyse. Meistens kennt man eine sinnvolle obere Schranke \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 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 \tilde f für die (gerundeten) Eingabedaten \tilde x (mit \|\tilde x\|\neq 0) lautet:


\varepsilon_{\rm R}(\tilde x) := \inf\left\{\frac{\|\hat x-\tilde x\|}{\|\tilde x\|}\mid \hat x \in\operatorname{Db} f\;\wedge\; f(\hat x)=\tilde f(\tilde x) \right\},

wobei \operatorname{Db} für Definitionsbereich steht.

Der Algorithmus ist rückwärtsstabil, wenn der relative Rückwärtsfehler für alle \tilde x \in \operatorname{Db} \tilde f kleiner als der unvermeidbare relative Eingabefehler ist. Für manche Anwendungen schwächt man diese Forderung ab und lässt noch eine dem Problem angemessene Konstante C>1 zu, mit der

für alle 
\tilde x \in \operatorname{Db}\tilde f:\; \varepsilon_{\rm R}(\tilde x)\leq C\varepsilon

gelten soll. 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[Bearbeiten]

Addition[Bearbeiten]

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[Bearbeiten]

Bei numerischen Lösern für Differentialgleichungen mit Anfangs- oder Randwerten, bzw. mit rechter Seite  f versucht man eine Abschätzung der entwickelten Lösung von diesen Eingabegrößen zu erhalten. Im Sinne der Vorwärtsanalyse gibt es in diesem Fall die Konstante  \sigma .

Gewöhnliche Differentialgleichungen[Bearbeiten]

Hier 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 \xi=\Delta t \cdot \lambda für die das numerische Verfahren bei der Lösung der dahlquistschen Testgleichung

y'=\lambda y, \quad y(0)=1

bei fester Schrittweite \Delta t eine monoton fallende 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[Bearbeiten]

Das Standardverfahren zur Stabilitätsanalyse von numerischen Verfahren für partielle Differentialgleichungen ist die Von-Neumann-Stabilitätsanalyse, die für lineare Probleme notwendige und hinreichende Aussagen macht, für nichtlineare Probleme jedoch nur notwendige.

Siehe auch: Stabilitätstheorie

Literatur[Bearbeiten]

  • J. H. Wilkinson: Error Analysis of Direct Methods of Matrix Inversion. Journal of the ACM, Vol. 8(1961), No. 3, pp. 281-330
  • Deuflhard, Hohmann: Numerische Mathematik I deGruyter
  • Krause: Praktische Mathematik Universität Bonn
  • Hermann, M.: Numerische Mathematik, Oldenbourg Verlag, München und Wien, 2001, ISBN 3-486-25558-4
  • Hermann, M.: Numerik gewöhnlicher Differentialgleichungen, Anfangs- und Randwertprobleme, Oldenbourg Verlag, München und Wien, 2004, ISBN 3-486-27606-9