The global convergence bounds of conjugate gradients are too pessimistic, how can the super-linear convergence, experienced in practice, be explained?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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...
There was actually a paper on this:
Superlinear Convergence of Conjugate Gradients Bernhard Beckermann and Arno B. J. Kuijlaars