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:

    “If all feeling for grace and beauty were not extinguished in the mass of mankind at the actual moment, such a method of locomotion as cycling could never have found acceptance; no man or woman with the slightest aesthetic sense could assume the ludicrous position necessary for it.”
    —Ouida [Marie Louise De La Ramée] (1839–1908)

    “... [a] girl one day flared out and told the principal “the only mission opening before a girl in his school was to marry one of those candidates [for the ministry].” He said he didn’t know but it was. And when at last that same girl announced her desire and intention to go to college it was received with about the same incredulity and dismay as if a brass button on one of those candidate’s coats had propounded a new method for squaring the circle or trisecting the arc.”
    —Anna Julia Cooper (1859–1964)