Power Iteration - The Method

The Method

The power iteration algorithm starts with a vector b0, 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 bk 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

Read more about this topic:  Power Iteration

Famous quotes containing the word method:

    “There is no method but to be very intelligent.”
    —T.S. (Thomas Stearns)

    “The good husband finds method as efficient in the packing of fire-wood in a shed, or in the harvesting of fruits in the cellar, as in Peninsular campaigns or the files of the Department of State.”
    —Ralph Waldo Emerson (1803–1882)