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

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

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 [93]: 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 [93]. This case is addressed either by re-biorthogonalization [105] or by not computing the Ritz vectors that correspond to spurious modes [93].

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 [354]. In [29] 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.