next up previous

2.4.3 Conjugate Gradient     continued...

When one refers to the CG method, one often means the linear Conjugate Gradient; that is, the implementation for the convex quadratic form. In this case, minimizing is equivalent to solving the linear system . Consequently, the conjugate directions , as well as the step lengths , can be computed in closed form. Below we sketch such an algorithm from a given . We define the residual vector and use the vectors below to denote the CG search vectors.

Note here that only a few vectors are stored, the product is required but not knowledge (or storage) of per se, and the cost only involves several scalar and vector operations. The value of the step length can be derived in the closed form above by minimizing the quadratic function as a function of (producing ) and then using the conjugacy relation: for all j<k [45].

See the linear algebra chaptergif for further details and examples.