A European Informational Website
learn more
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. Various nonlinear conjugate gradient methods seek minima to nonlinear equations.
Suppose we want to solve the following system of linear equations where the n-by-n matrix A is symmetric (i.e., A<sup>T</sup> = A), positive definite (i.e., x<sup>T</sup>Ax > 0 for all non-zero vectors x in R<sup>n</sup>), and real.
We denote the unique solution of this system by x<sub>*</sub>.
We say that two non-zero vectors u and v are conjugate (with respect to A) if Since A is symmetric and positive definite, the left-hand side defines an inner product 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<sub>k</sub>} is a sequence of n mutually conjugate directions. Then the p<sub>k</sub> form a basis of R<sup>n</sup>, so we can expand the solution x<sub>*</sub> of Ax = b in this basis: The coefficients are given by 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 α<sub>k</sub>.
If we choose the conjugate vectors p<sub>k</sub> carefully, then we may not need all of them to obtain a good approximation to the solution x<sub>*</sub>. 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<sub>*</sub> by x<sub>0</sub>. We can assume without loss of generality that x<sub>0</sub> = 0 (otherwise, consider the system Az = b − Ax<sub>0</sub> instead). Note that the solution x<sub>*</sub> is also the unique minimizer of the quadratic form This suggests taking the first basis vector p<sub>1</sub> to be the gradient of f at x = x<sub>0</sub>, which equals -b. The other vectors in the basis will be conjugate to the gradient, hence the name conjugate gradient method.
Let r<sub>k</sub> be the residual at the kth step: Note that r<sub>k</sub> is the negative gradient of f at x = x<sub>k</sub>, so the gradient descent method would be to move in the direction r<sub>k</sub>. Here, we insist that the directions p<sub>k</sub> are conjugate to each other, so we take the direction closest to the gradient r<sub>k</sub> under the conjugacy constraint. This gives the following expression:
After some simplifications, this results in the following algorithm for solving where is a real, symmetric, positive-definite matrix. The input vector can be an approximate initial solution or 0.
repeat if r<sub>k+1</sub> is "sufficiently small" then exit loop end if end repeat The result is
A preconditioner is a matrix P such that P<sup>-1</sup>A has a smaller condition number (κ) than A and so solving P<sup>-1</sup>Ax=b is faster than solving Ax=b (see preconditioned conjugate gradient method).
The conjugate gradient method can be applied to an arbitrary n-by-m matrix by applying it to normal equations A<sup>T</sup>A and A<sup>T</sup>b, since A<sup>T</sup>A is a symmetric positive (semi-)definite matrix for any A. The result is conjugate gradient on the normal equations (CGNR).
As an iterative method, it is not necessary to form A<sup>T</sup>A explicitly in memory but only to perform the matrix-vector and transpose matrix-vector multiplications. Therefore CGNR is suitable as a general purpose method when A is a sparse matrix. However the condition number κ(A<sup>T</sup>A) is equal to κ(A)<sup>2</sup> and so the rate of convergence of CGNR may be slow. Finding a good preconditioner is often an important part of using the CGNR method.
Several algorithms have been proposed (e.g. CGLS, LSQR). The LSQR algorithm purportedly has the best numerical stability when A is ill-conditioned, i.e. A has a large condition number.
The conjugate gradient method was originally proposed in
Descriptions of the method can be found in the following text books: