The conjugate gradient method is an algorithm for finding the nearest local minimum of a function of gradient of the
function can be computed. It uses conjugate directions instead of the local gradient
for going downhill. If the vicinity of the minimum has
the shape of a long, narrow valley, the minimum is reached
in far fewer steps than would be the case using the method
of steepest descent .
For a discussion of the conjugate gradient method on vector and shared memory computers, see Dongarra et al. (1991). For discussions of the method for more general
parallel architectures, see Demmel et al. (1993) and Ortega (1988) and the
references therein.
See also Biconjugate Gradient Method ,
Biconjugate Gradient Stabilized
Method ,
Chebyshev Iteration ,
Conjugate
Gradient Method on the Normal Equations ,
Conjugate
Gradient Squared Method ,
Generalized
Minimal Residual Method ,
Gradient ,
Linear
System of Equations ,
Local Minimum ,
Method
of Steepest Descent ,
Minimal Residual Method ,
Minimum ,
Quasi-Minimal
Residual Method ,
Stationary Iterative
Method ,
Symmetric LQ Method
Portions of this entry contributed by Noel Black and Shirley Moore, adapted from Barrett et al. (1994) (author's link )
Explore with Wolfram|Alpha
References Axelsson, O. and Barker, A. Finite Element Solution of Boundary Value Problems: Theory and Computation. Barrett, R.; Berry, M.; Chan, T. F.;
Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; and van
der Vorst, H. Templates
for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed. http://www.netlib.org/linalg/html_templates/Templates.html . Brodile,
K. W. "Unconstrained Minimization." §3.1.7 in The
State of the Art in Numerical Analysis Bulirsch, R. and Stoer,
J. "The Conjugate-Gradient Method of Hestenes and Stiefel." §8.7 in
Introduction
to Numerical Analysis. Concus,
P.; Golub, G.; and O'Leary, D. "Generalized Conjugate Gradient Method for the
Numerical Solution of Elliptic Partial Differential Equations." In Sparse
Matrix Computations Demmel, J.; Heath, M.; and van der Vorst,
H. "Parallel Numerical Linear Algebra." In Acta Numerica, Vol. 2.
Cambridge, England: Cambridge University Press, 1993. Dongarra, J.; Duff,
I.; Sorensen, D.; and van der Vorst, H. Solving
Linear Systems on Vector and Shared Memory Computers. Golub, G. and O'Leary, D. "Some History of the Conjugate Gradient
and Lanczos Methods." SIAM Rev. 31 , 50-102, 1989. Golub,
G. H. and Van Loan, C. F. Matrix
Computations, 3rd ed. Hackbusch, W. Iterative
Lösung großer schwachbesetzter Gleichungssysteme. Kaniel, S. "Estimates for Some Computational Techniques
in Linear Algebra." Math. Comput. 20 , 369-378, 1966. Ortega,
J. M. Introduction
to Parallel and Vector Solution of Linear Systems. Polak, E. "Conjugate Gradient in Rn" in Computational
Methods in Optimization." §2.3 in Computational
Methods in Optimization. Press,
W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T.
Numerical
Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Reid, J. "On
the Method of Conjugate Gradients for the Solution of Large Sparse Systems of Linear
Equations." In Large
Sparse Sets of Linear Equations: Proceedings of the Oxford conference of the Institute
of Mathematics and Its Applications held in April, 1970 van der Sluis, A. and
van der Vorst, H. "The Rate of Convergence of Conjugate Gradients." Numer.
Math. 48 , 543-560, 1986. Referenced on Wolfram|Alpha Conjugate Gradient Method
Cite this as:
Black, Noel ; Moore, Shirley ; and Weisstein, Eric W. "Conjugate
Gradient Method." From MathWorld https://mathworld.wolfram.com/ConjugateGradientMethod.html
Subject classifications
variables which presupposes that the gradient of the
function can be computed. It uses conjugate directions instead of the local gradient
for going downhill. If the vicinity of the minimum has
the shape of a long, narrow valley, the minimum is reached
in far fewer steps than would be the case using the method
of steepest descent.
