Numerical Analysis/Power iteration examples

From Wikiversity
Jump to: navigation, search

w:Power method is an eigenvalue algorithm which can be used to find the w:eigenvalue with the largest absolute value but in some exceptional cases, it may not numerically converge to the dominant eigenvalue and the dominant eigenvector. We should know the definition for dominant eigenvalue and eigenvector before learning some exceptional examples.

Definitions[edit]

Let , ,.... be the eigenvalues of an matrix . is called the dominant eigenvalue of A if

The eigenvectors corresponding to are called dominant eigenvector of . Next we should show some examples where the power method will not converge to the dominant eigenpair of a given matrix.

Example: Bad starting guess[edit]

Use the power method to find an eigenvalue and its corresponding eigenvector of the matrix

starting with the vector

.

We apply the power method and get

,

with , and it implies

.

In this way,

,

so , and it implies

.

As we can see, the sequence converges to 2.

Using the w:characteristic polynomial, the eigenvalues of matrix are , , and , so the dominant eigenvalue is 5, and our hand calculations converged to the second largest eigenvalue.

The problem is that our initial guess led us to exactly the eigenvector corresponding to . If we run this long enough on a computer then roundoff error will eventually introduce a component of the eigenvector for , and that will dominate. This process can be achieved by w:Matlab. Below is the code in the matlab language. This code will plot the convergence of the sequence .

eest=zeros(100,1);
for i=1:100
    x=A*v;
    e=(x'*v)/(v'*v);
    v=x/norm(x);
    eest(i)=e;
end
plot(eest);

We can see the convergence of the sequence in the following figure:

File:Powermethod.jpg
Graph of the convergence of the sequence by w:Rayleigh quotient

We can draw the conclusion that if the starting guess we chose is very close to the corresponding eigenvector of the second largest eigenvalue, the estimation of the dominant eigenvalue will converge to the second largest eigenvalue first and dominant eigenvalue finally. Changing the starting guess will fix this problem.

Example: Complex eigenvalue[edit]

Consider the matrix

.

Apply the power method to find the eigenvalue of the matrix with starting guess

.

We compute

,

thus , and it implies

.

We continue doing some iterations:

so , and it implies

.

so , and it implies

.

We can see the sequence and are oscillating. The above matrix has eigenvalues 1 and and the dominant eigenvalues are w:complex conjugate to each other. The power method applied to a real matrix with a real starting guess can not work for matrices with the dominant eigenvalues which are complex conjugate to each other. Sometimes even though the sequence and can be convergent, the convergence has nothing to do with the dominant eigenpair. we can see the convergence of the sequence from the figure below:

File:Conjugate.jpg
Graph of the the sequence by w:Rayleigh quotient

As we can see, the sequence converges to -5 which has nothing to with our dominant eigenvalues and the power method will not work if the matrix has dominant eigenvalues which are complex conjugate to each other and our starting guess has all real entries. When we change our starting guess to the vectors which have complex entries, the power method should work as usual.

Reference[edit]

Power method for approximating eigenvalues

http://ceee.rice.edu/Books/LA/eigen/

Deri Prasad, An Introduction to Numerical Analysis, Third Edition,P7.2-7.18