Next: Rayleigh Quotient Iteration Up: Single- and Multiple-Vector Iterations Previous: Power Method   Contents   Index

Inverse Iteration

The drawbacks of the power method can be partially overcome by applying the power method to instead of , where is called a shift. This will let the method converge to the eigenvalue closest to , rather than just . This method is called inverse iteration, or the inverse power method.

Note that there is no need to compute the inverse explicitly at step (4). We only have to solve a system like for efficiently, which formally gives .

As in the power method, we should expect the sequence of vectors generated by the inverse power method to become increasingly parallel to the eigenvector corresponding to the largest eigenvalue of in magnitude. More specifically, assume that and are an eigenvalue and eigenvector pair of so that is the largest eigenvalue of in magnitude. The inverse power method converges if is not perpendicular to . The convergence rate is , where is an eigenvalue of such that is the second largest eigenvalue of in magnitude.

One advantage of inverse iteration over the power method is the ability to converge to any desired eigenvalue (the one nearest ). By choosing very close to a desired eigenvalue, inverse iteration can converge very quickly. This method is particularly effective when we have a good approximation to an eigenvalue and only want to compute this eigenvalue and its corresponding eigenvector. However, inverse iteration does require a factorization of the matrix , making it less attractive when this factorization is expensive.

Next: Rayleigh Quotient Iteration Up: Single- and Multiple-Vector Iterations Previous: Power Method   Contents   Index
Susan Blackford 2000-11-20