Superlinear convergence of conjugate gradients

We give a theoretical explanation for superlinear convergence behavior obse rved while solving large symmetric systems of equations using the conjugate gradient method or other Krylov subspace methods. We present a new bound o n the relative error after n iterations. This bound is valid in an asymptot ic sense when the size N of the system grows together with the number of it erations. The bound depends on the asymptotic eigenvalue distribution and o n the ratio n/N. Under appropriate conditions we show that the bound is asy mptotically sharp. Our findings are related to some recent results concerning asymptotics of d iscrete orthogonal polynomials. An important tool in our investigations is a constrained energy problem in logarithmic potential theory. The new asymptotic bounds for the rate of convergence are illustrated by di scussing Toeplitz systems as well as a model problem stemming from the disc retization of the Poisson equation.