yawiki.org entry for Power iteration

	Navigation Home Recent Most Active Popular Blog Credits RSS
	Interaction Register Statistics
	Help Suggestions Contact Us How to Edit Help

[Edit]

In mathematics, power iteration is an eigenvalue algorithm: given a matrix A, the algorithm will produce a number λ (the eigenvalue) and a nonzero vector v (the eigenvector), such that Av = λv.
The power iteration is a very simple algorithm. It does not compute a matrix decomposition, and hence it can be used when A is very large sparse matrix. However, it will find only one eigenvalue (the one with the greatest absolute value) and it may converge only slowly.

    Power iteration
        The method
        Analysis
        Applications

top

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

$b_ = rac.$

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

b_

has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue.

then:

A subsequence of

left( b_

ight) converges to an eigenvector associated with the dominant eigenvalue
Note that the sequence

left( b_ 
ight)

does not necessarily converge. It can be shown that:

b_ = e^ v_ + r_

where:

v_

is an eigenvector associated with the dominant eigenvalue, and

| r_ | 
ightarrow 0

. The presence of the term

e^

implies that

left( b_ 
ight)

does not converge unless

e^ = 1

Under the two assumptions listed above, the sequence

left( mu_ 
ight)

defined by:

mu_ = rac

converges to the dominant eigenvalue.

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

$rac = rac.$

top

Analysis

Let

A

be decomposed into its Jordan canonical form:

A=VJV^

,
where the first column of

V

is an eigenvector of

A

corresponding to the dominant eigenvalue

lambda_

.
Since the dominant eigenvalue of

A

is unique,
the first Jordan block of

J

is the

1 	imes 1

matrix

egin lambda_ end

, where

lambda_

is the largest eigenvalue of A in magnitude.
The starting vector

b_

can be written as a linear combination of the columns of V:

b_ = c_v_ + c_v_ + cdots + c_v_

.
By assumption,

b_

has a nonzero component in the direction of the dominant eigenvalue, so

c_ 
e 0

.
The computationally useful recurrence relation for

b_

can be rewritten as:

b_=rac=rac

,
where the expression:

rac

is more amenable to the following analysis.

egin
b_ &=& rac \
      &=& rac \
      &=& rac \
      &=& rac
                \
      &=& rac
                 \
      &=& left( rac 
ight)^ rac
          rac
               
           
end

The expression above simplifies as

k 
ightarrow infty

& & & & \ & left( rac J_ ight)^& & & \ & & ddots & \ & & & left( rac J_ ight)^ \ end ightarrow egin 1 & & & & \ & 0 & & & \ & & ddots & \ & & & 0 \ end

k 
ightarrow infty

.

The limit follows from the fact that the eigenvalue of

rac J_

is less than in 1 in magnitude, so

left( rac J_ 
ight)^ 
ightarrow 0

k 
ightarrow infty

It follows that:

rac V left( rac J 
ight)^ 
left( c_e_ +  cdots + c_e_ 
ight)

ightarrow 0

k 
ightarrow infty

Using this fact,

b_

can be written in a form that emphasizes its relationship with

v_

when k is large:

egin
b_ &=& left( rac 
ight)^ rac
          rac
               
      &=& e^ rac v_ + r_
end

where

e^ = lambda_ / |lambda_|

and

| r_ | 
ightarrow 0

k 
ightarrow infty

The sequence

left( b_ 
ight)

is bounded, so it contains a convergent subsequence. Note that the eigenvector corresponding to the dominant eigenvalue is only unique up to a scalar, so although the sequence

left(b_
ight)

may not converge,

b_

is nearly an eigenvector of A for large k.

Alternatively, if A is diagonalizable, then the following proof yields the same result

Let λ₁, λ₂, …, λ_m be the m eigenvalues (counted with multiplicity) of A and let v₁, v₂, …, v_m be the corresponding eigenvectors. Suppose that

lambda_1

is the dominant eigenvector, so that

|lambda_1| > |lambda_j|

for

j>1

.

The initial vector

b_0

can be written:

$b_0 = c_v_ + c_v_ + cdots + c_v_.$

b_0

is chosen randomly (with uniform probability), then c₁ ≠ 0 with probability 1. Now,

$eginA^b_0 & = & c_A^v_ + c_A^v_ + cdots + c_A^v_ \$

& = & c_lambda_^v_ + c_lambda_^v_ + cdots + c_lambda_^v_ \ & = & c_lambda_^ left( v_ + racleft(rac ight)^v_ + cdots + racleft(rac ight)^v_ ight). end

The expression within parentheses converges to

v_1

because

|lambda_j/lambda_1| < 1

for

j>1

. On the other hand, we have

$b_k = rac.$

Therefore,

b_k

converges to (a multiple of) the eigenvector

v_1

. The convergence is geometric, with ratio

$left| rac$

ight|,
where

lambda_2

denotes the second dominant eigenvalue. Thus, the method converges slowly if there is an eigenvalue close in magnitude to the dominant eigenvalue.

top

Applications

Power iteration is not used very much because it can find only the dominant eigenvalue. Nevertheless, the algorithm is very useful in some specific situations. For instance, Google uses it to calculate the page rank of documents in their search engine.

Some of the more advanced eigenvalue algorithms can be understood as variations of the power iteration. For instance, the inverse iteration method applies power iteration to the matrix

A^

. Other algorithms look at the whole subspace generated by the vectors

b_k

. This subspace is known as the Krylov subspace. It can be computed by Arnoldi iteration or Lanczos iteration.

	Source Privacy License Download Contact Us Atlas Scientus.org Dictionary (Yet Another Wiki) RC : 1.39 MIT OpenCourseWare This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Power iteration". link