On the real convergence rate of the conjugate gradient method

AbstractWe present a parametrized class of matrices for which the rate of convergence of the conjugate gradient method varies greatly with the parameter and does not appreciably depend on the algorithm implementation. A small change in the eigenvalue distribution can lead to a large change in the sensitivity of CG to rounding errors. A theorem is proved which gives a necessary and sufficient condition for ordering exact arithmetic CG processes for systems with different spectra according to the energy norm of the error. Theorems 4.1 and 4.2 continue Paige's and Greenbaum's work