The new $QR$-algorithm

To illustrate the applicability of the new $QR$-algorithm onto unitary Hessenberg matrices, we assume we are working with a lower unitary Hessenberg matrix $Z=G_{n-1} G_{n-2} \ldots G_{1}.$ There is no loss of generality in this assumption, as one can operate also on $H^H$.

To start with the new approach (we will only consider the case $\kappa=0$), one needs to compute the $RQ$-factorization of the matrix $Z$. Fortunately the matrix is already factored in this form:

$$Z=RQ=R \left(G_{n-1} G_{n-2} \ldots G_{1}\right)= I \left(G_{n-1} G_{n-2} \ldots G_{1}\right)$$

in which $R$ is simply the identity matrix.

To proceed with the new method we obtain, for a suitable chosen shift $\sigma$:

$$Z-\sigma I = ( ZQ^H - \sigma I Q^H ) Q$$

$$= (I-\sigma Q^H)Q$$

$$= \hat{Q} \hat{R} Q.$$

The unitary transformation $\hat{Q}$ determines the new unitary similarity transformation to be performed onto the matrix $Z$. Similarly as in the traditional case the unitary similarity transformation is uniquely determined by the first column of the matrix $\hat{Q}$.

The first column is in turn determined by the unitary transformation $\tilde{Q}$ satisfying $\tilde{Q}^H (I-\sigma Q^H) \mathbf{e}_1=\beta \mathbf{e}_1$. Again this transformation $\tilde{Q}$ is a Givens transformation, chosen such that

$$\tilde{Q}^H [1-\sigma \bar{c}_1,-s,0,\ldots,0]=\beta \mathbf{e}_1.$$ (13)

This transformation needs to be applied onto the lower unitary Hessenberg matrix $Z$, followed by a structure restoring chasing which will also consist of $n-2$ Givens transformations. Again also the shift through lemma can be used to obtain the new Schur parameterization.