Kurs:Numerik I/Normen und Fehlerabschätzungen

Einführung

Diese Seite kann als Wiki2Reveal Folien angezeigt werden. Einzelne Abschnitte werden als Folien betrachtet und Änderungen an den Folien wirken sich sofort auf den Inhalt der Folien aus.

Ziel

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 ℝ^{n \times n}$ und des Vektors $b \in ℝ^{n}$ auf die Lösung des linearen Gleichungssystems $A x = b$ untersucht. Im Hinblick auf weitere Anwendungen werden wir dabei zunächst Vektoren aus $𝕂^{n}$ und Matrizen aus $𝕂^{n \times n}$ zulassen, wobei $𝕂 : = ℝ$ oder $𝕂 : = ℂ$ ist.

Fehlerabschätzung in reellen Zahlen

Sei $x \in ℝ$ ein exakter Wert (Sollwert) (z.B. $x : = \sqrt{2}$ ) und $\tilde{x} \in ℝ$ ( $\tilde{x} = 1, 41$ ) ein Näherungswert des exakten Wertes, so dass $\tilde{x} \approx x$

Absoluter Fehler

$Δ x = \tilde{x} - x$ heißt absoluter Fehler (im Beispiel: $Δ x = 1, 41 - \sqrt{2}$ ).^[1]. Der absolute Fehler $Δ x = 1, 41 - \sqrt{2}$ besitzt im Beispiel ein negatives Vorzeichen. Das bedeutet, dass der Näherungswert zu klein ist im Vergleich zum Sollwert.

Relativer Fehler

δ_{x} = \frac{Δ x}{x}

heißt im Falle

x \neq 0

relativer Fehler.

Fehlerschranke

Wenn $| Δ x | \leq ϵ$ ist, so heißt $ϵ$ absolute Fehlerschranke.
Wenn $\frac{ϵ}{∣ x ∣} \leq ρ$ gilt, so heißt $ρ$ relative Fehlerschranke.

Abschätzung der Fehlerschranke

Für die relative Fehlerschranke gilt folgende Abschätzung:

\frac{| Δ x |}{∣ x ∣} \leq \frac{ϵ}{∣ x ∣} \leq ρ

Absolu

Fehlerabschätzung in normierten Räumen

Analog kann man die Fehlerabschätzung auf normierte Räume übertragen. Die Norm dient dazu, um die Abweichung von Sollwert und Näherungswert zu messen.

Beispiel

Sei $x \in V$ die exakte vektorielle Darstellung (Sollvektor). Als Beispiel wird der Vektor $x : = (\sqrt{2}, π) \in ℝ^{2} = V$ verwendet. Wenn man $\tilde{x} \in V$ als näherungsweise Darstellung von $x$ in Berechnungen verwendet, so kann man z.B. $\tilde{x} = (1.41, 3.14)$ als den Vektor, der näherungsweise den exakten Vektor $x$ darstellt (d.h. $\tilde{x} \approx x$ ).

Fehler

Analog zu den reellen Zahlen versucht man nun die Fehler als Abstand zwischen dem Sollvektor und der näherungsweisen Darstellung mathematisch zu beschreiben. Die Norm berechnet dabei die Länge von Vektoren und $‖ \tilde{x} - x ‖$ liefert damit ein Maß für den Fehler. Gilt $‖ \tilde{x} - x ‖ = 0$ , so ist die Darstellung exakt.

Normen - Fehlerabschätzung 1

Im Folgenden sei $V$ ein beliebiger Vektorraum über $𝕂$ . Mit der Definition von Normen hat man ein Messinstrument in dem Vektorraum zur Verfügung, mit dem Abstände zwischen Vektoren $x$ und $y$ über die Metrik $d (x, y) : = ‖ x - y ‖$ Längen $‖ x ‖$ von einem Vektor $x$ über die Norm messen kann.

Normen - Fehlerabschätzung 2

Die über die Abbildung $‖ \cdot ‖ : V \to ℝ_{0}^{+}$ Norm ist dabei verträglich mit den Vektorraumoperationen. Repräsentiert der Vektor $x$ einen Fehler:

(N1) $‖ x ‖ = 0 \Leftrightarrow x = 0, x \in V,$ - Fehlervektor $0_{V}$ - Nullvektor
(N2) $‖ α \cdot x ‖ = | α | \cdot ‖ x ‖, x \in V, α \in 𝕂$ - Streckung/Stauchung von Fehlervektoren,
(N3) $‖ x + y ‖ \leq ‖ x ‖ + ‖ y ‖, x, y \in V$ - Dreiecksungleichung zur Fehlerabschätzung.

Vektornorm - Matrixnorm

Eine Norm $‖ \cdot ‖ : 𝕂^{n} \to ℝ_{0}^{+}$ wird auch Vektornorm und entsprechend eine Norm $‖ \cdot ‖ : 𝕂^{n \times n} \to ℝ_{+}$ auch Matrixnorm genannt.

Fehler in Summen

Seien $x_{o}, y_{o} \in V$ die exakten Vektoren und $x, y \in V$ die numerische Näherung von $x_{o}$ bzw. $y_{o}$ . Mit der Dreiecksungleichung zur Fehlerabschätzung kann man den Summenfehler wie folgt nach oben abschätzen:

‖ (x + y) - (x_{o} + y_{o}) ‖ = ‖ (x - x_{o}) + (y - y_{o}) ‖ \leq ‖ x - x_{o} ‖ + ‖ y - y_{o} ‖,

Fehler bei skalaren Vielfachen eine Vektor

Sei $x_{o} \in V$ der exakte Vektor und $x \in V$ die numerische Näherung von $x_{o}$ . Mit der Homogenität der Norm kann man den Fehler des skalierten Vektorswie folgt nach oben berechnen:

‖ α \cdot (x - x_{o}) ‖ = | α | \cdot ‖ x - x_{o} ‖, α \in 𝕂

.

Der Fehler vervielfacht somit um $| α |$ bei der Multiplikation mit Skalaren.

Fehlerschranken in normierten Räumen

Sei $(V, ‖ \cdot ‖)$ ein normierter Raum und dann kann man mit der Norm die Länge des Fehlervektors $Δ x : = \tilde{x} - x$ bestimmen.

Wenn $‖ Δ x ‖ \leq ϵ$ ist, so heißt $ϵ$ absolute Fehlerschranke für den Fehlervektor $Δ x \in V$ .
Wenn $\frac{ϵ}{‖ x ‖} \leq ρ$ gilt, so heißt $ρ$ relative Fehlerschranke.

Abschätzung der Fehlerschranke in normierten Räumen

Für die relative Fehlerschranke gilt in einem normierten Raum $(V, ‖ \cdot ‖)$ folgende Abschätzung:

\frac{‖ Δ_{x} ‖}{‖ x ‖} \leq \frac{ϵ}{‖ x ‖} \leq ρ

Lemma - umgekehrte Dreiecksungleichung

Für eine Norm $‖ \cdot ‖ : 𝒱 \to ℝ_{+}$ gilt die umgekehrte Dreiecksungleichung

| ‖ x ‖ - ‖ y ‖ | \leq ‖ x - y ‖, x, y \in 𝒱 .

Beweis - umgekehrte Dreiecksungleichung

Es seien $x, y \in 𝒱$ . Dann gilt

‖ x ‖ = ‖ x - y + y ‖ \leq ‖ x - y ‖ + ‖ y ‖

Beweis 1

Damit erhält man durch Umformung

(UDG1) $‖ x ‖ - ‖ y ‖ \leq ‖ x - y ‖$

Nun betrachten wir

(UDG1) $‖ x - y ‖ = | - 1 | \cdot ‖ y - x ‖ = ‖ y - x ‖$

Beweis 2

Das Vertauschen von $x$ und $y$ liefert analog folgende Abschätzung

(UDG2)

‖ y ‖ - ‖ x ‖ \leq ‖ x - y ‖

Die Ungleichungen (UDG1) und (UDG2) zusammen liefern die Behauptung.

q.e.d.

Fehler bei Differenzen

Seien $x_{o}, y_{o} \in V$ die exakten Vektoren und $x, y \in V$ die numerische Näherung von $x_{o}$ bzw. $y_{o}$ . Mit der obigen Fehlerabschätzung kann man den Summenfehler wie folgt nach oben abschätzen:

\begin{matrix} | ‖ x - x_{o} ‖ - ‖ y - y_{o} ‖ | & \leq & ‖ (x - x_{o}) - (y - y_{o}) ‖ \\ = & ‖ (x - y) - (x_{o} - y_{o}) ‖ \end{matrix}

Man kann also den Betrag der Differenz der Einzelfehler nach oben gegen Norm des Subtraktionsfehlers abschätzen.

Fehler bei Differenzen - Abschätzung nach oben

Den Fehler der Differenz kann man oben gegen die Summe der Einzelfehler abschätzen und nicht gegen die Differenz der Einzelfehler.

\begin{matrix} | ‖ x - x_{o} ‖ - ‖ y - y_{o} ‖ | & \leq & ‖ (x - x_{o}) - (y - y_{o}) ‖ \\ = & ‖ (x - y) - (x_{o} - y_{o}) ‖ \\ \leq & ‖ x - y ‖ + ‖ x_{o} - y_{o}) ‖ \end{matrix}

Vektorraum - Norm - Fehlermaße

Einen Vektorraum $𝒱$ , auf dem eine Norm $‖ \cdot ‖$ definiert ist, bezeichnet man als einen normierten Vektorraum. Man kennzeichnet ihn auch durch $(𝒱, ‖ \cdot ‖)$ . Auf endlich dimensionalen Vektorräumen sind die Normen äquivalent bzgl. Konvergenz, allerdings kommt es in der Numerik bei der Fehlerabschätzung auf Fehlerschranken an und diese hängen von der konkreten Wahl der Norm ab.

Konvergenz im normierten Raum

Mit numerischen Interationsverfahren versucht man beispielsweise einen Fehler zu minimieren bzw. die Ausgabe einer funktionalen Darstellung $f_{t}$ zum Zeitpunkt $t$ an Sollwerte mit wachsendem Zeitindex/Interationindex anzupassen. Der mit einer Norm gemessene Abstand zwischen Soll- und Ist-Wert bestimmt dabei den Fehler des Verfahrens zum Zeitpunkt. Für eine solche Mathematisierung benötigt man den Konvergenzbegriff auf normierten Räumen.

Definition - Konvergenz im normierten Raum

Es sei $(𝒱, ‖ \cdot ‖)$ ein normierter Vektorraum. Eine Folge $(x_{n})$ von Elementen $x_{n} \in 𝒱$ konvergiert gegen $x_{0} \in 𝒱$ , kurz

\lim_{n \to \infty} x_{n} = x_{0},

wenn gilt:

\lim_{n \to \infty} ‖ x_{n} - x_{0} ‖ = 0 .

Korollar - Stetigkeit der Normabbildung

Eine Norm $‖ \cdot ‖ : 𝒱 \to ℝ_{+}$ ist stetig, d. h., es gilt

x_{0}, x_{n} \in 𝒱, \lim_{n \to \infty} x_{n} = x \Rightarrow \lim_{n \to \infty} ‖ x_{n} ‖ = ‖ x ‖ .

Beispiele von Normen

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

(1) $‖ x ‖_{2} : = {(\sum_{j = 1}^{n} | x_{j} |^{2})}^{1 / 2}$ (Euklidische oder $l_{2}$ -Norm),
(2) $‖ x ‖_{1} : = \sum_{j = 1}^{n} | x_{j} |$ (Summen- oder $l_{1}$ -Norm),
(3) $‖ x ‖_{\infty} : = \max_{j = 1, \dots, n} | x_{j} |$ (Maximum- oder $l_{\infty}$ -Norm).

Aufgaben - Normeigenschaften

Beweisen Sie, dass die Maximumnormen tatsächlich die Normeigenschaften erfüllen.
Beweisen Sie, dass die Summennormen tatsächlich die Normeigenschaften erfüllen.

Beweis 1 - Euklidische Norm

Für die Euklidische Norm folgt die Dreiecksungleichung mit der Cauchy-Schwarzschen Ungleichung. Und zwar schließt man mit

‖ x ‖_{2}^{2} = ⟨ x, x ⟩ = \sum_{j = 1}^{n} {\overline{x}}_{j} x_{j} = \overset{T}{\overline{x}} x = x^{H} x

für $x^{H} : = \overset{T}{\overline{x}}$

Beweis 2 - Euklidische Norm

Damit erhält man folgende Abschätzung:

\begin{matrix} ‖ x + y ‖_{2}^{2} & = & ⟨ x + y, x + y ⟩ \\ = & \underset{= ‖ x ‖_{2}^{2}}{\underset{⏟}{⟨ x, x ⟩}} + \underset{\leq 2 ‖ x ‖_{2} ‖ y ‖_{2}}{\underset{⏟}{2 Re (⟨ x, y ⟩)}} + \underset{= ‖ y ‖_{2}^{2}}{\underset{⏟}{⟨ y, y ⟩}} \\ \leq & (‖ x ‖_{2} + ‖ y ‖_{2})^{2} \end{matrix}

für alle $x, y \in 𝕂^{n}$ gilt, wobei $Re (x)$ den Realteil von $x$ bezeichnet.

Dreicksungleichung für l_p-Normen

Allgemeiner ist, wie man zeigen kann, für jedes $1 \leq p < \infty$ durch

‖ x ‖_{p} : = {(\sum_{j = 1}^{n} | x_{j} |^{p})}^{1 / p}

(

l_{p}

-Norm)

eine Norm definiert,

l_p-Normen und Maximumsnorm

Es gilt folgende Konvergenzaussage:

\lim_{p \to \infty} ‖ x ‖_{p} = ‖ x ‖_{\infty} .

Normenäquivalenzsatz

Man kann mit dem Normenäquivalenzsatz zeigen, dass je zwei auf einem endlich-dimensionalen Vektorraum $𝒱$ 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} \leq ‖ x ‖_{b} \leq c_{2} ‖ x ‖_{a}, x \in 𝒱 .

Fehlerschranken

Wenn man in einem konkreten Problem Fehlerschranken hat, die nicht überschritten werden dürfen, muss man bei dem Übergang von einer Norm zu einem äquivalenten Norm die Fehlerschranken anpassen. Dies ist leicht erkennbar, wenn man eine Norm $‖ \cdot ‖$ durch eine äquivalente Norm $‖ \cdot ‖_{a} : = a \cdot ‖ \cdot ‖$ ersetzt.

Abschätzungen der Normen

Bei den oben genannten Beispielnormen auf $𝒱 : = 𝕂^{n}$ gelten die folgenden Abschätzungen:

(A1) $‖ x ‖_{\infty} \leq ‖ x ‖_{2} \leq \sqrt{n} ‖ x ‖_{\infty}, x \in 𝕂^{n},$
(A2) $‖ x ‖_{\infty} \leq ‖ x ‖_{1} \leq n ‖ x ‖_{\infty}, x \in 𝕂^{n},$
(A3) $‖ x ‖_{2} \leq ‖ x ‖_{1} \leq \sqrt{n} ‖ x ‖_{2}, x \in 𝕂^{n} .$

Aufgaben

Beweisen Sie die beiden ersten Abschätzungen (A1) und (A2) als Übung.

Nachweis der Abschätzung (A3)

Die erste Abschätzung in (A3) folgt aus

\sum_{j = 1}^{n} | x_{j} |^{2} \leq {(\sum_{j = 1}^{n} | x_{j} |)}^{2},

Die zweite mit der Cauchy-Schwarzschen Ungleichung aus

\sum_{j = 1}^{n} 1 \cdot | x_{j} | = ⟨ e, x ⟩ \leq ‖ e ‖_{2} ‖ x ‖_{2} = \sqrt{n} ‖ x ‖_{2},

wobei $e \in 𝕂^{n}$ der Vektor ist, der in jeder Komponenten $e_{j} : = 1$ ist.

Bemerkung - Abschätzung (A3)

Für große $n \in ℕ$ sind allerdings die jeweils zweiten Abschätzungen in (A3) aufgrund der Größe der auftretenden Konstanten numerisch bedeutungslos.

Beispiele - Matrixnormen

Die folgenden Normen sind Matrixnormen für Matrizen $A : = (a_{k j}) \in 𝕂^{n \times n}$ :

(M1) $‖ A ‖ : = {(\sum_{k = 1}^{n} \sum_{j = 1}^{n} | a_{k j} |^{2})}^{1 / 2}$ (Frobenius-Norm),
(M2) $‖ A ‖_{z} : = \max_{k = 1, \dots, n} \sum_{j = 1}^{n} | a_{k j} |$ (Zeilensummennorm),
(M3) $‖ A ‖_{s} : = \max_{j = 1, \dots, n} \sum_{k = 1}^{n} | a_{k j} |$ (Spaltensummennorm).

Aufgabe - Normeigenschaften

Beweisen Sie, dass die Zeilen- und Spaltensummennorm tatsächlich die Normeigenschaften erfüllen,

Identifikation Matrizen mit Vektoren

Jede Matrix $A \in 𝕂^{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.

Definition - Submultiplikativität

Eine Matrixnorm $‖ \cdot ‖ : 𝕂^{n \times n} \to ℝ_{0}^{+}$ nennt man submultiplikativ, falls

‖ A \cdot B ‖ \leq ‖ A ‖ \cdot ‖ B ‖, A, B \in 𝕂^{n \times n},

Definition - Verträglichkeit Matrixnorm Vektorrnorm

Eine Matrixnorm $‖ \cdot ‖ : 𝕂^{n \times n} \to ℝ_{0}^{+}$ nennt man mit einer gegebenen Vektornorm $‖ \cdot ‖_{v} : 𝕂^{n} \to ℝ_{0}^{+}$ verträglich, falls folgende Abschätzung gilt:

‖ A x ‖_{v} \leq ‖ A ‖ \cdot ‖ x ‖_{v}, A \in 𝕂^{n \times n}, x \in 𝕂^{n} .

Zusammenhang Stetigkeitssatz für lineare Abbildungen

Man kann eine quadratische Matrix $𝕂^{n \times n}$ als lineare Abbildung von dem $𝕂^{n}$ auffassen. Die obige Abschätzung $‖ A x ‖_{v} \leq ‖ A ‖ ‖ x ‖_{v}$ hängt mit dem Stetigkeitssatz für lineare Abbildungen zusammen, da stetige lineare Operatoren eine endliche Operatornorm besitzen.

Definition - Induzierte Matrixnorm

Sei $‖ \cdot ‖_{v} : 𝕂^{n} \to ℝ_{+}$ eine Vektornorm. Dann heißt die durch

‖ A ‖ : = \max_{x \in 𝕂^{n} ∖ {0}} \frac{‖ A x ‖_{v}}{‖ x ‖_{v}} = \max_{‖ x ‖_{v} = 1} ‖ A x ‖_{v}, A \in 𝕂^{n \times n}

definierte Norm die durch die Vektornorm $‖ \cdot ‖$ induzierte Matrixnorm (oder auch Operatornorm von $A$ ).

Bemerkung

Man beachte, dass wegen der Kompaktheit der Menge ${x \in 𝕂^{n} | ‖ x ‖_{v} = 1}$ und der Stetigkeit der Vektornorm das Maximum in der Definition von $‖ A ‖$ tatsächlich angenommen wird. Offenbar gilt für die Indentität (Einheitsmatrix) $‖ I ‖ = 1$ .

Satz - Induzierten Matrixnorm

Die durch eine Vektornorm induzierte Matrixnorm

(IM1) beistzt die in Normeigenschaften (N1), (N2), (N3) angegebenen Normeigenschaften,
(IM2) bezüglich der zugrunde liegenden Vektornorm verträglich und
(IM3) submultiplikativ

Beweis - Induzierten Matrixnorm

Es seien $‖ \cdot ‖_{v} : 𝕂^{n} \to ℝ_{0}^{+}$ die Vektornorm und $‖ \cdot ‖ : 𝕂^{n \times n} \to ℝ_{0}^{+}$ die induzierte Matrixnorm.

(IM1) Normeigenschaften

Die Normeigenschaften der Vektornorm $‖ \cdot ‖_{v}$ liefern die Normeigenschaften der induzierten Matrixnorm $‖ \cdot ‖$ unmittelbar.

(IM2) Verträglichkeit

Ihre Verträglichkeit mit der Vektornorm folgt aus

‖ A x ‖_{v} = \frac{‖ A x ‖_{v}}{‖ x ‖_{v}} ‖ x ‖_{v} \leq (\max_{x \in 𝕂^{n} ∖ {0}} \frac{‖ A x ‖_{v}}{‖ x ‖_{v}}) ‖ x ‖_{v} = ‖ A ‖ ‖ x ‖_{v}

für $x \neq 0$ .

(IM3) Submultiplikativität - 1

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

\begin{matrix} ‖ A B x ‖_{v} & = & \frac{‖ A (B x) ‖_{v}}{‖ B x ‖_{v}} \frac{‖ B x ‖_{v}}{‖ x ‖_{v}} \cdot ‖ x ‖_{v} \\ \leq & ‖ A ‖ \cdot ‖ B ‖ \cdot ‖ x ‖_{v} \end{matrix}

(IM4) Submultiplikativität - 2

Im Fall $x \neq 0_{V}$ gilt dann

0 \leq \frac{‖ A \cdot B \cdot x ‖_{v}}{‖ x ‖_{v}} \leq ‖ A ‖ \cdot ‖ B ‖ .

Somit folgt auch die Submultiplikativität der induzierten Matrixnorm.