FOR FREE MATERIALS

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 ${\mathbf{X}}_{\mathbf{1}}\mathbf{,}\mathbf{ }{\mathbf{X}}_{\mathbf{2}}\mathbf{,}\mathbf{ }\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{ }\mathbf{,}\mathbf{ }{\mathbf{X}}_{\mathbf{n}}$, 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 ${\mathbf{\text{Y}}}^{\mathbf{(}\mathbf{m}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{1}\mathbf{)}}$ 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{(}\mathbf{-}\mathbf{1}\mathbf{)}}$ 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]