Beweis

Es seien ${\displaystyle x,y\in {\mathcal {V}}}$. Dann gilt

${\displaystyle \|x\|=\|x-y+y\|\leq \|x-y\|+\|y\|}$

und somit

(2.1) ${\displaystyle \|x\|-\|y\|\leq \|x-y\|}$

Das Vertauschen von ${\displaystyle x}$ und ${\displaystyle y}$ in (2.1) liefert

(2.2) ${\displaystyle \|y\|-\|x\|\leq \|x-y\|}$

Die Ungleichungen (2.1) und (2.2) zusammen liefern die Behauptung.

q.e.d.

Einen Vektorraum ${\displaystyle {\mathcal {V}}}$, auf dem eine Norm ${\displaystyle \|\cdot \|}$ definiert ist, bezeichnet man als einen normierten Vektorraum. Man kennzeichnet ihn auch durch ${\displaystyle ({\mathcal {V}},\|\cdot \|)}$.

Beispiel 2.5

Es sei ${\displaystyle x\in \mathbb {K} ^{n}}$. Beispiele für Vektornomen sind

(1) ${\displaystyle \|x\|_{2}:=\left(\sum _{j=1}^{n}|x_{j}|^{2}\right)^{1/2}}$ (Euklidische oder ${\displaystyle l_{2}}$-Norm),

(2) ${\displaystyle \|x\|_{1}:=\sum _{j=1}^{n}|x_{j}|}$ (Summen- oder ${\displaystyle l_{1}}$-Norm),

(3) ${\displaystyle \|x\|_{\infty }:=\max _{j=1,\ldots ,n}|x_{j}|}$ (Maximum- oder ${\displaystyle l_{\infty }}$-Norm).

Der Beweis dafür, dass die Maximum- und Summennormen tatsächlich die Normeigenschaften erfüllen, ist elementar und wird hier nicht vorgeführt. Für die Euklidische Norm folgt die Dreiecksungleichung mit der Cauchy-Schwarzschen Ungleichung. Und zwar schließt man mit

${\displaystyle \|x\|_{2}^{2}=\sum _{j=1}^{n}|x_{j}|^{2}=\sum _{j=1}^{n}{\overline {x}}_{j}x_{j}={\overline {x}}^{T}x=x^{H}x}$

für ${\displaystyle x^{H}:={\overline {x}}^{T}}$, dass

${\displaystyle \|x+y\|_{2}^{2}=(x+y)^{H}(x+y)=\underbrace {x^{H}x} _{=\|x\|_{2}^{2}}+\underbrace {2\operatorname {Re} (x^{H}y)} _{\leq 2\|x\|_{2}\|y\|_{2}}+\underbrace {y^{H}y} _{=\|y\|_{2}^{2}}\leq (\|x\|_{2}+\|y\|_{2})^{2}}$

für alle ${\displaystyle x,y\in \mathbb {K} ^{n}}$ gilt, wobei ${\displaystyle \operatorname {Re} (x)}$ den Realteil von ${\displaystyle x}$ bezeichnet. Allgemeiner ist, wie man zeigen kann, für jedes ${\displaystyle 1\leq p<\infty }$ durch

(4) ${\displaystyle \|x\|_{p}:=\left(\sum _{j=1}^{n}|x_{j}|^{p}\right)^{1/p}}$ (${\displaystyle l_{p}}$-Norm)

eine Norm definiert, und es gilt

${\displaystyle \lim _{p\to \infty }\|x\|_{p}=\|x\|_{\infty }.}$

Man kann zeigen, dass je zwei paarweise verschiedene, auf einem endlich-dimensionalen Vektorraum ${\displaystyle {\mathcal {V}}}$ definierte Normen ${\displaystyle \|\cdot \|_{a}}$ und ${\displaystyle \|\cdot \|_{b}}$ äquivalent sind, d. h., dass es Konstanten ${\displaystyle c_{1},c_{2}>0}$ gibt, so dass gilt:

${\displaystyle c_{1}\|x\|_{a}\leq \|x\|_{b}\leq c_{2}\|x\|_{a},\quad x\in {\mathcal {V}}.}$

Wie man leicht verifiziert, hat man speziell für die im Beispiel 2.5 genannten Normen auf ${\displaystyle {\mathcal {V}}:=\mathbb {K} ^{n}}$ die folgenden Abschätzungen:

(2.3) ${\displaystyle \|x\|_{\infty }\leq \|x\|_{2}\leq {\sqrt {n}}\|x\|_{\infty },\quad x\in \mathbb {K} ^{n},}$

${\displaystyle \|x\|_{\infty }\leq \|x\|_{1}\leq n\|x\|_{\infty },\quad x\in \mathbb {K} ^{n},}$

${\displaystyle \|x\|_{2}\leq \|x\|_{1}\leq {\sqrt {n}}\|x\|_{2},\quad x\in \mathbb {K} ^{n}.}$

Die (scharfen) Abschätzungen in den ersten beiden Zeilen von (2.3) sind dabei leicht einzusehen. Die erste Abschätzung in der dritten Zeile folgt aus

${\displaystyle \sum _{j=1}^{n}|x_{j}|^{2}\leq \left(\sum _{j=1}^{n}|x_{j}|\right)^{2},}$

die zweite mit der Cauchy-Schwarzschen Ungleichung aus

${\displaystyle \sum _{j=1}^{n}1\cdot |x_{j}|\leq \|e\|_{2}\|x\|_{2}={\sqrt {n}}\|x\|_{2},}$

wobei ${\displaystyle e\in \mathbb {K} ^{n}}$ der Vektor mit den Komponenten ${\displaystyle e_{j}:=1}$ ist. Für große ${\displaystyle n\in \mathbb {N} }$ sind allerdings die jeweils zweiten Abschätzungen in (2.3) aufgrund der Größe der auftretenden Konstanten numerisch bedeutungslos.

Beispiel 2.6

Die folgenden Normen sind Matrixnormen für Matrizen ${\displaystyle A:=(a_{kj})\in \mathbb {K} ^{n\times n}}$:

(1) ${\displaystyle \|A\|:=\left(\sum _{j,k=1}^{n}|a_{kj}|^{2}\right)^{1/2}}$ (Frobenius-Norm),

(2) ${\displaystyle \|A\|:=\max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|}$ (Zeilensummennorm),

(3) ${\displaystyle \|A\|:=\max _{j=1,\ldots ,n}\sum _{k=1}^{n}|a_{kj}|}$ (Spaltensummennorm).

Der Beweis dafür, dass die Zeilen- und Spaltensummennorm tatsächlich die Normeigenschaften erfüllen, ist elementar. Jede Matrix ${\displaystyle A\in \mathbb {K} ^{n\times n}}$ lässt sich als Vektor der Länge ${\displaystyle n^{2}}$ auffassen und die Frobenius-Norm fällt dann mit der Euklidischen Vektornorm zusammen. Somit genügt die Frobenius-Norm auch den Normeigenschaften.

Beweis

Es seien ${\displaystyle \|\cdot \|:\mathbb {K} ^{n}\to \mathbb {R} _{+}}$ die Vektornorm und ${\displaystyle \|\cdot \|:\mathbb {K} ^{n\times n}\to \mathbb {R} _{+}}$ die induzierte Matrixnorm. Die Normeigenschaften der induzierten Matrixnorm sind leicht nachzuprüfen. Ihre Verträglichkeit mit der Vektornorm folgt aus

${\displaystyle \|Ax\|={\frac {\|Ax\|}{\|x\|}}\|x\|\leq \left(\max _{x\in \mathbb {K} ^{n}\setminus \{0\}}{\frac {\|Ax\|}{\|x\|}}\right)\|x\|=\|A\|\|x\|}$

für ${\displaystyle x\neq 0}$. Weiter gilt für ${\displaystyle A,B\in \mathbb {K} ^{n\times n}}$ und ${\displaystyle x\in \mathbb {K} ^{n}}$ mit ${\displaystyle Bx\neq 0}$

${\displaystyle \|ABx\|={\frac {\|A(Bx)\|}{\|Bx\|}}{\frac {\|Bx\|}{\|x\|}}\leq \|A\|\|B\|.}$

Im Fall ${\displaystyle x\neq 0}$ und ${\displaystyle Bx=0}$ hat man sicher auch

${\displaystyle 0={\frac {\|ABx\|}{\|x\|}}\leq \|A\|\|B\|.}$

Somit folgt auch die Submultiplikativität der induzierten Matrixnorm.

q.e.d.

Beweis.

Sei ${\displaystyle x\in \mathbb {C} ^{n}\setminus \{0\}}$ Eigenvektor zum Eigenwert ${\displaystyle \lambda \in \mathbb {C} }$ einer Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$, d. h.

${\displaystyle Ax=\lambda x.}$

Mit der zugehörigen Vektornorm ${\displaystyle \|\cdot \|:\mathbb {C} ^{n}\to \mathbb {R} _{+}}$ gilt dann

${\displaystyle \|A\|\geq {\frac {\|Ax\|}{\|x\|}}={\frac {|\lambda |\|x\|}{\|x\|}}=|\lambda |}$

Daraus folgt die Ungleichung (2.4).

q.e.d.

Der folgende Satz besagt, dass die durch die Vektornormen ${\displaystyle \|\cdot \|_{\infty }}$ und ${\displaystyle \|\cdot \|_{1}}$ induzierten Matrixnormen ${\displaystyle \|A\|_{\infty }}$ bzw. ${\displaystyle \|A\|_{1}}$ gerade die in Beispiel 2.6 eingeführte Zeilensummen- und Spaltensummennorm sind.

Beweis.

Wir weisen zunächst die Behauptung für die Zeilensummennorm nach. Für ${\displaystyle x\in \mathbb {K} ^{n}}$ gilt

${\displaystyle \|Ax\|_{\infty }=max_{k=1,\ldots ,n}\left|\sum _{j=1}^{n}a_{kj}x_{j}\right|\leq \max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}||x_{j}|\leq \left(\max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|\right)\|x\|_{\infty }}$

und somit

${\displaystyle {\frac {\|Ax\|_{\infty }}{\|x\|_{\infty }}}\leq \max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|,}$

woraus

${\displaystyle \|A\|_{\infty }\leq \max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|}$

folgt. Zum Beweis der umgekehrten Abschätzung sei ${\displaystyle k\in \{1,\ldots ,n\}}$ beliebig, aber fest gewählt. Für ${\displaystyle x:=(x_{j})\in \mathbb {K} ^{n}}$ mit

${\displaystyle x_{j}:={\begin{cases}|a_{kj}|/a_{kj},&{\text{falls }}a_{kj}\neq 0\\1,&{\text{sonst}}\end{cases}}}$

gilt dann ${\displaystyle \|x\|_{\infty }=1}$. Somit hat man

(2.5) ${\displaystyle \|A\|_{\infty }=\max _{\|y\|_{\infty }=1}\|Ay\|_{\infty }\geq \|Ax\|_{\infty }\geq \left|\sum _{j=1}^{n}a_{kj}x_{j}\right|=\sum _{j=1}^{n}|a_{kj}|.}$

Da ${\displaystyle k}$ beliebig gewählt war, folgt die behauptete Darstellung für ${\displaystyle \|A\|_{\infty }}$.

Nun gilt weiter für ${\displaystyle x\in \mathbb {K} ^{n}}$

${\displaystyle \|Ax\|_{1}=\sum _{k=1}^{n}\left|\sum _{j=1}^{n}a_{kj}x_{j}\right|\leq \sum _{k=1}^{n}\sum _{j=1}^{n}|a_{kj}||x_{j}|=\sum _{j=1}^{n}\left(\sum _{k=1}^{n}|a_{kj}|\right)|x_{j}|}$

${\displaystyle \leq \left(\max _{j=1,\ldots ,n}\sum _{k=1}^{n}|a_{kj}|\right)\sum _{j=1}^{n}|x_{j}|=\left(\max _{j=1,\ldots ,n}\sum _{k=1}^{n}|a_{kj}|\right)\|x\|_{1}.}$

Zum Beweis der umgekehrten Aussage sei ${\displaystyle \ell \in \{1,\ldots ,n\}}$ beliebig, aber fest gewählt. Mit dem Einheitsvektor ${\displaystyle e^{\ell }:=(\delta _{k\ell })\in \mathbb {K} ^{n}}$ erhält man dann

${\displaystyle \|A\|_{1}=\max _{\|y\|_{1}=1}\|Ay\|_{1}\geq \|Ae^{\ell }\|_{1}=\sum _{k=1}^{n}\left|\sum _{j=1}^{n}a_{kj}\delta _{j\ell }\right|=\sum _{k=1}^{n}|a_{k\ell }.}$

Damit folgt auch die behauptete Darstellung von ${\displaystyle \|A\|_{1}}$.

q.e.d.

Im Folgenden beschränken wir uns auf den reellen Fall ${\displaystyle \mathbb {K} :=\mathbb {R} }$. Als unmittelbare Konsequenz aus Satz 2.12 erhält man

Beweis.

Es ist ${\displaystyle A^{T}A\in \mathbb {R} ^{n\times n}}$ eine symmetrische und wegen

(2.6) ${\displaystyle x^{T}A^{T}Ax=(Ax)^{T}(Ax)=\|Ax\|_{2}^{2}\geq 0,\quad x\in \mathbb {R} ^{n}}$

positiv semi-definite Matrix. Somit besitzt ${\displaystyle A^{T}A}$ Eigenwerte ${\displaystyle \lambda _{k}\geq 0}$ ${\displaystyle (k=1,\ldots ,n)}$ und gibt es zu ${\displaystyle A^{T}A}$ ein System ${\displaystyle u_{1},\ldots ,u_{n}\in \mathbb {R} ^{n}}$ von orthonormalen Eigenvektoren, d. h. es ist

${\displaystyle A^{T}Au_{k}=\lambda _{k}u_{k},\quad k=1,\ldots ,n}$

und ${\displaystyle u_{k}^{T}u_{l}=\delta _{lk}}$. Für ${\displaystyle x\in \mathbb {R} ^{n}}$ gilt daher mit der Darstellung ${\displaystyle x=\sum _{k=1}^{n}c_{k}u_{k}}$

${\displaystyle \|Ax\|_{2}^{2}=x^{T}A^{T}Ax=\left(\sum _{k=1}^{n}c_{k}u_{k}\right)^{T}\left(\sum _{j=1}^{n}c_{j}(A^{T}A)u_{j}\right)}$

${\displaystyle =\left(\sum _{k=1}^{n}c_{k}u_{k}\right)^{T}\left(\sum _{j=1}^{n}\lambda _{j}c_{j}u_{j}\right)=\sum _{k=1}^{n}\lambda _{k}c_{k}^{2}}$

${\displaystyle \leq \left(\max _{k=1,\ldots ,n}\lambda _{k}\right)\cdot \sum _{k=1}^{n}c_{k}^{2}=\varrho (A^{T}A)\|x\|_{2}^{2}.}$

Gleichheit wird in dieser Abschätzung für einen Eigenvektor ${\displaystyle {\tilde {x}}\in \mathbb {R} ^{n}}$ zu einem maximalen Eigenwert ${\displaystyle \lambda _{\max }}$ von ${\displaystyle A^{T}A}$ angenommen, denn

${\displaystyle \|A{\tilde {x}}\|_{2}^{2}={\tilde {x}}^{T}A^{T}A{\tilde {x}}=\lambda _{\max }{\tilde {x}}^{T}{\tilde {x}}=\lambda _{\max }\|{\tilde {x}}\|_{2}^{2}.}$

Damit ist alles bewiesen.

q.e.d.

Die Matrixnorm ${\displaystyle \|A\|_{2}}$ bezeichnet man auch als Spektralnorm. Dieser Name begründet sich durch den letzten Satz bzw. die in folgendem Satz angegebene Identität für reelle, symmetrische Matrizen.

Beweis.

Wegen ${\displaystyle \sigma (A^{2})=\{\lambda ^{2}|\lambda \in \sigma (A)\}}$ gilt ${\displaystyle \varrho (A^{2})=[\varrho (A)]^{2}}$ und daher aufgrund der Symmetrie von ${\displaystyle A}$

${\displaystyle \|A\|_{2}={\sqrt {\varrho (A^{T}A)}}={\sqrt {\varrho (A^{2})}}=\varrho (A).}$

Der zweite Teil der Behauptung folgt nun mit (2.4).

q.e.d.

Beispiel 2.16

(1) Die symmetrische Matrix

${\displaystyle A={\begin{pmatrix}1&3\\3&2\end{pmatrix}}}$

besitzt die Eigenwerte ${\displaystyle \lambda _{1,2}=(3\pm {\sqrt {37}})/2}$, so dass folgt:

${\displaystyle \|A\|_{2}=(3+{\sqrt {37}})/2\approx 4.541.}$

Weiter hat man ${\displaystyle \|A\|_{\infty }=\|A\|_{1}=5}$. Damit zeigt dieses Beispiel, dass sich die in (2.3) stehenden Beziehungen ${\displaystyle \|x\|_{\infty }\leq \|x\|_{2}\leq \|x\|_{1},x\in \mathbb {R} ^{n}}$ nicht auf die entsprechenden induzierten Matrixnormen übertragen lassen.

(2) Für die nicht symmetrische Matrix ${\displaystyle A\in \mathbb {R} ^{2\times 2}}$, definiert durch

${\displaystyle A={\begin{pmatrix}0&1\\0&1\end{pmatrix}}\Rightarrow A^{T}A={\begin{pmatrix}0&0\\0&2\end{pmatrix}},}$

gilt offenbar ${\displaystyle \varrho (A)=1=\|A\|_{\infty },\|A\|_{2}={\sqrt {2}}}$ und ${\displaystyle \|A\|_{1}=2}$. Letzteres zeigt, dass auf die Voraussetzung „${\displaystyle A=A^{T}}$“ in Satz 2.15 nicht verzichtet werden kann.

Der folgende Satz liefert noch Abschätzungen für die Spektralnorm beliebiger quadratischer Matrizen.

Beweis.

Mit Satz 2.14 und Korollar 2.13 hat man

${\displaystyle \|A\|_{2}={\sqrt {\varrho (A^{T}A)}}={\sqrt {\|A^{T}A\|_{2}}}\leq {\sqrt {\|A^{T}A\|_{\infty }}}\leq {\sqrt {\|A^{T}\|_{\infty }\|A\|_{\infty }}}={\sqrt {\|A\|_{1}\|A\|_{\infty }}}}$

Die zweite Abschätzung in (2.9) erhält manmit der Cauchy-Schwarz-Ungleichung:

${\displaystyle \|Ax\|_{2}=\left(\sum _{k=1}^{n}\left|\sum _{j=1}^{n}a_{kj}x_{j}\right|^{2}\right)^{1/2}\leq \left[\sum _{k=1}^{n}\left(\sum _{j=1}^{n}|a_{kj}|^{2}\right)\left(\sum _{j=1}^{n}|x_{j}|^{2}\right)\right]^{1/2}=\|A\|_{F}\|x\|_{2}}$

für alle ${\displaystyle x\in \mathbb {R} ^{n}}$.

q.e.d.

Beweis.

Die Beziehung (2.10) ergibt sich aus

${\displaystyle \|A^{-1}\|=\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\|}}=\max _{\|x\|=1}{\frac {1}{\|Ax\|}}=\left(\min _{\|x\|=1}\|Ax\|\right)^{-1}.}$

q.e.d.

Die Konditionszahl ${\displaystyle \operatorname {cond} (A)}$ gibt also die Bandbreite an, um die sich die Vektorlänge eines Vektors ${\displaystyle x}$ bei Multiplikation mit ${\displaystyle A}$ ändern kann. Aus (2.10) ergibt sich zudem

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

Beweis.

Die umgekehrte Dreiecksungleichung liefert für ${\displaystyle x\in \mathbb {R} ^{n}}$

(2.11) ${\displaystyle \|(I+F)x\|=\|x+Fx\|\geq \|x\|-\|Fx\|\geq \|x\|-\|F\|\|x\|=(1-\|F\|)\|x\|.}$

Also ist für ${\displaystyle x\neq 0}$ auch ${\displaystyle (I+F)x\neq 0}$, was die Invertierbarkeit von ${\displaystyle I+F}$ impliziert. Die Setzung ${\displaystyle y:=(I+F)x}$ in (2.11) liefert weiter

${\displaystyle \|y\|\geq (1-\|F\|)\|(I+F)^{-1}y\|,\quad y\in \mathbb {R} ^{n}}$

und damit

${\displaystyle {\frac {\|(I+F)^{-1}y\|}{\|y\|}}\leq {\frac {1}{1-\|F\|}},\quad y\in \mathbb {R} ^{n},}$

was den Beweis des Lemmas komplettiert.

q.e.d.

Beweis.

Es ist

${\displaystyle \|A^{-1}\Delta A\|\leq \|A^{-1}\|\|\Delta A\|<1}$

und nach Lemma 2.20 somit die Matrix ${\displaystyle A+\Delta A=A(I+A^{-1}\Delta A)}$ regulär. Mit der Darstellung ${\displaystyle (A+\Delta A)^{-1}=(I+A^{-1}\Delta A)^{-1}A^{-1}}$ erhält man ferner mit Lemma 2.20

${\displaystyle \|(A+\Delta A)^{-1}\|\leq {\frac {\|A^{-1}\|}{1-\|A^{-1}\Delta A\|}}\leq {\frac {\|A^{-1}\|}{1-\|A^{-1}\|\|\Delta A\|}}.}$

Mit der Darstellung

${\displaystyle (A+\Delta A)^{-1}-A^{-1}=(A+\Delta A)^{-1}[I-(A+\Delta A)A^{-1}]=-(A+\Delta A)^{-1}\Delta AA^{-1}}$

und der ersten Ungleichung des Korollars folgt für ${\displaystyle \|\Delta A\|\leq 1/(2\|A^{-1}\|)}$

${\displaystyle \|(A+\Delta A)^{-1}-A^{-1}\|=\|(A+\Delta A)^{-1}\|\|A^{-1}\|\|\Delta A\|\leq {\frac {\|A^{-1}\|}{1-{\frac {1}{2}}}}\|A^{-1}\|\|\Delta A\|=2\|A^{-1}\|^{2}\|\Delta A\|.}$

q.e.d.

Beweis.

Aus (2.12) folgt unmittelbar ${\displaystyle A\Delta x=\Delta b}$ bzw. ${\displaystyle \Delta x=A^{-1}\Delta b}$ und damit (2.13). Aus (2.13) wiederum ergibt sich

${\displaystyle {\frac {\|\Delta x\|}{\|x\|}}={\frac {\|A^{-1}\Delta b\|}{\|x\|}}{\stackrel {Ax=b}{\leq }}{\frac {\|A^{-1}\|\|\Delta b\|}{\|x\|}}{\frac {\|Ax\|}{\|b\|}}\leq \operatorname {cond} (A){\frac {\|\Delta b\|}{\|b\|}}.}$

q.e.d.

Wenn die Kondition einer Matrix ${\displaystyle A}$ groß, also ${\displaystyle \operatorname {cond} (A)\gg 1}$ ist, ist auch die obere Schranke für den relativen Fehler in der Lösung der fehlerbehafteten Version des linearen Gleichungssystems ${\displaystyle Ax=b}$ groß. In einem solchen Fall spricht man von einem schlecht konditionierten Gleichungssystem. Wir geben ein Beispiel für eine Matrix mit großer Kondition.

Beispiel 2.23

Sei ${\displaystyle \varepsilon \in (0,1)}$ sehr klein und ${\displaystyle A}$ gegeben durch

${\displaystyle A:={\begin{pmatrix}1&0\\0&\varepsilon \end{pmatrix}}\Rightarrow A^{-1}={\begin{pmatrix}1&0\\0&1/\varepsilon \end{pmatrix}}}$

Dann ist ${\displaystyle \|A\|_{2}=1}$ und ${\displaystyle \|A^{-1}\|_{2}=1/\varepsilon }$ und somit die Kondition

${\displaystyle \operatorname {cond} _{2}(A):=\|A\|_{2}\|A^{-1}\|_{2}={\frac {1}{\varepsilon }}}$

sehr groß. Ein Gleichungssystem mit ${\displaystyle A}$ ist also ein schlecht konditioniertes Gleichungssystem.

Ähnliches gilt auch im Falle gestörter Matrizen.

Beweis.

Aus (2.15) folgt unmittelbar

${\displaystyle (A+\Delta A)\Delta x=\Delta b-\Delta Ax.}$

Korollar 2.21 liefert nun die Regularität der Matrix ${\displaystyle A+\Delta A}$ sowie die Abschätzung

${\displaystyle \|\Delta x\|\leq {\frac {\|A^{-1}\|}{1-\|A^{-1}\|\|\Delta A\|}}(\|\Delta b\|+\|\Delta A\|\|x\|)}$

Division durch ${\displaystyle \|x\|}$ und Erweiterung der rechten Seite mit ${\displaystyle \|A\|}$ liefert

${\displaystyle {\frac {\|\Delta x\|}{\|x\|}}\leq {\frac {\|A\|\|A^{-1}\|}{1-\|A^{-1}\|\|\Delta A\|}}\left({\frac {\|\Delta A\|}{\|A\|}}+{\frac {\|\Delta b\|}{\|A\|\|x\|}}\right).}$

Wegen ${\displaystyle \|b\|\leq \|A\|\|x\|}$ folgt die Behauptung.

q.e.d.

Der Nenner in der Konstanten auf der rechten Seite in (2.16) wird manchmal auch in der Form ${\displaystyle 1-\|A^{-1}\|\|\Delta A\|}$ geschrieben.