Past exam of the mathematics course of the University of Cambridge / 2014 / ib / Paper 1 / 18C (Numerical Analysis)

For a nonzero real vector $v$, the Householder transformation isWriting $P=v{v}^T/(v^{T}v)$ gives $P^T=P$, $P^2=P$, so $H^T=H$ and $H^{T}H=(I-2P{)}^2=I$. Thus $H$ is orthogonal. It reverses the component along $v$ and fixes its orthogonal complement.

For Householder QR decomposition, successively choose a reflector on each trailing row block to send its current column to a multiple of the first coordinate vector. Each step annihilates the subdiagonal entries without disturbing earlier columns. The reflector product gives an upper-trapezoidal $R$ and its transpose gives an orthogonal $Q$ with $A=QR$.

Here the first column has norm four. Taking $v=(-1,1,-1,1{)}^T$ gives $H_1=I-v{v}^T/2$ andThe second column already has no unwanted entries. On the last two rows, reflect using $(-1,2{)}^T$:This maps $(9,12{)}^T$ to $(15,0{)}^T$. Therefore a full QR factorization isBoth displayed factors arise from the explicit reflectors; in particular $Q^{T}Q=I_4$ and $QR=A$.

The first three diagonal entries of $R$ are nonzero, so the column rank is three and a consistent system has a unique solution. Consistency requires the last component of $Q^{T}b$ to vanish. For the given right side this component isHenceFor this value the transformed right side is $(3,2,5,0{)}^T$. Back substitution also gives $x=(-5/12,1/2,1/3{)}^T$. This illustrates the Householder reduction of an overdetermined consistent system.