TOPICS
Search

Conjugate Gradient Method


The conjugate gradient method is an algorithm for finding the nearest local minimum of a function of n 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.

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, Flexible Generalized Minimal Residual Method, Generalized Minimal Residual Method, Gradient, Linear System of Equations, Local Minimum, Method of Steepest Descent, Minimal Residual Method, Minimum, Nonstationary Iterative Method, Preconditioner, Quasi-Minimal Residual Method, Stationary Iterative Method, Symmetric LQ Method, Transpose-Free Quasi-Minimal Residual 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. Orlando, Florida: Academic Press, 1984.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. Philadelphia, PA: SIAM, 1994. 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 (Ed. D. A. E. Jacobs). London: Academic Press, pp. 229-268, 1977.Bulirsch, R. and Stoer, J. "The Conjugate-Gradient Method of Hestenes and Stiefel." §8.7 in Introduction to Numerical Analysis. New York: Springer-Verlag, 1991.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 (Ed. J. Bunch and D. Rose). New York: Academic Press, pp. 309-332, 1976.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. Philadelphia, PA: SIAM, 1991.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. Baltimore, MD: Johns Hopkins University Press, p. 310, 1996.Hackbusch, W. Iterative Lösung großer schwachbesetzter Gleichungssysteme. Stuttgart, Germany: Teubner, 1991.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. New York: Plenum Press, 1988.Polak, E. "Conjugate Gradient in Rn" in Computational Methods in Optimization." §2.3 in Computational Methods in Optimization. New York: Academic Press, pp. 44-66, 1971.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 413-417, 1992.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 (Ed. J. Reid). London: Academic Press, pp. 231-254, 1971.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--A Wolfram Web Resource. https://mathworld.wolfram.com/ConjugateGradientMethod.html

Subject classifications