Power and Inverse Power Methods

MATH421: Numerical Analysis Method

Summer 2023

Prepared by:
Adam Farhat
Dalia Harfoush
Malek Jammal
Razan Ghannam
Table of Contents

Introduction.................................................................................................................................................3

Power Method.............................................................................................................................................3

Power method formulas..........................................................................................................................4

Example on Power Method.....................................................................................................................4

When we Can’t Use Power Method.........................................................................................................5

Power Method MATLAB Code.................................................................................................................6

Inverse Power Method................................................................................................................................8

Example on Inverse Power Method.........................................................................................................8

When we can’t use Inverse Power Method.............................................................................................9

Inverse Power Method MATLAB Code...................................................................................................10

Conclusion.................................................................................................................................................11

Page 1 of 11
Table of Figures

Figure 1: Power Method Formulas..............................................................................................................4

Figure 2: Large Matrix Example...................................................................................................................6

Figure 3: MATLAB Code of Power Method..................................................................................................7

Figure 4: Result of MATLAB code of Power Method....................................................................................7

Figure 5: Non invertible Matrix Example.....................................................................................................9

Figure 6: Non-Symmetric Matrix.................................................................................................................9

Figure 7: MATLAB Code of Inverse Power Method....................................................................................10

Figure 8: Result of Inverse Power Method MATLAB Code..........................................................................10

Page 2 of 11
Introduction
The Power Method and Inverse Power Method are two iterative algorithms used to find the
largest and smallest eigenvalues and their corresponding eigenvectors of a matrix.

The Power Method is used to find the largest eigenvalue and its corresponding eigenvector of a
matrix. It is an iterative algorithm that starts with an initial guess for the eigenvector and iteratively
multiplies the matrix with this vector until it converges to the eigenvector corresponding to the largest
eigenvalue. The convergence rate of the Power Method depends on the ratio of the largest and second-
largest eigenvalues of the matrix.

The inverse power method is an iterative algorithm used in linear algebra to find the eigenvector
and eigenvalue of a square matrix, where the eigenvalue is closest to a given value (usually the smallest
eigenvalue). It involves using the inverse of the original matrix and iteratively multiplying it by a vector,
then normalizing the result, to obtain the eigenvector corresponding to the eigenvalue of interest.

Both methods are widely used in various fields, including physics, engineering, finance, and
computer science, among others. They are particularly useful for solving systems of linear equations,
where the matrix is large and sparse, and direct methods are computationally expensive.

Power Method
The Power Method is a numerical algorithm used to find the dominant eigenvalue and
corresponding eigenvector of a square matrix. The algorithm works by repeatedly multiplying the matrix
by a vector and normalizing the result until it converges to the eigenvector associated with the dominant
eigenvalue.

Here are the steps to use the Power Method:

 Let A=[aij] be a matrix of order n x n matrix

 We start with any non-zero vector x0 with n components equal to 1 such that Ax0=x


To get a convergent sequence of eigenvectors scaling method is adopted.


Each component is divided by its largest component at each iteration.


Then we should use the scaled vector in the next iteration

Page 3 of 11
 
The largest component is tended to be the largest eigenvalue.


By dividing each component by its largest component, we

get Ax0=x= λ1x1, in which x1 is the scaled vector of x

 The scaled vector x1 is to be used in the next iteration to obtain Ax1=x= λ2x2

 Proceeding in this way, finally we get Axn=x= λn-1xn-1 where n=1,2,3…. Where λn-1 is the
numerically largest eigenvalue and xn-1 is the eigenvector

Power method formulas

The power method can be implemented using the following formulas:

Figure 1: Power Method Formulas

Example on Power
Method:

Question: Use power method to calculate the largest eigenvalue and its corresponding
2 3
eigenvector for A=[ ]
4 10

2 3 1
Solution: Let A=[ ]and x0= [ ]
4 10 1

Page 4 of 11
 2 3 1 5
Y (1) =Ax0= ] = [ ] x1= 14 [0.35714]
]
[ [
4 10 1 14 1

Page 5 of 11
 2 3 3.71429
Y (2) =Ax1= 0.35714 = [ ] x2=11.42857 0.325
[ ] ] [ ]
4 10[ 1 11.42857 1

2 3
Y (3) =Ax2= ] 0.325 3.65 x3= 11.3 [ ]
[ ]=[ 0.32301
[
]
4 10 1 11.3 1

2 3 0.32288
Y (4) =Ax3= ] 0.32301 ] = ] x4= 11.29204 [ ]
[ [ [ 3.64602
4 10 1 11.29204 1

Then the dominant eigenvalue λ in the fourth iteration is=11.29204

0.32288
The dominant eigenvector x=
[ ]
1
When we Can’t Use Power Method:

The power method is a widely used iterative algorithm for finding the dominant eigenvector and
eigenvalue of a matrix, but there are situations where it may not be suitable or effective. Here are some
scenarios where the power method may not be applicable:

1. Non-diagonalizable matrices: If a matrix is not diagonalizable, the power method may not
converge to the dominant eigenvalue. In such cases, one can use other methods like the Jordan
canonical form to find the eigenvalues and eigenvectors.

1 1
Ex: [ ]
0 1

2. Complex eigenvalues: The power method works only for real eigenvalues. If a matrix has
complex eigenvalues, the algorithm may not converge, or it may converge to a non-dominant
eigenvalue. In such cases, one can use methods like the QR algorithm or the Schur
decomposition to find the eigenvalues and eigenvectors.

1 −2
Ex: A=[ 1−λ −2
] A- ]
λI=[
1 3 1 3−λ
det(A-λI) = (3 − λ)(1 − λ) + 2(1) = 0

3-3 λ- λ + λ2 +2=0

λ2- 4λ + 5=0
Page 6 of 11
λ1 =2-i & λ2 =2+i

Page 7 of 11
 3. Singular matrices: If a matrix is singular, i.e., it has a zero determinant, then it does not have any
nonzero eigenvalues. The power method will converge to a zero vector in such cases.

3 8 1
Ex: [−4 1 1]
−4 1 1

4. Large matrices: The power method can be computationally expensive for large matrices since it
requires matrix-vector multiplications at each iteration. In such cases, one can use faster
algorithms like the Lanczos method or the Arnold method.

Ex:

Figure 2: Large Matrix Example

5. Multiple eigenvalues: If a matrix has multiple eigenvalues of the same magnitude, the power
method may converge to any of them. In such cases, one can use other methods like the inverse
power method or the Rayleigh quotient iteration to find the desired eigenvalue and eigenvector.

−7 2 −3
−24
Ex: [ 0 −48
7 7 ]
0 0 0

Power Method MATLAB Code

The power method is an iterative algorithm used to find the dominant eigenvalue and corresponding
eigenvector of a matrix, and it can be easily implemented in MATLAB.

Page 8 of 11
 Figure 3: MATLAB Code of Power Method

The result of this code as follows:

Figure 4: Result of MATLAB code of Power Method

Page 9 of 11
Inverse Power Method
The inverse power method is an algorithm used in linear algebra to find the eigenvector and eigenvalue
of a square matrix, specifically the eigenvalue with the smallest absolute value (i.e., the eigenvalue
closest to zero).

The method works by first computing the inverse of the original matrix and then applying the power
method to the inverse matrix. This yields the eigenvector with the largest absolute value of the inverse
matrix, which is also the eigenvector with the smallest absolute value of the original matrix. The
corresponding eigenvalue is then obtained by taking the reciprocal of the resulting eigenvector. This
method uses the same algorithm as the power method, but it uses the inverse of the matrix.

Target: y=A-1 x = λ-1x

Example on Inverse Power Method:

Question: Use inverse power method to calculate the largest eigenvalue and its corresponding eigenvector
37
for A=[ ]
4 5
3 7 1
Solution: Let A=[ ]and x0= [ ]
4 5 1
1
We need to determine A-1, so A-1= 5 −7
𝑑𝑒𝑡𝐴 [
−4 3]

Det A=5*3 - (-4) (-7) =-13

-1 1
A = 5 −7 −0.38 0.5385
−13 [−4 3 ]=[ 0.3077 −0.2308 ]

−0.38 0.5385 1 1
y (1) =A-1x0=[ ] [ ] = [ 0.15 ] 0.1538x1=0.15[ ]
0.3077 −0.2308 1 0.0769 0.51
−0.38 0.5385 1 ] = [−0.11538] x2=0.1923 [−0.6
y (2) =A-1x1=[ ][
0.3077 −0.2308 0.51 ]
0.1923 1
−0.38 0.5385 −0.6 0.7692 1
y (3) =A-1x2=[ ]=[ ] x3=0.7692 [ ]
][
0.3077 −0.2308 1 −0.4153 −0.54
−0.38 0.5385 1 1
y (4) =A-1x3=[ ][ −0.7292 x4=−0.7292 [ ]
]=
0.3077 −0.2308 −0.54 [ ]
0.4554 −0.6245
1
Then the dominant eigenvalue in the fourth iteration is λ= = −1.38
1
The dominant eigenvector x=[ ]
−0.6245
Page 10 of
11
−0.7292

Page 11 of
11
When we can’t use Inverse Power Method

There are some cases where the inverse power method may not be suitable or effective for finding
eigenvalues and eigenvectors. Here are some situations where the inverse power method may not work
well:

1. If the matrix A is not invertible: In this case, the inverse power method cannot be applied as it
requires the computation of the inverse of A.

Figure 5: Non invertible Matrix Example

2. If matrix A has eigenvalues that are equal in magnitude: In this scenario, the inverse power
method may converge to any of the eigenvectors corresponding to the eigenvalue with the same
magnitude, instead of the one closest to zero.

1 2 0
Ex: [0 1 2]
2 0 1

3. If matrix A is not symmetric: The inverse power method requires the matrix to be symmetric to
ensure that the eigenvalues are real and that the eigenvectors are orthogonal. If the matrix is
not symmetric, then the inverse power method may not produce accurate results.

Figure 6: Non-Symmetric Matrix

4. If matrix A is too large: The inverse power method can be computationally expensive,
particularly when dealing with large matrices. In this case, other iterative methods such as the
Lanczos method or the Arnoldi method may be more suitable.

Page 12 of
11
 5. If the initial guess for the eigenvector is poor: The inverse power method is sensitive to the
choice of the initial guess for the eigenvector, and a poor guess can lead to slow convergence or
convergence to the wrong eigenvector. In such cases, other methods such as the Rayleigh
quotient iteration or the QR algorithm may be more effective.

1 2 0
Ex: [0 2 1]
0 0 3

Inverse Power Method MATLAB Code

The inverse power method is an iterative algorithm used to find the smallest eigenvalue and corresponding
eigenvector of a matrix, and it can also be implemented in MATLAB.

Figure 7: MATLAB Code of Inverse Power Method

Figure 8: Result of Inverse Power Method MATLAB Code

Page 10 of 11
Conclusion
In conclusion, the power method and inverse power method are two commonly used iterative
algorithms for finding the dominant eigenvalue and corresponding eigenvector, and the eigenvalue
closest to zero and corresponding eigenvector, respectively, of a square matrix.

The power method works well for symmetric matrices with distinct eigenvalues but may not
converge or converge slowly in other cases. In contrast, the inverse power method can be used for any
square matrix and is particularly effective for finding eigenvalues and eigenvectors near zero.

Both methods involve repeated matrix-vector multiplication and normalization, and the
convergence rate depends on the ratio of the eigenvalues. The power method converges to the
eigenvector corresponding to the dominant eigenvalue, while the inverse power method converges to
the eigenvector corresponding to the eigenvalue closest to zero.

Despite their simplicity and effectiveness, both methods have limitations. The power method
may converge to a different eigenvalue if the matrix is not diagonalizable or if the initial guess is not well
chosen, while the inverse power method may fail if the matrix is singular or has eigenvalues with equal
magnitudes.

Overall, the power method and inverse power method are important tools in numerical linear
algebra and have numerous applications in science and engineering. Their effectiveness and limitations
highlight the need for careful consideration of the properties of the matrix and the choice of algorithm
for finding eigenvalues and eigenvectors.

Page 11 of 11