[Math] Eigenvalues of an upper Hessenberg matrix

companion-matriceseigenvalues-eigenvectorslinear algebramatricesmatrix decomposition

I'm interested in calculating the roots of an 11th degree polynom.
To do so, I calculated the $10 \times 10$ companion matrix which eigenvalues are the roots of the polynomial.

Now, the eigenvalues could be real or complex and in my code, I just need real ones. Is there a way to find the real eigenvalues only of an upper Hessenberg matrix (companion matrix) using iterations of the QR algorithm?

Let $A$ be our upper Hessenberg matrix. I tried the following

M=A
for i=1:100
[Q,R]=qr(M);
M=R*Q;
end

diag(M) will converge to eig(A) if A is symmetric, if not real eigenvalues exist but complex ones dosen't. I just need real eigenvalues but how to distinguish in diag(M) values that the entry correspond to a real eigenvalue?

Best Answer

First, there is no advantage to trying to compute only the real eigenvalues versus just computing them all; they could all be real or all be complex.

Second, the QR algorithm as you've written it converges extremely slowly compared to state-of-the-art implicitly shifted Hessenberg QR. If you use eig() in Matlab, it will use the faster algorithm and almost certainly be faster than your qr in a loop.

Related Question