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 ).
{{{Example}}}
The symmetric matrix
is equal to the product of the triangular matrix and of its transposed :
with
{{{Theorem}}}
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.
{{{Algorithm}}}
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
{{{Solution of linear system}}}
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.
{{{Calculating Matrix Determinant}}}
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