Finding smallest magnitude eigen value

[akerman]

Hello,
I have been asked to implement an algorithm which will find the smallest magnitude eigen value of the matrice. I have already seen many implementation of it. However, all of them are for the symmetric matrices.
My problem is that I need to do it for non-symmetric matrices which makes it completed for me as I don't really know how to do it.
So my problem should be testking it for normally distributed radnom martices. With this at the beggining what would be the best process to follow to find the smallest magnitude eigenvalue?

Can someone clearly ourline some steps which need to be satsfied in order to find the solution?

I have found thisView attachment 2116
I think it can only be used for symmetric matrices. Can anyone help?

 

[I like Serena]

Re: finding smallest magnitude eigen value

Hi akerman!

I see no references to symmetric matrices.
It seems to me that the method should work for any matrix.

What is the reason that you think it can only be applied to symmetric matrices?

 

[akerman]

Re: finding smallest magnitude eigen value

I think the iteration method can only be used for symmetric but I might be wrong... So in fact my question is what would be a fastest and the best process to execute in order to find th smallest magnitude?

 

[I like Serena]

Re: finding smallest magnitude eigen value

I think the iteration method can only be used for symmetric but I might be wrong... So in fact my question is what would be a fastest and the best process to execute in order to find th smallest magnitude?

I haven't researched this, but the inverse iteration method (without shift) seems quite a good way to do it.
Intuitively it is guaranteed to work as long as the initial vector has a significant component of the desired eigenvector.
Did you search for alternative methods?

If you choose to implement this inverse iteration method, that brings the question how to pick the initial vector.
And also how to solve $Aw=v^{(k-1)}$.
Any thoughts on those?

Working those out might give a clue on how fast the process actually is.
Since someone may have figured that out already, it might help to search for it.

 

[akerman]

Re: finding smallest magnitude eigen value

I am still searching for something exiting stuff, however it's very difficult to actually find the outline of the whole process. So do you think this method will work for unsymmetric matrices?
I found this it's the best so far. The inverse power method reverses the iteration step of the power method. We write:

$\displaystyle A x^{(k+1)} = x^{(k)} $

or, equivalently,

$\displaystyle x^{(k+1)} = A^{-1} x^{(k)} $

In other words, this looks like we are just doing a power method iteration, but now for the matrix $ A^{-1}$. You can immediately conclude that this process will often converge to the eigenvector associated with the largest eigenvalue of $ A^{-1}$. The eigenvectors of $ A$ and $ A^{-1}$ are the same, and if $ {\bf v}$ is an eigenvector of $ A$ for the eigenvalue $ \lambda$, then it is also an eigenvector of $ A^{-1}$ for $ 1/\lambda$ and vice versa.

This means that we can freely choose to study the eigenvalue problem of either $ A$ or $ A^{-1}$, and easily convert information from one problem to the other. The difference is that the inverse power iteration will find us the biggest eigenvalue of $ A^{-1}$, and that's the eigenvalue of $ A$ that's smallest in magnitude, while the plain power method finds the eigenvalue of $ A$ that is largest in magnitude.

The inverse power method iteration is given in the following algorithm.

Starting with any nonzero vector $ \bf x$, divide by its length to make a unit vector called $ {\bf x}^{(0)}$,
Solve $ A\hat{\bf x} = {\bf x}^{(k)}$, and
Normalize the iterate by setting $ {\bf x}^{(k+1)}=\hat{\bf x}/\vert\vert\hat{\bf x}\vert\vert$;
Compute the Rayleigh quotient of the iterate (unit vector) $ r^{(k+1)} = ({\bf x}^{(k+1)}\cdot A{\bf x}^{(k+1)})$; and,
Return to step 2.

 

[akerman]

So, I have found usefull solution for unsymmetric matrices but its finding k largest eigenvalues. So I have this:

for $k=1,2,\dots$

$\quad Z^{(k)} = AQ^{(k-1)}$

$\quad Q^{(k)}R = Z^{(k)}$ (QR decomposition)

$\quad A^{(k)} = [Q^{(k)}]^HAQ^{(k)}$

end

its finding the largest eigenvalues. How can I twick it to find the smallest magnitude eigenvalue?

 

[I like Serena]

If putting $A$ into your procedure gives you the largest magnitude eigenvalue, try putting $A^{-1}$ into it. Its largest magnitude eigenvalue is the inverse of the smallest magnitude eigenvalue of $A$.

 

[akerman]

If putting $A$ into your procedure gives you the largest magnitude eigenvalue, try putting $A^{-1}$ into it. Its largest magnitude eigenvalue is the inverse of the smallest magnitude eigenvalue of $A$.

So just by putting A^-1 which is the inverse I should be getting the smallest magnitude eigen value. But are you sure rest of the calculations won't change?