On Meinardus’ examples for the conjugate gradient method

Abstract:

The conjugate gradient (CG) method is widely used to solve a positive definite linear system $Ax=b$ of order $N$. It is well known that the relative residual of the $k$th approximate solution by CG (with the initial approximation $x_0=0$) is bounded above by \[ 2\left [\Delta _{\kappa }^k+\Delta _{\kappa }^{-k}\right ]^{-1} \quad \mbox {with}\quad \Delta _{\kappa }=\frac {\sqrt {\kappa }+1}{\sqrt {\kappa }-1}, \] where $\kappa \equiv \kappa (A)=\|A\|_2\|A^{-1}\|_2$ is $A$’s spectral condition number. In 1963, Meinardus (Numer. Math., 5 (1963), pp. 14–23) gave an example to achieve this bound for $k=N-1$ but without saying anything about all other $1\le k<N-1$. This very example can be used to show that the bound is sharp for any given $k$ by constructing examples to attain the bound, but such examples depend on $k$ and for them the $(k+1)$th residual is exactly zero. Therefore it would be interesting to know if there is any example on which the CG relative residuals are comparable to the bound for all $1\le k\le N-1$. There are two contributions in this paper:

1. A closed formula for the CG residuals for all $1\le k\le N-1$ on Meinardus’ example is obtained, and in particular it implies that the bound is always within a factor of $\sqrt 2$ of the actual residuals;

2. A complete characterization of extreme positive linear systems for which the $k$th CG residual achieves the bound is also presented.