In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive definite. The conjugate gradient method is an iterative method, so it can be applied to sparse systems which are too large to be handled by direct methods such as the Cholesky decomposition. Such systems arise regularly when numerically solving partial differential equations.

The conjugate gradient method can also be used to solve unconstrained optimization problems.

The biconjugate gradient method provides a generalization to non-symmetric matrices.

Description of the method

---

Suppose we want to solve the following system of linear equations

$Ax\; =\; b,\backslash ,$

where the n-by-n matrix A is symmetric (i.e., A^T = A), positive definite (i.e., x^TAx > 0 for all non-zero vectors x in Rⁿ), and real.

We denote the unique solution of this system by x_*.

The conjugate gradient method as a direct method

We say that two non-zero vectors u and v are conjugate (with respect to A) if

$u^\backslash top\; A\; v\; =\; 0.$

Since A is symmetric and positive definite, the left-hand side defines an inner product

$\backslash langle\; u,v\; \backslash rangle\_A\; =\; u^\backslash top\; A\; v.$

So, two vectors are conjugate if they are orthogonal with respect to this inner product. Being conjugate is a symmetric relation: if u is conjugate to v, then v is conjugate to u. (Note. This notion of conjugate is not related to the notion of complex conjugate.)

Suppose that {p_k} is a sequence of n mutually conjugate directions. Then the p_k form a basis of Rⁿ, so we can expand the solution x_* of Ax = b in this basis:

$x\_*\; =\; \backslash alpha\_1\; p\_1\; +\; \backslash cdots\; +\; \backslash alpha\_n\; p\_n.$

The coefficients are given by

$\backslash alpha\_k\; =\; \backslash frac\{p\_k^\backslash top\; b\}\{p\_k^\backslash top\; A\; p\_k\}.$

This result is perhaps most transparent by considering the inner product defined above.

This gives the following method for solving the equation Ax = b. We first find a sequence of n conjugate directions and then we compute the coefficients α_k.

The conjugate gradient method as an iterative method

If we choose the conjugate vectors p_k carefully, then we may not need all of them to obtain a good approximation to the solution x_*. So, we want to regard the conjugate gradient method as an iterative method. This also allows us to solve systems where n is so large that the direct method would take too much time. We denote the initial guess for x_* by x₀. We can assume without loss of generality that x₀ = 0 (otherwise, consider the system Az = b − Ax₀ instead). Note that the solution x_* is also the unique minimizer of

$f(x)\; =\; \backslash frac12\; x^\backslash top\; A\; x\; -\; b^\backslash top\; x,\; \backslash quad\; x\backslash in\backslash mathbf\{R\}^n.$

This suggests taking the first basis vector p₁ to be the gradient of f at x = x₀, which equals b. The other vectors in the basis will be conjugate to the gradient, hence the name conjugate gradient method.

Let r_k be the residual at the kth step:

$r\_k\; =\; b\; -\; Ax\_k.\backslash ,$

Note that r_k is the gradient of f at x = x_k, so the gradient descent method would be to move in the direction r_k. Here, we insist that the directions p_k are conjugate to each other, so we take the direction closest to the gradient r_k under the conjugacy constraint. This gives the following expression:

$p\_\{k+1\}\; =\; r\_k\; -\; \backslash frac\{p\_k^\backslash top\; A\; r\_k\}\{p\_k^\backslash top\; A\; p\_k\}\; p\_k.$

The resulting algorithm

After some simplifications, this results in the following algorithm for solving $Ax\; =\; b$ where $A$ is a real, symmetric, positive-definite matrix. The input vector $x\_0$ can be an approximate initial solution or 0.

$k\; :=\; 0$

$r\_0\; :=\; b\; -\; A\; x\_0$

repeat until $r\_k$ is "sufficiently small":

$k\; :=\; k\; +\; 1$

if $k\; =\; 1$

$p\_1\; :=\; r\_0$

else

$p\_k\; :=\; r\_\{k-1\}\; +\; \backslash frac\{r\_\{k-1\}^\backslash top\; r\_\{k-1\}\}\{r\_\{k-2\}^\backslash top\; r\_\{k-2\}\}~p\_\{k-1\}$

end if

$\backslash alpha\_k\; :=\; \backslash frac\{r\_\{k-1\}^\backslash top\; r\_\{k-1\}\}\{p\_k^\backslash top\; A\; p\_k\}$

$x\_k\; :=\; x\_k-1\; +\; \backslash alpha\_k\; p\_k$

$r\_k\; :=\; r\_k-1\; -\; \backslash alpha\_k\; A\; p\_k$

end repeat

The result is $x\_k$

External links

---

• Méthode du gradient conjugé (Conjugate gradient method, in French) by N. Soualem.
• Méthode du gradient conjugé préconditionné (Preconditioned conjugate gradient method, in French) by N. Soualem.
• An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuk.

References

---

The conjugate gradient method was originally proposed in

• Magnus R. Hestenes and Eduard Stiefel (1952), Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49, 409–436.

A description of method can be found in the following text books:

• Kendell A. Atkinson (1988), An introduction to numerical analysis (2nd ed.), Section 8.9, John Wiley and Sons. ISBN 0-471-50023-2.
• Gene H. Golub and Charles F. Van Loan, Matrix computations (3rd ed.), Chapter 10, Johns Hopkins University Press. ISBN 0-8018-5414-8.

Numerical linear algebra | Optimization algorithms

CG-Verfahren | Méthode du gradient conjugué | 共役勾配法 | 共轭梯度法