Perturbation lemma

In numerics, a perturbation lemma is a sentence that makes a statement about the norm of the inverse of a regular matrix for small perturbations.

statement

Let be a regular matrix and a matrix with ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ ${\displaystyle \delta A\in \mathbb {R} ^{n\times n}}$

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

in a sub-multiplicative matrix norm . Then the matrix is ​​also regular and the following applies to its inverse : ${\displaystyle \|\cdot \|}$ ${\displaystyle A+\delta A}$

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

proof

Be . Then applies ${\displaystyle T:=I-A^{-1}(A+\delta A)}$

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

So the Neumann series converges and is invertible. Since is invertible, it follows that is also invertible and ${\displaystyle \sum _{n=0}^{\infty }T^{n}}$ ${\displaystyle I-T=A^{-1}(A+\delta A)}$ ${\displaystyle A^{-1}}$ ${\displaystyle A+\delta A}$

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

use

This lemma is used to the condition number for solving systems of linear equations as

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

derive.

literature

• JW Demmel: Applied Numerical Linear Algebra . SIAM, Philadelphia 1997
• A. Kielbasinski and H. Schwetlick: Numerical linear algebra . Deutscher Verlag der Wissenschaften, 1988, ISBN 3-326-00194-0