Power Method MATLAB Program

0
2887

Power Method, used in mathematics and numerical methods, is an iteration method to compute the dominant eigenvalue and eigenvector of a matrix. It is a simple algorithm which does not compute matrix decomposition, and hence it can be used in cases of large sparse matrices. Power method gives the largest eigenvalue and it converges slowly.

In earlier tutorials, we discussed algorithm/flowchart and C program for power method. Here, we are going to write a program source code for Power method in MATLAB and go through its theoretical background along with a numerical example.

Theoretical Background of Power Method:

In linear algebra, eigenvalue of a square matrix is defined as a vector which points invariant direction under the associated linear transformation. If λ be the eigenvalue of a square matrix A, it can be mathematically depicted as:

Av = λv

where, ‘v’ is a vector (called eigenvector) which is non-zero. This vector ‘v’ is said to be normalized if its coordinate of largest magnitude is unity.

Theorem Derivation:

Consider a matrix A of order mxn which has n distinct eigenvalues λ1, λ2, λ3,… λn. The descending order of these eigenvalues can be given as:

1| > |λ2| > |λ3| …… > |λn|

Choose an appropriate value of x0 . Now, the sequence can be given as:

{ xk = (x1(k), x2(k), x3(k), ………. xn(k))T}

The sequence of  {Ck}  is generated by:

Yn = AXk and Xk+1 = 1/(Ck+1) * Yk

where, Ck+1 = Xj(k) and Xj (k) = max{|xi(k)|

These values will converge to the dominant eigenvalue λ1 and eigenvector v1.

Alternative Approach:

Power Method uses continuous guesses of X to the eigenvector and λ to the eigenvalue. In both manual calculation and programming approach (MATLAB code) of Power method, the matrix must be symmetric i.e. aij = aji.

Now, again consider a matrix A, whose eigenvector X and eigenvalue λ are to be found out, such that:

[A]{X} = λ{X}

Say, we’re given these three set of equations:

a11x1 + a12x2 + a13x3 = λx1
a12x1 + a22x2 + a23x3 = λx2
a31x1 + a32x2 + a33x3 = λx3

These equations can be re-written as:

(a11-λ)x1 +a12x2 +a13x3 = 0
a21x1 +(a22-λ)x2 +a23x3 = 0
a31x1 +a32x2 + (a33-λ)x3 = 0

Hence, the determinant of the 3*3 matrix thus formed out of the coefficients of ‘x’ terms gives three roots: λ1, λ2 and λ3. These roots are the required eigenvalues or characteristic values.

And, for each of these values, we obtain a set of column vector with elements x1, x2 and x3. This vector is the required eigenvector. This technique is utilized in the below program for Power method in MATLAB.

Did you know??

Google uses power iteration method to calculate the PageRank of webpages in their search engine! Also, the recommendations like “who to follow” in Twitter are based on this method!

Power Method in MATLAB:

The above code for power method in MATLAB is used to calculate the eigenvalue and eigenvector of a square matrix of any order by using iteration principle of power method. In this program, the matrix whose eigenvalue is to be determined is the input and its corresponding eigenvalue and eigenvector are the output.

As the program is executed, it asks for the value of matrix whose eigenvalue and eigenvector are to be found out. After that, the input matrix is checked whether it is square or not. If the matrix is not a square matrix, an error message is displayed. Further, the matrix should be symmetric or positive definitive.

Then, an initial guess value is to be given to the code, and based on that value and following the theory explained above, the program calculates eigenvalue and eigenvector of the entered matrix. Here’s a sample output of the program:

Power method in MATLAB - Output

Power Method Numerical Example:

Let’s now analyze numerically the above program for power method in MATLAB with this example. We have to find out the dominant eigenvalue of the following matrix using Power method:

Power method in MATLAB - Matrix A
First, assume an initial iteration vector as:

Power method in MATLAB - Initial Guess Eigenvector

Now, the following approximation can be obtained:

Power method in MATLAB - Calculation

Thus, the eigenvalue of the given matrix is 190 and the eigenvector is [3 1].

If you have any questions regarding Power method or its MATLAB code, bring them up the comments section. You can find more Numerical Methods tutorial using MATLAB here.

NO COMMENTS

LEAVE A REPLY