### review of CG method:IV

#### by Yi Zhang

I have shown that in method of conjuate direction, the searching directions are in some sense orthogonal to each other:

Which makes more sense when the whole thing is considered under a new coordinate system, a system obtained by impose tranform of , in which is the upper-triangle matrix from ‘s Cholesky decomposition.

Similar conclusion includes that is -orthogonal to , resulting in that is orthogonal to the residual:

This condition actually implies that one can use the residual processed by * Gram-Schimdt conjugation* to obtain the direction , and this is the conjugate gradient (CG) method. The advantage of CG is that, instead of finding a set of directions at the beginning, is obtained along with the iteration, because the process of Gram-Schimdt conjugation is “triagonal”, i.e., one variable is determined by its predecessors. In particular, starting from (the first step is the same as steepest descent method), the following searching directions is determined by

Coefficient is obtained by conjugate condition:

Then we have

In order to simplify this expression, remember that during this process of generating from , for any ,

so

The Gram-Schimdt process also indicates that (prove it). The above two identities can be used to simplify , and prove that

and eventually

Finally, a complete iteration, when is known, consists of