Past exam of the numerical linear algebra and approximation course of the University of Oxford / 2008 / 4

The Krylov subspace is $\boxed{K_k(A,b)=\mathrm{span}\{b,Ab,\dots ,A^{k-1}b\}}$. If $y\in K_k$, write $y=q(A)b$ with $\mathrm{deg}q\le k-1$. Since $b=Ax$,which has degree at most $k$ and $p(0)=1$. Conversely, if $x-y=p(A)x$ with these properties, then $q(t)=(1-p(t))/t$ is a polynomial of degree at most $k-1$ andThis is the polynomial description of the admissible errors in a Krylov subspace method.

For a symmetric positive-definite matrix, the conjugate gradient method chooses the unique point in $x_0+K_k(A,r_0)$ minimizing the energy norm of the error. Equivalently it minimizes $\frac{1}{2}{y}^{T}Ay-b^{T}y$ on that affine space. Here $x_0=0$ and $r_0=b$.

Choose the eigenbasis orthonormally, as the spectral theorem permits, and write $x={\sum }_i{\alpha }_i{v}_i$. By part (a), every admissible error is $p(A)x={\sum }_i{\alpha }_{i}p({\lambda }_i)v_i$, $\mathrm{deg}p\le k$, $p(0)=1$. Orthogonality then givesThus the implicit CG polynomial minimizes exactly the displayed weighted sum. Strictly, the printed hypothesis that the eigenvectors are individually normalized must be supplemented by mutual orthogonality when eigenvalues repeat. Otherwise cross terms within a repeated-eigenvalue eigenspace need not vanish. An orthonormal eigenbasis always supplies the intended formulation.

If at most $\ell$ eigenvectors contribute to $x$, a polynomial with one factor $1-t/\lambda$ for each distinct contributing eigenvalue is admissible by step $\ell$ and makes that error zero. CG minimizes a nonnegative quantity, so $\boxed{\text{exact termination occurs in at most }\ell \text{ steps}}$.

For the last question, write $x=\alpha v_1+\beta v_2$ with eigenvalues $1,L$, $L=10^6$. The first polynomial has the form $p_1(t)=1-\eta t$. Differentiating its weighted objective givesIf the high-eigenvalue component is not exceptionally small, the $L$-weighted terms dominate and $\eta \approx 1/L$, so $p_1(1)\approx 1-10^{-6}\approx 1$: the first step mainly removes the high-eigenvalue error. This is the spectral weighting of conjugate gradient error. The expectation is conditional on the coefficients, not guaranteed by the two eigenvalues alone; if $\beta =0$, the first step instead solves the low-eigenvalue component exactly.