Aus Wikiversity

In diesem Kapitel werden die Begriffe einer Vektor- und Matrixnorm bereit gestellt und wird in Vorbereitung auf die numerische Lösung linearer Gleichungssysteme der Einfluss von Störungen der Matrix $A \in \mathbb R^{n \times n}$ und des Vektors $b \in \mathbb R^n$ auf die Lösung des linearen Gleichungssystems $A x = b$ untersucht. Im Hinblick auf weitere Anwendungen werden wir dabei zunächst Vektoren aus $\mathbb K^n$ und Matrizen aus $\mathbb K^{n \times n}$ zulassen, wobei $\mathbb K := \mathbb R$ oder $\mathbb K := \mathbb C$ ist.

[Bearbeiten] 2.1 Normen

Im Folgenden sei $\mathcal V$ ein beliebiger Vektorraum über $\mathbb K$ .

[Bearbeiten] Definition 2.1

Eine Abbildung $\|\cdot\|: \mathcal V \to \mathbb R_+$ heißt Norm, falls folgendes gilt:

(i) $\|x\| = 0 \Leftrightarrow x = 0, \quad x \in \mathcal V,$

(ii) $\|\alpha x\| = |\alpha| \|x\|, \quad x \in \mathcal V, \alpha \in \mathbb K$ (Positive Homogenität),

(iii) $\|x + y\| \le \|x\| + \|y\|, \quad x, y \in \mathcal V$ (Dreiecksungleichung).

Eine Norm $\|\cdot\|: \mathbb K^n \to \mathbb R_+$ wird auch Vektornorm und entsprechend eine Norm $\|\cdot\|: \mathbb K^{n \times n} \to \mathbb R_+$ auch Matrixnorm genannt.

[Bearbeiten] Lemma 2.2

Für eine Norm $\|\cdot\|: \mathcal V \to \mathbb R_+$ gilt die umgekehrte Dreiecksungleichung

$|\|x\| - \|y\|| \le \|x - y\|, \quad x, y \in \mathcal V.$

[Bearbeiten] Beweis

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

$\|x\| = \|x - y + y\| \le \|x - y\| + \|y\|$

und somit

(2.1) $\|x\| - \|y\| \le \|x - y\|$

Das Vertauschen von $x$ und $y$ in (2.1) liefert

(2.2) $\|y\| - \|x\| \le \|x - y\|$

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

q.e.d.

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

[Bearbeiten] Definition 2.3

Es sei $(\mathcal V, \|\cdot\|)$ ein normierter Vektorraum. Eine Folge $(x n)$ von Elementen $x_n \in \mathcal V$ konvergiert gegen $x \in \mathcal V$ , kurz

$\lim_{n \to \infty} x_n = x,$

wenn gilt:

$\lim_{n \to \infty} \|x_n - x\| = 0.$

Unter Verwendung dieser Definition folgt sofort aus Lemma 2.2 das folgende Ergebnis.

[Bearbeiten] Korollar 2.4

Eine Norm $\|\cdot\|: \mathcal V \to \mathbb R_+$ ist stetig, d. h., es gilt

$x, x_n \in \mathcal V, \quad \lim_{n \to \infty} x_n = x \Rightarrow \lim_{n \to \infty} \|x_n\| = \|x\|.$

[Bearbeiten] Beispiel 2.5

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

(1) $\|x\|_2 := \left( \sum^n_{j=1} |x_j|^2 \right)^{1/2}$ (Euklidische oder

l 2

-Norm),

(2) $\|x\|_1 := \sum^n_{j=1} |x_j|$ (Summen- oder

l 1

-Norm),

(3) $\|x\|_\infty := \max_{j=1, \ldots, n} |x_j|$ (Maximum- oder $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

$\|x\|_2^2 = \sum^n_{j=1} |x_j|^2 = \sum^n_{j=1} \overline x_jx_j = \overline x^T x = x^Hx$

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

$\|x + y\|^2_2 = (x + y)^H (x + y) = \underbrace{x^Hx}_{=\|x\|^2_2} + \underbrace{2 \operatorname{Re} (x^Hy)}_{\le 2 \|x\|_2 \|y\|_2} + \underbrace{y^Hy}_{=\|y\|^2_2} \le (\|x\|_2 + \|y\|_2)^2$

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

(4) $\|x\|_p := \left( \sum^n_{j=1} |x_j|^p \right)^{1/p}$ (

l p

-Norm)

eine Norm definiert, und es gilt

$\lim_{p \to \infty} \|x\|_p = \|x\|_\infty.$

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

$c_1 \|x\|_a \le \|x\|_b \le 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 $\mathcal V := \mathbb K^n$ die folgenden Abschätzungen:

(2.3) $\|x\|_\infty \le \|x\|_2 \le \sqrt{n} \|x\|_\infty, \quad x \in \mathbb K^n,$

$\|x\|_\infty \le \|x\|_1 \le n \|x\|_\infty, \quad x \in \mathbb K^n,$

$\|x\|_2 \le \|x\|_1 \le \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

$\sum^n_{j=1} |x_j|^2 \le \left( \sum^n_{j=1} |x_j| \right)^2,$

die zweite mit der Cauchy-Schwarzschen Ungleichung aus

$\sum^n_{j=1} 1 \cdot |x_j| \le \|e\|_2 \|x\|_2 = \sqrt{n} \|x\|_2,$

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

[Bearbeiten] Beispiel 2.6

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

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

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

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

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

[Bearbeiten] Definition 2.7

Eine Matrixnorm $\|\cdot\|: \mathbb K^{n \times n} \to \mathbb R_+$ nennt man

(i) submultiplikativ, falls

$\|AB\| \le \|A\| \|B\|, \quad A, B \in \mathbb K^{n \times n},$

(ii) mit einer gegebenen Vektornorm $\|\cdot\|: \mathbb K^n \to \mathbb R_+$ verträglich, falls

$\|Ax\| \le \|A\| \|x\|, \quad A \in \mathbb K^{n \times n}, \quad x \in \mathbb K^n.$

[Bearbeiten] Definition 2.8

Sei $\|\cdot\|: \mathbb K^n \to \mathbb R_+$ eine Vektornorm. Dann heißt die durch

$\|A\| := \max_{x \in \mathbb K^n \setminus \{0\}} \frac{\|Ax\|}{\|x\|} = \max_{\|x\| = 1} \|Ax\|, A \in \mathbb K^{n \times n}$

definierte Norm die durch die Vektornorm $\|\cdot\|$ induzierte Matrixnorm.

Man beachte, dass wegen der Kompaktheit der Menge $\{x \in \mathbb K^n | \|x\| = 1\}$ und der Stetigkeit der Vektornorm das Maximum in der Definition von $\|A\|$ tatsächlich angenommen wird. Offenbar gilt $\|I\| = 1$ .

[Bearbeiten] Satz 2.9

Die durch eine Vektornorm induzierte Matrixnorm besitzt die in Definition 2.1 angegebenen Normeigenschaften. Ferner ist sie submultiplikativ und bezüglich der zugrunde liegenden Vektornorm verträglich.

[Bearbeiten] Beweis

Es seien $\|\cdot\|: \mathbb K^n \to \mathbb R_+$ die Vektornorm und $\|\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

$\|Ax\| = \frac{\|Ax\|}{\|x\|} \|x\| \le \left( \max_{x \in \mathbb K^n \setminus \{0\}} \frac{\|Ax\|}{\|x\|} \right) \|x\| = \|A\| \|x\|$

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

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

Im Fall $x \neq 0$ und $B x = 0$ hat man sicher auch

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

Somit folgt auch die Submultiplikativität der induzierten Matrixnorm.

q.e.d.

[Bearbeiten] 2.2 Spezielle Matrixnormen

Die wesentlichen Eigenschaften der durch Vektornormen induzierten Matrixnormen sind im Folgenden zusammengefasst.

[Bearbeiten] Definition 2.10

Für eine Matrix $B \in \mathbb K^{n \times n}$ nennt man

$\sigma(B) := \{\lambda \in \mathbb C | \lambda\ ist\ Eigenwert\ von\ B\}$

das Spektrum und

$\varrho(B) := \max \{|\lambda|| \lambda \in \sigma(B)\}$

den Spektralradius von $B$ .

[Bearbeiten] Satz 2.11

Sei $A \in \mathbb C^{n \times n}$ . Für die durch eine Vektornorm induzierte Matrixnorm $\|\cdot\|: \mathbb C^{n \times n} \to \mathbb R_+$ gilt

(2.4) $\|A\| \ge \varrho(A).$

[Bearbeiten] Beweis.

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

A x = λ x .

Mit der zugehörigen Vektornorm $\|\cdot\|: \mathbb C^n \to \mathbb R_+$ gilt dann

$\|A\| \ge \frac{\|Ax\|}{\|x\|} = \frac{|\lambda| \|x\|}{\|x\|} = |\lambda|$

Daraus folgt die Ungleichung (2.4).

q.e.d.

[Bearbeiten] Satz 2.12

Für $A := (a_{kj}) \in \mathbb K^{n \times n}$ und die durch die Vektornormen $\|\cdot\|_\infty$ und $\|\cdot\|_1$ induzierten Matrixnormen $\|A\|_\infty$ bzw. $\|A\|_1$ gilt

$\|A\|_\infty = \max_{k=1, \ldots, n} \sum^n_{j=1} |a_{kj}|$ (Zeilensummennorm),

$\|A\|_1 = \max_{j=1, \ldots, n} \sum^n_{k=1} |a_{kj}|$ (Spaltensummennorm).

[Bearbeiten] Beweis.

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

$\|Ax\|_\infty = max_{k=1, \ldots, n} \left| \sum^n_{j=1} a_{kj} x_j \right| \le \max_{k=1, \ldots, n} \sum^n_{j=1} |a_{kj}| |x_j| \le \left( \max_{k=1, \ldots, n} \sum^n_{j=1} |a_{kj}| \right) \|x\|_\infty$

und somit

$\frac{\|Ax\|_\infty}{\|x\|_\infty} \le \max_{k=1, \ldots, n} \sum^n_{j=1} |a_{kj}|,$

woraus

$\|A\|_\infty \le \max_{k=1, \ldots, n} \sum^n_{j=1} |a_{kj}|$

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

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

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

(2.5) $\|A\|_\infty = \max_{\|y\|_\infty=1} \|Ay\|_\infty \ge \|Ax\|_\infty \ge \left| \sum^n_{j=1} a_{kj}x_j \right| = \sum^n_{j=1} |a_{kj}|.$

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

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

$\|Ax\|_1 = \sum^n_{k=1} \left| \sum^n_{j=1} a_{kj} x_j \right| \le \sum^n_{k=1} \sum^n_{j=1} |a_{kj}| |x_j| = \sum^n_{j=1} \left( \sum^n_{k=1} |a_{kj}| \right) |x_j|$

$\le \left( \max_{j=1, \ldots, n} \sum^n_{k=1} |a_{kj}| \right) \sum^n_{j=1} |x_j| = \left( \max_{j=1, \ldots, n} \sum^n_{k=1} |a_{kj}| \right) \|x\|_1.$

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

$\|A\|_1 = \max_{\|y\|_1=1} \|Ay\|_1 \ge \|Ae^\ell\|_1 = \sum^n_{k=1} \left| \sum^n_{j=1} a_{kj} \delta_{j\ell} \right| = \sum^n_{k=1} |a_{k\ell}.$

Damit folgt auch die behauptete Darstellung von $\|A\|_1$ .

q.e.d.

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

[Bearbeiten] Korollar 2.13

Für Matrizen $A \in \mathbb R^{n \times n}$ gilt

$\|A\|_\infty = \|A^T\|_1, \quad \|A\|_1 = \|A^T\|_\infty.$

Der nachstehende Satz liefert im Fall reeller Matrizen für die durch die Euklidische Vektornorm induzierte Matrixnorm eine spezielle Darstellung.

[Bearbeiten] Satz 2.14

Sei $A \in \mathbb R^{n \times n}$ . Für die durch die Euklidische Vektornorm $\|\cdot\|_2: \mathbb R^n \to \mathbb R_+$ induzierte Matrixnorm $\|\cdot\|_2: \mathbb R^{n \times n} \to \mathbb R_+$ gilt

$\|A\|_2 = \sqrt{\varrho(A^TA)}.$

[Bearbeiten] Beweis.

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

(2.6) $x^TA^TAx = (Ax)^T (Ax) = \|Ax\|_2^2 \ge 0, \quad x \in \mathbb R^n$

positiv semi-definite Matrix. Somit besitzt $A T A$ Eigenwerte $\lambda_k \ge 0$ $(k = 1, \ldots, n)$ und gibt es zu $A T A$ ein System $u_1, \ldots, u_n \in \mathbb R^n$ von orthonormalen Eigenvektoren, d. h. es ist

$A^TAu_k = \lambda_k u_k, \quad k = 1, \ldots, n$

und $u^T_k u_l = \delta_{lk}$ . Für $x \in \mathbb R^n$ gilt daher mit der Darstellung $x = \sum^n_{k=1} c_ku_k$

$\|Ax\|^2_2 = x^TA^TAx = \left( \sum^n_{k=1} c_k u_k \right)^T \left( \sum^n_{j=1} c_j (A^TA) u_j \right)$

$= \left( \sum^n_{k=1} c_k u_k \right)^T \left( \sum^n_{j=1} \lambda_j c_j u_j \right) = \sum^n_{k=1} \lambda_k c_k^2$

$\le \left( \max_{k=1, \ldots, n} \lambda_k \right) \cdot \sum^n_{k=1} c_k^2 = \varrho(A^TA) \|x\|^2_2.$

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

$\|A\tilde x\|_2^2 = \tilde x^TA^TA\tilde x = \lambda_\max \tilde x^T \tilde x = \lambda_\max \|\tilde x\|^2_2.$

Damit ist alles bewiesen.

q.e.d.

Die Matrixnorm $\|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.

[Bearbeiten] Satz 2.15

Sei $A \in \mathbb R^{n \times n}$ eine symmetrische Matrix, d. h. $A = A T$ . Dann gilt

(2.7) $\|A\|_2 = \varrho(A).$

Für jede andere durch eine Vektornorm induzierte Matrixnorm $\|\cdot\|: \mathbb R^{n \times n} \to \mathbb R_+$ gilt

(2.8) $\|A\|_2 \le \|A\|.$

[Bearbeiten] Beweis.

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

$\|A\|_2 = \sqrt{\varrho(A^TA)} = \sqrt{\varrho(A^2)} = \varrho(A).$

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

q.e.d.

[Bearbeiten] Beispiel 2.16

(1) Die symmetrische Matrix

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

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

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

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

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

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

gilt offenbar $\varrho(A) = 1 = \|A\|_\infty, \|A\|_2 = \sqrt{2}$ und $\|A\|_1 = 2$ . Letzteres zeigt, dass auf die Voraussetzung „ $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.

[Bearbeiten] Satz 2.17

Für jede Matrix $A \in \mathbb R^{n \times n}$ gilt

(2.9) $\|A\|_2 \le \sqrt{\|A\|_\infty \|A\|_1}, \quad \|A\|_2 \le \|A\|_F,$

wobei $\|A\|_F$ die in Beispiel 2.6 (a) definierte Frobenius-Norm sei.

[Bearbeiten] Beweis.

Mit Satz 2.14 und Korollar 2.13 hat man

$\|A\|_2 = \sqrt{\varrho(A^TA)} = \sqrt{\|A^TA\|_2} \le \sqrt{\|A^TA\|_\infty} \le \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:

$\|Ax\|_2 = \left( \sum^n_{k=1} \left| \sum^n_{j=1} a_{kj} x_j \right|^2 \right)^{1/2} \le \left[ \sum^n_{k=1} \left( \sum^n_{j=1} |a_{kj}|^2 \right) \left( \sum^n_{j=1} |x_j|^2 \right) \right]^{1/2} = \|A\|_F \|x\|_2$

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

q.e.d.

[Bearbeiten] 2.3 Die Konditionszahl einer Matrix

[Bearbeiten] Definition 2.18

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\| \|A^{-1}\|$

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

Man beachte, dass die Konditionszahl einer Matrix im Allgemeinen von der gewählten Matrixnorm abhängig ist. Es gilt:

[Bearbeiten] Satz 2.19

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

(2.10) $\operatorname{cond}(A) = \left( \max_{\|x\|=1} \|Ax\| \right) / \left( \min_{\|x\|=1} \|Ax\| \right).$

[Bearbeiten] Beweis.

Die Beziehung (2.10) ergibt sich aus

$\|A^{-1}\| = \max_{y \in \mathbb R^n \setminus \{0\}} \frac{\|A^{-1} y\|}{\|y\|} \stackrel{y=Ax}{=} \max_{y \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 $\operatorname{cond}(A)$ gibt also die Bandbreite an, um die sich die Vektorlänge eines Vektors $x$ bei Multiplikation mit $A$ ändern kann. Aus (2.10) ergibt sich zudem

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

[Bearbeiten] 2.4 Störungsresultate für Matrizen

[Bearbeiten] Lemma 2.20

Sei $\|\cdot\|: \mathbb R^{n \times n} \to \mathbb R_+$ eine durch eine Vektornorm induzierte Matrixnorm und $F \in \mathbb R^{n \times n}$ eine Matrix mit $\|F\| < 1$ . Dann ist die Matrix $I + F$ regulär, und es gilt

$\|(I + F)^{-1}\| \le \frac{1}{1 - \|F\|}.$

[Bearbeiten] Beweis.

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

(2.11) $\|(I + F)x\| = \|x + Fx\| \ge \|x\| - \|Fx\| \ge \|x\| - \|F\| \|x\| = (1 - \|F\|) \|x\|.$

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

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

und damit

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

was den Beweis des Lemmas komplettiert.

q.e.d.

[Bearbeiten] Korollar 2.21

Sei $\|\cdot\|: \mathbb R^{n \times n} \to \mathbb R_+$ die durch eine Vektornorm induzierte Matrixnorm und $A \in \mathbb R^{n \times n}$ sei eine reguläre Matrix. Für jede Matrix $\Delta A \in \mathbb R^{n \times n}$ mit $\|\Delta A\| < 1/\|A^{-1}\|$ ist dann die Matrix $A + Δ A$ regulär, und es gelten die Abschätzungen

$\|(A + \Delta A)^{-1}\| \le \frac{\|A^{-1}\|}{1 - \|A^{-1}\| \|\Delta A\|},$

$\|(A + \Delta A)^{-1} - A^{-1}\| \le 2\|A^{-1}\|^2 \|\Delta A\|$ , falls $\|\Delta A\| \le 1/(2A^{-1})$ .

[Bearbeiten] Beweis.

Es ist

$\|A^{-1} \Delta A\| \le \|A^{-1}\| \|\Delta A\| < 1$

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

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

Mit der Darstellung

(A + Δ A) - 1 - A - 1 = (A + Δ A) - 1 [I - (A + Δ A) A - 1] = - (A + Δ A) - 1 Δ A A - 1

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

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

q.e.d.

[Bearbeiten] 2.5 Fehlerabschätzungen für gestörte Gleichungssysteme

Wir beweisen nun als nächstes ein Resultat, welches den Einfluss einer Störung der rechten Seite eines Gleichungssystems auf seine Lösung zeigt.

[Bearbeiten] Satz 2.22

Mit $\|\cdot\|$ seien gleichzeitig eine Vektornorm auf $\mathbb R^n$ und die durch sie induzierte Matrixnorm auf $\mathbb R^{n \times n}$ bezeichnet. Weiter sei $A \in \mathbb R^{n \times n}$ eine reguläre Matrix und $b, x \in \mathbb R^n$ und $\Delta b, \Delta x \in \mathbb R^n$ seien Vektoren mit

(2.12) $Ax = b, \quad A(x + \Delta x) = b + \Delta b.$

Dann gelten für den absoluten bzw. den relativen Fehler von $x + Δ x$ bezüglich $x$ die Abschätzungen

(2.13) $\|(x + \Delta x) - x\| = \|\Delta x\| \le \|A^{-1} \|\Delta b\|,$

(2.14) $\frac{\|(x + \Delta x) - \|x\|}{\|x\|} = \frac{\|\Delta x\|}{\|x\|} \le \operatorname{cond}(A) \frac{\|\Delta b\|}{\|b\|}.$

[Bearbeiten] Beweis.

Aus (2.12) folgt unmittelbar $A Δ x = Δ b$ bzw. $Δ x = A - 1 Δ b$ und damit (2.13). Aus (2.13) wiederum ergibt sich

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

q.e.d.

Wenn die Kondition einer Matrix $A$ groß, also $\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 $A x = 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.

[Bearbeiten] Beispiel 2.23

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

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

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

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

sehr groß. Ein Gleichungssystem mit $A$ ist also ein schlecht konditioniertes Gleichungssystem.

Ähnliches gilt auch im Falle gestörter Matrizen.

[Bearbeiten] Satz 2.24

Mit $\|\cdot\|$ seien gleichzeitig eine Vektornorm auf $\mathbb R^n$ und die durch sie induzierte Matrixnorm auf $\mathbb R^{n \times n}$ bezeichnet. Weiter sei $A \in \mathbb R^{n \times n}$ eine reguläre Matrix und $\Delta A \in \mathbb R^{n \times n}$ sei eine Matrix mit $\|\Delta A\| < 1/\|A^{-1}\|$ . Dann gilt für beliebige Vektoren $b, x \in \mathbb R^n$ und $\Delta b, \Delta x \in \mathbb R^n$ mit

(2.15) $Ax = b, \quad (A + \Delta A) (x + \Delta x) = b + \Delta b$

die Abschätzung

(2.16) $\frac{\|\Delta x\|}{\|x\|} \le \frac{\operatorname{cond}(A)}{1 - \operatorname{cond}(A) \frac{\|\Delta A\|}{\|A\|}} \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right).$

[Bearbeiten] Beweis.

Aus (2.15) folgt unmittelbar

(A + Δ A)Δ x = Δ b - Δ A x .

Korollar 2.21 liefert nun die Regularität der Matrix $A + Δ A$ sowie die Abschätzung

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

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

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

Wegen $\|b\| \le \|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 $1 - \|A^{-1}\| \|\Delta A\|$ geschrieben.

Kurs:Numerik I/2 Normen und Fehlerabschätzungen

Aus Wikiversity

Inhaltsverzeichnis

[Bearbeiten] 2.1 Normen

[Bearbeiten] Definition 2.1

[Bearbeiten] Lemma 2.2

[Bearbeiten] Beweis

[Bearbeiten] Definition 2.3

[Bearbeiten] Korollar 2.4

[Bearbeiten] Beispiel 2.5

[Bearbeiten] Beispiel 2.6

[Bearbeiten] Definition 2.7

[Bearbeiten] Definition 2.8

[Bearbeiten] Satz 2.9

[Bearbeiten] Beweis

[Bearbeiten] 2.2 Spezielle Matrixnormen

[Bearbeiten] Definition 2.10

[Bearbeiten] Satz 2.11

[Bearbeiten] Beweis.

[Bearbeiten] Satz 2.12

[Bearbeiten] Beweis.

[Bearbeiten] Korollar 2.13

[Bearbeiten] Satz 2.14

[Bearbeiten] Beweis.

[Bearbeiten] Satz 2.15

[Bearbeiten] Beweis.

[Bearbeiten] Beispiel 2.16

[Bearbeiten] Satz 2.17

[Bearbeiten] Beweis.

[Bearbeiten] 2.3 Die Konditionszahl einer Matrix

[Bearbeiten] Definition 2.18

[Bearbeiten] Satz 2.19

[Bearbeiten] Beweis.

[Bearbeiten] 2.4 Störungsresultate für Matrizen

[Bearbeiten] Lemma 2.20

[Bearbeiten] Beweis.

[Bearbeiten] Korollar 2.21

[Bearbeiten] Beweis.

[Bearbeiten] 2.5 Fehlerabschätzungen für gestörte Gleichungssysteme

[Bearbeiten] Satz 2.22

[Bearbeiten] Beweis.

[Bearbeiten] Beispiel 2.23

[Bearbeiten] Satz 2.24

[Bearbeiten] Beweis.

Ansichten

Persönliche Werkzeuge

Suche

Navigation

Aktuell

Werkzeuge