Bauer–Fike theorem

For the theorem in algebraic number theory, see Bauer's 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:

• A ∈ C^n,n is a diagonalizable matrix;
• V ∈ C^n,n is the non-singular eigenvector matrix such that A = VΛらむだV ⁻¹, where Λらむだ is a diagonal matrix.
• If X ∈ C^n,n is invertible, its condition number in p-norm is denoted by κかっぱ_p(X) and defined by:

$\kappa _{p}(X)=\|X\|_{p}\left\|X^{-1}\right\|_{p}.$

The Bauer–Fike Theorem

Bauer–Fike Theorem. Let μみゅー be an eigenvalue of A + δでるたA. Then there exists λらむだ ∈ Λらむだ(A) such that:

$|\lambda -\mu |\leq \kappa _{p}(V)\|\delta A\|_{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

${\begin{aligned}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(\Lambda +V^{-1}\delta AV-\mu I\right)\\&=\det(\Lambda -\mu I)\det \left((\Lambda -\mu I)^{-1}V^{-1}\delta AV+I\right)\\\end{aligned}}$

However our assumption, μみゅー ∉ Λらむだ(A), implies that: det(Λらむだ − μみゅーI) ≠ 0 and therefore we can write:

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

This reveals −1 to be an eigenvalue of

$(\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:

$1=|-1|\leq \left\|(\Lambda -\mu I)^{-1}V^{-1}\delta AV\right\|_{p}\leq \left\|(\Lambda -\mu I)^{-1}\right\|_{p}\left\|V^{-1}\right\|_{p}\|V\|_{p}\|\delta A\|_{p}=\left\|(\Lambda -\mu I)^{-1}\right\|_{p}\ \kappa _{p}(V)\|\delta A\|_{p}$

But (Λらむだ − μみゅーI)⁻¹ is a diagonal matrix, the p-norm of which is easily computed:

$\left\|\left(\Lambda -\mu I\right)^{-1}\right\|_{p}\ =\max _{\|{\boldsymbol {x}}\|_{p}\neq 0}{\frac {\left\|\left(\Lambda -\mu I\right)^{-1}{\boldsymbol {x}}\right\|_{p}}{\|{\boldsymbol {x}}\|_{p}}}=\max _{\lambda \in \Lambda (A)}{\frac {1}{|\lambda -\mu |}}\ ={\frac {1}{\min _{\lambda \in \Lambda (A)}|\lambda -\mu |}}$

whence:

$\min _{\lambda \in \Lambda (A)}|\lambda -\mu |\leq \ \kappa _{p}(V)\|\delta A\|_{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:

$\left|\lambda -\lambda ^{a}\right|\leq \kappa _{p}(V){\frac {\|{\boldsymbol {r}}\|_{p}}{\left\|{\boldsymbol {v}}^{a}\right\|_{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:

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

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

$\left\|{\boldsymbol {v}}^{a}\right\|_{p}=\left\|V\left(D-\lambda ^{a}I\right)^{-1}V^{-1}{\boldsymbol {r}}\right\|_{p}\leq \|V\|_{p}\left\|\left(D-\lambda ^{a}I\right)^{-1}\right\|_{p}\left\|V^{-1}\right\|_{p}\|{\boldsymbol {r}}\|_{p}=\kappa _{p}(V)\left\|\left(D-\lambda ^{a}I\right)^{-1}\right\|_{p}\|{\boldsymbol {r}}\|_{p}.$

However

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

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

$\left\|\left(D-\lambda ^{a}I\right)^{-1}\right\|_{p}=\max _{\|{\boldsymbol {x}}\|_{p}\neq 0}{\frac {\left\|\left(D-\lambda ^{a}I\right)^{-1}{\boldsymbol {x}}\right\|_{p}}{\|{\boldsymbol {x}}\|_{p}}}=\max _{\lambda \in \sigma (A)}{\frac {1}{\left|\lambda -\lambda ^{a}\right|}}={\frac {1}{\min _{\lambda \in \sigma (A)}\left|\lambda -\lambda ^{a}\right|}}$

whence:

$\min _{\lambda \in \lambda (A)}\left|\lambda -\lambda ^{a}\right|\leq \kappa _{p}(V){\frac {\|{\boldsymbol {r}}\|_{p}}{\left\|{\boldsymbol {v}}^{a}\right\|_{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:

${\frac {|\lambda -\mu |}{|\lambda |}}\leq \kappa _{p}(V)\left\|A^{-1}\delta A\right\|_{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:

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

If we set:

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

then we have:

$\left(A^{a}+(\delta A)^{a}-I\right){\boldsymbol {v}}={\boldsymbol {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:

$\min _{\lambda \in \Lambda (A)}\left|{\frac {\mu }{\lambda }}-1\right|=\min _{\lambda \in \Lambda (A)}{\frac {|\lambda -\mu |}{|\lambda |}}\leq \kappa _{p}(V)\left\|A^{-1}\delta A\right\|_{p}$

The Case of Normal Matrices

If A is normal, V is a unitary matrix, therefore:

$\|V\|_{2}=\left\|V^{-1}\right\|_{2}=1,$

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

$\exists \lambda \in \Lambda (A):\quad |\lambda -\mu |\leq \|\delta A\|_{2}$

Or in alternate formulation:

$\exists \lambda \in \Lambda (A):\quad \left|\lambda -\lambda ^{a}\right|\leq {\frac {\|{\boldsymbol {r}}\|_{2}}{\left\|{\boldsymbol {v}}^{a}\right\|_{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.

References

• Bauer, F. L.; Fike, C. T. (1960). "Norms and Exclusion Theorems". Numer. Math. 2 (1): 137–141. doi:10.1007/BF01386217. S2CID 121278235.
• Eisenstat, S. C.; Ipsen, I. C. F. (1998). "Three absolute perturbation bounds for matrix eigenvalues imply relative bounds". SIAM Journal on Matrix Analysis and Applications. 20 (1): 149–158. CiteSeerX 10.1.1.45.3999. doi:10.1137/S0895479897323282.