Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Linear Systems > **Cholesky decomposition**

All the versions of this article: [English] [français]

We will study a direct method for solving linear systems: the Cholelsky decomposition. Given a symmetric positive definite matrix A, the aim is to build a lower triangular matrix L which has the following property: the product of L and its transpose is equal to A.

Given a symmetric positive definite matrix , the Cholesky decomposition constructs a lower triangular matrix L which has the following property: . A symmetric matrix is positive definite if, for any vector , the product is positive.

The matrix is sometimes called the Â« square root Â» of . The Cholesky decomposition is often used to calculate the inverse matrix and the determinant of (equal to the square of the product of the diagonal elements of ).

The symmetric matrix

is equal to the product of the triangular matrix and of its transposed :

with

Cholesky Factorization:

If is a symmetric positive definite matrix, there is at least a lower triangular real matrix such as :

We can also impose that the diagonal elements of the matrix are all positive, and corresponding factorization is then unique.

The Cholesky matrix is given by:

Equality gives :

since if

The matrix being symmetric, it is enough that the relations above are checked for , i.e. the elements of the matrix must satisfy:

For j=1, we determine the first column of :

(i=1) so

(i=2) so

...

(i=n) so

After having calculated the (j-1) first columns, we determine the j-th column of :

(i=j) so

(i=j+1) so

...

(i=n) so

For the resolution of linear system : , the system becomes

We solve the system (1) to find the vector , then the system (2) to find the vector . The resolution is facilitated by the triangular shape of the matrices.

The Cholesky decomposition also makes it possible to calculate the determinant of , which is equal to the square of the product of the diagonal elements of the matrix , since