** Next:** Example 11.2.1.
** Up:** Inexact Methods K. Meerbergen
** Previous:** Arnoldi Method with Inexact
** Contents**
** Index**

##

Davidson Method

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.

**Subsections**

** Next:** Example 11.2.1.
** Up:** Inexact Methods K. Meerbergen
** Previous:** Arnoldi Method with Inexact
** Contents**
** Index**
Susan Blackford
2000-11-20