Superlinear convergence of conjugate gradients

Question

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

Answer 1

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...

Answer 2

There was actually a paper on this:

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