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 | -vector |

Approximate eigenvector | -vector |

Temporary vectors | 1-2 -vectors |

Action | Major cost |

Rayleigh quotient | dots |

Residual | matrix-vector products |

Preconditioned residual | Depends on preconditioner |

Approximate eigenvector | update |

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.