The QR algorithm for unitary Hessenberg matrices

摘要

Let H be an n × n unitary right Hessenberg matrix with positive subdiagonal elements. Using what we call the Schur parameterization of H, we show how one step of the shifted QR algorithm for H can be carried out in O(n) arithmetic operations. Coupled with the shift strategy of Eberlein and Huang [3], this will permit computation of the spectrum of H, to machine precision, in O(n2) operations. One potential application is the computation of Gauss-Szegö quadrature formulas [12], given the associated Schur parameters [7]. The weights can also be computed, by direct analogy with [6].