I'm trying find the eigenvalues of a matrix A using QR iteration with Householder. I used this code which I found from Cornell University that decomposes QR with Householder.

 A=  [3.56829648331616, -2.19026841424281,0.557474633283884,-0.126072015319561;
    -3.25393787896303, 4.81285873937612,-2.79568990543933,0.632240894103258
    1.14081451177546,   -4.13904528762030,  6.19190034744431,-2.98172499459682
    -0.639981731971678, 2.32194922534595,   -7.91889162828103,6.11802605281534]

[m,n] = size(A);
Q = eye(m); % Orthogonal transform so far
R = A; % Transformed matrix so far

for j = 1:n
% -- Find H = I-tau*w*w’ to put zeros below R(j,j)
normx = norm(R(j:end,j));
s = -sign(R(j,j));
u1 = R(j,j) - s*normx;
w = R(j:end,j)/u1;
w(1) = 1;
tau = -s*u1/normx;
% -- R := HR, Q := QH
R(j:end,:) = R(j:end,:)-(tau*w)*(w'*R(j:end,:));
Q(:,j:end) = Q(:,j:end)-(Q(:,j:end)*w)*(tau*w)';

Now that I have the correct R and Q verified through MATLAB, I should be able to find the eigenvalues by multiplying R and Q.

Let $E=RQ$,

where the diagonal elements of E must contain the eigenvalues and is symmetric.

However, upon doing so its not giving me the correct eigenvalues.

Do I have to write another iteration to find the eigenvalues with Q and R?

  • 7
    $\begingroup$ Welcome to SciComp.SE! You should look up QR iteration, e.g., on Wikipedia -- as the name implies, it's an iterative algorithm: every time you repeat those steps, the diagonal entries of $E$ (under some conditions) will be closer and closer to the eigenvalues of $A$. (It's impossible to obtain the eigenvalues of a general matrix in a finite number of steps, since this would be equivalent to finding the roots of the corresponding characteristic polynomial by a finite sequence of algebraic operations, which has been proven to be impossible by Abel in 1824.) $\endgroup$ – Christian Clason Mar 28 '17 at 21:57
  • $\begingroup$ I think a worthwhile step is writing the method down formally, then in pseudocode (perhaps even here), and testing with a very small example that you might find online or in a textbook. This would both help your understanding and facilitate a compact, useful, answer here. $\endgroup$ – Spencer Bryngelson Mar 28 '17 at 23:40
  • 4
    $\begingroup$ A separate thing worth mentioning: If your goal is to understand the method, then this is a good question worth answering. If your goal is to just obtain some eigenvalues and move on with your life, just use a linear algebra library (Lapack, Arpack, SLEPc, Eig, or whatever). $\endgroup$ – Spencer Bryngelson Mar 28 '17 at 23:45
  • 4
    $\begingroup$ In practice you won't get very fast convergence of the QR algorithm without using a shift. $\endgroup$ – Brian Borchers Mar 29 '17 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.