Description

Hessenberg matrices

Hessenberg matrices $H$ satisfy $[H{]}_{ij}=h_{ij}=0,$ for all $i,j$ such that $i>j+1.$ The structure of a Hessenberg matrix can be viewed as that of an upper triangular matrix with an additional $($first$)$ subdiagonal. A $4-$by$-4$ example is included below. Hessenberg matrices allow for several simplified algorithms, due to their simplified structure. For example, the computation of eigenvalues relies on transforming a generic matrix $Ain{R}^{nn}$ into an upper Hessenberg matrix, followed by repeated QR factorisations as part of the celebrated QR algorithm: this approach greatly reduces the complexity of eigenvalue computations.

Givens$-$QR factorisations

Let $H$ denote a square upper Hessenberg matrix. Givens rotations can be used to construct a QR factorisation of $H$ via a sequence of multiplications from the left. This process $($known as the Givens$-$QR factorisation$)$ is illustrated below for a $4-$by$-4$ upper Hessenberg matrix:

Note that the arrows indicate multiplication from the left. These matrices are chosen to zero$-$out the entries indicated by a $+.$ In particular,

$G_1=G(c_1)o+I_2,$ where $c_1$ is the vector containing the entries $1$ and $2$ in the first column of $H_1$;

$G_2=I_{1}o+G(c_2)o+I_1,$ where $c_2$ is the vector containing the entries $2$ and $3$ in the second column of $H_2$;

$G_3=I_{2}o+G(c_3)$ where $c_3$ is the vector containing the entries $3$ and $4$ in the third column of $H_3,$

where $G(c_i)$ are $2-$by$-2$ Givens rotations.

The above process can be written in pseudocode as follows:

$H_1=H$

for $i=1,2,$dots

$,H_{i+1}=G_i{H}_i$

end

$R=H_n$

where the matrices $G_{i}in{R}^{nn}$ are Givens rotations embedded in the identity matrix as indicated above.

$1$

Task

Write a function file givensqr.m to compute the Givens$-$QR factorisation of a general square upper Hessenberg matrix $H.$ Your implementation should fulfil the following requirements and contain the following:

Input variables: square upper Hessenberg matrix $H.$

Output variables: matrices $Q,R$ in this exact order.

Your implementation should not generate the $nn$ matrices $G_i$ : instead it should use the corresponding imbedded $22$ rotations $G(c_i).$

Your implementation should be generally efficient; in particular, it should avoid computations with zeros or ones.

Comments $($using the $\%$ sign$)$ providing short descriptions of your implementation to the user.

The implementation should not use the Householder QR factorisation of $H($which was discussed in Lab $2).$