Past exam of the options II course of the University of Oxford / 2011 / P / P4

For $w\ne 0$, the Householder transformation isLet $P=w{w}^T/(w^{T}w)$. Then $P^T=P$ and $P^2=P$, since $P$ is the orthogonal projection matrix onto the span of $w$. Hence $H^T=H$ andThus $H$ is a symmetric matrix and an orthogonal matrix. Geometrically it reverses the component parallel to $w$ and fixes the perpendicular hyperplane.

Let $r=\Vert u{\Vert }_2>0$, and choose $s=1$ if $u_1\ge 0$ and $s=-1$ otherwise. SetThis vector is nonzero, because $w_1$ has magnitude $|u_1|+r$. Direct computation givesso the Householder transformation satisfiesThe first entry is nonzero and every other entry is zero. The sign choice also avoids cancellation when forming the first entry of $w$, which is useful in numerical computation.

Apply part (b) to the first column of $A$, using the identity if it is already the zero vector. This gives an orthogonal matrix $H_1$ for which $H_{1}A$ has zeros below its first diagonal entry. At stage $j$, apply a Householder transformation to rows $j,\dots ,n$ of column $j$, and extend it by the identity on the first $j-1$ coordinates. If that trailing column is zero, again use the identity. The transformation preserves zeros in earlier columns, since their trailing entries already vanish.

After at most $n-1$ stages,is an upper triangular matrix. Each $H_j$ is symmetric and orthogonal, so withwe have $Q^{T}Q=I$ andNo invertibility assumption was used, so the Householder QR decomposition also exists for singular matrices.

Multiply $Ax=b$ by $Q^T$ to get the equivalent triangular systemFor nonsingular $A$, compute $c=Q^{T}b$ and use back substitution:Orthogonal transformations preserve the Euclidean norm, making this a numerically stable reduction. The factors can be applied as stored Householder transformations without explicitly forming $Q$.

Since $Q$ is invertible, $A$ is singular exactly when $R$ is singular. For an upper triangular matrix,Thus a singular $A$ forces at least one zero diagonal entry in $R$. In that case, ordinary division-based back substitution must be replaced by a consistency/rank analysis: the system may have no solution or infinitely many solutions, and a rank-revealing factorization can identify the free parameters.