I. Basic math.
 II. Pricing and Hedging.
 III. Explicit techniques.
 IV. Data Analysis.
 V. Implementation tools.
 VI. Basic Math II.
 VII. Implementation tools II.
 1 Calculational Linear Algebra.
 B. Method of steepest descent.
 C. Method of conjugate directions.
 E. Convergence analysis of conjugate gradient method.
 F. Preconditioning.
 G. Recursive calculation.
 H. Parallel subspace preconditioner.
 2 Wavelet Analysis.
 3 Finite element method.
 4 Construction of approximation spaces.
 5 Time discretization.
 6 Variational inequalities.
 VIII. Bibliography
 Notation. Index. Contents.

## Method of conjugate directions.

he formula ( Orthogonality of residues ) shows the steepest descent method sometimes takes steps in the same direction that was taken before. This is a waste of efficiency. We would like to find a procedure that never takes the same direction. Instead of search directions we would like to find a set of linearly independent search directions . Of course, if the directions are chosen badly then the best length of step in every direction would be impossible to determine. Since we are minimizing it makes sense to choose directions orthogonal with respect to the scalar product . This way we can perform a -minimization in every direction (see the section ( Method of steepest descent )) and guarantee that the iteration remains -optimal with respect to the directions of the previous steps. Therefore such procedure has to hit the solution after steps or less (under theoretical assumption that numerical errors are absent).

We produce a set search direction by performing the Gram-Schmidt orthogonalization (see the section ( Gram-Schmidt orthogonalization )) with respect to the scalar product and starting from any set of linearly independent vectors. Let be a result of such orthogonalization: The following calculations are motivationally similar to the calculations of the section ( Method of steepest descent ). We start from any point . At a step we look at the line and seek Note at this point that changing from to for any vector that is -orthogonal to would not alter the result of minimization. Hence, if we perform this procedure times we arrive to a point that is optimal with respect to every vector . Therefore, such point is a solution.

To perform the minimization we calculate the derivative At this point we substitute the formula ( Connection between SLA and minimization ) and disappears from the calculation. We equate the derivative to zero and obtain We collect the results: Similarly to the section ( Method of steepest descent ) one can eliminate one matrix multiplication by transforming the equation . We multiply by and subtract :

Algorithm

(Conjugate directions) Let be a set of vectors with the property Take any point , calculate and iterate for

Note for future use that means or In fact, is orthogonal to all directions for previous steps because, as we noted already, remains -optimal:

 (Orthogonality of residues 2)

 Notation. Index. Contents.