Bauer–Fike theorem

The Bauer–Fike Theorem

Bauer–Fike Theorem. Let μ be an eigenvalue of A + δA. Then there exists λ ∈ Λ(A) such that:

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

Proof. We can suppose μ ∉ Λ(A), otherwise take λ = μ and the result is trivially true since κ_p(V) ≥ 1. Since μ is an eigenvalue of A + δA, we have det(A + δA − μI) = 0 and so

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

However our assumption, μ ∉ Λ(A), implies that: det(Λ − μI) ≠ 0 and therefore we can write:

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

This reveals −1 to be an eigenvalue of

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

Since all p-norms are consistent matrix norms we have |λ| ≤ ||A||_p where λ is an eigenvalue of A. In this instance this gives us:

${\displaystyle 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 (Λ − μI)⁻¹ is a diagonal matrix, the p-norm of which is easily computed:

${\displaystyle {\Vert {\left(\mathrm{\Lambda }-\mu I\right)}^{-1}\Vert }_p=\underset{\Vert \mathit{x}{\Vert }_p\ne 0}{max}\frac{{\Vert {\left(\mathrm{\Lambda }-\mu I\right)}^{-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:

${\displaystyle \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 A, but knows only an approximate eigenvalue-eigenvector couple, (λ^a, v^a) and needs to bound the error. The following version comes in help.

Bauer–Fike Theorem (Alternate Formulation). Let (λ^a, v^a) be an approximate eigenvalue-eigenvector couple, and r = Av^a − λ^av^a. Then there exists λ ∈ Λ(A) such that:

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

Proof. We can suppose λ^a ∉ Λ(A), otherwise take λ = λ^a and the result is trivially true since κ_p(V) ≥ 1. So (A − λ^aI)⁻¹ exists, so we can write:

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

since A is diagonalizable; taking the p-norm of both sides, we obtain:

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

However

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

is a diagonal matrix and its p-norm is easily computed:

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

whence:

${\displaystyle \underset{\lambda \in \lambda (A)}{min}\left|\lambda -{\lambda }^a\right|\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 A is invertible and that μ is an eigenvalue of A + δA. Then there exists λ ∈ Λ(A) such that:

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

Note. ||A⁻¹δA|| can be formally viewed as the relative variation of A, just as ⁠|λ − μ|/|λ|⁠ is the relative variation of λ.

Proof. Since μ is an eigenvalue of A + δA and det(A) ≠ 0, by multiplying by −A⁻¹ from left we have:

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

If we set:

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

then we have:

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

which means that 1 is an eigenvalue of A^a + (δA)^a, with v as an eigenvector. Now, the eigenvalues of A^a are ⁠μ/λ_i⁠, while it has the same eigenvector matrix as A. Applying the Bauer–Fike theorem to A^a + (δA)^a with eigenvalue 1, gives us:

${\displaystyle \underset{\lambda \in \mathrm{\Lambda }(A)}{min}\left|\frac{\mu }{\lambda }-1\right|=\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 A is normal, V is a unitary matrix, therefore:

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

so that κ₂(V) = 1. The Bauer–Fike theorem then becomes:

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

Or in alternate formulation:

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

which obviously remains true if A 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 A ↦ Λ(A) 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 C.