Skip to main content
GameDev.net gamedev.net
🔒 Locked

QR algorithm and multiple eigenvalues

Started by FluxCapacitor Jan 30, 2008 at 1:50 AM 0 replies 900+ views
Original Post
FluxCapacitor
FluxCapacitor
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!
alvaro
alvaro
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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.