   Next: 2.4 Eigenvalues and Eigenvectors Up: 2.3 Iterative Methods Previous: 2.3.4 Successive Over-Relaxation (SOR)

Task: Solve . This may be interpreted as a minimization problem:

Let Then the -vector which minimizes (with the minimum value ) is the desired solution.

Minimization of a quadratic function of variables: Warm-up: Cauchy's Steepest Descent Method

Assume to depend on two variables only. The lines of equal elevation of a quadratic function are ellipses that may be very elongated (see the figure).

• Start from with position vector and follow the local gradient (2.2)

This direction will not lead directly to the extremal point of .
• Find the lowest point along this path. Determine once more the local gradient ; by construction it must be perpendicular to the previous direction .
• Iterate this procedure to arrive, after many mutually orthogonal bends, at the bottom of the channel (or top of the hill).

Now for the serious work: Conjugate Gradients

From point take the direction instead of .

How to find ?

Require that along the change of the gradient of has no component parallel to . (In contrast: along , the gradient of has initially no -component). As a consequence, a gradient in the direction of will not develop immediately (on quadratic surfaces never!). This requirement leads to the prescription given in the Figure. For dimension this is all there is; is the solution vector. For systems of higher dimension one has to go on from in the direction until the next low point'' is reached at with Next we determine and so forth, until we arrive at the solution .

Advantage of CG: No matrix inversion!

But: Several multiplication ; therefore most efficient for sparse matrices.

EXAMPLE: To see the mechanics of the method, assume The gradient vector at is and such that Similarly, and thus which is the desired solution vector in this 2-dimensional case. If were a matrix, such steps would be necessary.   Next: 2.4 Eigenvalues and Eigenvectors Up: 2.3 Iterative Methods Previous: 2.3.4 Successive Over-Relaxation (SOR)
Franz J. Vesely Oct 2005