Iteration number for the conjugate gradient method
The author presents new results about the behaviour of the conjugate gradient method (CGM). The convergence of CGM takes can be described mainly in three phases: (i) an initial phase of rapid convergence during small number of iterations (depends only on the initial error); (ii) a middle phase of essentially linear rate of convergence (depends on the spectral condition number); (iii) a final phase with a superlinear rate of convergence (depends on how the smallest eigenvalues are distributed). The paper is concerned with simplified, unified and improved estimates for a spectrum containing some well separated small eigenvalues and for which the remaining spectrum of largest eigenvalues is fairly uniformly distributed in some interval. The new estimate shows that if the relative precision \(\varepsilon\) is sufficiently small then the method enters the superlinear convergent phase and the the number of iterations depends on the number of computed digits, ln\((1/\varepsilon)\) as O(ln\((1/\varepsilon))^s\) where \(s<1\).
scientific article; zbMATH DE number 1882281