Magic

Some properties of the conjugate-gradient approach are well known but hard to explain. D. G. Luenberger's book, Introduction to Linear and Nonlinear Programming, is a good place to look for formal explanations of this magic. (His book also provides other forms of the conjugate-gradient algorithm.) Another helpful book is Strang's Introduction to Applied Mathematics. Known properties follow:

1.

The conjugate-gradient method gets the exact answer (assuming exact arithmetic) in n descent steps (or less), where n is the number of unknowns.

2.

Since it is helpful to use the previous step, you might wonder why not use the previous two steps, since it is not hard to solve a three-by-three set of simultaneous linear equations. It turns out that the third direction does not help: the distance moved in the extra direction is zero.