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

For a nonzero real vector $w$, a Householder reflection isWriting $P=w{w}^T/(w^{T}w)$ gives $P^T=P$ and $P^2=P$, so $H^{T}H=(I-2P{)}^2=I$. Thus a Householder matrix is an orthogonal matrix, and it reflects across the hyperplane perpendicular to $w$.

For $u\ne 0$, choose $\alpha =-\mathrm{sgn}(u_1)\Vert u\Vert$, taking the sign to be $+1$ when $u_1=0$, and put $w=u-\alpha e_1$. This $w$ is nonzero. Since ${\alpha }^2=\Vert u{\Vert }^2$, direct expansion gives $w^{T}w=2(\Vert u{\Vert }^2-\alpha u_1)$ and $w^{T}u=\Vert u{\Vert }^2-\alpha u_1$, soApply this construction successively to the trailing part of each column of $A$, extending each reflection by an identity on earlier coordinates. Previously created zeros are preserved. If a trailing column vector is zero, use the identity there. The resulting product $Q^T$ is orthogonal and $Q^{T}A=R$ is upper triangular, yielding the QR factorization $A=QR$ even when $A$ is singular.

To solve $Ax=b$, multiply by $Q^T$ and use back substitution on $Rx=Q^{T}b$ when $R$ is nonsingular. If $A$ is singular, $\det R=\det (Q^T)\det A=0$; an upper triangular determinant is its diagonal product, so at least one diagonal entry is zero. In that case consistency and free variables require separate treatment.

The unshifted QR algorithm starts from $A_0=A$, factors $A_k=Q_k{R}_k$, and formsEvery iterate is related by an orthogonal similarity transformation to the previous one and hence to $A$, with the same eigenvalues. Symmetry is preserved. For symmetric matrices with appropriate spectral separation, the iterates approach diagonal form: the off-diagonal entries decrease and the diagonal exposes the eigenvalues. Practical shifted QR accelerates convergence and uses deflation when off-diagonal couplings become negligible. With a shift ${\mu }_k$, factor $A_k-{\mu }_{k}I=Q_k{R}_k$ and set $A_{k+1}=R_k{Q}_k+{\mu }_{k}I$; the same similarity identity still holds.

Universal diagonal convergence of unshifted QR would be too strong. For example $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ admits the standard factorization $Q=A$, $R=I$, so the iteration remains at $A$ rather than becoming diagonal, although its eigenvalues are $\pm 1$. Such equal-modulus cases require a convergence qualification or treatment of a retained block. Similarity is unconditional; convergence to a useful limiting form is an additional algorithmic property.