Sign in to follow this  
FluxCapacitor

QR algorithm and multiple eigenvalues

Recommended Posts

Hi; I'm trying to write an eigensolver for (real) symmetric/tridiagonal matrices using the QR method. While I have the basic algorithm working, I'm unclear on how to deal with the case where not all eigenvalues have distinct absolute values (i.e. some eigenvalue has multiplicity > 1 or some eigenvalue pair are negations of each other). From what I've read (although the only proof I've seen of the algorithm dealt solely with the simple case), while most of the matrix will converge to be diagonal, the multiple eigenvalues will congregate into block matrices along the diagonal (each of size p x p, where p is the multiplicity of the corresponding eigenvalue). Then my understanding is that one must somehow detect this occurrence and split out the block matrix and recursively run the QR algorithm on it. Can anyone elaborate on how to go about performing the detection step, or point me to some (preferably free, online) resources dealing with the topic? Also, once one finds the eigenvalues hidden in these smaller matrices, how does one go about finding the corresponding eigenvectors? Currently I just read off the eigenvectors from the columns of Q, but this method would seem to break in the presence of the block matrices. Thanks!

Share this post


Link to post
Share on other sites
The last question is easier. Once you have an eigenvalue lambda, you know (by definition) that

M * v = lambda * v,

where M is your matrix and v is the eigenvector you seek. That can be rewritten as

(M-I*lambda)*v = 0

So just subtract lambda from all the diagonal elements of the matrix and try to find vectors that are mapped to 0. The solutions of that linear system of equations are all the eigenvectors for the given eigenvalue.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this