Kurs:Numerik I/Konditionszahl einer Matrix

Einleitung

Die Konditionszahl einer Matrix ist eine Indikator dafür, wie stark Veränderungen der Daten auf die Lösung der Gleichung wirken. Anschaulich kann man das mit zwei Objektiven einer Kamera erläutern. Wenn das Bild einer Standardkamera betrachtet, kann man diese in der Hand halten und im darstellten Bild bemerkt man kaum die geringen Bewegungen, die unsere Hand im Vergleich zu einer auf dem Stativ fixierten Kamera besitzt. Bei Teleobjektive, die entfernt Objekte heranzoomen und vergößern kann man dagegen große Schwankung im Bildbereich erkennen. Daher werden Fotos mit Teleobjektiven i.d.R. mit Stativen aufgenommen.

Definition - Konditionszahl

Sei $A\in \mathbb {R} ^{n\times n}$ eine reguläre Matrix und $\|\cdot \|:\mathbb {R} ^{n\times n}\to \mathbb {R} _{+}$ eine Matrixnorm. Die Zahl

\operatorname {cond} (A):=\|A\|\cdot \|A^{-1}\|

heißt Kondition oder Konditionszahl der Matrix $A$ .

Bemerkung - Semantik der Konditionszahl

Bei einem numerischen Problem, das gut konditioniert ist, ist die Konditionszahl klein. Damit verursachen kleine Änderungen in den Daten auch nur geringfügige Änderungen in der Lösung des Problems. Betrachtet man allerdings numerische Probleme mit einer großen Konditionszahl (d.h. das Problem schlecht konditioniert) können geringfügige Veränderungen in den Daten bereits große Änderungen in der Lösung des Problems bewirken.

Bemerkung zur Definition über Matrixnorm

Eine Matrixnorm $\|A\|$ bzw. $\|A^{-1}\|$ beschreibt wie "lang" Bildvektoren aus der Rand der Einheitskugel $\partial (B_{1}(0_{V})):=\{x\in \mathbb {R} ^{n}\,:\,\|x\|=1\}$ maximal werden können.

Inverse Matrix und Streckfaktoren

Betrachtet man Matrizen als lineare Abbildung liefert $A\cdot A^{-1}=E_{n}$ die Einheitsmatrix und eine Streckung $A\cdot x=y$ wird von $A^{-1}\cdot y=x$ wieder gestaucht. Die Definition der Konditionszahl betrachtet die maximalen Streckfaktoren $\|A\|$ bzw. $\|A^{-1}\|$ allerdings bzgl. des Arguments $x$ bzw. $y$ für die Matrizen $A$ bzw. $A^{-1}$ getrennt und nicht als Verkettung von Abbildungen.

Bemerkung - Satz zur Konditionszahl

Der folgende Satz über die Konditionzahl wird zeigen, wie die Konditionszahl von einem Quotienten aus minimalen und maximalen Streckfaktoren von $A$ auf dem Rand der Einheitskugel $\partial (B_{1}(0_{V})):=\{x\in \mathbb {R} ^{n}\,:\,\|x\|=1\}$ abhängt. Je mehr sich das Maximum und Minimum der Streckfaktoren voneinander unterscheiden, um so schlechter ("größer") ist die Konditionszahl. In dem Satz wird als Teilaussage nachgewiesen, dass folgender Zusammenhang gilt:

\|A^{-1}\|={\frac {1}{\displaystyle \min _{\|x\|=1}\|Ax\|}}

Bemerkung - Konditionszahl - Abhängigkeit von der Matrixnorm

Man beachte, dass die Konditionszahl einer Matrix im Allgemeinen von der gewählten Matrixnorm abhängig ist. Für diesen Zusammenhang gilt die folgende Aussage:

Satz - Konditionszahl

Sei $A\in \mathbb {R} ^{n\times n}$ eine reguläre Matrix und $\|\cdot \|:\mathbb {R} ^{n}\to \mathbb {R} _{o}^{+}$ eine Vektornorm. Für die Kondition von $A$ gilt dann bezüglich der durch $\|\cdot \|$ induzierten Matrixnorm

\operatorname {cond} (A)={\frac {\displaystyle \max _{\|x\|=1}\|Ax\|}{\displaystyle \min _{\|x\|=1}\|Ax\|}}.

Beweis 1 - Umformung Matrixnorm

Allgemein gilt für beliebige reguläre Matrizen $B\in \mathbb {R} ^{n\times n}$ über die Homogenität von Normen:

{\begin{array}{rcl}\|B\|&=&\displaystyle \max _{\|x\|=1}\|B\cdot x\|\\&=&\displaystyle \max _{x\in \mathbb {R} ^{n}\setminus \{0\}}\left\|B\cdot {\frac {x}{\|x\|}}\right\|\\&=&\displaystyle \max _{x\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|B\cdot x\|}{\|x\|}}\\\end{array}}

Im folgenden Beweisschritt wird diese Gleichheit 2x angewendet.

Beweis 2 - Konditionszahl

Die Beziehung ergibt sich aus der Definition der induzierten Matrixnorm

{\begin{array}{rcl}\|A^{-1}\|&=&\displaystyle \max _{y\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|A^{-1}y\|}{\|y\|}}\ \ {\stackrel {y=Ax}{=}}\ \max _{x\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|x\|}{\|Ax\|}}\\&=&\displaystyle \max _{x\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {1}{{\frac {1}{\|x\|}}\cdot \|Ax\|}}=\displaystyle \max _{\|x\|=1}{\frac {1}{\|Ax\|}}\\&=&\displaystyle \left(\min _{\|x\|=1}\|Ax\|\right)^{-1}\\\end{array}}

Durch Einsetzen in Definition der Konditionszahl erhält man die Behauptung. q.e.d.

Bemerkung - Konditionszahl

Die Konditionszahl $\operatorname {cond} (A)$ einer regulären Matrix $A$ gibt also die Bandbreite an, um die sich die Vektorlänge eines Vektors $x$ bei Multiplikation mit $A$ ändern kann. Aus dem Satz zur Konditionszahl ergibt sich zudem über die Berechnung des Maximums im Zähler und des Minimums im Nenner folgende Eigenschaft:

\operatorname {cond} (I)=1,\quad \operatorname {cond} (A)\geq 1.

wobei $I$ die $n\times n$ -Einheitsmatrix (Identität) bezeichnet.

Aufgaben für Studierende

Zeigen Sie die folgenden Aussagen:

$\operatorname {cond} (I)=1$ , wobei $I\in \mathbb {R} ^{n\times n}$ die n-dimensionale Einheitsmatrix ist.
$\operatorname {cond} (A^{-1})=\operatorname {cond} (A).$
$\operatorname {cond} (A)\geq 1.$ für eine Matrix $A\in GL(n,\mathbb {R} )\subset \mathbb {R} ^{n\times n}$ .

$GL(n,\mathbb {K} )$ bezeichnet die Menge der invertierbaren/regulären $n\times n$ -Matrizen über dem Körper $\mathbb {K} =\mathbb {R} ,\mathbb {C}$ .