An error analysis of a unitary Hessenberg QR algorithm

Abstract

Several direct implementations of the QR algorithm for a unitary Hessenberg matrix are numerically unstable. In this paper we give an analysis showing how the instability in a particular rational form of the algorithm specialized to the case of a unimodular shift comes from two sources: loss of accuracy due to cancellation in a particular formula and a dynamic instability in the propagation of the normalization conditions on the Schur parameters and complementary parameters used to represent the matrix. The first problem can be fixed through the use of an alternate formula proposed by Gragg. The second problem can be controlled by not relying on the fact that the matrix is numerically unitary to enforce implicitly the unimodularity of the computed shift; if the shift is explicitly normalized then experiments suggest that the algorithm is stable in practice although stability cannot be proven. A third small modification, introduced to eliminate a potential for a relatively slow exponential growth in normalization errors leads to a provably stable algorithm. This stable rational algorithm for computing the eigenvalues leads directly to a stable algorithm for computing a complete eigenvalue decomposition.