As mentioned, Algorithm 11.1 does not allow updates of the zero of the Cayley transform without a complete restart. We now describe the Davidson method, which by contrast updates the zero in each iteration.
The Davidson method [99] was developed to solve quantum chemistry
problems in which the matrices have diagonal elements that are both large
and varying in
magnitude. It was originally derived as a perturbation method. Given an
approximate eigenvector, a correction is developed. In [335],
the Davidson
method was viewed as a diagonal preconditioning method and was
generalized
for other preconditioners. We now give an algorithm. The vector
is a correction to the approximate eigenvector
. The
preconditioner is left unspecified, but for Davidson's original method, the
choice is
We next discuss the asymptotic convergence of the Davidson method.
Observe
that if and
were fixed, the Davidson method would develop a
Krylov subspace generated with the operator
. So
once a Ritz pair begins to converge to an eigenpair, say
,
then the subspace generated from that point is approximately the same as
a Krylov subspace generated by
.
has the correct eigenvector, namely
, and the
corresponding eigenvalue of
is 0.
If the other eigenvalues of
are compressed
around
by the preconditioning, then
will be well separated and
convergence rapid.
An important question is whether in practice the spectrum of
is
really
an improvement over that of the original eigenvalue problem. There is
potential, because in the best case, where
, we then have
the exact
Cayley transformation. Also, we know that in the iterative solution of
linear equations, spectra are improved by preconditioning. On the other
hand, preconditioning of eigenvalue problems is probably tougher than for
linear equations, because asymptotically the singular matrix
is being approximated. This matrix is also indefinite if
is not an exterior eigenvalue. We will look at two examples of
how preconditioning can work for eigenvalue problems.