An error analysis of a unitary Hessenberg QR algorithm. (English) Zbl 1119.65024
The author proves the numerical stability of a variant of W. B. Gragg’s unitary Hessenberg QR algorithm (UHQR) [J. Comput. Appl. Math. 16, 1–8 (1986; Zbl 0623.65041)].
The first section represents an overview concerning unitary Hessenberg matrices, the Schur parameters and the complementary parameters of a Hessenberg matrix \(H\), and the unitary Hessenberg QR algorithm from the point of view of existing results in the literature. ection two presents the UHQR algorithm, which in its original formulation is numerically unstable, W. B. Gragg [Stabilization of the UHQR algorithm. Z. Chen Y. Li, C. Michelli and Y. Xu (eds.), Lect. Notes Pure Appl. Math. 202, 139–154 (1998; Zbl 0932.65047)]. Three modifications lead to a provably stable algorithm. Then, the author presents a stabilized UHQR algorithm. If the eigenvectors are not desired, the above stabilized UHQR algorithm can be converted to a rational algorithm that avoids the use of square roots.
The general issues are given in section three. Thus, the analysis involves both forward and backward errors. With \(\varepsilon\) defined by the unit roundoff, bounds on the forward and backward errors are written in terms of the three basic sources of error \(\varepsilon\), \(\delta\) and \(\delta_z\). All three errors must be small for the resulting bounds to imply stability.
Section four begins with an analysis of the normalization errors. The author shows that the normalization errors \(\delta_k\) do not increase over the course of repeated UHQR iterations.
He continues in section five with a backward error analysis and one bounds the backward errors.
Section six concerns the forward errors. Combining the results of this section with the results of the previous one, the author deduces bounds on the relative backward errors and bounds on the relative forward errors.
The last section is devoted to the final error bounds.
The first section represents an overview concerning unitary Hessenberg matrices, the Schur parameters and the complementary parameters of a Hessenberg matrix \(H\), and the unitary Hessenberg QR algorithm from the point of view of existing results in the literature. ection two presents the UHQR algorithm, which in its original formulation is numerically unstable, W. B. Gragg [Stabilization of the UHQR algorithm. Z. Chen Y. Li, C. Michelli and Y. Xu (eds.), Lect. Notes Pure Appl. Math. 202, 139–154 (1998; Zbl 0932.65047)]. Three modifications lead to a provably stable algorithm. Then, the author presents a stabilized UHQR algorithm. If the eigenvectors are not desired, the above stabilized UHQR algorithm can be converted to a rational algorithm that avoids the use of square roots.
The general issues are given in section three. Thus, the analysis involves both forward and backward errors. With \(\varepsilon\) defined by the unit roundoff, bounds on the forward and backward errors are written in terms of the three basic sources of error \(\varepsilon\), \(\delta\) and \(\delta_z\). All three errors must be small for the resulting bounds to imply stability.
Section four begins with an analysis of the normalization errors. The author shows that the normalization errors \(\delta_k\) do not increase over the course of repeated UHQR iterations.
He continues in section five with a backward error analysis and one bounds the backward errors.
Section six concerns the forward errors. Combining the results of this section with the results of the previous one, the author deduces bounds on the relative backward errors and bounds on the relative forward errors.
The last section is devoted to the final error bounds.
Reviewer: R. Militaru (Craiova)
