5.15 Conjugate gradient method
The solution to a matrix equation by descent methods involves ﬁnding the minimum of the equation in quadratic form. This can be illustrated using the contours of the paraboloid describing the quadratic for the case with values and .
The search for the minimum involves a series of updates to of the form
The intuitive way to reach the minimum is to follow the direction of steepest descent. The method is fairly simple because the direction is deﬁned by the negative of gradient of the quadratic form which is the residual .
The distance to “walk” is naturally until the lowest point is reached, corresponding to5
The conjugate direction
The conjugate gradient (CG) method chooses search directions that are conjugate with . This means each new direction corresponds to the previous one , satisfying
This can be imagined as the directions being orthogonal with the stretch in the paraboloid removed. For 2 values, CG ﬁnds the minimum in 2 steps, rather than several zigzag steps.
CG provides the basis for practical matrix solvers for CFD, described in Sec. 5.16 . For a detailed explanation of the CG method, see the reference below.