Bauer–Fike theorem

In mathematics, the Bauer–Fike theorem is a standard result in the perturbation theory of the eigenvalue of a complex-valued diagonalizable matrix. In its substance, it states an absolute upper bound for the deviation of one perturbed matrix eigenvalue from a properly chosen eigenvalue of the exact matrix. Informally speaking, what it says is that the sensitivity of the eigenvalues is estimated by the condition number of the matrix of eigenvectors.

The theorem was proved by Friedrich L. Bauer and C. T. Fike in 1960.

The setup

In what follows we assume that:

• Template:Math is a diagonalizable matrix;
• Template:Math is the non-singular eigenvector matrix such that Template:Math, where Template:Math is a diagonal matrix.
• If Template:Math is invertible, its condition number in [[matrix norm|Template:Mvar-norm]] is denoted by Template:Math and defined by:

${\kappa }_p(X)=\Vert X{\Vert }_p{\Vert X^{-1}\Vert }_p.$

The Bauer–Fike Theorem

Bauer–Fike Theorem. Let Template:Mvar be an eigenvalue of Template:Math. Then there exists Template:Math such that:

$|\lambda -\mu |\le {\kappa }_p(V)\Vert \delta A{\Vert }_p$

Proof. We can suppose Template:Math, otherwise take Template:Math and the result is trivially true since Template:Math. Since Template:Mvar is an eigenvalue of Template:Math, we have Template:Math and so

$\begin{array}{rl}0& =\det (A+\delta A-\mu I)\\ & =\det (V^{-1})\det (A+\delta A-\mu I)\det (V)\\ & =\det (V^{-1}(A+\delta A-\mu I)V)\\ & =\det (V^{-1}AV+V^{-1}\delta AV-V^{-1}\mu IV)\\ & =\det (\mathrm{\Lambda }+V^{-1}\delta AV-\mu I)\\ & =\det (\mathrm{\Lambda }-\mu I)\det ((\mathrm{\Lambda }-\mu I{)}^{-1}{V}^{-1}\delta AV+I)\\ \end{array}$

However our assumption, Template:Math, implies that: Template:Math and therefore we can write:

$\det ((\mathrm{\Lambda }-\mu I{)}^{-1}{V}^{-1}\delta AV+I)=0.$

This reveals Template:Math to be an eigenvalue of

$(\mathrm{\Lambda }-\mu I{)}^{-1}{V}^{-1}\delta AV.$

Since all Template:Mvar-norms are consistent matrix norms we have Template:Math where Template:Mvar is an eigenvalue of Template:Mvar. In this instance this gives us:

$1=|-1|\le {\Vert (\mathrm{\Lambda }-\mu I{)}^{-1}{V}^{-1}\delta AV\Vert }_p\le {\Vert (\mathrm{\Lambda }-\mu I{)}^{-1}\Vert }_p{\Vert V^{-1}\Vert }_p\Vert V{\Vert }_p\Vert \delta A{\Vert }_p={\Vert (\mathrm{\Lambda }-\mu I{)}^{-1}\Vert }_p{\kappa }_p(V)\Vert \delta A{\Vert }_p$

But Template:Math is a diagonal matrix, the Template:Mvar-norm of which is easily computed:

${\Vert {(\mathrm{\Lambda }-\mu I)}^{-1}\Vert }_p=\underset{\Vert \mathit{x}{\Vert }_p\ne 0}{\max }\frac{{\Vert {(\mathrm{\Lambda }-\mu I)}^{-1}\mathit{x}\Vert }_p}{\Vert \mathit{x}{\Vert }_p}=\underset{\lambda \in \mathrm{\Lambda }(A)}{\max }\frac{1}{|\lambda -\mu |}=\frac{1}{\underset{\lambda \in \mathrm{\Lambda }(A)}{\min }|\lambda -\mu |}$

whence:

$\underset{\lambda \in \mathrm{\Lambda }(A)}{\min }|\lambda -\mu |\le {\kappa }_p(V)\Vert \delta A{\Vert }_p.$

An Alternate Formulation

The theorem can also be reformulated to better suit numerical methods. In fact, dealing with real eigensystem problems, one often has an exact matrix Template:Mvar, but knows only an approximate eigenvalue-eigenvector couple, Template:Math and needs to bound the error. The following version comes in help.

Bauer–Fike Theorem (Alternate Formulation). Let Template:Math be an approximate eigenvalue-eigenvector couple, and Template:Math. Then there exists Template:Math such that:

$|\lambda -{\lambda }^a|\le {\kappa }_p(V)\frac{\Vert \mathit{r}{\Vert }_p}{{\Vert {\mathit{v}}^a\Vert }_p}$

Proof. We can suppose Template:Math, otherwise take Template:Math and the result is trivially true since Template:Math. So Template:Math exists, so we can write:

${\mathit{v}}^a={(A-{\lambda }^{a}I)}^{-1}\mathit{r}=V{(D-{\lambda }^{a}I)}^{-1}{V}^{-1}\mathit{r}$

since Template:Mvar is diagonalizable; taking the Template:Mvar-norm of both sides, we obtain:

${\Vert {\mathit{v}}^a\Vert }_p={\Vert V{(D-{\lambda }^{a}I)}^{-1}{V}^{-1}\mathit{r}\Vert }_p\le \Vert V{\Vert }_p{\Vert {(D-{\lambda }^{a}I)}^{-1}\Vert }_p{\Vert V^{-1}\Vert }_p\Vert \mathit{r}{\Vert }_p={\kappa }_p(V){\Vert {(D-{\lambda }^{a}I)}^{-1}\Vert }_p\Vert \mathit{r}{\Vert }_p.$

However

${(D-{\lambda }^{a}I)}^{-1}$

is a diagonal matrix and its Template:Mvar-norm is easily computed:

${\Vert {(D-{\lambda }^{a}I)}^{-1}\Vert }_p=\underset{\Vert \mathit{x}{\Vert }_p\ne 0}{\max }\frac{{\Vert {(D-{\lambda }^{a}I)}^{-1}\mathit{x}\Vert }_p}{\Vert \mathit{x}{\Vert }_p}=\underset{\lambda \in \sigma (A)}{\max }\frac{1}{|\lambda -{\lambda }^a|}=\frac{1}{\underset{\lambda \in \sigma (A)}{\min }|\lambda -{\lambda }^a|}$

whence:

$\underset{\lambda \in \lambda (A)}{\min }|\lambda -{\lambda }^a|\le {\kappa }_p(V)\frac{\Vert \mathit{r}{\Vert }_p}{{\Vert {\mathit{v}}^a\Vert }_p}.$

A Relative Bound

Both formulations of Bauer–Fike theorem yield an absolute bound. The following corollary is useful whenever a relative bound is needed:

Corollary. Suppose Template:Mvar is invertible and that Template:Mvar is an eigenvalue of Template:Math. Then there exists Template:Math such that:

$\frac{|\lambda -\mu |}{|\lambda |}\le {\kappa }_p(V){\Vert A^{-1}\delta A\Vert }_p$

Note. Template:Math can be formally viewed as the relative variation of Template:Mvar, just as Template:Math is the relative variation of Template:Mvar.

Proof. Since Template:Mvar is an eigenvalue of Template:Math and Template:Math, by multiplying by Template:Math from left we have:

$-A^{-1}(A+\delta A)\mathit{v}=-\mu A^{-1}\mathit{v}.$

If we set:

$A^a=\mu A^{-1},(\delta A{)}^a=-A^{-1}\delta A$

then we have:

$(A^a+(\delta A{)}^a-I)\mathit{v}=\mathit{0}$

which means that Template:Math is an eigenvalue of Template:Math, with Template:Math as an eigenvector. Now, the eigenvalues of Template:Math are Template:Math, while it has the same eigenvector matrix as Template:Mvar. Applying the Bauer–Fike theorem to Template:Math with eigenvalue Template:Math, gives us:

$\underset{\lambda \in \mathrm{\Lambda }(A)}{\min }|\frac{\mu }{\lambda }-1|=\underset{\lambda \in \mathrm{\Lambda }(A)}{\min }\frac{|\lambda -\mu |}{|\lambda |}\le {\kappa }_p(V){\Vert A^{-1}\delta A\Vert }_p$

The Case of Normal Matrices

If Template:Mvar is normal, Template:Mvar is a unitary matrix, therefore:

$\Vert V{\Vert }_2={\Vert V^{-1}\Vert }_2=1,$

so that Template:Math. The Bauer–Fike theorem then becomes:

$\mathrm{\exists }\lambda \in \mathrm{\Lambda }(A):|\lambda -\mu |\le \Vert \delta A{\Vert }_2$

Or in alternate formulation:

$\mathrm{\exists }\lambda \in \mathrm{\Lambda }(A):|\lambda -{\lambda }^a|\le \frac{\Vert \mathit{r}{\Vert }_2}{{\Vert {\mathit{v}}^a\Vert }_2}$

which obviously remains true if Template:Mvar is a Hermitian matrix. In this case, however, a much stronger result holds, known as the Weyl's theorem on eigenvalues. In the hermitian case one can also restate the Bauer–Fike theorem in the form that the map Template:Math that maps a matrix to its spectrum is a non-expansive function with respect to the Hausdorff distance on the set of compact subsets of Template:Math.