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 unmittelbar zwei wichtige Abschätzungen für Matrizen und Vektoren mit passenden Dimensionen:

Die gewählte Vektornorm bestimmt die induzierte Matrixnorm.

Spektralradius und Spektralnorm

Für eine quadratische Matrix ist der Spektralradius

Jede induzierte Matrixnorm beschränkt den Spektralradius:

Für die Spektralnorm gilt

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.

Konditionszahl eines linearen Gleichungssystems

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 kleinste Betrag, nicht der algebraisch kleinste Eigenwert.

Ein zweidimensionales Beispiel

Betrachten wir

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 eine Richtung nahezu zusammenfallen lässt.

Störungsabschätzung

Es seien $Ax=b$ und

mit derselben induzierten Norm gegeben. Falls

gilt, wird die relative Lösungsänderung beschränkt durch

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

Kondition ist nicht algorithmische Stabilität

Die beiden Begriffe beantworten verschiedene Fragen:

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