We present the single-vector version of the method
for the pencil in Algorithm 11.5.
On the output,
and
approximate
the largest eigenvalue
and
its corresponding eigenvector.
We note that the shift
requires knowledge of
, or its estimate from below.
If
is nonnegative definite, then
may simply be replaced with
.
The standard arguments, based on the eigendecomposition of
for the pencil
, do not allow us to
show that the power method converges, as eigenvectors
in the eigendecomposition are not necessarily eigenvectors
of the iteration operator. This makes convergence theory
quite tricky. D'yakonov and his colleagues [150,146,147]
obtained explicit estimates of linear convergence for
iterative Algorithm 11.5
using assumption (11.9).
Somewhat simplified (see [264,265,268]),
the convergence rate estimate
for Algorithm 11.5
can be written as
The estimate shows that the convergence is (at least)
linear. Note that condition numbers of and
do not appear in the estimate.
Similar results can be obtained if
for some
holds [147].
In numerical experiments, Algorithm 11.5
usually converges to
for a random initial guess. When
,
the sequence
needs to pass
eigenvectors, which are
saddle points of the Rayleigh quotient, to reach
. The convergence may slow down, in principle,
near every saddle point.
For a general preconditioner
, it is hard
to predict whether this can happen for a given initial guess
.
We have collected the dominant costs per iteration for Algorithm 11.5 in terms of storage and floating point operations respectively, in the following two tables.
Item | Storage |
Residual | ![]() ![]() |
Approximate eigenvector | ![]() ![]() |
Temporary vectors | 1-2 ![]() |
Action | Major cost |
Rayleigh quotient ![]() |
![]() |
Residual ![]() |
![]() |
Preconditioned residual ![]() |
Depends on preconditioner ![]() |
Approximate eigenvector | ![]() |
The main advantage of the preconditioned shifted power method is, of course, its algorithmic simplicity and the low costs per iteration. Using an a priori chosen shift provides the total control of the iterative method. The method is very stable and robust. A solid convergence theory exists.
The need of bounds for
and
to calculate the shift is a clear disadvantage.
Also, other preconditioned
eigensolvers we consider below converge linearly as well, but
typically with a better rate.