Inverse iteration
|
|
In numerical analysis, inverse iteration is an iterative eigenvalue algorithm based on power iteration that achieves superior flexibility and performance.
The basic idea of power iteration is choosing an initial vector b (either an eigenvector approximation or a random vector) and iteratively calculating <math>Ab, A^{2}b, A^{3}b,...<math>. Except for a set of zero measure, for any initial vector, the result will converge to an eigenvector corresponding to the dominant eigenvalue. In practice, the vector should be normalized after every iteration.
Unfortunately, power iteration can only find the eigenvector corresponding to the dominant eigenvalue. We could modify the algorithm so that instead we calculate <math>A^{-1}b, A^{-2}b, A^{-3}b,...<math>. This algorithm would find the eigenvector corresponding to the smallest magnitude eigenvalue. This is still not enough flexibility to find all the eigenvalues/eigenvectors.
However, imagine we have an approximation μ to the eigenvalue we are interested in. If μ is closer to <math>\lambda_{k}<math> than any other eigenvalue of A, then <math>\lambda_{k} - \mu<math> is the smallest eigenvalue of the matrix <math>(A - \mu I)<math>. By calculating <math>(A - \mu I)^{-1}b,(A - \mu I)^{-2}b,(A - \mu I)^{-3}b,...<math>, we can find the eigenvector corresponding to this eigenvalue. Once we have a suitable eigenvector approximation, we can use the Rayleigh quotient to find the eigenvalue.
The inverse iteration algorithm converges fairly quickly. We can, however, achieve even faster convergence by using a better eigenvalue approximation each time. This is the idea behind Rayleigh quotient iteration.
The inverse iteration algorithm requires solving a linear system at each step. This would appear to require <math>O(n^{3})<math> operations. However, this can be reduced to <math>O(n^{2})<math> if we first reduce A to Hessenberg form. This is usually done in practice.