Matrixnormen und Konditionszahlen

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:

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

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\\|x\\|_2=\sqrt{x^{\mathsf T}x}$

Für eine quadratische Matrix ist der Spektralradius

Jede induzierte Matrixnorm beschränkt den Spektralradius:

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

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

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

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

Für eine invertierbare symmetrische Matrix wird daraus

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.

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

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

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.

Wir betrachten das Ausgangssystem $Ax=b$ und das folgende gestörte System.

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

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

\frac{\|\delta x\|}{\|x\|}\le\frac{\kappa(A)}{1-\kappa(A)\|\delta A\|/\|A\|}\left(\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right)

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 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.

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\\|x\\|_2=\sqrt{x^{\mathsf T}x}$

Matrixnormen und Konditionszahlen

Induzierte Matrixnormen

Matrixnormen und Konditionszahlen

Induzierte Matrixnormen

Spektralradius und Spektralnorm

Konditionszahl eines linearen Gleichungssystems

Empfindlichkeit eines zweidimensionalen Diagonalsystems

Störungsabschätzung

Problemkondition und algorithmische Stabilität