Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 40E (Numerical Analysis)

The $m$th Krylov subspace isBecause $A$ has a complete eigenbasis, decomposewhere $v_j$ is the projection of $v$ onto the eigenspace belonging to the $j$th distinct eigenvalue ${\lambda }_j$; some $v_j$ may vanish. ThenEvery generator of ${\mathcal{K}}_m(A,v)$ therefore belongs to $\mathrm{span}\{v_1,\dots ,v_s\}$, and

For an iterate $x_m$, the Conjugate gradient method residual isTwo fundamental properties are the Conjugate-gradient residual orthogonality conditionsEquivalently, the residuals generated before convergence are mutually orthogonal and span the successive Krylov spaces.

Since $A$ has only $s$ distinct eigenvalues, its minimal polynomial has degree at most $s$. ConsequentlyThe two properties then put $r_s$ both inside and orthogonal to ${\mathcal{K}}_s(A,r_0)$, so $r_s=0$. Hence $A{x}_s=b$, and

Let $e_1=(1,0,\dots ,0{)}^T$. The displayed lower-bidiagonal matrix $Q$ satisfiesSince $P=Q^{-1}$, the Preconditioned conjugate gradient method usesSolving $Qz=e_1$ givesThe rank-one matrix $I+z{z}^T$ has eigenvalue $1+n$ in the direction $z$ and eigenvalue $1$ on the $(n-1)$-dimensional orthogonal complement of $z$. It therefore has only two distinct eigenvalues. Part (b) gives

Because $A$ is a positive-definite matrix, it has a positive-definite inverse square root. Choose the exact inverse-square-root preconditionerThenwhich has one distinct eigenvalue, so preconditioned CG terminates in one step.

This construction is of little computational use because obtaining and applying $A^{-1/2}$ is generally at least as expensive in storage and arithmetic as directly factoring or solving the original system. A useful preconditioner must only approximate this transformation while remaining cheap to construct and apply.