The transmission of shifts and shift blurring in the QR algorithm

AbstractThe QR algorithm is one of the most widely used algorithms for calculating the eigenvalues of matrices. The multishift QR algorithm with multiplicity m is a version that effects m iterations of the QR algorithm at a time. It is known that roundoff errors cause the multishift QR algorithm to perform poorly when m is large. In this paper the mechanism by which the shifts are transmitted through the matrix in the course of a multishift QR iteration is identified. Numerical evidence showing that the mechanism works well when m is small and poorly when m is large is presented. When the mechanism works poorly, the convergence of the algorithm is degraded proportionately