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

A full QR decomposition of a real $m$ by $n$ matrix with $m\ge n$ writeswhere $Q$ is an orthogonal $m$ by $m$ matrix and $R$ is upper triangular $n$ by $n$. In the full-column-rank case $R$ is invertible. Equivalently the reduced factorization is $A=Q_{1}R$ with $Q_1^T{Q}_1=I_n$. Householder transformations can construct the full factorization.

Let $Q^{T}b=\left(\genfrac{}{}{0ex}{}{c_1}{c_2}\right)$ with $c_1\in {\mathbb{R}}^n$. Since orthogonal transformations preserve the Euclidean norm,Therefore the linear least-squares problem has the full-rank solutionBack substitution solves this triangular system without forming $A^{T}A$. If the matrix is rank deficient, use a rank-revealing pivoted factorization and minimize over its independent columns; the minimizer need not be unique. The original PDF minimizes over $x\in {\mathbb{R}}^n$; the converted TeX's minimization over $b$ is a transcription error.

For a nonzero real vector $v$, its Householder reflection isLet $P=v{v}^T/(v^{T}v)$. Then $P^T=P$ and $P^2=P$, soThus $H$ is an orthogonal matrix, and it is also symmetric with $H^{-1}=H$. It sends $v$ to $-v$ and fixes every vector perpendicular to $v$, explaining the reflection in the hyperplane $v^{\perp }$. For a target reduction of a vector $a$ to $\Vert a\Vert e_1$, choose $v=a-\Vert a\Vert e_1$ when this vector is nonzero; an alternative sign avoids cancellation in numerical implementations.

The first column is $a=(2,1,2{)}^T$ with length three. Choose $v=a-3e_1=(-1,1,2{)}^T$, so $v^{T}v=6$. Its Householder reflection isDirect multiplication givesTo eliminate the remaining third-row entry in the second column, reflect the last two coordinates using $v_2=(0,1,-1{)}^T$. ThenandBoth steps are Householder reflections; the second happens to exchange two coordinates. Solve the leading triangular equations $3x_1+3x_2=3$ and $3x_2=-3$ to obtainFor an independent check, $A{x}^{\ast }-b=(-1,-2,2{)}^T$, whose squared norm is nine and which is orthogonal to both columns of $A$. Thus $A^T(A{x}^{\ast }-b)=0$, confirming the least-squares minimizer.