Methods of Conjugate Gradients for Solving Linear Systems

Authors

Magnus R. Hestenes, Eduard Stiefel

Year

1952

Journal Paper

Algorithm

Conjugate Gradient

Source

Journal of Research of the National Bureau of Standards

Identifiers

DOI 10.6028/JRES.049.044

Abstract¶

An iterative algorithm is given for solving a system Ax = k of n linear equations in n unknowns. The solution is given in n steps. It is shown that this method is a special case of a very general method which also includes Gaussian elimination. These general algorithms are essentially algorithms for finding an n dimensional ellipsoid. Connections are made with the theory of orthogonal polynomials and continued fractions.

Summary¶

Hestenes and Stiefel introduce the conjugate gradient method for solving linear systems, especially symmetric positive-definite systems, using mutually conjugate directions. The paper explains finite-step exactness in exact arithmetic, connects the method to Gaussian elimination and orthogonal polynomial theory, and became a cornerstone of large-scale numerical linear algebra.