21 Jun 2017

Cholesky Decomposition

In linear algebra, the Cholesky decomposition or Cholesky factorization is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful e.g. for efficient numerical solutions and Monte Carlo simulations. When it is applicable, the Cholesky decomposition is roughly twice as efficient as the LU decomposition for solving systems of linear equations.

function z=cholesky(M)
[r c] = size(M);
for i=1:r
M(i,i) = sqrt(M(i,i));
M(i+1:r,i) = M(i+1:r,i)/M(i,i);
for j=i+1:r
M(j:r,j) = M(j:r,j) - M(j,i)*M(j:r,i);
end
end
z = tril(M);

The above function provides the lower triangular matrix L such that A = L*L’.

For n = 3 with matrices M = (aij) with aij = 1/i+j−1:

Cholesky

We also compare the obtained output with the matlab’s inbuilt function chol and we can see that the obtained matrices are same.