Conjugate Gradient Method - The Conjugate Gradient Method As A Direct Method

The Conjugate Gradient Method As A Direct Method

We say that two non-zero vectors u and v are conjugate (with respect to A) if

Since A is symmetric and positive definite, the left-hand side defines an inner product

Two vectors are conjugate if they are orthogonal with respect to this inner product. Being conjugate is a symmetric relation: if u is conjugate to v, then v is conjugate to u. (Note: This notion of conjugate is not related to the notion of complex conjugate.)

Suppose that {p_k} is a sequence of n mutually conjugate directions. Then the p_k form a basis of Rn, so we can expand the solution of Ax = b in this basis:

and we see that

The coefficients are given by

(because are mutually conjugate)

This result is perhaps most transparent by considering the inner product defined above.

This gives the following method for solving the equation Ax = b: find a sequence of n conjugate directions, and then compute the coefficients .