Iterative Methods for Linear Systems Consider the system \(Ax=b\), in which \(A\) is a symmetric positive definite real \(m\times m\) matrix, and denote by \(x_*\) its true solution. The conjugate gradient (CG) algorithm for finding the solution to the system is:
Set \(x_0=0\), \(r_0=b\), and \(p_0=r_0\).
For \(n=1,2,3,\ldots \), \[ \alpha _n=\frac {r_{n-1}^T r_{n-1}}{p_{n-1}^T A p_{n-1}}, \] \[ x_n=x_{n-1}+\alpha _n p_{n-1}, \] \[ r_n=r_{n-1}-\alpha _n A p_{n-1}, \] \[ \beta _n=\frac {r_n^T r_n}{r_{n-1}^T r_{n-1}}, \] \[ p_n=r_n+\beta _n p_{n-1}. \] End.
The vectors generated by this algorithm have the property that, provided \(r_{n-1}\ne 0\), \[ \begin {aligned} \mathcal {K}_n &= \operatorname {span}\{b,Ab,A^2b,\ldots ,A^{n-1}b\} = \operatorname {span}\{x_1,x_2,\ldots ,x_n\}\\ &= \operatorname {span}\{r_0,r_1,\ldots ,r_{n-1}\} = \operatorname {span}\{p_0,p_1,\ldots ,p_{n-1}\} \end {aligned} \] and \(r_n^T r_j=0\) and \(p_n^T A p_j=0\) for all \(j<n\).
Let \(e_n=\lVert x_n-x_*\rVert _A\), where the \(A\)-norm of a vector \(x\) is defined by \(\lVert x\rVert _A=(x^T Ax)^{1/2}\).
a) Prove the following: Suppose the CG algorithm is applied to the symmetric positive definite system \(Ax=b\) and that it has not yet converged (\(r_{n-1}\ne 0\)). Then \(e_n<\lVert y-x_*\rVert _A\) for all \(y\in \mathcal {K}_n\), \(y\ne x_n\); \(\lVert e_n\rVert _A\le \lVert e_{n-1}\rVert _A\); and \(e_N\to 0\) for some \(N\le m\).
b) In practice this result is not very useful. Why is this, and what determines the speed of convergence of \(x_n\) to \(x_*\)? What is ‘preconditioning’ and how is it related to the speed of convergence of the CG algorithm?