Kurs:Numerik I/Störungsresultate für Matrizen

Störungsresultate für Matrizen

Wie das numerisches Problem auf Störungen in den Anfangsdaten reagiert, wird mit der Kondition gemessen. Hat ein Problem eine große Kondition, so hängt die Lösung des Problems empfindlich von den Anfangsdaten ab, d.h. bei leichten Veränderungen des Anfangszustand kann sich die Lösung des numerischen Verfahrens stark verändern. Dies hängt insbesondere mit Rundungsfehler zusammen, die als Störung der Anfangsdaten aufgefasst werden können.

Störung - absoluter Fehler

In der folgenden Formulierung wird die Störung als absoluter Fehler $\Delta A$. In den Komponenten der Matrix steht der Wert für die Abweichung vom tatsächlichen Wert. Diese "Störungen" können in der Praxis durch externe Einflüsse entstehen, die dann die Messungenauigkeiten verschlechtern.

Beispiel

Stellen wir z.B. ein Bild als quadratische Pixelmatrix $A$, das von einem optischen Teleskop bei der Beobachtung von Sternen generiert wird. Die Lichtverschmutzung bei der Sternbeobachtung stört die Aufnahme von $A$ um $\Delta A$. Das resultierende Bild ist dann $A+\Delta A$.

Aufgaben - Anwendungsbezug

• Geben Sie weiter Anwendungsbespiele für störende Einflüsse, die Messungen verfälschen können (z.B. Verkehrsprognosen, Wettervorhersage, Klausurergebnisse, Börsenkurse,...)!
• Betrachten Sie nun eine Übergangsmatrix $A$ im Kontext von Markow-Ketten und erläutern Sie, wie relative Häufigkeiten mit dem Gesetz der großen Zahlen einen Näherungswert für eine theoretische Wahrscheinlichkeit darstellen. Welche Ähnlichkeiten und Unterschiede können Sie zwischen einem numerischen und statistischen Zugang erkennen?

Konditionszahl und invertierbar Matrizen

Für eine reguläre/invertierbare Matrix $A\in \mathbb {R} ^{n\times n}$ mit einer Matrixnorm $\|\cdot \|:\mathbb {R} ^{n\times n}\to \mathbb {R} _{+}$ wird die Konditionszahl über

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

berechnet. Das folgende Lemma ist hilfreich, um für die Konditionszahl die Matrixnorm $\|A^{-1}\|$ mit $A:=I+F$ nach oben abzuschätzen.

Lemma - Regularität und induzierte Matrixnorm

Sei $\|\cdot \|:\mathbb {R} ^{n\times n}\to \mathbb {R} _{0}^{+}$ eine durch eine Norm auf $\mathbb {R} ^{n}$ 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}\|\leq {\frac {1}{1-\|F\|}}.$

Beweis - 1 - Regularität und induzierte Matrixnorm

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

${\begin{array}{rcl}\|(I+F)x\|&=&\|x+Fx\|\\&=&\|x-(-Fx)\|{\stackrel {umgek.\,\Delta -Ungl}{\geq }}\|x\|-\underbrace {\|Fx\|} _{=\|-Fx\|}\\&\geq &\|x\|-\|F\|\|x\|=(1-\|F\|)\cdot \|x\|.\\\end{array}}$

Also ist für $x\neq 0_{v}$ auch $(I+F)x\neq 0_{v}$.

Beweis - 2 - Regularität und induzierte Matrixnorm

Wenn für alle $x\neq 0_{v}$ auch $\underbrace {(I+F)} _{=:B}x\neq 0_{v}$ gilt, ist der Nullvektor $0_{v}$ das einzige Element im Kern von $B:=I+F$. Damit die Invertierbarkeit von $I+F$ impliziert.

Beweis - 2 - Regularität und induzierte Matrixnorm

Mit der Setzung $y:=(I+F)x$ liefert die obige Ungleichung in Beweisschritt 1:

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

und damit

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

was den Beweis des Lemmas durch Maximumsbildung in der Matrixnorm komplettiert.

q.e.d.

Störungen als Differenzmatrizen

Wenn man eine Matrix $A\in \mathbb {R} ^{n\times n}$ gegeben hat und eine Störung als Veränderung $\Delta A\in \mathbb {R} ^{n\times n}$ auffasst, ist es wesentlich die Konditionszahl $cond(A+\Delta A)$ der Matrix $A+\Delta A$ zu berechnen. Nach Definition der Konditionszahl $cond(B):=\|B\|\cdot \|B^{-1}\|$ muss man für $B:=A+\Delta A$ die induzierte Matrixnorm $\|B^{-1}\|$ abschätzen. Das folgende Korrolar liefert das als Resultat.

Korollar - Regularität und induzierte Matrixnorm

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 $\textstyle \|\Delta A\|<{\frac {1}{\|A^{-1}\|}}$ ist dann die Matrix $A+\Delta A$ regulär, und es gelten unter der Bedingung $\textstyle \|\Delta A\|\leq {\frac {1}{2\cdot \|A^{-1}\|}}$ die Abschätzungen

${\begin{array}{rcl}\|(A+\Delta A)^{-1}\|&\leq &{\frac {\|A^{-1}\|}{1-\|A^{-1}\|\cdot \|\Delta A\|}}\\\|(A+\Delta A)^{-1}-A^{-1}\|&\leq &2\cdot \|A^{-1}\|^{2}\cdot \|\Delta A\|\\\end{array}}$

Beweis - 1 - Korollar

Mit der Submultiplikativität $\|A\cdot B\|\leq \|A\|\cdot \|B\|$ der induzierten Matrixnorm erhält man

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

Dabei erhält man die Abschätzung nach oben gegen 1 unter der gegebenen Voraussetzung $\|\Delta A\|<{\frac {1}{\|A^{-1}\|}}$.

Beweis - 2 - Korollar

Nach Lemma über die Regularität ist somit die Matrix $I+A^{-1}\Delta A$ eine reguläre Matrix. Da nach Voraussetzung $A\in GL(n,\mathbb {R} )$ ist auch das Produkt von regulären Matrizen $A\cdot (I+A^{-1}\cdot \Delta A)\in GL(n,\mathbb {R} )$ wieder regulär und man erhält:

$A+\Delta A=A(I+A^{-1}\cdot \Delta A)\in GL(n,\mathbb {R} )$

Beweis - 3 - Korollar

Mit $(M_{1}\cdot M_{2})^{-1}=M_{2}^{-1}\cdot M_{1}^{-1}$ und der Darstellung aus dem vorherigen Schritt erhält man die folgende Darstellung:

${\begin{array}{rcl}(A+\Delta A)^{-1}&=&\left(A\cdot (I+A^{-1}\cdot \Delta A)^{-1})\right)^{-1}\\&=&(I+A^{-1}\cdot \Delta A)^{-1}\cdot A^{-1}\end{array}}$

Beweis - 4 - Korollar

Durch Anwendung des Lemmas über Regularität und induzierte Matrixnorm erhält man man nun die Abschätzung:

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

Beweis - 5 - Korollar

Mit $A^{-1}=(A+\Delta A)^{-1}\cdot (A+\Delta A)\cdot A^{-1}$ erhält man die folgende Darstellung:

${\begin{array}{rcl}(A+\Delta A)^{-1}-A^{-1}&=&(A+\Delta A)^{-1}\left(I-(A+\Delta A)A^{-1}\right)\\&=&(A+\Delta A)^{-1}{\big (}I-\underbrace {A\cdot A^{-1}} _{=I}+\Delta A\cdot A^{-1}{\big )}\\&=&-(A+\Delta A)^{-1}\cdot \Delta A\cdot A^{-1}\\\end{array}}$

Beweis - 6 - Korollar

Zusammen mit der ersten Ungleichung des Korollars in Beweisschritt 3 folgt und der Verwendung der Submultiplikativität der Matrixnorm:

${\begin{array}{rcl}\|(A+\Delta A)^{-1}-A^{-1}\|&\leq &\|(A+\Delta A)^{-1}\|\cdot \|A^{-1}\|\cdot \|\Delta A\|\\&\leq &{\frac {\|A^{-1}\|}{1-\underbrace {\|A^{-1}\|\cdot \|\Delta A\|} _{\leq {\frac {1}{2}}}}}\cdot \|A^{-1}\|\cdot \|\Delta A\|\\&\leq &{\frac {\|A^{-1}\|}{1-{\frac {1}{2}}}}\cdot \|A^{-1}\|\cdot \|\Delta A\|\\&=&2\cdot \|A^{-1}\|^{2}\cdot \|\Delta A\|.\\\end{array}}$

q.e.d.

Bemerkung zu Beweisschritt 6

In der zweiten Ungleichung liefert mit $\|\Delta A\|\leq {\frac {1}{2\cdot \|A^{-1}\|}}$ bzw. $\|\Delta A\|\cdot \|A^{-1}\|\leq {\frac {1}{2}}$ im Nenner $1-\|\Delta A\|\cdot \|A^{-1}\|\geq 1-{\frac {1}{2}}>0$ die Abschätzung nach oben.

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. 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 GL(n,\mathbb {R} )\subset \mathbb {R} ^{n\times n}$ eine reguläre Matrix.

Satz - Fehlerabschätzung gestörter Gleichungssysteme

Sei $A\in GL(n,\mathbb {R} )$ und $b,x\in \mathbb {R} ^{n}$ und $\Delta b,\Delta x\in \mathbb {R} ^{n}$ seien Vektoren mit

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

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

(FG2) $\|(x+\Delta x)-x\|=\|\Delta x\|\leq \|A^{-1}\|\cdot \|\Delta b\|,$

(FG3) ${\frac {\|(x+\Delta x)-x\|}{\|x\|}}={\frac {\|\Delta x\|}{\|x\|}}\leq \operatorname {cond} (A)\cdot {\frac {\|\Delta b\|}{\|b\|}}.$

Beweis 1 - Fehlerabschätzung gestörter Gleichungssysteme

Aus (FG1) folgt unmittelbar über Multiplikation mit $A^{-1}$ die Aussage (FG2) mit $\|\Delta b\|\not =0$

${\begin{array}{rcl}A\cdot \Delta x&=&\Delta b\\\Delta x&=&A^{-1}\cdot A\cdot \Delta x=A^{-1}\cdot \Delta b\\\|\Delta x\|&=&\|A^{-1}\cdot \Delta b\|=\underbrace {\left\|A^{-1}\cdot {\frac {\Delta b}{\|\Delta b\|}}\right\|} _{\leq \|A^{-1}\|}\cdot \|\Delta b\|\\&\leq &\|A^{-1}\|\cdot \|\Delta b\|\end{array}}$

Beweis 2 - Fehlerabschätzung gestörter Gleichungssysteme

${\begin{array}{rcl}{\frac {\|\Delta x\|}{\|x\|}}&{\stackrel {(FG2)}{=}}&{\frac {\|A^{-1}\cdot \Delta b\|}{\|x\|}}\cdot {\frac {\|b\|}{\|b\|}}{\stackrel {Ax=b}{=}}{\frac {\|A^{-1}\cdot \Delta b\|}{\|x\|}}\cdot {\frac {\|Ax\|}{\|b\|}}\\&\leq &{\frac {\|A^{-1}\|\cdot \|\Delta b\|}{\|x\|}}\cdot {\frac {\|Ax\|}{\|b\|}}\\&=&\|A^{-1}\|\cdot \underbrace {\frac {\|Ax\|}{\|x\|}} _{\leq \|A\|}\cdot {\frac {\|\Delta b\|}{\|b\|}}\\&\leq &\underbrace {\operatorname {cond} (A)} _{=\|A^{-1}\|\cdot \|A\|}\cdot {\frac {\|\Delta b\|}{\|b\|}}.\\\end{array}}$

$A\cdot \Delta x=\Delta b$ bzw. $\Delta x=A^{-1}\cdot \Delta b$ líefert damit mit (FG2) die Behauptung (FG3). q.e.d.

Bemerkung

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 $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 1a

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}}$

Beispiel 1b

Dann ist bei sehr kleinem $\varepsilon$ die Matrixnorm von $\|A\|_{2}\approx 1$, von $\|A^{-1}\|_{2}\approx 1/\varepsilon$ und somit die Kondition

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

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

Ähnliches gilt auch im Falle gestörter Matrizen.

Satz - Fehlerabschätzung und Konditionszahl

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

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

die Abschätzung

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

Beweis 1 - Fehlerabschätzung und Konditionszahl

Aus (FK1) folgt mit $A\cdot \Delta x=A\cdot ({\tilde {x}}-x)=A\cdot {\tilde {x}}-A\cdot x={\tilde {b}}-b=\Delta b$ unmittelbar

${\begin{array}{rcl}(A+\Delta A)\cdot \Delta x&=&A\cdot \Delta x+\Delta A\cdot \Delta x\\&=&\Delta b-\Delta A\cdot x\\(A+\Delta A)\cdot x&=&A\cdot x+\Delta A\cdot x\\\end{array}}$

Insgesamt erhält man: $(A+\Delta A)\cdot (x+\Delta x)=b+\Delta b$

Beweis 2 - Fehlerabschätzung und Konditionszahl

Korollar zur Regularität und Spektralnorm liefert nun die Invertierbarkeit der Matrix $A+\Delta A$ sowie die Abschätzung

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

Beweis 3 - Fehlerabschätzung und Konditionszahl

Mit der Abschätzung des absoluten Fehlers im Beweisschritt 2 erhält man bei Division durch $\|x\|$ ein Abschätzung für den relativen Fehler mit $\|x\|>0$.

${\frac {\|\Delta x\|}{\|x\|}}\leq {\frac {\|A^{-1}\|}{1-\|A^{-1}\|\cdot \|\Delta A\|}}\cdot {\bigg (}{\frac {\|\Delta b\|}{\|x\|}}+\|\Delta A\|\cdot \underbrace {\frac {\|x\|}{\|x\|}} _{=1}{\bigg )}.$

Beweis 4 - Fehlerabschätzung und Konditionszahl

Da $A\in GL(n,\mathbb {R} )$ regulär ist, gilt $\|A\|>0$. Durch Erweiterung des Ausdruck auf der rechten Seite der Ungleichung mit $\|A\|$ erhält man:

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

Beweis 5 - Fehlerabschätzung und Konditionszahl

Wegen $\|b\|\leq \|A\|\cdot \|x\|$ wird der Nenner nach unten und der Ausdruck aus Beweisschritt 4 weiter nach oben abgeschätzt und man erhält

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

Beweis 6 - Fehlerabschätzung und Konditionszahl

Wegen $\|\Delta A\|=\|A\|\cdot {\frac {\|\Delta A\|}{\|A\|}}$ sowohl im Zähler als auch im Nenner die Konditionszahl der Matrix $A$ und damit die Behauptung:

${\frac {\|\Delta x\|}{\|x\|}}\leq {\frac {\overbrace {\|A\|\cdot \|A^{-1}\|} ^{=\operatorname {cond} (A)}}{1-\underbrace {\|A^{-1}\|\cdot \|A\|} _{=\operatorname {cond} (A)}\cdot {\frac {\|\Delta A\|}{\|A\|}}}}\cdot \left({\frac {\|\Delta b\|}{\|b\|}}+{\frac {\|\Delta A\|}{\|A\|}}\right).$

q.e.d.

Bemerkung 1

Das Resultat liefert also eine Abschätzung des relativen Fehlers ${\frac {\|\Delta x\|}{\|x\|}}$ einer Lösung $x\in \mathbb {R} ^{n}$ des Gleichungssystems $Ax=b$ nach oben gegen eine Ausdruck, der

• von der Konditionszahl der Matrix $A$ und
• von relativen Fehler der Matrix $A$ und des relativen Fehlers des Vektors $b$

abhängt.

Bemerkung 2

Der Nenner in der Konstanten auf der rechten Seite in obigen Gleichung wird manchmal auch in der Form $1-\|A^{-1}\|\cdot \|\Delta A\|$ geschrieben.

Aufgabe - Tabellekalkulation

Berechnen Sie näherungsweise die induzierte Matrixnorm für eine beliebige $2\times 2$-Matrix $A\in \mathbb {R} ^{2\times 2}$ bzgl. der euklischen Norm.

$\|x\|=\left\|\left({\begin{array}{c}x_{1}\\x_{2}\end{array}}\right)\right|:={\sqrt {x_{1}^{2}+x-2^{2}}}$. Ferner sei $Ax=b=\left({\begin{array}{c}b_{1}\\b_{2}\end{array}}\right)$

• Berechnen Sie fehlende Spalteneinträge in E und F und bestimmen Sie dann in LibreOffice-Calc das Maximum aus Spalte G.

näherungsweise Berechnung - induzierte Matrixnorm

(A) k	(B) Winkel	(C)$x_{1}$	(D)$x_{2}$	(E)$b_{1}$	(F)$b_{2}$	(G)$\|Ax\|$
1	$2\pi \cdot {\frac {1}{n}}$	=cos(B2)	=sin(C2)	...	...	...
2	$2\pi \cdot {\frac {2}{n}}$	=cos(B2)	=sin(C2)	...	...	...
...	...	...	...	...	...	...
n	$2\pi \cdot {\frac {n}{n}}$	=cos(B$n+1$)	=sin(C$n+1$)	...	...	...

• Überprüfen Sie in der Tabellenkalkulation, ob die Determinante der Matrix von 0 verschieden ist.
• Berechnen Sie mit der Tabellenkalkulation die inverse Matrix von A, unter der Bedingung, dass die Matrix $A$ invertierbar ist.
• Berechnen Sie dann die Konditionszahl $cond(A)$ der Matrix $A$!
• Wählen Sie $\Delta A$ und $\Delta b$ und schätzen Sie den Fehler mit der Störungsresultaten ab!

Siehe auch

• Normen, Metriken, Topologie
• Besonderheiten des numerischen Rechnens
• Matrixnorm und Spektrum
• Konditionszahl einer Matrix
• Diskretisierung des Vektorraumes
• Relativer Fehler und absoluter Fehler
• Übergangsmatrizen und Markow-Ketten

Seiteninformation

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

Wiki2Reveal

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%20I/St%C3%B6rungsresultate%20f%C3%BCr%20Matrizen
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.