Kondition (Mathematik)

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 der Eingangsfehler im ungünstigsten Fall verstärkt wird. Sie ist unabhängig von konkreten Lösungsverfahren, aber abhängig vom mathematischen Problem.

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 der Kondition eines Problems und der Konsistenz des Algorithmus lässt sich wie folgt modellieren:

Es sei $f:{𝕂}^n\to {𝕂}^m$ 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 – auch als Konvergenz bezeichnet – abschätzen:

$\Vert f(x)-\tilde{f}(\tilde{x})\Vert$.

Mit der Dreiecksungleichung gilt:

$\Vert f(x)-\tilde{f}(\tilde{x})\Vert =\Vert f(x)-f(\tilde{x})+f(\tilde{x})-\tilde{f}(\tilde{x})\Vert \le \Vert f(x)-f(\tilde{x})\Vert +\Vert f(\tilde{x})-\tilde{f}(\tilde{x})\Vert .$

Hierbei bezeichnet man mit $\Vert f(x)-f(\tilde{x})\Vert$ die Kondition des Problems und mit $\Vert f(\tilde{x})-\tilde{f}(\tilde{x})\Vert$ die Konsistenz des Algorithmus.

Absolute Kondition

Die absolute Kondition von $f$ am Punkt $x$ wird definiert als

${\kappa }_{\text{abs}}=\underset{\tilde{x}\to x}{\mathrm{lim\; sup}}\frac{\Vert f(\tilde{x})-f(x)\Vert }{\Vert \tilde{x}-x\Vert }.$

Also ist die absolute Kondition ${\kappa }_{\text{abs}}$ genau die kleinste Zahl, für die gilt:

$(\mathrm{\exists }\delta >0)(\mathrm{\forall }\tilde{x}\in {𝕂}^n)(\Vert \tilde{x}-x\Vert <\delta ⟹\Vert f(\tilde{x})-f(x)\Vert \le {\kappa }_{\text{abs}}\Vert \tilde{x}-x\Vert )$.

Relative Kondition

Die relative Kondition von $f$ am Punkt $x$ wird definiert als kleinste Zahl ${\kappa }_{\text{rel}}\ge 0$ mit der Eigenschaft: Es gibt ein $\delta >0$, so dass für alle $\tilde{x}$ mit $0<\Vert \tilde{x}-x\Vert <\delta$ die Ungleichung

$\frac{\Vert f(\tilde{x})-f(x)\Vert }{\Vert f(x)\Vert }\le {\kappa }_{\text{rel}}\frac{\Vert \tilde{x}-x\Vert }{\Vert x\Vert }$

gilt.

Dabei ist $\frac{\Vert f(\tilde{x})-f(x)\Vert }{\Vert f(x)\Vert }$ die relative Änderung des Funktionswertes und $\frac{\Vert \tilde{x}-x\Vert }{\Vert x\Vert }$ die relative Änderung der Eingabedaten. Diese Definition lässt sich auch schreiben als

${\kappa }_{\text{rel}}=\underset{\tilde{x}\to x}{\mathrm{lim\; sup}}\frac{\Vert f(\tilde{x})-f(x)\Vert }{\Vert \tilde{x}-x\Vert }\cdot \frac{\Vert x\Vert }{\Vert f(x)\Vert }$. Ist $f$ an der Stelle $x$ differenzierbar, dann folgt

${\kappa }_{\text{rel}}=\frac{\Vert Df(x)\Vert \Vert x\Vert }{\Vert f(x)\Vert }$.

Dabei ist $Df(x)$ die Jacobi-Matrix von $f$ an der Stelle $x$ und die Norm $\Vert Df(x)\Vert$ eine mit der verwendeten Vektornorm verträgliche Matrixnorm.

Herleitung der relativen Konditionszahl aus der Taylorreihe

Lässt man für eine Funktion $f:ℝ\to ℝ$ in der Taylorreihe Terme höherer Ordnung unberücksichtigt, so ergibt sich

$f(\tilde{x})=f(x)+f^{\prime }(x)(\tilde{x}-x)$,

folglich

$f(\tilde{x})-f(x)=f^{\prime }(x)(\tilde{x}-x).$

Hierbei stellt $f(\tilde{x})-f(x)$ den absoluten Fehler in der Ausgabe dar. Durch Division durch $f(x)$ ergibt sich sofort der relative Ausgabefehler:

$\frac{f(\tilde{x})-f(x)}{f(x)}=\frac{f^{\prime }(x)}{f(x)}(\tilde{x}-x).$

Um den relativen Fehler in der Eingabe auf der rechten Seite sichtbar zu machen, wird nun noch mit $x$ erweitert:

$\left|\frac{f(\tilde{x})-f(x)}{f(x)}\right|=\left|\frac{f^{\prime }(x)}{f(x)}x\right|\cdot \left|\frac{(\tilde{x}-x)}{x}\right|.$

Somit ist alleine aus der Taylorreihe ersichtlich, dass die Fehlerverstärkung durch

${\kappa }_{\text{rel}}=\left|\frac{f^{\prime }(x)}{f(x)}x\right|$

in guter Näherung (Terme höherer Ordnung wurden vernachlässigt!) beschrieben ist.

Kondition von linearen Abbildungen und linearen Gleichungssystemen

Lineare Gleichungssysteme treten häufig in der Numerik auf und daher möchte man gerne die Kondition dieser gut bestimmen können. Es können verschiedene Spezialfälle einzeln betrachtet werden.

Invertierbare Matrix

Für eine invertierbare Matrix $A\in {ℝ}^{n\times n}$ ist die (relative) Kondition definiert als:

${\kappa }_{\Vert \cdot \Vert }(A)=\Vert A\Vert \Vert A^{-1}\Vert ,$

wobei $\Vert \cdot \Vert$ eine submultiplikative Matrixnorm ist. Da häufig durch den Kontext klar ist, um welche Matrixnorm es sich handelt, wird oft auch nur $\kappa (A)$ anstelle von ${\kappa }_{\Vert \cdot \Vert }(A)$ geschrieben.

Störung in der rechten Seite

Sei $x$ die exakte Lösung von $Ax=b$ und $\tilde{x}$ eine Näherungslösung für eine gestörte rechte Seite $\tilde{b}$, also:

$A\tilde{x}=\tilde{b}.$

Nun kann man den Fehler $e$ und den Fehler im Bildraum (Residuum) $r$ definieren:

$\begin{array}{cc}e& :=x-\tilde{x}\\ r& :=b-\tilde{b}=Ae.\end{array}$

Für den relativen Fehler $\frac{\Vert e\Vert }{\Vert x\Vert }$ kann man nun die folgenden Schranken angeben:

$\frac{1}{\kappa (A)}\frac{\Vert r\Vert }{\Vert b\Vert }\le \frac{\Vert e\Vert }{\Vert x\Vert }\le \kappa (A)\frac{\Vert r\Vert }{\Vert b\Vert }.$

Störung in der Matrix

Sei $x$ die exakte Lösung von $Ax=b$ und $\tilde{x}$ eine Näherungslösung für eine gestörte Koeffizientenmatrix $\tilde{A}$, also:

$\tilde{A}\tilde{x}=b.$

Nun kann man den relativen Fehler $\frac{\Vert e\Vert }{\Vert x\Vert }$ nur noch nach Ordnungen in $\Vert A-\tilde{A}\Vert$ entwickeln. Als Abschätzung erhält man:

$\frac{\Vert e\Vert }{\Vert x\Vert }\le \kappa (A)\frac{\Vert A-\tilde{A}\Vert }{\Vert A\Vert }+𝒪(\Vert A-\tilde{A}{\Vert }^2)\text{für}\Vert A-\tilde{A}\Vert \to 0.$

Matrix mit vollem Rang

Für $A\in {ℝ}^{m\times n}$ mit $m\ge n$ und vollem Rang:

$\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}(A)=n$

so definiert man die Kondition $\kappa (A)$ als:

$\kappa (A)=\frac{\underset{\Vert x\Vert =1}{\max }\Vert Ax\Vert }{\underset{\Vert x\Vert =1}{\min }\Vert Ax\Vert }.$

Dies lässt sich mit folgender Überlegung herleiten: setzt man in die obige Definition der relativen Kondition der Funktion $f(x)=Ax$ ein, so gilt:

$\frac{\Vert Ax-A\tilde{x}\Vert }{\Vert Ax\Vert }\le \frac{\underset{\Vert \hat{x}\Vert =1}{\max }\Vert A\hat{x}\Vert }{\underset{\Vert \hat{x}\Vert =1}{\min }\Vert A\hat{x}\Vert }\cdot \frac{\Vert x-\tilde{x}\Vert }{\Vert x\Vert }$.

Damit ist die Kondition von Matrizen die größtmögliche Verzerrung der Einheitskugel.

Außerdem lässt sich die Kondition normaler Matrizen bezüglich der Spektralnorm aus dem Verhältnis des betragsmäßig größten zum betragsmäßig kleinsten Eigenwert der Matrix berechnen:

${\kappa }_{\Vert \cdot {\Vert }_2}(A)={\kappa }_2(A)=\left|\frac{{\lambda }_{\text{max}}(A)}{{\lambda }_{\text{min}}(A)}\right|.$

Beliebige Matrix

Für $A\in {ℝ}^{m\times n}$ beliebig mit $m\ge n$ definiert man die Kondition $\kappa (A)$ mittels der Pseudoinversen $A^{+}$ als:

$\kappa (A)=\Vert A\Vert \Vert A^{+}\Vert .$

Beachte: Häufig bestimmt man die Pseudoinversen $A^{+}$ mittels der Singulärwertzerlegung von $A=U\mathrm{\Sigma }{V}^T$, als: $A^{+}=V{\mathrm{\Sigma }}^{+}{U}^T$. Die Definition von ${\mathrm{\Sigma }}^{+}$ kann man bei der Berechnung der Pseudoinversen nachlesen.

Beispiele

Ein oft angegebenes Beispiel für eine schlecht konditionierte Matrix ist die Hilbert-Matrix $H_n\in {ℝ}^{n\times n}$. Ihre Kondition wächst stark mit der Dimension:

$\kappa (H_n)=𝒪\left(\frac{(1+\sqrt{2}{)}^{4n}}{\sqrt{n}}\right).$

Man kann somit nicht erwarten, dass das lineare Gleichungssystem $H_{n}x=b$ gut nach $x$ aufgelöst werden kann (für $n$ groß).

Interpretation und Ausblick

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 deutlich, wenn man sich den Unterschied zwischen den realen Eingangswerten (beispielsweise reelle Zahlen) und den tatsächlichen Eingangsdaten in Form von Maschinenzahlen klarmacht. Es liegen also einem Computerprogramm als Daten stets bereits verfälschte Werte vor. Das Computerprogramm sollte nun ein brauchbares Ergebnis liefern. Wenn aber das Problem bereits schlecht konditioniert ist, darf man nicht erwarten, dass der Algorithmus brauchbare Ergebnisse liefert.

Hat ein gegebenes Problem eine schlechte Kondition, so ist es in manchen Fällen möglich, es umzuformulieren. So erreicht man bei Matrizen durch geschickte Zeilenvertauschung eine bessere Gesamt-Kondition (hierbei wird die Kondition der Matrix an sich nicht verändert). Die äquivalente Umformulierung eines Problems mit dem Ziel der Konditionsverbesserung nennt man Vorkonditionierung. Zum Testen numerischer Verfahren an Matrizen mit besonders schlechter Kondition eignen sich die Hilbert-Matrizen.

Bei physikalischen Problemen wird die Kondition oft dadurch verbessert, dass die eingehenden Zahlenwerte auf gut verarbeitbare Zahlenwerte normiert (also skaliert) werden.

Beispiele

Multiplikation

Die Multiplikation lässt sich als Abbildung $f:{ℝ}^2\to ℝ$ beschreiben, wobei $f(x)=f(x_1,x_2)$ durch

$f(x_1,x_2)=x_1\cdot x_2$ gegeben ist.

Aus der mehrdimensionalen Taylor-Formel der Funktion $f(x_1,x_2)$ an der Stelle $a=(a_1,a_2)$ ergibt sich

$f(x_1,x_2)=f(a_1,a_2)+\frac{\partial f}{\partial x_1}(a)\cdot (x_1-a_1)+\frac{\partial f}{\partial x_2}(a)\cdot (x_2-a_2)+R_{2}f(x;a)$.

Wegen $\frac{\partial f}{\partial x_1}(a)=a_2,\frac{\partial f}{\partial x_2}(a)=a_1$ ergibt sich für die relative Kondition nach kurzer Rechnung

${\kappa }_{\text{rel}}=1$.

Das zeigt, dass die Multiplikation zweier reeller Zahlen stets gut konditioniert ist.

Addition

Addition: $x_1+x_2$

Die Addition ist eine Abbildung $f:{ℝ}^2\to ℝ$ gegeben durch

$f(x_1,x_2)=x_1+x_2$.

Dafür ergibt sich mit der Summennorm:

${\kappa }_{\text{rel}}:=\frac{\left|x_1\right|+\left|x_2\right|}{|x_1+x_2|}$

Die Addition, wie auch die Subtraktion, ist daher für kleine Nenner $|x_1+x_2|\approx 0$ sehr schlecht konditioniert. In diesem Fall spricht man von Auslöschung. Dies tritt bei der Addition zweier etwa gleich großer Zahlen mit unterschiedlichen Vorzeichen auf – wenn man dies als Subtraktion verstehen möchte, dann bedeutet dies die Subtraktion von Zahlen gleichen Vorzeichens und in etwa gleicher Größe.

Literatur

• Vorlage:Literatur