Math 6610 • Analysis of Numerical Methods I

{Krylov Subspace Methods}
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\)
\[
\begin{aligned}
  \alpha_n &= 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 &= r_n^T r_n/r_{n-1}^T r_{n-1},\\
  p_n &= r_{n-1}+\beta_n p_{n-1}.
\end{aligned}
\]
End

The vectors generated by this algorithm have the property that, provided
\(r_{n-1}\ne0\),
\[
\begin{aligned}
  \mathcal{K}_n
    &\equiv \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^TAx)^{1/2}\).

\textbf{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}\ne0\)). 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=0\) for some \(N\le m\).

\textbf{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?