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 (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 .
Now, the vector is multiplied successively by the matrix A.
We can choose 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 is the largest eigenvalue, then
Hence,
Therefore, taking the ratio of the magnitude of and , 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 which is the least eigenvalue of A.
GRAPHICAL REPRESENTATION
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[0]
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
Read a[i][j])
[End of ‘for’ loop]
[End of ‘for’ loop]
[taking the initial approximation of the eigen vector]
for i = 0 to n - 1 repeat
Read x[i]
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]
APPLICATION
1. This method is used to find out the largest eigenvalue of a matrix.
Contributed by