Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 4 / 37E (Numerical Analysis)

The Krylov subspace is $K_m(A,v)=\mathrm{span}\{v,Av,\dots ,A^{m-1}v\}$. Let $s$ be the first index for which $A^{s}v$ depends linearly on $v,\dots ,A^{s-1}v$. Such an index exists with $1\le s\le n$, since $v\ne 0$ and any $n+1$ vectors are dependent. The first $s$ vectors are independent. The relation for $A^{s}v$ shows that their span is invariant under $A$: multiplying any generator by $A$ stays in that span. Repeated multiplication makes every higher power stay there too. ThereforeOnce a Krylov subspace stops growing, it cannot resume growth.

Let the distinct eigenvalues be ${\lambda }_1,\dots ,{\lambda }_{s^{\prime }}$. Distinct-eigenvalue eigenvectors are independent. A relation ${\sum }_{k=0}^{m-1}{a}_k{A}^{k}v=0$ becomes ${\sum }_i{c}_{i}p({\lambda }_i)w_i=0$, with $p(z)={\sum }_{k<m}{a}_k{z}^k$. Since every $c_i\ne 0$, it requires $p({\lambda }_i)=0$ for every $i$. No nonzero polynomial of degree below $s^{\prime }$ has that many distinct roots. Thus the first $s^{\prime }$ powers are independent, while ${\prod }_i(A-{\lambda }_{i}I)v=0$ gives the next dependence. Hence $\boxed{s=s^{\prime }}$. Equivalently the coefficients of these powers form a full-rank Vandermonde matrix through this index.

The linear-system residual at an approximate solution $x_m$ is $r_m=b-A{x}_m$. For symmetric positive definite $A$, the Conjugate gradient method has $x_m\in x_0+K_m(A,r_0)$ and minimizes the squared $A$-norm of the error over that affine space; its residual is orthogonal to $K_m(A,r_0)$.

If $A$ has $t$ distinct eigenvalues, interpolate $q(\lambda )=1/\lambda$ on them with a polynomial of degree at most $t-1$. The finite-dimensional spectral theorem gives $A^{-1}=q(A)$, so the exact correction $x_{\ast }-x_0=A^{-1}{r}_0$ lies in $K_t(A,r_0)$. The minimum possible error at step $t$ is therefore zero. Thus $\boxed{\text{CG terminates in at most }t\text{ steps}}$ in exact arithmetic, possibly earlier if the initial residual has fewer eigencomponents. If $r_0=0$, it terminates immediately.

A symmetric positive definite matrix preconditioner $M$ changes the system to $M^{-1/2}A{M}^{-1/2}z=M^{-1/2}b$, with $x=M^{-1/2}z$; practical preconditioned CG applies solves with $M$. It can accelerate convergence by reducing the spectral condition number of a positive-definite matrix, which improves the usual bound involving $(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$, and by clustering eigenvalues, which allows low-degree residual polynomials small on the spectrum even when the extreme-eigenvalue bound is pessimistic.

Choosing $\boxed{M=A}$ makes the transformed matrix $I$, so one step suffices. But applying $M^{-1}$ already requires solving the original problem, and constructing an exact factorization generally incurs its original computational cost. It is therefore not a useful shortcut for a single unsolved system, though an available factorization can be reused for multiple right-hand sides. Effective matrix preconditioning balances spectral improvement against inexpensive application.