2.4. Fehlerabschätzung bei der Lösung linearer Gleichungssysteme

Im Folgenden wollen wir verstehen, wie sich Fehler in den Eingabedaten auf die echte Lösung \(x\) linearer Gleichungssysteme der Form \(Ax = b\) mit \(A\in\mathbb{R}^{n \times n}\) und \(b,x \in \mathbb{R}^n\) auswirken. Wir betrachten \(\tilde A \tilde x \ = \ \tilde b\) als ein gestörtes lineares Gleichungssystem von \(Ax=b\) und wollen eine Abschätzung für die Abweichung \(\tilde x - x\) herleiten. Zu den Störungen betrachten wir jeweils

• \(\Delta_x := \tilde{x} - x\in \R^n\) die Störung in der Lösung \(x\),

• \(\Delta_b := \tilde{b} - b \in \R^n\) die Störung in \(b\),

• \(\Delta_A := \tilde{A} - A\in \R^{n \times n}\) die Störung in \(A\).

Dabei ist einerseits der absolute Fehler

\[\delta_x^{\text{abs}} \ \coloneqq \ \norm{\tilde{x}-x} \ = \ \norm{\Delta_x} \in \mathbb{R}^+_0\]

interessant, jedoch sucht man meist aber eine Abschätzung für den relativen Fehler

\[\begin{aligned} \delta_x^{\text{rel}} \ \coloneqq \ \frac{\norm{\Delta_x}}{\Vert x \Vert} \ = \ \frac{\delta_x^{\text{abs}}}{\Vert x \Vert} \in \mathbb{R}^+_0. \end{aligned}\]

Satz 2.4 (Fehlerabschätzung für das gestörte LGS)

Sei \(A \in \R^{n\times n}\) eine reguläre Matrix und \(\Delta_A \in \R^{n\times n}\) eine Störung von \(A\), so dass \(||A^{-1}\Delta_A|| < 1\) gilt und die gestörte Matrix \(\tilde{A} \in \R^{n \times n}\) noch regulär ist.

Betrachten wir das exakte und das gestörte lineare Gleichungssystem

\[Ax \ = \ b, \qquad \tilde{A} \tilde{x} \ = \ \tilde{b},\]

für \(x,\tilde{x},b,\tilde{b}\in\R^n\), so gilt für den absoluten Fehler,

\[\begin{aligned} \delta_x^{\text{abs}} \ \leq \ \frac{\Vert A^{-1} \Vert}{1- \Vert A^{-1} \Vert \cdot \norm{\Delta_A}} (\norm{\Delta_A} \cdot \Vert x \Vert + \norm{\Delta_b}) \end{aligned}\]

und für den relativen Fehler,

(2.7)\[\begin{aligned} \delta_x^{\text{rel}}\ \leq \ \frac{\kappa(A)}{1- \kappa(A) \cdot \frac{\norm{\Delta_A}}{\Vert A \Vert}} \left( \frac{\norm{\Delta_A}}{\norm{A}} + \frac{\norm{\Delta_b}}{ \Vert b \Vert} \right). \end{aligned}\]

Proof. Es gilt zunächst

\[\begin{aligned} \tilde A (x - \tilde x) \ = \ \tilde A x - \tilde A \tilde x \ = \ \tilde A x - Ax + Ax - \tilde{b} \ = \ \Delta_A x - \Delta_b . \end{aligned}\]

Da die gestörte Matrix \(\tilde A \in \mathbb{R}^{n \times n}\) regulär ist erhalten wir auf Grund der Submultiplikativität der Matrixnorm

(2.8)\[\norm{x - \tilde x} \ = \ \norm{\tilde A^{-1} \big( \Delta_A x - \Delta_b \big)} \ \leq \ \Vert \tilde A^{-1} \Vert \cdot \Vert \Delta_A x - \Delta_b \Vert.\]

Um \(\norm{\tilde{A}^{-1}}\) abzuschätzen, betrachten wir zunächst die folgende Identität,

\[\norm{(I-A^{-1}(A - \tilde A))^{-1} A^{-1}} \ = \ \norm{(I - I + A^{-1}\tilde A)^{-1} A^{-1}} \ = \ \norm{\tilde A^{-1}}.\]

Durch Anwendung des Satzes über die Neumannsche Reihe in Satz 2.2 und wegen der Submultiplikativität der Matrixnorm erhalten wir somit die folgende Abschätzung

\[\begin{aligned} \Vert \tilde A^{-1} \Vert &\leq \ \Vert (I+A^{-1}\Delta_A)^{-1} \Vert \cdot \Vert A^{-1} \Vert \\ \ &\leq \ \frac{\Vert A^{-1} \Vert}{1- \norm{A^{-1}\Delta_A}} \ \leq \ \frac{\Vert A^{-1} \Vert}{1- \Vert A^{-1} \Vert \cdot \Vert \Delta_A \Vert} . \end{aligned}\]

Eingesetzt in (2.8) folgt nun insgesamt die Abschätzung für den absoluten Fehler,

\[\begin{aligned} \delta_x^{\text{abs}} \ = \ \Vert x - \tilde x \Vert \ \leq \ \frac{\Vert A^{-1} \Vert}{1- \Vert A^{-1} \Vert \cdot \norm{\Delta_A}} (\norm{\Delta_A} \cdot \Vert x \Vert + \norm{\Delta_b}). \end{aligned}\]

Wir dividieren nun durch die Norm von \(x\) und erweitern außerdem den Bruch um \(\Vert A \Vert\) und erhalten

\[\begin{aligned} \frac{\Vert x - \tilde x \Vert}{\Vert x \Vert} \ &\leq \ \frac{\Vert A^{-1} \Vert}{1- \Vert A^{-1} \Vert \cdot \norm{\Delta_A}} \cdot \frac{\norm{\Delta_A} \cdot \Vert x \Vert + \norm{\Delta_b}}{\Vert x \Vert} \cdot \frac{\Vert A \Vert}{\Vert A \Vert}\\ \ &= \ \frac{\Vert A \Vert \cdot \Vert A^{-1} \Vert}{1- \Vert A^{-1} \Vert \cdot \norm{\Delta_A}} \left( \frac{\norm{\Delta_A}}{\Vert A \Vert} + \frac{\norm{\Delta_b}}{\Vert A \Vert \cdot \Vert x \Vert} \right). \end{aligned}\]

Mit \(\Vert b \Vert = \Vert Ax \Vert \leq \Vert A \Vert \cdot \Vert x \Vert\) folgern wir nun die zentrale Abschätzung des relativen Fehlers in \(x\) durch den relativen Fehler in \(A\) und \(b\), denn es gilt

\[\delta_x^{\text{rel}} \ = \ \frac{\Vert x - \tilde x \Vert}{\Vert x \Vert} \ \leq \ \frac{\kappa(A)}{1- \kappa(A) \cdot \frac{\norm{\Delta_A}}{\Vert A \Vert}} \left( \frac{\norm{\Delta_A}}{\norm{A}} + \frac{\norm{\Delta_b}}{ \Vert b \Vert} \right).\]

◻

Wir sehen, dass die Konditionszahl \(\kappa(A)\) der Matrix \(A\) die entscheidende Konstante für die Abschätzung des relativen Fehlers ist. Ist die Konditionszahl nahe der Eins und der relative Fehler in der Matrix nicht zu groß, dann wird der relative Fehler in den Daten nur gering verstärkt.

Ist hingegen die Konditionszahl groß, so ist zunächst der erlaubte relative Fehler in der Matrix, der Regularität erhält, sehr klein (siehe auch der Nenner in der Abschätzung). Darüber hinaus wird auch die Fehlerverstärkung im Zähler signifikant. Dies gilt auch, wenn keine Störung der Matrix \(A\) vorliegt, denn in diesem Fall erhalten wir aus (2.7) die kompakte Abschätzung:

\[\delta_x^{\text{rel}} \ = \ \frac{\Vert x - \tilde x \Vert}{\Vert x \Vert} \ \leq \ {\kappa(A)} \cdot \frac{\norm{\Delta_b}}{ \Vert b \Vert} .\]