Powermethod (Eigenvalue problems)

Question

I don't really get it, when the method converges..

The formula I have says that if the eigenvalue with the greatest absolute value has the algebraic multiplicity of 1, and is strictly greater than all other eigenvalues, which means if:

|lambda 1| > |lambda 2| >= |lambda 3| >= .... >= |lambda n|

then the method converges.

And if there are many eigenvalues with the same greatest absolute value, then xi can loop between 2 eigenvectors and not converge.

Now, I have this matrix:

And I'm trying to iterate with the Rayleigh-Quotient-method, which is based on the power method, with starting value x_0 = (1, 0) and assumed eigenvalue near lambda_0 = 4.

I end up after 2nd iteration with lambda_2 = 5.0583 and x_2 = (0.4759, 0.8795)

And 3rd iteration with lambda_3 = 4.99999 and x_3 = (-0.4475, -15.495)

if I try the 4th iteration with these values, I get x_4 = (-0.4472, -0.8943) and lambda_4 = 4.999889.

What can I say about: 1) the convergence? 2) the absolute value greatest eigenvalue? 3) the eigenvector?

It seems that it's converging to Eigenvalue = 5, and eigenvector x = (-0.4472, -0.8943). Is it right or I'm wrong?

Thank you so much for any hints! I am really confused!

Answer 1

What can I say about: 1) the convergence?

It converges when there is a dominant eigenvalue. It has trouble converging when they are very close together, which isn't the case here.

2) the absolute value greatest eigenvalue?

The matrix is small so you can check it by hand.

$$ A = \begin{pmatrix} 1 & 2 \\ 4 & 3 \end{pmatrix} $$

then

$$ \det(A- \lambda I) = \det(\begin{pmatrix} 1-\lambda & 2 \\ 4 & 3-\lambda \end{pmatrix}) = (1-\lambda)(3-\lambda) - 8 =\lambda^{2} - 4 \lambda - 5 $$

Then

$$ \lambda^{2} - 4\lambda -5 = (\lambda +1)(\lambda-5) \implies \lambda_{1} = 5 , \lambda_{2} = -1$$

3) the eigenvector?

To get the eigenvector we plug that in

$$ A-5 I = \begin{pmatrix} -4 & 2 \\ 4 & -2 \end{pmatrix}$$

Then we have that $v_{1} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}$ so

$$ q_{1} = \begin{pmatrix} \frac{1}{\sqrt{5}} \\ \frac{2}{\sqrt{5}}\end{pmatrix}$$

I created a small program for this...

import  numpy as np
A = np.array([[1,2],[4,3]])
xk = np.array([[1],[0]])


def iterate(A,x):
    rho = np.dot(A,x)
    #lambda_i
    nk = np.max(np.absolute(rho))
    # v_i
    xk = 1/nk* rho

    return rho, nk, xk

n = 55

for i in range(n):
    if (i % 5 == 0):
        rho, nk, xk = iterate(A,xk)
        print("The {i}'th lambda iterate is:{lambda_i}".format(i=i+1,lambda_i =nk))
        print("The {i}'th eig_vec iterate is:{vec_i}".format(i=i+1,vec_i =xk))

If you use it, you should have

$$ x_{1} = \begin{pmatrix} \frac{1}{4} \\ 1 \end{pmatrix}$$

$$ x_{2} = \begin{pmatrix} .5625 \\ 1 \end{pmatrix}$$

$$ x_{3} = \begin{pmatrix} .4880 \\ 1 \end{pmatrix}$$

$$ x_{3} = \begin{pmatrix} .5024 \\ 1 \end{pmatrix}$$

$$ x_{4} = \begin{pmatrix} .49952 \\ 1 \end{pmatrix}$$

$$ x_{5} = \begin{pmatrix} .50009 \\ 1 \end{pmatrix}$$

after 50 iterations you'll have

$$ x_{50} =\begin{pmatrix} .5 \\ 1 \end{pmatrix} $$

or

$$ v_{1} = \begin{pmatrix} 1 \\ 2 \end{pmatrix} $$