Cholesky Decomposition

Cholesky Decomposition

For a symmetric positive definite (SPD) matrix $A$, the Cholesky decomposition gives:

$A = L L^T$

where $L$ is lower triangular with positive diagonal entries.

Why Cholesky?

• Twice as fast as LU (exploits symmetry)
• Numerically more stable
• The positive diagonal entries confirm $A$ is truly SPD

Algorithm

$L_{ij} = \frac{A_{ij} - \sum_{k < j} L_{ik}\, L_{jk}}{L_{jj}} \quad (i > j, \text{ off-diagonal})$

$L_{jj} = \sqrt{A_{jj} - \sum_{k < j} L_{jk}^2} \quad (\text{diagonal})$

Example

$A = \begin{pmatrix} 4 & 2 & 2 \\ 2 & 5 & 3 \\ 2 & 3 & 6 \end{pmatrix}, \quad L = \begin{pmatrix} 2 & 0 & 0 \\ 1 & 2 & 0 \\ 1 & 1 & 2 \end{pmatrix}$

Check: $L L^T = A$.

Your Task

Implement cholesky(A) returning the lower triangular factor L.