Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / P / P4

For nonzero $w$, the Householder transformation isThe rank-one matrix $P=w{w}^T/(w^{T}w)$ is symmetric and satisfies $P^2=P$. Consequently $H^T=H$ and $H^{T}H=(I-2P{)}^2=I-4P+4P^2=I$. Thus the matrix is symmetric and orthogonal; geometrically it reflects the component along $w$ and fixes its perpendicular hyperplane.

Let $r=\Vert u{\Vert }_2>0$ and choose $s=1$ when $u_1\ge 0$, otherwise $s=-1$. Set $w=u+sr{e}_1$, which is nonzero because $r+s{u}_1>0$. ComputeThus the reflecting term in $H(w)u$ is exactly $w$, givingIts first coordinate is nonzero and all remaining coordinates vanish. The choice of sign also avoids subtracting nearly equal vectors when the first component is large.

Apply part (b) to the first column of $A$, using an orthogonal reflection to zero all entries below the first. Next apply a Householder reflection to the trailing subvector of the second column, embedded as $\mathrm{diag}(1,H_2)$ so it leaves the first row and the zeros already created intact. Continue similarly through the columns. If a trailing column subvector is zero, skip that step.

The product of these embedded orthogonal matrices sends $A$ to an upper triangular matrix $R$. Write that product as $Q^T$; its transpose $Q$ is also orthogonal. HenceThe argument uses no inverse of $A$ and therefore includes singular matrices.

Multiplying the system by $Q^T$ turns it into $Rx=Q^{T}b$. For nonsingular $A$, compute the transformed right side and solve the upper triangular system by back substitution. Orthogonal transformations preserve Euclidean lengths and do not amplify errors in that transformation.

If $A$ is singular,Since $\det Q=\pm 1$, at least one diagonal entry of $R$ is zero. The resulting triangular system must then be checked for consistency and any free variables, rather than applying divisions by zero.