Finding roots of polynomial using companion matrix

Question

The standard method for finding roots of a polynomial is to form the companion matrix, balance it, then compute the eigenvalues by double shift QR algorithm. This method is used by Matlab ROOTS command implementing Francis's double shift QR algorithm. There is another version working on Hessenberg matrices using only a single shift as follows:

 Do until convergence
    determine Q(k),R(k) such that
    Q(k)R(k) = T(k−1) − μI (QR factorization);
    then, let
    T(k) = R(k)Q(k) + μI.

The question is: is it possible to apply the above single shift QR on companion matrices in order to obtain real eigenvalues without resorting to the double shift QR?

Answer 1

The question is, how do you determine $μ$?

In the end, even the unshifted QR method will converge to a form where you can read off the single real eigenvalues (single in terms of absolute value). A good selection of shifts will accelerate the convergence towards certain eigenvalues, those closest to $μ$ in the case of a constant shift. And of course it influences the order of the eigenvalues to be in the magnitude of $|\lambda_i-μ|$ instead of $|\lambda_i|$ for the unshifted method.