conjugate gradient algorithm

The conjugate gradient algorithm is used to solve the quadratic minimization problem:


or equivalently to solve the linear system Qx-b=0, where Q is a given n by n symmetricPlanetmathPlanetmathPlanetmathPlanetmath positive definite matrix and b is a given n vector.

The algorithmMathworldPlanetmath requires n iterationsMathworldPlanetmath, starting from an arbitrary initial guess x0 (often x0=0 is used). We will use the following notation:

  • i — iteration number;

  • xi — solution approximation;

  • di — search direction;

  • ri — residual, which is defined as b-Qxi.


  1. 1.

    Initialization. Let x0=0 (or other starting point). Let r0=d0=-Qx0+b. (The initial search direction is set to minus the gradientMathworldPlanetmath of the quadratic function being minimized, evaluated at the starting point).

  2. 2.

    For i=0 to n-1 compute


    If ri<ε or i=n-1 Stop, the solution has been found. Otherwise, continue:


    (In each iteration the solution estimate is set to the previous estimate plus a multiple of the previous search direction. The next search direction is then set to the gradient plus a multiple of the previous search direction).


The conjugate gradient method was developed in 1952 by Hestenes and Stiefel as an improvement to the steepest descent method. Whereas steepest descent approaches the solution asymptotically, the conjugate gradient method will find the solution in n iterations (assuming no roundoff error).

Why the name? The search directions di are conjugate in the sense that djTQdi=0 for j<i. In addition these directions are computed from (but are not equal to) the gradient.

The conjugate gradient method has been generalized to the case where the function being minimized is only approximately quadratic. In that case the explicit formula for α given above is replaced by a line-search procedure; this is a trial and error method in which various values of α are tried, and the value that leads to the smallest value of the objective is chosen. Well known generalized c.g. methods include the Fletcher-Reeves method and the Polak-Ribiere method.




We have




and finally


which is the solution.


Luenberger: Introduction to Linear and Nonlinear Programming, Addison-Wesley, 1973

Jonathan Richard Shewchuk: An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, August 1994. \htmladdnormallink jrs/jrspapers.html jrs/jrspapers.html [A detailed derivation of the method from first principles].

Press, et al.: Numerical Recipes in C, Cambridge University Press, 1995 [Chapter 10.6 contains an implementation of the generalized conjugate gradient method of Polak and Ribiere].

Title conjugate gradient algorithm
Canonical name ConjugateGradientAlgorithm
Date of creation 2013-03-22 14:58:54
Last modified on 2013-03-22 14:58:54
Owner aplant (12431)
Last modified by aplant (12431)
Numerical id 16
Author aplant (12431)
Entry type Algorithm
Classification msc 15A06
Classification msc 90C20
Synonym method of conjugate gradients