The usual error analysis of the symmetric eigenproblem (using any LAPACK routine in subsection 2.2.4 or any EISPACK routine) is as follows [64]:

The computed eigendecomposition is nearly the exact eigendecomposition ofA+E, i.e., is a true eigendecomposition so that is orthogonal, where and . Herep(n) is a modestly growing function ofn. We takep(n) = 1 in the above code fragment. Each computed eigenvalue differs from a true by at mostThus large eigenvalues (those near ) are computed to high relative accuracy and small ones may not be.

The angular difference between the computed unit eigenvector and a true unit eigenvector satisfies the approximate bound

if is small enough. Here is the

absolute gapbetween and the nearest other eigenvalue. Thus, if is close to other eigenvalues, its corresponding eigenvector may be inaccurate. The gaps may be easily computed from the array of computed eigenvalues using subroutineSDISNA. The gaps computed bySDISNAare ensured not to be so small as to cause overflow when used as divisors.Let be the invariant subspace spanned by a collection of eigenvectors , where is a subset of the integers from 1 to

n. LetSbe the corresponding true subspace. Thenis the absolute gap between the eigenvalues in and the nearest other eigenvalue. Thus, a cluster of close eigenvalues which is far away from any other eigenvalue may have a well determined invariant subspace even if its individual eigenvectors are ill-conditioned.

In the special case of a real symmetric tridiagonal matrix `T`, the eigenvalues
and eigenvectors can be computed much more accurately. xSYEV (and the other
symmetric eigenproblem drivers) computes the eigenvalues and eigenvectors of
a dense symmetric matrix by first reducing it to tridiagonal form `T`, and then
finding the eigenvalues and eigenvectors of `T`.
Reduction of a dense matrix to tridiagonal form `T` can introduce
additional errors, so the following bounds for the tridiagonal case do not
apply to the dense case.

The eigenvalues ofTmay be computed with small componentwise relative backward error () by using subroutine xSTEBZ (subsection 2.3.4) or driver xSTEVX (subsection 2.2.4). IfTis also positive definite, they may also be computed at least as accurately by xPTEQR (subsection 2.3.4). To compute error bounds for the computed eigenvalues we must make some assumptions aboutT. The bounds discussed here are from [13]. SupposeTis positive definite, and writeT=DHDwhere and . Then the computed eigenvalues can differ from true eigenvalues bywhere

p(n) is a modestly growing function ofn. Thus if is moderate, each eigenvalue will be computed to high relative accuracy, no matter how tiny it is. The eigenvectors computed by xPTEQR can differ from true eigenvectors by at most aboutif is small enough, where is the

relative gapbetween and the nearest other eigenvalue. Since the relative gap may be much larger than the absolute gap, this error bound may be much smaller than the previous one.could be computed by applying xPTCON (subsection 2.3.1) to

H. The relative gaps are easily computed from the array of computed eigenvalues.

Jacobi's method [69][76][24] is another algorithm for finding eigenvalues and eigenvectors of symmetric matrices. It is slower than the algorithms based on first tridiagonalizing the matrix, but is capable of computing more accurate answers in several important cases. Routines implementing Jacobi's method and corresponding error bounds will be available in a future LAPACK release.

Tue Nov 29 14:03:33 EST 1994