Choleski Decomposition

TL;DR

• Factorizes a symmetric, positive definite matrix A into L · L^T, where L is lower triangular.
• Produces factors (L and L^T) that make solving Ax = b efficient via forward and backward substitution.
• Requires A to be symmetric and positive definite.

Definition

Choleski decomposition is a numerical method used in linear algebra to decompose a symmetric, positive definite matrix into the product of a lower triangular matrix and its transpose. This decomposition is named after André-Louis Choleski, who first published it in 1918.

Explanation

Given a symmetric, positive definite matrix A, Choleski decomposition produces a lower triangular matrix L such that:

$$A = L L^{T}$$

Symmetric means A = A^{T}. Positive definite means that for any non-zero vector x, the scalar $x^{T} A x$ is positive.

For a 3×3 matrix A, the lower triangular factor L has the form:

$$L = \begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{bmatrix}$$

The source describes the diagonal elements as the square roots of the diagonal elements of A:

$$l_{11} = \sqrt{a_{11}},\quad l_{22} = \sqrt{a_{22}},\quad l_{33} = \sqrt{a_{33}}.$$

The off-diagonal elements are obtained by solving the system of equations:

$$\begin{aligned} l_{11} \cdot l_{21} + l_{22} \cdot l_{31} &= a_{21} \\ l_{11} \cdot l_{31} + l_{22} \cdot l_{32} &= a_{31} \\ l_{11} \cdot l_{32} + l_{22} \cdot l_{33} &= a_{32} \end{aligned}$$

The source gives the resulting expressions:

$$l_{21} = \frac{a_{21}}{l_{11}},\quad l_{31} = \frac{a_{31} - l_{21} \cdot l_{31}}{l_{22}},\quad l_{32} = \frac{a_{32} - l_{21} \cdot l_{32}}{l_{22}}.$$

Once L is obtained, its transpose L^{T} is the upper triangular factor and

$$A = L L^{T}.$$

To solve a linear system Ax = b using Choleski decomposition:

1. Decompose A = L L^{T}.
2. Solve Ly = b for y using forward substitution.
3. Solve L^{T} x = y for x using backward substitution.

Examples

Example 3×3 matrix A:

$$A = \begin{bmatrix} 5 & 2 & 1 \\ 2 & 5 & 1 \\ 1 & 1 & 4 \end{bmatrix}$$

The lower triangular factor L (as given in the source) is:

$$L = \begin{bmatrix} \sqrt{5} & 0 & 0 \\ \frac{2}{\sqrt{5}} & \sqrt{3} & 0 \\ \frac{1}{\sqrt{5}} & \frac{1}{\sqrt{3}} & \sqrt{4} \end{bmatrix}$$

The transpose L^{T} is:

$$L^{T} = \begin{bmatrix} \sqrt{5} & \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} \\ 0 & \sqrt{3} & \frac{1}{\sqrt{3}} \\ 0 & 0 & \sqrt{4} \end{bmatrix}$$

The decomposition satisfies:

$$A = L L^{T} = \begin{bmatrix} 5 & 2 & 1 \\ 2 & 5 & 1 \\ 1 & 1 & 4 \end{bmatrix}$$

Solving Ax = b using the decomposition proceeds by first solving:

$$L y = b$$

(by forward substitution) and then:

$$L^{T} x = y$$

(by backward substitution).

Use cases

• Solving systems of linear equations Ax = b efficiently and accurately by factoring A into L and L^{T}.

Notes or pitfalls

• The decomposition requires A to be symmetric and positive definite.
• The method yields lower and upper triangular factors (L and L^{T}) that enable forward and backward substitution.

Related terms

• Choleski factors (L and L^{T})
• Lower triangular matrix
• Symmetric matrix
• Positive definite matrix
• Forward substitution
• Backward substitution