next up previous contents index
Next: Clipping Up: No Title Previous: Chi-Square Test

Cholesky Decomposition

  A symmetric and positive definite matrix can be efficiently decomposed into a lower and upper triangular matrix. For a matrix of any type, this is achieved by the LU decomposition which factorizes A = LU. If A satisfies the above criteria, one can decompose more efficiently into , where L (which can be seen as the ``square root'' of A) is a lower triangular matrix with positive diagonal elements. To solve Ax = b, one solves first Ly = b for y, and then for x.

A variant of the Cholesky decomposition is the form , where R is upper triangular.

Cholesky decomposition is often used to solve the normal equations in linear least squares problems; they give , in which is symmetric and positive definite.

To derive , we simply equate coefficients on both sides of the equation:

to obtain:

a11 = l112
a21 = l21l11
a22=l212 + l222
a32=l31l21+l32l22 l32=(a32-l31l21)/l22, etc.

In general for and :

Because A is symmetric and positive definite, the expression under the square root is always positive, and all lij are real (see [Golub89]).

Rudolf K. Bock, 7 April 1998