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:

a₃₂=l₃₁l₂₁+l₃₂l₂₂ l₃₂=(a₃₂-l₃₁l₂₁)/l₂₂, etc.

In general for and :

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