Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 2 / 19D (Numerical Analysis)

A Givens rotation is the identity outside rows and columns $p,q$, with the $2\times 2$ blockThe block's transpose times itself is the identity, so the whole matrix satisfies $\boxed{{\Omega }^T\Omega =I}$ and is an orthogonal matrix. In particular it preserves the Euclidean norm. To annihilate the lower entry of a column pair $(a,b{)}^T$, take $c=a/r$, $s=b/r$, $r=\sqrt{a^2+b^2}$; the rotated pair is $(r,0{)}^T$. If both entries are zero, take the identity rotation.

A QR decomposition of an $m\times n$ matrix, $m\ge n$, is $A=QR$, where $Q$ is an $m\times m$ orthogonal matrix and $R$ is $m\times n$ and upper trapezoidal: $R_{ij}=0$ for $i>j$. In particular its bottom $m-n$ rows vanish.

Successive left Givens rotations annihilate the entries below the diagonal, column by column. When working on column $j$, rotate rows $j$ and $i>j$; their earlier columns are already zero, so the earlier eliminations persist. If $G_k\cdots G_{1}A=R$, thenA product of orthogonal matrices is orthogonal. The construction remains valid for a rank-deficient matrix, although uniqueness is not asserted. This is QR decomposition by Givens rotations.

First rotate rows $2,3$ with $c=4/5$, $s=3/5$. The second column pair $(4,3)$ becomes $(5,0)$ and the corresponding third column pair $(1,2)$ becomes $(2,1)$. Next rotate rows $3,4$ with $c=4/5$, $s=3/5$, sending the third column pair $(1,3/4)$ to $(5/4,0)$. Thus $R=G_{34}{G}_{23}A$ and $Q=G_{23}^T{G}_{34}^T$. One exact QR decomposition isThe construction proves $Q^{T}Q=I$, and direct multiplication checks $QR=A$.

The orthogonal matrix $Q$ preserves the Euclidean norm, soThe first three entries of $Rx-Q^{T}b$ can be set to zero by backward substitution in a triangular system, while its fourth entry is always $3$. Solving the triangular system gives $x_3=16/5$, $x_2=(35-2x_3)/5=143/25$, and $x_1=(98/25-x_2-x_3)/3=-5/3$. Thus the unique least-squares solution and residual norm areUniqueness follows from the nonzero diagonal entries of the top triangular block, equivalently the full column rank of $A$.