The Rate of Convergence of the Conjugate Gradient Method

In the two previous chapters, it was shown that conjugate gradient-type methods have many advantages, one being simplicity of implementation: No method parameter need be estimated, and the method consists mainly of matrix vector multiplications and vector operations. In the present chapter, we shall analyze the rate of convergence of the methods. This will be done not only for the case of a symmetric, positive definite matrix but also for general matrices. First, it will be shown that if the matrix is normal, then the norm of the residual can be estimated by the error in a best polynomial approximation problem. It will then be shown that the rate of convergence depends on the distribution of eigenvalues and, to some extent, also on the initial residual. If the matrix is not normal, the estimate involves also the condition number of the matrix that transforms the given matrix to Jordan canonical form. In general, we are unable to give exact estimates of the rate of convergence, but we shall derive various upper bounds using different methods of estimation. The rate of convergence can be measured in various norms. When we use a relative measure—say, the ratio of the norm of the current residual and the initial residual—it will be shown that the condition number of the matrix can frequently be used to give a sufficiently accurate estimate.