Cholesky decomposition.

(13.33) |

This factorization is sometimes referred to, as ``taking the square root'' of the matrix .

The Cholesky decomposition is a particular case of the decomposition. The decomposition is the following:

where is a lower triangular matrix and is a upper triangular matrix. For example, in the case of a matrix , we have:

We can use the decomposition to solve the linear set: by first solving for the vector such that and then solving . These two systems are trivial to solve because they are triangular.

Equations 13.36 - 13.38, totalize equations for the unknown 's and 's (the diagonal being represented twice). Since the number of unknowns is greater than the number of equations, we have to specify of the unknowns arbitrarily and then solve for the others. In fact, as we shall see, it is always possible to take:

A surprising procedure, now, is

- Set
- For each
do these two procedures:

First, for use 13.36, 13.37 and 13.39 to solve for , namely

Second, for , use 13.38 to solve for , namely

Be sure to do both procedures before going on to the next j.

and

If you apply Equation 13.42 and 13.43 in the order , you will see the the 's that occur on the right-hand side are exactly determined by the time they are needed. Also, only components with are referenced.

If the matrix is not positive definite, the algorithm will stop, trying to take the square root of a negative number in equation 13.42.

What about pivoting? Pivoting (i.e., the selection of a salubrious pivot element for the division in Equation 13.43) is not really required for the stability of the algorithm. In fact, the only cause of failure is if the matrix (or, with roundoff error, another very nearby matrix) is not positive definite.