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⁽ⁱ⁾ has the following form:

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

If we now define the matrix L_i by

then we can write A⁽ⁱ⁾ as

where

Note that b_i b_i^* 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⁽ⁿ⁺¹⁾ = I. Hence, the lower triangular matrix L we are looking for is calculated as