Störungslemma

Als Störungslemma bezeichnet man in der Numerik einen Satz, der eine Aussage über die Norm der Inversen einer regulären Matrix bei kleinen Störungen macht.

Aussage

Sei ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ eine reguläre Matrix und ${\displaystyle \delta A\in \mathbb {R} ^{n\times n}}$ eine Matrix mit

${\displaystyle \|A^{-1}\|\cdot \|\delta A\|<1}$

in einer submultiplikativen Matrixnorm ${\displaystyle \|\cdot \|}$. Dann ist auch die Matrix ${\displaystyle A+\delta A}$ regulär und es gilt für ihre Inverse:

${\displaystyle \|(A+\delta A)^{-1}\|\leq {\frac {\|A^{-1}\|}{1-\|A^{-1}\|\|\delta A\|}}.}$

Beweis

Sei ${\displaystyle T:=I-A^{-1}(A+\delta A)}$. Dann gilt

${\displaystyle \|T\|=\|A^{-1}\cdot \delta A\|\leq \|A^{-1}\|\cdot \|\delta A\|<1}$

Also konvergiert die Neumann-Reihe ${\displaystyle \sum _{n=0}^{\infty }T^{n}}$ und ${\displaystyle I-T=A^{-1}(A+\delta A)}$ ist invertierbar. Da ${\displaystyle A^{-1}}$ invertierbar ist, folgt, dass auch ${\displaystyle A+\delta A}$ invertierbar ist und

${\displaystyle \|(A+\delta A)^{-1}\|=\|(I-T)^{-1}A^{-1}\|\leq \|A^{-1}\|\sum _{n=0}^{\infty }\|T^{n}\|\leq {\frac {\|A^{-1}\|}{1-\|A^{-1}\|\|\delta A\|}}}$

Verwendung

Dieses Lemma wird verwendet, um die Konditionszahl für das Lösen linearer Gleichungssysteme als

${\displaystyle \kappa (A)=\|A\|\cdot \|A^{-1}\|}$

herzuleiten.

Literatur

• J. W. Demmel: Applied Numerical Linear Algebra. SIAM, Philadelphia 1997
• A. Kielbasinski und H. Schwetlick: Numerische lineare Algebra. Deutscher Verlag der Wissenschaften, 1988, ISBN 3-326-00194-0