Editing Conjugate gradient method (section)

{{Short description|Mathematical optimization algorithm}}
[[File:Conjugate gradient illustration.svg|right|thumb|A comparison of the convergence of [[gradient descent]] with optimal step size (in green) and conjugate vector (in red) for minimizing a quadratic function associated with a given linear system. Conjugate gradient, assuming exact arithmetic, converges in at most ''n'' steps, where ''n'' is the size of the matrix of the system (here ''n''&nbsp;=&nbsp;2).]]

In [[mathematics]], the '''conjugate gradient method''' is an [[algorithm]] for the [[numerical solution]] of particular [[system of linear equations|systems of linear equations]], namely those whose matrix is [[positive-semidefinite matrix|positive-semidefinite]]. The conjugate gradient method is often implemented as an [[iterative method|iterative algorithm]], applicable to [[sparse matrix|sparse]] systems that are too large to be handled by a direct implementation or other direct methods such as the [[Cholesky decomposition]]. Large sparse systems often arise when numerically solving [[partial differential equation]]s or optimization problems.

The conjugate gradient method can also be used to solve unconstrained [[Mathematical optimization|optimization]] problems such as [[energy minimization]]. It is commonly attributed to [[Magnus Hestenes]] and [[Eduard Stiefel]],<ref>{{cite journal|last = Hestenes|author-link = Magnus Hestenes|first = Magnus R.  |author2=Stiefel, Eduard |author-link2=Eduard Stiefel |title = Methods of Conjugate Gradients for Solving Linear Systems|journal = Journal of Research of the National Bureau of Standards|volume = 49|issue = 6|page = 409|date=December 1952|doi=10.6028/jres.049.044|doi-access = free| url=http://nvlpubs.nist.gov/nistpubs/jres/049/6/V49.N06.A08.pdf}}</ref><ref>{{cite thesis |degree=PhD |last=Straeter |first=T. A. |date=1971 |title=On the Extension of the Davidon–Broyden Class of Rank One, Quasi-Newton Minimization Methods to an Infinite Dimensional Hilbert Space with Applications to Optimal Control Problems |via=NASA Technical Reports Server |publisher=North Carolina State University |hdl=2060/19710026200 |hdl-access=free}}</ref> who programmed it on the [[Z4 (computer)|Z4]],<ref>{{cite book |author-link=Ambros Speiser |last=Speiser |first=Ambros |trans-chapter=Konrad Zuse and the ERMETH: A worldwide comparison of architectures |chapter=Konrad Zuse und die ERMETH: Ein weltweiter Architektur-Vergleich |editor-first=Hans Dieter |editor-last=Hellige |title=Geschichten der Informatik. Visionen, Paradigmen, Leitmotive |location=Berlin |publisher=Springer |year=2004 |isbn=3-540-00217-0 |page=185 |language=de }}</ref> and extensively researched it.<ref name="BP">{{cite book |author-link=Boris T. Polyak |last=Polyak |first=Boris |title=Introduction to Optimization |year=1987 |language=en |url=https://www.researchgate.net/publication/342978480 }}</ref><ref name="AG">{{cite book |author-link=Anne Greenbaum |last=Greenbaum |first=Anne |title=Iterative Methods for Solving Linear Systems |year=1997 |language=en |isbn=978-0-89871-396-1 |doi=10.1137/1.9781611970937  }}</ref>

The [[biconjugate gradient method]] provides a generalization to non-symmetric matrices. Various [[nonlinear conjugate gradient method]]s seek minima of nonlinear optimization problems.