Kurs:Numerik I/Normen und Fehlerabschätzungen

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.

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

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

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

${\displaystyle \delta _{x}={\frac {\Delta x}{x}}}$ heißt im Falle ${\displaystyle x\neq 0}$ relativer Fehler.

• Wenn ${\displaystyle |\Delta x|\leq \epsilon }$ ist, so heißt ${\displaystyle \epsilon }$ absolute Fehlerschranke.
• Wenn ${\displaystyle {\frac {\epsilon }{\mid x\mid }}\leq \rho }$ gilt, so heißt ${\displaystyle \rho }$ relative Fehlerschranke.

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

${\displaystyle {\frac {|\Delta x|}{\mid x\mid }}\leq {\frac {\epsilon }{\mid x\mid }}\leq \rho }$

Absolu

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.

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

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 ${\displaystyle \|{\tilde {x}}-x\|}$ liefert damit ein Maß für den Fehler. Gilt ${\displaystyle \|{\tilde {x}}-x\|=0}$, so ist die Darstellung exakt.

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

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

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

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

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

${\displaystyle \|(x+y)-(x_{o}+y_{o})\|=\|(x-x_{o})+(y-y_{o})\|\leq \|x-x_{o}\|+\|y-y_{o}\|,}$

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

${\displaystyle \|\alpha \cdot (x-x_{o})\|=|\alpha |\cdot \|x-x_{o}\|,\quad \alpha \in \mathbb {K} }$.

Der Fehler vervielfacht somit um ${\displaystyle |\alpha |}$ bei der Multiplikation mit Skalaren.

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

• Wenn ${\displaystyle \|\Delta x\|\leq \epsilon }$ ist, so heißt ${\displaystyle \epsilon }$ absolute Fehlerschranke für den Fehlervektor ${\displaystyle \Delta x\in V}$.
• Wenn ${\displaystyle {\frac {\epsilon }{\|x\|}}\leq \rho }$ gilt, so heißt ${\displaystyle \rho }$ relative Fehlerschranke.

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

${\displaystyle {\frac {\|\Delta _{x}\|}{\|x\|}}\leq {\frac {\epsilon }{\|x\|}}\leq \rho }$

Für eine Norm ${\displaystyle \|\cdot \|:{\mathcal {V}}\to \mathbb {R} _{+}}$ gilt die umgekehrte Dreiecksungleichung

${\displaystyle {\big |}\|x\|-\|y\|{\big |}\leq \|x-y\|,\quad x,y\in {\mathcal {V}}.}$

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

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

Damit erhält man durch Umformung

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

Nun betrachten wir

• (UDG1) ${\displaystyle \|x-y\|=|-1|\cdot \|y-x\|=\|y-x\|}$

Das Vertauschen von ${\displaystyle x}$ und ${\displaystyle y}$ liefert analog folgende Abschätzung

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

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

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

${\displaystyle {\begin{array}{rcl}|\,\|x-x_{o}\|-\|y-y_{o}\|\,|&\leq &\|(x-x_{o})-(y-y_{o})\|\\&=&\|(x-y)-(x_{o}-y_{o})\|\\\end{array}}}$

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

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

${\displaystyle {\begin{array}{rcl}|\,\|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{array}}}$

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 \|)}$. 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.

Mit numerischen Interationsverfahren versucht man beispielsweise einen Fehler zu minimieren bzw. die Ausgabe einer funktionalen Darstellung ${\displaystyle f_{t}}$ zum Zeitpunkt ${\displaystyle 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.

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

${\displaystyle \lim _{n\to \infty }x_{n}=x_{0},}$

wenn gilt:

${\displaystyle \lim _{n\to \infty }\|x_{n}-x_{0}\|=0.}$

Eine Norm ${\displaystyle \|\cdot \|:{\mathcal {V}}\to \mathbb {R} _{+}}$ ist stetig, d. h., es gilt

${\displaystyle x_{0},x_{n}\in {\mathcal {V}},\quad \lim _{n\to \infty }x_{n}=x\Rightarrow \lim _{n\to \infty }\|x_{n}\|=\|x\|.}$

Es sei ${\displaystyle x\in \mathbb {K} ^{n}}$. Beispiele für Vektornormen 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).

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

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

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

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

Damit erhält man folgende Abschätzung:

${\displaystyle {\begin{array}{rcl}\|x+y\|_{2}^{2}&=&\langle x+y,x+y\rangle \\&=&\underbrace {\langle x,x\rangle } _{=\|x\|_{2}^{2}}+\underbrace {2\operatorname {Re} (\langle x,y\rangle )} _{\leq 2\|x\|_{2}\|y\|_{2}}+\underbrace {\langle y,y\rangle } _{=\|y\|_{2}^{2}}\\&\leq &(\|x\|_{2}+\|y\|_{2})^{2}\\\end{array}}}$

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

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

eine Norm definiert,

Es gilt folgende Konvergenzaussage:

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

Man kann mit dem Normenäquivalenzsatz zeigen, dass je zwei 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}}.}$

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 ${\displaystyle \|\cdot \|}$ durch eine äquivalente Norm ${\displaystyle \|\cdot \|_{a}:=a\cdot \|\cdot \|}$ ersetzt.

Bei den oben genannten Beispielnormen auf ${\displaystyle {\mathcal {V}}:=\mathbb {K} ^{n}}$ gelten die folgenden Abschätzungen:

• (A1) ${\displaystyle \|x\|_{\infty }\leq \|x\|_{2}\leq {\sqrt {n}}\|x\|_{\infty },\quad x\in \mathbb {K} ^{n},}$
• (A2) ${\displaystyle \|x\|_{\infty }\leq \|x\|_{1}\leq n\|x\|_{\infty },\quad x\in \mathbb {K} ^{n},}$
• (A3) ${\displaystyle \|x\|_{2}\leq \|x\|_{1}\leq {\sqrt {n}}\|x\|_{2},\quad x\in \mathbb {K} ^{n}.}$

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

Die erste Abschätzung in (A3) 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}|=\langle e,x\rangle \leq \|e\|_{2}\|x\|_{2}={\sqrt {n}}\|x\|_{2},}$

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

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

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

• (M1) ${\displaystyle \|A\|:=\left(\sum _{k=1}^{n}\sum _{j=1}^{n}|a_{kj}|^{2}\right)^{1/2}}$ (Frobenius-Norm),
• (M2) ${\displaystyle \|A\|_{z}:=\max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|}$ (Zeilensummennorm),
• (M3) ${\displaystyle \|A\|_{s}:=\max _{j=1,\ldots ,n}\sum _{k=1}^{n}|a_{kj}|}$ (Spaltensummennorm).

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

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.

Eine Matrixnorm ${\displaystyle \|\cdot \|:\mathbb {K} ^{n\times n}\to \mathbb {R} _{0}^{+}}$ nennt man submultiplikativ, falls

${\displaystyle \|A\cdot B\|\leq \|A\|\cdot \|B\|,\quad A,B\in \mathbb {K} ^{n\times n},}$

Eine Matrixnorm ${\displaystyle \|\cdot \|:\mathbb {K} ^{n\times n}\to \mathbb {R} _{0}^{+}}$ nennt man mit einer gegebenen Vektornorm ${\displaystyle \|\cdot \|_{v}:\mathbb {K} ^{n}\to \mathbb {R} _{0}^{+}}$ verträglich, falls folgende Abschätzung gilt:

${\displaystyle \|Ax\|_{v}\leq \|A\|\cdot \|x\|_{v},\quad A\in \mathbb {K} ^{n\times n},\quad x\in \mathbb {K} ^{n}.}$

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

Sei ${\displaystyle \|\cdot \|_{v}:\mathbb {K} ^{n}\to \mathbb {R} _{+}}$ eine Vektornorm. Dann heißt die durch

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

definierte Norm die durch die Vektornorm ${\displaystyle \|\cdot \|}$ induzierte Matrixnorm (oder auch Operatornorm von ${\displaystyle A}$).

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

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

Es seien ${\displaystyle \|\cdot \|_{v}:\mathbb {K} ^{n}\to \mathbb {R} _{0}^{+}}$ die Vektornorm und ${\displaystyle \|\cdot \|:\mathbb {K} ^{n\times n}\to \mathbb {R} _{0}^{+}}$ die induzierte Matrixnorm.

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

Ihre Verträglichkeit mit der Vektornorm folgt aus

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

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 {\begin{array}{rcl}\|ABx\|_{v}&=&{\frac {\|A(Bx)\|_{v}}{\|Bx\|_{v}}}{\frac {\|Bx\|_{v}}{\|x\|_{v}}}\cdot \|x\|_{v}\\&\leq &\|A\|\cdot \|B\|\cdot \|x\|_{v}\\\end{array}}}$

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

${\displaystyle 0\leq {\frac {\|A\cdot B\cdot x\|_{v}}{\|x\|_{v}}}\leq \|A\|\cdot \|B\|.}$

Somit folgt auch die Submultiplikativität der induzierten Matrixnorm.

• Cauchy-Schwarz-Ungleichung
• Stetigkeitssatz für lineare Abbildungen
• Normen, Metriken, Topologie
• Eigenwerte, Eigenvektoren,
• Diagonalisierung

1. ↑ Bronstein-Semendjajew, Taschenbuch der Mathematik, 19. Aufl. 1979, S. 151.

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20%20I/2%20Normen%20und%20Fehlerabsch%C3%A4tzungen
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.