next up previous contents index
Next: Error Bound for Computed Up: Stability and Accuracy Assessments Previous: Transfer Residual Error to   Contents   Index


Error Bounds for Computed Eigenvalues.

For the Hermitian eigenproblem, the $i$th largest eigenvalue of $A$ differs from the $i$th largest eigenvalue of $A+E$ by at most $\Vert E\Vert _2$. Therefore a small backward error implies a small (forward) error in the computed eigenvalue, i.e.,
\begin{displaymath}
\vert\wtd\lambda-\lambda\vert \le \Vert E_2\Vert _2=\Vert r\Vert _2
\end{displaymath} (63)

for some eigenvalue $\lambda$ of $A$.

With more information, a better error bound can be obtained. Let us assume that $(\wtd\lambda,\wtd x)$ is an approximation of the eigenpair $(\lambda,x)$ of $A$. The ``best'' $\wtd\lambda$ corresponding to $\wtd x$ is the Rayleigh quotient $\wtd\lambda = \wtd x^{\ast} A \wtd x$, so we assume that $\wtd\lambda$ has this value. Suppose that $\wtd\lambda$ is closer to $\lambda$ than any other eigenvalues of $A$, and let $\delta$ be the gap between $\wtd\lambda$ and any other eigenvalue: $\delta = \min_{\lambda_j \neq \lambda} \vert \wtd\lambda - \lambda_j \vert$. Then we have

\begin{displaymath}
\vert\wtd\lambda-\lambda\vert \le \frac {\Vert r\Vert _2^2}{\delta}.
\end{displaymath} (64)

This improves (4.54) if the gap $\delta$ is reasonably big. In practice we can always pick the better one.

Note that (4.55) needs information on $\delta$, besides the residual error $r$. Usually such information is available after a successful computation by, e.g., a Lanczos algorithm with SI, which usually delivers eigenvalues in the neighborhood of a shift and consequently yields good information on $\delta$. This comment also applies to the bound in (4.56) below.


next up previous contents index
Next: Error Bound for Computed Up: Stability and Accuracy Assessments Previous: Transfer Residual Error to   Contents   Index
Susan Blackford 2000-11-20