## Power Method

Back to Programming

### Description

The power method is an eigenvalue algorithm which is also known as power iteration. From a diagonalizable matrix, a number is produced which is the greatest eigenvalue and a non-zero eigenvector. This method is used for eigenvalue problems where very few roots of the characteristic equation are to be found.

DERIVATION

Let all the eigenvalues be distinct. So, an arbitrary vector ${\mathbf{Y}}^{\mathbf{\left(}\mathbf{0}\mathbf{\right)}}$ (say) can be expressed as a linear combination of eigenvectors , etc.

To find the numerically largest or dominant eigenvalue and its associate eigenvectors we start with an arbitrary vector ${\mathbf{Y}}^{\mathbf{\left(}\mathbf{0}\mathbf{\right)}}$.

Now, the vector is multiplied successively by the matrix A.

We can choose ${\mathbf{Y}}^{\mathbf{\left(}\mathbf{0}\mathbf{\right)}}$ as [1,0]’ , [1, 0, 0]’ , [1,1]’ , [1,-1]’ , [0, 1]’ , [0, 0, 0, 1]’, [1, 1, 1, 1]’ or any other vector of correct size.

Now,

Multiplying by A again we get:

Proceeding in this way, we get at the mth iteration

Let ${\mathrm{\gamma }}_{1}$ is the largest eigenvalue, then

Hence,

Therefore, taking the ratio of the magnitude of  and ${\mathbf{Y}}^{\mathbf{\left(}\mathbf{m}\mathbf{\right)}}$, we get

To find the least eigenvalue, we have to first find out the inverse of the matrix A and then we have to find out the largest eigenvalue of ${\mathbf{A}}^{\mathbf{\left(}\mathbf{-}\mathbf{1}\mathbf{\right)}}$ which is the least eigenvalue of A.

GRAPHICAL REPRESENTATION

### Algorithm

INPUT:

A matrix

OUTPUT:

The largest eigenvalue

PROCESS:

``````Step 1: [defining the function to find the max value from an array]
Set max ← absolute value of x1
for i = 1 to n-1 repeat
if (absolute value of x1[i]) > max then
Set max ← absolute value of x1[i]
[End of ‘if’]
[End of ‘for’ loop]
return max
[End of function]

Step 2: [defining the power method]
Read n [the number of rows of the matrix]
[taking the matrix elements as inputs]
for i = 0 to n - 1 repeat
for j = 0 to n - 1 repeat
[End of ‘for’ loop]
[End of ‘for’ loop]
[taking the initial approximation of the eigen vector]
for i = 0 to n - 1 repeat
Read aerr [the maximum allowed error]
Read maxitr [the maximum number of iterations]
Set e ← maximum element of array x
for itr = 1 to maxitr repeat
for i = 0 to n - 1 repeat
Set s ← 0
for k = 0 to n - 1 repeat
Set s ← s + a[i][k] × x[k]
Set r[i] ← s
[end of ‘for’ loop]
Set t ← maximum value of array r
for i = 0 to n - 1 repeat
Set r[i] ← r[i]/t
[End of ‘for’ loop]
Set max_ele ← 0
for i = 0 to n - 1 repeat
Set err ← absolute value of(x[i] - r[i])
If err > max_ele then
Set max_ele ← err
[End of ‘if’]
Set x[i] ← r[i]
[end of ‘for’ loop]
Set errv ← absolute value of (t - e)
Set e ← t
Print itr, e
for i = 0 to n - 1
Print x[i]
[End of ‘for’ loop]
If(errv ≤ aerr) and (max_ele ≤ aerr) then
Print itr
Print e
for i = 0 to n - 1
Print i + 1, x[i]
[End of ‘for’ loop]
return
[End of ‘if’]
[End of ‘for’ loop]
Print "Solution does not coverage iterations not sufficient"
return
[End of ‘power’ method]``````

### Code

APPLICATION

1. This method is used to find out the largest eigenvalue of a matrix.