On the sublinear and superlinear rate of convergence of conjugate gradient methods (Q5934347)

The convergence of conjugate gradient methods for solving systems of linear equations with asymmetric positive definite matrix takes typically place in three phases, with a sublinear, linear and superlinear convergence rate, respectively. For explaining this behaviour, polynomials with \(P(0)=1\) and minimal \(\|x^s P(x)\|_{L_\infty [0,1]}\) are considered. [The case \(s=1/2\) can also be found in the analysis of cascadic multigrid methods.] The study also indicates that it can be very efficient to use different preconditioners in different phases.