miércoles, 28 de julio de 2010

Cholesky decomposition

decomposition or Cholesky triangle is a decomposition of a symmetric, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André-Louis Cholesky for real matrices and is an example of a square root of a matrix. When it is applicable, the Cholesky decomposition is roughly twice as efficient as the LU decomposition for solving systems of linear equations.

The Cholesky algorithm

The Cholesky algorithm, used to calculate the decomposition matrix L, is a modified version of Gaussian elimination.

The recursive algorithm starts with i := 1 and

At step i, the matrix A(i) has the following form:

where Ii−1 denotes the identity matrix of dimension i − 1.

If we now define the matrix Li by

then we can write A(i) as

where

Note that bi bi* is an outer product, therefore this algorithm is called the outer product version in (Golub & Van Loan).

We repeat this for i from 1 to n. After n steps, we get A(n+1) = I. Hence, the lower triangular matrix L we are looking for is calculated as