Conjugate Gradient Search

Iterative Methods for Linear Algebraic Systems Exact Line Search

Theorem

Let be Conjugate Directions and consider the sequence of iterates:

where

Then is orthogonal to . In particular .

Proof

Nothing special, just check.

The method

See Standard Conjugate Gradient Method for the optimized algorithm.

Initial conditions

For any initial , set

Iterate

For find and by the usual formula (above)

Next direction

The next conjugate direction is:

with

i.e. the value that makes normal to

Theorem (properties)

For every , the conjugate gradient satisfies:

1. For every :

2. For , we have orthogonality conditions:

3. The directions are conjugate, for :

Proof

Prove all three claims by one induction on .

Corollary (simplification)

Also is a multiple of so:

Corollary (number of iterations)

Let be the number of distinct eigenvalues of Then the method terminates in at most steps.

Proof

The Krylov Subspaces

Preconditioning

The method converges the fastest if the Condition Number is close to To that end, we introduce a change of variables , where is some nonsingular preconditioner. We now solve:

Note that similarity transformations preserve the spectrum so:

Now if is an approximation to such that we can set