The power method (also known as power iteration) is a simple algorithm for obtaining the “top” eigenvector and eigenvalue of a matrix.
Let be an matrix with real-valued entries. Assume that:
- is diagonalizable, or equivalently, has linearly independent eigenvectors . (From here on, I assume that the ‘s have unit norm.)
- We can order the eigenvectors such that the eigenvalues associated with them (i.e. such that ) satisfy the ordering . What is important here is the strict inequality between and .
The power method can be described as follows:
- Initialize to be some non-zero vector.
- For each , set , and set .
If satisfies the two assumptions above and has a non-zero component in the direction of , then converges to , and converges to . (This reference points out that if is negative, might end up “flip-flopping” between and . One way to avoid this is to always insist on having a non-negative first entry.)
The proof is pretty simple and can be found on the first page of the second reference. Section 6.2 of the third reference has some practical tips for how to use the power method in practice.
Can we say something about the convergence rate of the power method? In essence, the convergence rate depends on how close is to : the larger is, the faster the power method converges. Theorem 5.6 of the last reference makes this precise:
Write our initialization as a linear combination of the eigenvectors: . Assume that . Then there exists a constant such that
for all .
What if we are interested in eigenvalues/eigenvectors other than the top ones? We can use the power method to find and . It is then easy to show that the matrix
has eigenvalues and the same eigenvectors as . We can then apply the power method to to get and , and so on. This known as the power method with deflation. It should be noted that the deflation method becomes more inaccurate as we compute smaller and smaller eigenvalues/eigenvectors, because the errors of approximation for the earlier eigenvalues/eigenvectors add up.
- Wikipedia. Power iteration.
- The Power Method.
- Numerical calculation of eigenvalues.
- Lambers, J. (2009-10). The Eigenvalue Problem: Power Iterations.