Matrixnormen und Konditionszahlen

Induzierte Matrixnormen

Eine Vektornorm misst die $Größe eines Vektors$ . Die zugehörige induzierte Matrixnorm misst den größten Faktor, um den eine Matrix einen Vektor strecken kann:

\|A\|=\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}=\max_{\|x\|=1}\|Ax\|

Aus dieser Definition folgen zwei Abschätzungen für Matrizen und Vektoren mit passenden Dimensionen:

\|Ax\|\le\|A\|\|x\|

Die gewählte Vektornorm bestimmt die induzierte Matrixnorm.

Vektornorm	Induzierte Matrixnorm
$\displaystyle\\|x\\|_1=\sum_{i=1}^{n}\lvert x_i\rvert$	$\displaystyle\\|A\\|_1=\max_j\sum_i\lvert a_{ij}\rvert$ , die größte absolute Spaltensumme
$\displaystyle\\|x\\|_\infty=\max_i\lvert x_i\rvert$	$\displaystyle\\|A\\|_\infty=\max_i\sum_j\lvert a_{ij}\rvert$ , die größte absolute Zeilensumme
$\displaystyle\\|x\\|_2=\sqrt{x^{\mathsf T}x}$	$\displaystyle\\|A\\|_2=\sigma_{\max}(A)$ , der größte Singulärwert

Spektralradius und Spektralnorm

Für eine quadratische Matrix ist der Spektralradius

\rho(A)=\max_{\lambda\in\operatorname{spec}(A)}|\lambda|

Jede induzierte Matrixnorm beschränkt den Spektralradius:

\rho(A)\le\|A\|

Für die Spektralnorm gilt

\|A\|_2=\sigma_{\max}(A)=\sqrt{\lambda_{\max}(A^{\mathsf T}A)}

Ist $A$ reell symmetrisch, so sind ihre Singulärwerte die Beträge ihrer Eigenwerte. Daher gilt

\|A\|_2=\max_i|\lambda_i(A)|=\rho(A)

Bei einer allgemeinen nichtnormalen Matrix müssen Spektralradius und Spektralnorm $nicht übereinstimmen$ .

Konditionszahl eines linearen Gleichungssystems

Für eine invertierbare quadratische Matrix und eine induzierte Norm definieren wir

\kappa(A)=\|A\|\|A^{-1}\|

Die Konditionszahl ist mindestens eins. Eine singuläre Matrix hat eine unendliche Konditionszahl. In der euklidischen Norm gilt

\kappa_2(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}

Für eine invertierbare symmetrische Matrix wird daraus

\kappa_2(A)=\frac{\max_i|\lambda_i(A)|}{\min_i|\lambda_i(A)|}

Im Nenner steht der Eigenwert mit dem $kleinsten Betrag$ . Sein Vorzeichen entscheidet diese Auswahl nicht.

Größe von $\kappa(A)$	Bedeutung
Nahe bei $1$	Im $ungünstigsten Fall$ ist die relative Änderung der Lösung ungefähr so groß wie die relative Änderung der Eingabe.
Groß	Bestimmte Eingaberichtungen können viel größere relative Änderungen der Lösung erzeugen.
Unendlich	Die Matrix ist singulär, daher ist das inverse Problem nicht eindeutig lösbar.

Empfindlichkeit eines zweidimensionalen Diagonalsystems

Betrachten wir

A=\begin{pmatrix}1&0\\0&\varepsilon\end{pmatrix},\qquad 0<\varepsilon\ll1

Die Singulärwerte sind $1$ und $\varepsilon$ . Somit gilt

\kappa_2(A)=\frac{1}{\varepsilon}

Für $b=(b_1,b_2)^{\mathsf T}$ ist die Lösung

x=A^{-1}b=\begin{pmatrix}b_1\\b_2/\varepsilon\end{pmatrix}

Eine kleine Änderung von $b_2$ wird in der zweiten Lösungskomponente mit $1/\varepsilon$ $verstärkt$ . Die Matrix ist beinahe singulär, weil sie Vektoren in Richtung der zweiten Koordinatenachse mit dem nahezu null betragenden Wert $\varepsilon$ multipliziert.

Setze $\varepsilon=1/1000$ und vergleiche zwei rechte Seiten. Nur die zweite Beobachtung ändert sich.

$b$	$x=A^{-1}b$
$(1,1/1000)^T$	$(1,1)^T$
$(1,2/1000)^T$	$(1,2)^T$

\Delta b_2=\frac1{1000},\qquad\Delta x_2=\frac{1/1000}{1/1000}=1

Störungsabschätzung

Seien $A$ invertierbar und $b\ne0$ , damit die relativen Fehler unten $Nenner ungleich null$ besitzen. Wir betrachten das Ausgangssystem $Ax=b$ und das folgende gestörte System.

(A+\delta A)(x+\delta x)=b+\delta b

Für alle Größen wird dieselbe induzierte Norm verwendet. Die folgende Abschätzung setzt voraus, dass

\kappa(A)\frac{\|\delta A\|}{\|A\|}<1

Unter dieser Voraussetzung wird die relative Lösungsänderung beschränkt durch

\begin{aligned} \frac{\|\delta x\|}{\|x\|} &\le\frac{\kappa(A)}{1-\kappa(A)\|\delta A\|/\|A\|} \\ &\quad{}\cdot\left(\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right) \end{aligned}

Dies ist eine Abschätzung für den ungünstigsten Fall. Sie sagt nicht voraus, dass jede Störung die maximale Verstärkung erreicht.

Problemkondition und algorithmische Stabilität

Problemkondition und algorithmische Stabilität beschreiben verschiedene Eigenschaften:

$Kondition$ beschreibt $die Empfindlichkeit des mathematischen Problems gegenüber Eingabeänderungen$
$Stabilität$ beschreibt den zusätzlichen Fehler, den ein numerisches Verfahren einführt

Ein stabiles Verfahren kann die bereits vorhandene Empfindlichkeit eines schlecht konditionierten Problems nicht beseitigen. Umgekehrt kann eine instabile Implementierung auch ein gut konditioniertes Problem schlecht lösen. Ein kleines Residuum $\|b-A\hat{x}\|$ allein garantiert bei großer Konditionszahl $\kappa(A)$ ebenfalls keinen kleinen Vorwärtsfehler $\|x-\hat{x}\|$ .

In numerischen Berechnungen sollte man die reziproke Konditionszahl aus einer zuverlässigen Faktorisierung schätzen. Man bildet $A^{-1}$ nicht eigens explizit, nur um $\kappa(A)$ auszuwerten.