Past exam of the mathematics course of the University of Cambridge / 2021 / ib / Paper 2 / 17B (Numerical Analysis)

For a nonzero vector $v\in {\mathbb{R}}^n$, a Householder reflection isIt is immediately symmetric. If $P=v{v}^T/(v^{T}v)$, then $P^2=P$, soHence $H$ is also an orthogonal matrix, with $H^{-1}=H$.

The similarity transformation can be expanded asComputing $v^{T}A$, $Av$, and the scalar $v^{T}Av$ costs $O(n^2)$ arithmetic operations, after which the remaining updates are outer products and scalar multiples, also costing $O(n^2)$. Thus $HA{H}^{-1}$ can be formed in $O(n^2)$ operations rather than by two general $O(n^3)$ matrix multiplications.

Starting with $A_1=A$, for $k=1,\dots ,n-2$ choose a Householder reflection $H_k$ that acts only on coordinates $k+1,\dots ,n$ and maps the tail of column $k$,to a multiple of its first coordinate vector. SetThis zeros all entries in column $k$ below its first subdiagonal. Because $H_k$ fixes the first $k$ coordinates, it preserves the zeros created in earlier columns. After $n-2$ steps,is an Upper Hessenberg matrix.

Each $H_k$ is orthogonal and symmetric. Ifthen $Q$ is orthogonal andPart (a) shows that each similarity update costs $O(n^2)$ arithmetic operations, and there are $O(n)$ updates. The total cost is therefore