     Next: Multiple Eigenvalues. Up: Lanczos Method   Z. Bai Previous: Algorithm   Contents   Index

## Convergence Properties

In this section, we discuss convergence properties in detail. First the SI is reviewed in the context of the Lanczos algorithm. Next a convergence theory of two-sided algorithms for nonsymmetric eigenvalue problems is outlined with reference to other sections of this work. Finally techniques are reviewed to cope with the unavailability of normalized residuals.

The Ritz values tend to converge first to eigenvalues at the boundary of the convex hull of the spectrum. To compute interior eigenvalues it is often worthwhile to apply a spectral transformation to . The strategy is to accelerate the convergence rate by mapping the desired eigenvalues in the complex plane to the exterior of the transformed spectrum. The standard approach is to apply the Lanczos algorithm to the shifted and inverted matrix (150)

Eigenvalues in the complex plane nearest the shift converge first. Note that the LU factorization, (151)

can be used to compute both and as required in the Lanczos algorithm. See §10.3.

An inherent difficulty of a NHEP is that the known bounds on the distance from to an eigenvalue of are not practical to compute [425,256]. Another complication is that, to be of use, a convergence theory for two-sided algorithms must account for the fact that the left and right Krylov subspaces simultaneously approximate eigenvalues of . These two problems are resolved by bounding the distance, , to the nearest matrix, , with eigentriplet . Eigenvalue sensitivities (condition numbers) are also available. Recall that residual vectors and as defined in (7.40) and (7.41). Next observe that the biorthogonality condition (7.37) implies that . Together these relations imply that (152)

is the desired perturbation such that   (153)   (154)

and . See §7.13 for further discussion on how to derive estimated error bounds on the accuracy of approximate eigenvalues and eigenvectors to the exact eigenvalues and eigenvectors of .

There is a subtle yet critical complication concerning testing the Ritz vectors for convergence. The approximate eigenvectors of the original matrix are only calculated after the test in step (16) suggests the convergence of Ritz values to the desired eigenvalues of . If the Lanczos vectors are stored, then the bases and are used to get the approximate eigenvectors. If the Lanczos vectors are not stored, then there are two possibilities : one either reruns the three-term recurrences to generate the requested eigenvectors, or applies inverse iteration (see §7.4). The complication is that the decision whether or not to accept a Ritz vector as an approximate eigenvector cannot be based on these unnormalized residuals. After and are computed, it is necessary to compare the normalized residuals to user-specified tolerance. Normalized residuals can be larger in norm than the un-normalized residuals. It may be necessary to reject the computed Ritz vectors, continue the Lanczos algorithm, and then recompute the Ritz vectors. The Ritz vector is rejected if is significantly smaller than . There are two common causes for this shrinkage. The first is that due to the loss of biorthogonality, is a spurious eigenvalue . This case is addressed either by re-biorthogonalization  or by not computing the Ritz vectors that correspond to spurious modes .

The second common cause of shrinkage is best explained in terms of implementations of the Lanczos algorithm in which and are scaled to have unit Euclidean length [179,354,105]. The inner products bound the condition numbers of the matrices of Lanczos vectors . In  it was shown that where denotes the generalized inverse of and the bound also applies to . The right Krylov subspace is nearly invariant if is tiny relative to the product of the tridiagonal norm (which is easy to estimate) and . In this scaling, the bound simplifies the detection of invariant subspaces.

It is common for to decrease nearly monotonically and by many orders of magnitude over hundreds of Lanczos steps [179,105]. And in this case the unnormalized residuals are poor estimates for Ritz values that do not appear until after has decreased by several orders of magnitude. More precisely, for eigenvectors with the special property that is negligible, the lower bound is likely to be nearly an equality, and if is extremely small, then forming is discouraged.

Subsections     Next: Multiple Eigenvalues. Up: Lanczos Method   Z. Bai Previous: Algorithm   Contents   Index
Susan Blackford 2000-11-20