Further Details: Error Bounds for the Symmetric Eigenproblem

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

The computed eigendecomposition is nearly the exact eigendecomposition of, i.e., is a true eigendecomposition so that is orthogonal, where and . HereA+Eis a modestly growing function ofp(n). We takenin the above code fragment. Each computed eigenvalue differs from a true by at mostp(n)=1

Thus large eigenvalues (those near ) are computed to high relative accuracy and small ones may not be.

There are two questions to ask about the computed eigenvectors: ``Are they orthogonal?'' and ``How much do they differ from the true eigenvectors?'' The answer to the first question is that except for eigenvectors computed by computational routine xSTEIN (which is called by drivers with names ending in -EVX when only a subset of the eigenvalues and eigenvectors are requested), the computed eigenvectors are always nearly orthogonal to working precision, independent of how much they differ from the true eigenvectors. In other words

for . xSTEIN almost always returns orthogonal eigenvectors, but can occasionally fail when eigenvalues are tightly clustered.

Here is the answer to the second question about eigenvectors. The angular difference between the computed unit eigenvector and a true unit eigenvectorsatisfies the approximate boundz_{i}

if is small enough. Here is theabsolute gapbetween and the nearest other eigenvalue. Thus, if is close to other eigenvalues, its corresponding eigenvectormay be inaccurate. The gaps may be easily computed from the array of computed eigenvalues using subroutinez_{i}SDISNA. 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. Let be the corresponding true subspace. Thenn

where

is 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^{4.3}.

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

The eigenvalues ofmay be computed with small componentwise relative backward error () by using subroutine xSTEBZ (subsection 2.4.4) or driver xSTEVX (subsection 2.3.4). IfTis also positive definite, they may also be computed at least as accurately by xPTEQR or xSTEGR (subsection 2.4.4). To compute error bounds for the computed eigenvalues we must make some assumptions aboutT. The bounds discussed here are from [14]. SupposeTis positive definite, and writeTwhere andT=DHD. Then the computed eigenvalues can differ from true eigenvalues byh_{ii}= 1

whereis a modestly growing function ofp(n). 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 eigenvectorsnby at most aboutz_{i}

if is small enough, where is therelative 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. Independent of the difference between the computed and true eigenvectors, the computed eigenvectors are orthogonal to nearly full precision, i.e. for .

could be computed by applying xPTCON (subsection 2.4.1) to. The relative gaps are easily computed from the array of computed eigenvalues.H