The Power Method and the Dominant Eigenvalue

We know eigenvalues as the roots of a characteristic polynomial of a matrix. In practice, the problem of finding eigenvalues is virtually never solved by finding roots of the characteristic polynomial, as this task is computationally prohibitive for large matrices. Iterative methods are used instead. In this section we describe the Power Method and some variations. In QR Factorization we will touch upon a better iterative method for approximating eigenvalues of a non-singular matrix called the QR-algorithm. The methods we present in this text are a mere introduction to the iterative methods used to compute eigenvalues and eigenvectors.

Finding the Dominant Eigenvalue using the Power Method

In Exploration exp:motivate_diagonalization of Diagonalizable Matrices and Multiplicity, our initial rationale for diagonalizing matrices was to be able to compute the powers of a square matrix, and the eigenvalues were needed to do this. In this section, we are interested in efficiently computing eigenvalues, and it may come as no surprise that the first method we discuss uses the powers of a matrix.

When such an eigenvalue exists, one technique for finding it is as follows: Let in be a first approximation to a dominant eigenvector , and compute successive approximations as follows:

In general, we define We will see in this section that if the first estimate is good enough, these vectors will approximate the dominant eigenvector . This technique is called the Power Method (because for each ). Observe that if is any eigenvector corresponding to , then Because the vectors approximate dominant eigenvectors, this suggests that we define the Rayleigh quotients as follows: Then the numbers approximate the dominant eigenvalue .
Use the power method to approximate a dominant eigenvector and eigenvalue of .

The eigenvalues of are and , with eigenvectors and , as we can verify using Octave.

To do so, go to the Sage Math Cell Webpage, copy the code below into the cell, select OCTAVE as the language, and press EVALUATE.

A=[1 1; 2 0]
 
[EIGENVECTORS,EIGENVALUES] = eig(A)

If we take as the first approximation and compute successively, from , the result is

These vectors are approaching scalar multiples of the dominant eigenvector . Moreover, we will find that the Rayleigh quotients are and these are approaching the dominant eigenvalue .
(a)
Verify the above calculations using the following Octave window.
(b)
Try a different starting vector. Do we still get convergence?
(c)
What happens if the starting vector is changed to ? Why doesn’t this method work in this case?
(d)
Try using . You may need to increase the number of iterations to see convergence.

To use Octave, go to the Sage Math Cell Webpage, copy the code below into the cell, select OCTAVE as the language, and press EVALUATE.

% The Power Method
 
A=[1 1; 2 0]; %Input a square matrix  
x_0=[1;0]; %Input an initial vector  
maxit =5; %Choose number iterations  
x = x_0;  
count = 0;  
r=0;  
    while count < maxit  
    y=x;  
    x = A*y;  
        if count > 0;  
        r=(transpose(y)*x)/(transpose(y)*y);  
        RQUOTIENTS(count)=r;  
        end  
    count = count + 1;  
    VECTORS(:,count)=x;  
end  
VECTORS  
RQUOTIENTS

To see why the power method works, let be eigenvalues of with dominant and let be corresponding eigenvectors. What is required is that the first approximation be a linear combination of these eigenvectors:

If , the fact that and for each gives Hence The right side approaches as increases because is dominant

. Because , this means that approximates the dominant eigenvector .

The power method requires that the first approximation be a linear combination of eigenvectors. In Example exp:2x2PowerMethod, the eigenvectors form a basis of . But even in this case, the method fails if , where is the coefficient of the dominant eigenvector (as we saw in part exp:2x2PowerMethod_c). In general, the rate of convergence is quite slow if any of the ratios is near (as we saw in part exp:2x2PowerMethod_d).

Use the Power Method to approximate a dominant eigenvector and eigenvalue of

You can use Octave to employ the power method. To do so, go to the Sage Math Cell Webpage, copy the code below into the cell, select OCTAVE as the language, and press EVALUATE.

% The Power Method
 
A=[9 2 8; 2 -6 -2; -8 2 -5]; %Input a square matrix  
xinit=[1;1;1];  
%Input an initial vector  
maxit =15;  
%Choose number iterations  
x = xinit;  
count = 0;  
r=0;  
    while count < maxit  
    y=x;  
    x = A*y;  
        if count > 0;  
        r=(transpose(y)*x)/(transpose(y)*y);  
        RQUOTIENTS(count)=r;  
        end  
    count = count + 1;  
    VECTORS(:,count)=x;  
end  
VECTORS  
RQUOTIENTS  
[EIGENVECTORS, EIGENVALUES]=eig(A)  
VECTORS(:,maxit)/norm(VECTORS(:,maxit))

We observe that the Rayleigh quotients approach , which is the dominant eigenvalue. We can confirm this using the command ‘eig’. To see that our vectors are approaching the dominant eigenvector, in the last step we divide our final approximate vector by its norm to obtain a unit vector. Note that we get the same result as the ‘eig’ command. In practice, we achieve greater accuracy if we normalize the approximate eigenvector at each iteration rather than waiting until the end.

Finding Other Eigenvalues

If the Power Method converges to the dominant eigenvalue, how can we determine other eigenvalues of a matrix? This section is devoted to some variations of the Power Method that address this problem. Many of the ideas in this section can be employed in other settings.

The Inverse Power Method

The Inverse Power Method is based upon the following theorem.

Proof
The proof is left as an exercise. See Practice Problem prob:complete_eig_proofs.

We return to the matrix in Exploration exp:3x3PowerMethod. Let and let .

Now use Octave to verify that and that the eigenvalues of are indeed the reciprocals of the eigenvalues of .

To do so, go to the Sage Math Cell Webpage, copy the code below into the cell, select OCTAVE as the language, and press EVALUATE.

% Eigenvalues of the inverse are reciprocals of eigenvalues of the matrix
 
M=[9 2 8; 2 -6 -2; -8 2 -5];  
eig(M)  
A=inv(M)  
eig(A)

If we now apply the Power Method to , the Rayleigh quotients converge toward the dominant eigenvalue of , which is . If we take the reciprocal of the dominant eigenvalue of , we will have found the “least dominant” eigenvalue of , i.e., the eigenvalue closest to zero. Sure enough, the reciprocal of is , which is the eigenvalue of closest to zero.

The Shifted Power Method

Again, we begin with a theorem.

Proof
The proof is left as an exercise. See Practice Problem prob:complete_eig_proofs.

Once again, let and let .

Using Octave, you can verify that and that the eigenvalues of are obtained by subtracting from (i.e. by adding 3 to) each eigenvalue of . The dominant eigenvalue of gives us an eigenvalue of zero for (you may find it gives a number very close to zero, due to rounding error). So if we apply the Power Method to to find its dominant eigenvalue (which is 5), we can add to get the “second largest” eigenvalue of (i.e., the eigenvalue second-farthest from zero), which is 2.

To see this, go to the Sage Math Cell Webpage, copy the code below into the cell, select OCTAVE as the language, and press EVALUATE.

% The shifted power method
 
M=[9 2 8; 2 -6 -2; -8 2 -5];  
eig(M)  
c=-3;  
A=M-c*eye(3) %I love the fact that eye(n) is the command for the identity matrix  
eig(A)  
xinit=[1;1;1]; %Input an initial vector  
maxit =15; %Choose number iterations  
x = xinit;  
count = 0;  
r=0;  
    while count < maxit  
    y=x;  
    x = A*y;  
        if count > 0;  
        r=(y‘*x)/(y‘*y);  
        RQUOTIENTS(count)=r;  
        end  
    count = count + 1;  
    VECTORS(:,count)=x;  
end  
VECTORS  
RQUOTIENTS  
RQUOTIENTS(maxit-1)+c
The Shifted Inverse Power Method

The Shifted Inverse Power method combines the two ideas we just studied. Using the Inverse Power method, we know how to find the eigenvalue closest to zero. We also know that we can change which eigenvalue is the dominant eigenvalue using the Shifted Power method. With the Shifted Inverse Power method, we are able to find the eigenvalue closest to a target , where can be any number, real or complex. We begin with the following theorem.

Proof
Suppose . By Theorem th:eig_shifted we have Since is not an eigenvalue, , so is invertible. Also, since is not an eigenvalue, . We multiply both sides on the left by and divide both sides by the nonzero scalar . We arrive at as desired.

Again we let . We will use the Shifted Inverse Power Method to compute the eigenvalue of closest to the target .

Using Octave, you can verify that . When we apply the Power Method to to find its dominant eigenvalue, our Rayleigh quotients approach 1. This means that the eigenvalue of closest to our target is , or 2.

To do so, go to the Sage Math Cell Webpage, copy the code below into the cell, select OCTAVE as the language, and press EVALUATE.

% The shifted inverse power method
 
M=[9 2 8; 2 -6 -2; -8 2 -5];  
eig(M)  
tau=1;  
A=inv(M-tau*eye(3)) %I love the fact that eye(n) is the command for the identity matrix  
eig(A)  
xinit=[1;1;1]; %Input an initial vector  
maxit =15; %Choose number iterations  
x = xinit;  
count = 0;  
r=0;  
    while count < maxit  
    y=x;  
    x = A*y;  
        if count > 0;  
        r=(transpose(y)*x)/(transpose(y)*y);  
        RQUOTIENTS(count)=r;  
        end  
    count = count + 1;  
    VECTORS(:,count)=x;  
end  
VECTORS  
RQUOTIENTS  
RQUOTIENTS(maxit-1)+tau

Practice Problems

(a)
Prove Theorem th:eig_inverse.
Let be an eigenvalue of . Write down what this means. Then try to show for some vector .
(b)
Prove Theorem th:eig_shifted.
If is the eigenvector of corresponding to , it will also be the eigenvalue of corresponding to .
In each case, find the exact eigenvalues and determine corresponding eigenvectors. Then start with and compute and using the power method.
(a)
(b)
(c)
(d)
(a)
Eigenvalues , ; eigenvectors , ; ;
(b)
Eigenvalues , ; eigenvectors , ; ; (The true value is , to seven decimal places.)
Apply the power method to
, starting at . Does it converge? Explain.

Text Source

This section was adapted from Section 8.5 of Keith Nicholson’s Linear Algebra with Applications. (CC-BY-NC-SA)

W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, pp. 441–445.