Kondition in der Numerik

In der numerischen Mathematik beschreibt man mit der Kondition die Abhängigkeit der Lösung eines Problems von der Störung der Eingangsdaten. Die Konditionszahl stellt ein Maß für diese Abhängigkeit dar; sie beschreibt den Faktor, um den Eingangsfehler im ungünstigsten Fall verstärkt werden. Sie ist unabhängig von konkreten Lösungsverfahren.

Einleitung

In der Numerik unterscheidet man zwischen den drei Größen eines Verfahrens: Kondition, Stabilität und Konsistenz, die untereinander stark verwandt sind. Die Beziehung zwischen Kondition eines Problems und Stabilität lässt sich wie folgt modellieren:
Es sei f:Kn→Km f : \mathbb{K}^n \rightarrow \mathbb{K}^m das mathematische Problem in Abhängigkeit der Eingabe xx und es sei f~\tilde f der numerische Algorithmus, sowie x~\tilde x die gestörten Eingabedaten. So möchte man den folgenden Fehler abschätzen:
∥f(x)−f~(x~)∥\|f(x) - \tilde f(\tilde x)\|.
Mit der Dreiecksungleichung gilt:
∥f(x)−f~(x~)∥=∥f(x)−f(x~)+f(x~)−f~(x~)∥≤∥f(x)−f(x~)∥+∥f(x~)−f~(x~)∥\|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(x~)∥\|f(x) - f(\tilde x)\| die Kondition des Problems und ∥f(x~)−f~(x~)∥\|f(\tilde x) - \tilde f(\tilde x)\| die Stabilität. Man spricht dann davon, dass Kondition die Eigenschaft des Problems und Stabilität die Eigenschaft des Algorithmus ist.

Absolute Kondition

Die absolute Kondition κabs\kappa_{abs} ist definiert als lim sup⁡x→x0∣∣f(x)−f(x0)∣∣∣∣x−x0∣∣\limsup_{x \to x_0} \dfrac{||f(x)-f(x_0)||}{||x - x_0||}.
κabs\kappa_{abs} ist also genau die kleinste Zahl, für die gilt: ∃δ>0 ∀∣∣x−x0∣∣<δ:∣∣f(x)−f(x0)∣∣≤κabs∣∣x−x0∣∣\exists \delta > 0 \text{ }\forall ||x - x_0|| < \delta : \qquad ||f(x)-f(x_0)|| \leq \kappa_{abs} ||x - x_0||

Relative Kondition

Die relative Kondition von ff am Punkt xx wird definiert als kleinste Zahl κrel≥0\kappa_\text{rel} \geq 0 mit der Eigenschaft: Es gibt ein δ>0\delta > 0 , so dass für alle x~\tilde x mit 0<∥x~−x∥<δ0 < {\|\tilde x - x\|} < \delta die Ungleichung
∥f(x~)−f(x)∥∥f(x)∥≤κrel∥x~−x∥∥x∥\frac{\|f(\tilde x)-f(x)\|}{\|f(x)\|} \leq \kappa_\text{rel} \frac{\|\tilde x - x\|}{\|x\|}
gilt.
Dabei ist ∥f(x~)−f(x)∥∥f(x)∥\frac{\|f(\tilde x)-f(x)\|}{\|f(x)\|} die relative Änderung des Funktionswertes und ∥x~−x∥∥x∥\frac{\|\tilde x - x\|}{\|x\|} die relative Änderung der Eingabedaten. Diese Definition lässt sich auch schreiben als
κrel=lim sup⁡x~→x∥f(x~)−f(x)∥∥x~−x∥⋅∥x∥∥f(x)∥\kappa_\text{rel} = \limsup_{\tilde x \rightarrow x} \frac{\|f(\tilde x)-f(x)\|}{\|\tilde x - x\|} \cdot \frac{\|x\|}{\|f(x)\|} . Ist ff an der Stelle xx differenzierbar, dann folgt
κrel=∥Df(x)∥∥x∥∥f(x)∥\kappa_\text{rel} = \frac{\|D f(x)\| \|x\|}{\|f(x)\|} .
Dabei ist Df(x)Df(x) die Jacobi-Matrix von ff an der Stelle xx und die Norm ∥Df(x)∥\|D f(x)\| eine mit der verwendeten Vektornorm verträgliche Matrixnorm.

Herleitung der relativen Konditionszahl aus der Taylor-Reihe

Lässt man in der Taylorreihe Terme höherer Ordnung unberücksichtigt, so ergibt sich
f(x~)=f(x)+f′(x)(x~−x)f(\tilde x) = f(x) + f'(x)(\tilde x - x),
folglich
f(x~)−f(x)=f′(x)(x~−x)f(\tilde x) - f(x) = f'(x)(\tilde x - x)
Hierbei stellt f(x~)−f(x)f(\tilde x) - f(x) den absoluten Fehler in der Ausgabe dar. Durch Division durch f(x) f (x) ergibt sich sofort der relative Ausgabefehler:
f(x~)−f(x)f(x)=f′(x)f(x)(x~−x)\dfrac{f(\tilde x) - f(x)}{f(x)} = \dfrac{f'(x)}{f(x)}(\tilde x - x)
Um den relativen Fehler in der Eingabe auf der rechten Seite sichtbar zu machen, wird nun noch mit xx erweitert:
∣∣f(x~)−f(x)f(x)∣∣=∣∣f′(x)f(x)x∣∣⋅∣∣(x~−x)x∣∣\left|| \dfrac{f(\tilde x) - f(x)}{f(x)}\right|| = \left|| \dfrac{f'(x)}{f(x)} x \right|| \cdot \left|| \dfrac{(\tilde x - x)}{x} \right||
Somit ist alleine aus der Taylorreihe ersichtlich, dass die Fehlerverstärkung durch
κrel=∣∣f′(x)f(x)x∣∣\kappa _{rel} = \left||\dfrac{f'(x)}{f(x)} x\right||
in guter Näherung (Terme höherer Ordnung wurden vernachlässigt!) beschrieben ist.

Kondition von Linearen Abbildungen

Die Kondition von linearen Abbildungen lässt sich mithilfe der relativen Kondition herleiten. Setzt man für f(x)f(x) in obiger Definition die Funktion f(x)=Axf(x) = Ax ein, so gilt:
∥Ax−Ax~∥∥Ax∥≤max⁡∥x∥=1∥Ax∥min⁡∥x∥=1∥Ax∥⋅∥x−x~∥∥x∥\dfrac{\|Ax-A\tilde x\|}{\|Ax\|} \leq \dfrac{\max_{\|x\|=1}\|Ax\|}{\min_{\|x\|=1}\|Ax\|} \cdot \dfrac{ \|x-\tilde x\|}{\|x\|}
so ist die Kondition von Matrizen die größtmögliche Verzerrung der Einheitskugel:
κ(A)=(max⁡∥x∥=1∥Ax∥min⁡∥x∥=1∥Ax∥) \kappa(A) = \pmatrix{ {\max_{\|x\|=1} \|Ax\|} \\ { \min_{\|x\|=1} \| Ax\| } }.
Ist der Kern der Matrix nicht trivial, gibt es also Vektoren, die nicht 0 sind und auf die Null abgebildet werden, dann ist κ=∞ \kappa = \infty . Umgekehrt kann man zeigen, dass für reguläre Matrizen gilt:
κ(A)=∥A∥∥A−1∥ \kappa(A) = \|A\| \|A^{-1}\|.

Interpretation

Ist die Konditionszahl κ\kappa deutlich größer als 1 spricht man von einem schlecht konditionierten Problem, sonst von einem gut konditionierten Problem und ist die Konditionszahl unendlich, so handelt es sich um ein schlecht gestelltes Problem.
Die Bedeutung der Kondition wird offensichtlich, wenn man sich den Unterschied zwischen den realen Eingangsdaten (beispielsweise reelle Zahlen) und den tatsächlichen Eingangsdaten in Form von Maschinenzahlen klar macht. Es liegen also einem Computerprogramm stets bereits verfälschte Daten vor. Das Computerprogramm sollte nun ein brauchbares Ergebnis liefern. Wenn aber das Problem bereits schlecht konditioniert ist, darf man keine Wunder mehr vom Algorithmus erwarten.

Beispiele

Multiplikation

Multiplikation: x1⋅x2x_1 \cdot x_2
Die Multiplikation ist eine Abbildung f:R2→Rf:\mathbb{R}^2\to\mathbb{R} gegeben durch f(a,b)=a⋅bf(a,b)=a \cdot b. Die partiellen Ableitungen nach a,ba, b führen zu dfd(a,b)=(b,a)\dfrac{ df }{d(a,b)}=(b,a). Damit ergibt sich für die Kondition der Multiplikation nach obiger Formel
κ1,relativ:=∣f′(a,b)⋅(a,b)Tf(a,b)∣=∣ba+abab∣=2\kappa_{1,{\rm {relativ}}} := \left|\dfrac{f'(a,b) \cdot (a,b)^T}{f(a,b)}\right| = \left|\dfrac{b a + a b}{a b}\right| = 2 .
Die Multiplikation kann als gut konditioniert angesehen werden.

Addition

Addition: x1+x2x_1 + x_2
κ1,relativ:=∣x1∣+∣x2∣∣x1+x2∣\kappa_{1,{\rm relativ}} := \dfrac{\left|x_1 \right|+ \left|x_2\right|}{\left|x_1 + x_2\right|}
Die Addition ist daher für x1+x2≈0x_1 + x_2 \approx 0, die Subtraktion entsprechend im Fall x1≈x2x_1 \approx x_2, sehr schlecht konditioniert. In diesem Fall spricht man von Auslöschung.

Numerische Aspekte

Eines der Aufgabengebiete der Numerik ist die Untersuchung und Optimierung der Kondition für gegebene Probleme wie das Lösen von Gleichungssystemen. Bei der numerischen Lösung wird nun ein Problem in Teilprobleme zerlegt. Oft kann ein in schlecht konditionierte Probleme zerlegter Lösungsweg so durch eine geschicktere Zerlegung ersetzt werden, dass sich die Gesamt-Kondition entscheidend verbessert. So erreicht man bei Matrizen durch geschickte Zeilenvertauschung eine bessere Gesamt-Kondition (hierbei wird die Kondition der Matrix an sich nicht verändert); bei längeren Berechnungen versucht man Additionen sehr kleiner Zahlen oder Subtraktionen annähernd gleich großer Zahlen zur Vermeidung von Auslöschung zu umgehen.
Die äquivalente Umformulierung eines Problems mit dem Ziel der Konditionsverbesserung nennt man Vorkonditionierung.
 
 

Scherzhafte Beispiele haben manchmal größere Bedeutung als ernste.

Michael Stifel

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Kondition (Mathematik) aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Numerik