Konditionszahl

Erklärung

Die Konditionszahl misst, wie empfindlich die Lösung eines linearen Gleichungssystems $Ax = b$ auf Störungen der Daten reagiert. Ändert sich die rechte Seite um $\Delta b$, ändert sich die Lösung um $\Delta x = A^{-1}\Delta b$. Daraus folgt die Abschätzung oben: Der relative Fehler der Lösung ist höchstens $\kappa(A)$-mal so groß wie der relative Fehler der Daten. Eine ähnliche Abschätzung gilt für Störungen in $A$.

• Für jede induzierte Matrixnorm gilt $\kappa(A) \geq 1$.
• $\kappa(A)$ nahe $1$: gut konditioniert. Orthogonale Matrizen haben in der euklidischen Norm $\kappa = 1$.
• $\kappa(A)$ groß: schlecht konditioniert. Kleine Rundungs- oder Messfehler können die Lösung stark verfälschen.
• Faustregel: Man verliert etwa $\log_{10} \kappa(A)$ Dezimalstellen an Genauigkeit.

Der Wert hängt von der Norm ab. Häufig verwendet man die Zeilensummennorm $\|A\|_\infty = \max_i \sum_j |a_{ij}|$ oder die Spektralnorm. Für symmetrische Matrizen ist $\kappa_2(A) = \frac{|\lambda_{\max}|}{|\lambda_{\min}|}$, der Quotient der betragsgrößten und betragskleinsten Eigenwerte.

Die Kondition ist eine Eigenschaft des Problems, nicht des Lösungsverfahrens. Auch das beste Verfahren kann die Fehlerverstärkung eines schlecht konditionierten Problems nicht beseitigen.

Beispiele

In der Zeilensummennorm ist $\|A\|_\infty = 2{,}01$ und $\|A^{-1}\|_\infty = 201$, also

Zu $b = (2;\ 2{,}01)$ gehört die Lösung $x = (1;\ 1)$. Ändert man nur die zweite Komponente auf $2{,}02$, ist die Lösung $(0;\ 2)$. Die rechte Seite ändert sich relativ um $\frac{0{,}01}{2{,}01} \approx 0{,}005$, also ein halbes Prozent. Die Lösung ändert sich relativ um $\frac{1}{1} = 100\,\%$. Der Verstärkungsfaktor $201$ liegt unter der Schranke $404{,}01$. Nach der Faustregel gehen hier etwa $\log_{10} 404 \approx 2{,}6$ Stellen verloren.

Typische Fehler

• Eine kleine Determinante mit schlechter Kondition gleichsetzen. $0{,}1 \cdot I$ hat die Determinante $0{,}01$ (bei $n = 2$), ist aber mit $\kappa = 1$ perfekt konditioniert.
• Normen mischen: $\|A\|$ und $\|A^{-1}\|$ müssen in derselben Norm berechnet werden.
• Die Ungleichung als Gleichung lesen. Sie gibt den schlimmsten Fall an; oft ist die tatsächliche Verstärkung kleiner.
• Bei schlechter Kondition die Schuld beim Verfahren suchen. Auch exakte Rechnung reagiert so stark auf gestörte Daten.