1
$\begingroup$

The global convergence bounds of conjugate gradients are too pessimistic, how can the super-linear convergence, experienced in practice, be explained?

2 Answers 2

2

Well, the conjugate gradient methods is not an iterative technique in the strict sense. It gives the correct answer in a finite number of steps (in exact arithmetic). It is not just converging towards the right solution with some rate. However, in the presence of round-off errors things are complicated but CG behaves somehow stable. This may explain the "super-linear" convergence: The method should succeed when the number of iteration reached the rank of the matrix at hand but the residuum starts to wiggle around a very small number...

  • 1
    The round-off error is an issue, but The local convergence behaviour depends on the distribution of eigenvalues; the more clustered they are, the faster it converges, e.g. diag(1:1000) converges much slower than diag([1:10, 11:1000]). A heuristic explanation is that when the ritz values are sufficiently converged, the convergence is determined by the reduced spectrum.2011-11-14
1

There was actually a paper on this:

Superlinear Convergence of Conjugate Gradients Bernhard Beckermann and Arno B. J. Kuijlaars