View source for Conjugate gradients, method of

''conjugate-gradient method''

A method of solving a system of linear algebraic equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250301.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250302.png" /> is a positive-definite (symmetric) matrix. This is at the same time a direct and an iterative method: for any initial approximation, it converges after a finite number of iterations to give the exact solution. In this method the matrix of the system does not change in the process of calculation and at every iteration it is only used to multiply a vector. Therefore, the order of systems that can be solved on computers is high, being determined by the amount of numerical information needed to specify the matrix.

As a direct method, its structure is based on the process of sequential <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250303.png" />-orthogonalization of a set of vectors, and is an ordinary orthogonalization process (see [[Orthogonalization method|Orthogonalization method]]) with respect to the scalar product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250304.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250305.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250306.png" />-orthogonal basis of the space, then for any initial approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250307.png" />, the exact solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250308.png" /> of the system can be obtained from the decomposition

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c0250309.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503010.png" /> is the discrepancy of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503011.png" />. In the conjugate-gradient method, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503012.png" />-orthogonal vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503013.png" /> are constructed by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503014.png" />-orthogonalizing the discrepancies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503015.png" /> of the sequence of approximations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503016.png" />, given by the formulas

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503017.png" /></td> </tr></table>

The vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503019.png" /> constructed in this way have the following properties:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503020.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

The conjugate-gradient method is now defined by the following recurrence relations (see [[#References|[1]]]):

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503021.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

The process ends at some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503022.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503023.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503024.png" />. The cut-off point is determined by the initial approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503025.png" />. It follows from the recurrence relations (2) that the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503026.png" /> are linear combinations of the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503028.png" />. Since the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503029.png" /> are orthogonal, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503030.png" /> can only vanish when the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503032.png" /> are linearly dependent, as occurs for example when there are only <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503033.png" /> non-zero components in the decomposition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503034.png" /> with respect to a basis of eigen vectors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503035.png" />. This consideration can influence the choice of initial approximation.

The conjugate-gradient method is related to a class of methods in which for a solution a vector that minimizes some functional is taken. To calculate this vector an iterated sequence is constructed that converges to the minimum point. The sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503036.png" /> in (2) realizes a minimization of the functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503037.png" />. At the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503038.png" />-th step of the process (2) the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503039.png" /> coincides with the direction of steepest descent (in gradient) of the surface <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503040.png" /> on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503041.png" />-dimensional ellipsoid formed by intersecting the surface with the plane conjugate to the directions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503042.png" />.

This method and its analogues have many different names, such as the Lanczos method, the Hestenes method, the Stiefel method, etc. Of all the methods for minimizing a functional, the conjugate-gradient method is best in strategic layout: it gives the maximal minimization after <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503043.png" /> steps. However, the calculations (2) under real conditions of machine arithmetic are sensitive to rounding-off errors, and the conditions (1) may be violated. This prevents termination of the process after <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503044.png" /> steps. Therefore the method is continued beyond <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503045.png" /> iterations, and it can be regarded as an infinite iterative process for minimizing a functional. Modifications of the calculating scheme (2) that are more resistant to rounding-off errors are known (see [[#References|[3]]], [[#References|[4]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  D.K. Faddeev,   V.N. Faddeeva,   "Computational methods of linear algebra" , Freeman  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.S. Berezin,   N.P. Zhidkov,   "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.V. Voevodin,   "Numerical methods of algebra" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR></table>



====Comments====
The Stiefel method is related to the Zukhovitskii method for the minimax solution of a linear system, cf. [[#References|[a1]]].

Modifications of the method of steepest descent can be found in [[#References|[a1]]], [[#References|[a12]]].

The classic reference for the conjugate-gradient method is [[#References|[a4]]]. An up-to-date discussion with additional references is [[#References|[a3]]]. Its relation with matrix factorization is discussed in [[#References|[a9]]].

It appears that J.K. Reid was the first to use this method as an iterative method (cf. [[#References|[a8]]]).

Several modifications have been proposed. E.g. the pre-conditioned conjugate-gradient method (cf. [[#References|[a2]]]), and conjugate-gradient methods using incomplete Cholesky factorization (so-called ICCG methods, cf. [[#References|[a7]]] and [[#References|[a6]]]).

Extensions to non-symmetric conjugate-gradient methods are discussed in [[#References|[a1]]] and [[#References|[a10]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  O. Axelsson,   "Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations"  ''Lin. Alg. and its Appl.'' , '''34'''  (1980)  pp. 1–66</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Concus,   G.H. Golub,   D.P. O'Leary,   "A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations"  J.R. Bunch (ed.)  D.J. Rose (ed.) , ''Sparse matrix computations'' , Acad. Press  (1976)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.H. Golub,   C.F. van Loan,   "Matrix computations" , North Oxford Acad.  (1983)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M.R. Hestenes,   "Conjugate directions methods in optimization" , Springer  (1980)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M.R. Hestenes,   E. Stiefel,   "Methods of conjugate gradients for solving linear systems"  ''J. Res. Nat. Bur. Stand.'' , '''49'''  (1952)  pp. 409–436</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  T.A. Manteuffel,   "Shifted incomplete Cholesky factorization"  I.S. Duff (ed.)  G.W. Stewart (ed.) , ''Sparse matrix proceedings'' , SIAM Publ.  (1979)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.A. Meijerink,   H.A. van der Vorst,   "An iterative solution method for linear systems of which the coefficient matrix is a symmetric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025030/c02503046.png" />-matrix"  ''Math. Comp.'' , '''31'''  (1977)  pp. 148–162</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J.K. Reid,   "On the method of conjugate gradients for the solution of large systems of linear equations"  J.K. Reid (ed.) , ''Large sparse sets of linear equations'' , Acad. Press  (1971)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  G.W. Stewart,   "Conjugate gradients methods for solving systems of linear equations"  ''Numerical Math.'' , '''21'''  (1973)  pp. 284–297</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  D.M. Young,   K.C. Jea,   "Generalized conjugate gradient acceleration of non-symmetrizable iterative methods"  ''Lin. Alg. and its Appl.'' , '''34'''  (1980)  pp. 159–194</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  S.I. [S.I. Zukhovitskii] Zukhovitsky,   L.I. Avdeeva,   "Linear and convex programming" , Saunders  (1966)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  G. Zoutendijk,   "Methods of feasible directions" , Elsevier  (1960)</TD></TR></table>