Power Iteration - The Method

The Method

The power iteration algorithm starts with a vector b₀, which may be an approximation to the dominant eigenvector or a random vector. The method is described by the iteration

So, at every iteration, the vector b_k is multiplied by the matrix A and normalized.

Under the assumptions:

• A has an eigenvalue that is strictly greater in magnitude than its other eigenvalues
• The starting vector has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue.

then:

• A subsequence of converges to an eigenvector associated with the dominant eigenvalue

Note that the sequence does not necessarily converge. It can be shown that:
where: is an eigenvector associated with the dominant eigenvalue, and . The presence of the term implies that does not converge unless Under the two assumptions listed above, the sequence defined by: converges to the dominant eigenvalue.

This can be run as a simulation program with the following simple algorithm:

for each(''simulation'') { // calculate the matrix-by-vector product Ab for(i=0; iThe value of norm converges to the dominant eigenvalue, and the vector b to an associated eigenvector.

Note: The above code assumes real A,b. To handle complex; A becomes conj(A), and tmp*tmp becomes conj(tmp)*tmp

This algorithm is the one used to calculate such things as the Google PageRank.

The method can also be used to calculate the spectral radius of a matrix by computing the Rayleigh quotient