a  posteriori Error bounds

Theorem 8.5.1   If $A\in \hbox{{\sf I}\kern-.4em\hbox{\sf C}}^{n\times n}$ is such that $X^{-1}AX=\, {\rm diag}\, [\lambda _i]$, where X is the matrix whose columns are the eigenvectors of A then there is at least one value of i for which

$$\vert\lambda _i-\lambda \vert\leq \kappa _2(A)\frac{\left\Ver... ...\kern.05em \mbox{\boldmath$ x $ } \kern.05em \right\Vert _2},$$

where $\kappa _2(A)=\left\Vert \kern.05em X^{-1} \kern.05em \right\Vert _2\left\Vert \kern.05em X \kern.05em \right\Vert _2$ is the spectral condition number of A, $\mbox{\boldmath$\space \eta $ } =A\mbox{\boldmath$\space x $ } -\lambda \mbox{\boldmath$\space x $ }$, $\mbox{\boldmath$\space x $ } \not= \mbox{\bf0}$.

Remark: We can think of $\frac{\left\Vert \kern.05em \mbox{\boldmath$\space \eta $ } \kern.05em \right\V... ...{\left\Vert \kern.05em \mbox{\boldmath$\space x $ } \kern.05em \right\Vert _2}$ as a sort of relative residual error; the closeness of $\lambda$to an eigenvalue of A again depends on the spectral condition number.Proof.  We have

$$\mbox{\boldmath$ \eta $ } =(A-\lambda I)\mbox{\boldmath$ x $ ... ...m diag}\, [\lambda _i-\lambda ]X^{-1}\mbox{\boldmath$ x $ } .$$

If $\lambda _i\not= \lambda$ then

$$\begin{eqnarray*}\mbox{\boldmath$ x $ } & = & X\, {\rm diag}\, [\lambda _i-\lamb... ... \kern.05em \mbox{\boldmath$ x $ } \kern.05em \right\Vert _2}. \end{eqnarray*}$$

If $\lambda _i= \lambda$ for some value of i, this result is trivially true, hence the theorem is proved. The theorem gives a disc of radius $\kappa _2(A)\frac{\left\Vert \kern.05em \mbox{\boldmath$\space \eta $ } \kern... ...}{\left\Vert \kern.05em \mbox{\boldmath$\space x $ } \kern.05em \right\Vert _2}$ centred at an approximation $\lambda$, which contains an eigenvalue of A. Unfortunately, we do not usually know what the condition number is, except if A is Hermitian, when it takes the value 1.

Theorem 8.5.2   For a given matrix $A\in \hbox{{\sf I}\kern-.4em\hbox{\sf C}}^{n\times n}$ and a nonzero vector $\mbox{\boldmath$\space x $ } \in \hbox{{\sf I}\kern-.4em\hbox{\sf C}}^n$, $\left\Vert \kern.05em \mbox{\boldmath$\space \eta $ } \kern.05em \right\Vert _2... ...$\space x $ } -\lambda \mbox{\boldmath$\space x $ } \kern.05em \right\Vert _2$ is minimised when

$$\lambda =\lambda _R=\frac{\mbox{\boldmath$ x $ } ^*A\mbox{\bo... ...th$ x $ } }{\mbox{\boldmath$ x $ } ^*\mbox{\boldmath$ x $ } },$$

the Rayleigh Quotient.

Remark: This gives the best approximation to an eigenvalue, given an approximate eigenvector. Proof.  

$$\begin{eqnarray*}\left\Vert \kern.05em \mbox{\boldmath$ \eta $ } \kern.05em \rig... ...a -\lambda _R})\mbox{\boldmath$ x $ } ^*\mbox{\boldmath$ x $ } , \end{eqnarray*}$$

since $\mbox{\boldmath$\space x $ } ^*A\mbox{\boldmath$\space x $ } =\lambda _R\mbox{\boldmath$\space x $ } ^*\mbox{\boldmath$\space x $ }$ and $\mbox{\boldmath$\space x $ } ^*A^*\mbox{\boldmath$\space x $ } =(\mbox{\boldmat... ...^*=\bar{\lambda }_R\mbox{\boldmath$\space x $ } ^*\mbox{\boldmath$\space x $ }$.