An error analysis of a unitary Hessenberg QR algorithm
Date
1998
Authors
Stewart, Michael
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
QR algorithm, Hessenberg matrix, Schur parameters, Eigenvalue Decomposition, TR-CS
Citation
Collections
Source
Type
Working/Technical Paper
Book Title
Entity type
Access Statement
License Rights
DOI
Restricted until
Downloads
File
Description