Past exam of the numerical analysis course of the University of Oxford / 2015 / 3

A real square matrix $Q$ is an orthogonal matrix when $Q^{T}Q=I$, equivalently its columns form an orthonormal basis. Here $Q^T$ is the transpose and $I$ the identity matrix. For every vector $x$,Taking nonnegative square roots provesThus an orthogonal matrix preserves the Euclidean norm.

Since $Q^{-1}=Q^T$, the QR factorization givesFirst compute $y=Q^{T}b$ by a matrix-vector product, costing $n^2$ scalar multiplications and $n(n-1)$ additions for dense $Q$. Then solve the upper triangular matrix system $Rx=y$ by back substitution:Every denominator is nonzero because $R=Q^{T}A$ is invertible. The back substitution costs $n(n-1)$ multiplications and subtractions together, plus $n$ divisions, for $n^2$ arithmetic operations. Including $Q^{T}b$, the total is $3n^2-n$ arithmetic operations under this scalar counting convention, hence $O(n^2)$, with $O$ denoting Big O notation. The already supplied QR factorization is reused; no matrix inverse needs to be computed.

Choose the following consistent sign convention. The Givens rotation $J(i,j,\theta )$ equals the identity matrix except for the block on coordinates $i,j$:Thus it changes only the $i$th and $j$th coordinates of a vector. Write $c=\cos \theta$, $s=\sin \theta$. Its two-coordinate block satisfiesAll remaining coordinates are unchanged, so $J^{T}J=I_n$. Hence every such Givens rotation is an orthogonal matrix. With this convention the two-coordinate rotation matrix rotates through angle $-\theta$.

Let $r=\sqrt{x_i^2+x_j^2}$. If $r>0$, choose $\theta$ so thatSuch an angle exists because the two ratios have squared sum one. Then the changed coordinates areAll other coordinates satisfy $y_k=x_k$. If $r=0$, both input coordinates are zero; take $\theta =0$, giving the identity matrix on this pair. In all cases,This fixes a nonnegative retained coordinate and handles division by zero explicitly. For floating-point computation, the stable construction of a Givens rotation uses scaled Euclidean norm evaluation to avoid unnecessarily overflowing or underflowing the squares.

Apply the product from right to left, choosing every Givens rotation from the current first column. First $J(1,2)$ replaces $(a_1,a_2)$ by $(\sqrt{a_1^2+a_2^2},0)$. Next $J(1,3)$ combines that retained entry with $a_3$ and sets the third entry to zero. Inductively, after eliminating coordinates $2,\dots ,k$, the first coordinate isand coordinates $2,\dots ,k$ are zero. Later Givens rotations involve only coordinate one and a new coordinate, so those zeros remain zero. Thereforewhere $e_1$ is the first standard basis vector. The zero vector is included by choosing the identity matrix for every zero pair. The nonnegative sign follows from the convention fixed in part (c)(ii). This is the first-column stage of QR decomposition by Givens rotations.

Put $C=Q_{1}A$ and write its second column as $v$. For $n\ge 3$, takewhere each angle is computed from the current second column, in the right-to-left application order. These Givens rotations eliminate its entries in rows $3,\dots ,n$ by accumulating their Euclidean norm in row two.

Each rotation acts only on rows with indices at least two. The first column of $C$ is $\Vert a{\Vert }_2{e}_1$, whose entries in all those rows are zero. Mixing two zeros leaves them zero, and row one is untouched. Thus the first column is unchanged. The resulting matrix has the formThis verifies both required properties, including the case of zero second-column tail. When $n=2$ there are no rows to eliminate: take $Q_2=I_2$, the empty product. No sign change of $v_2$ is required in that case. Each Givens row-pair update preserves previously eliminated columns, which is the central invariant of QR decomposition by Givens rotations.

The orthonormal columns satisfy $\Vert a{\Vert }_2=\Vert b{\Vert }_2=1$ and $a^{T}b=0$. By part (i), $Q_{1}a=e_1$. A product of orthogonal matrices is an orthogonal matrix, since $Q_1^T{Q}_1=I$. ConsequentlyThe last expression is the first coordinate of the transformed second column. Thus the first row isThe one in the first entry uses the nonnegative retained-coordinate convention. A different consistent sign convention could give $(-1,0)$ instead; the second entry must still be zero by preservation of the inner product.