Cholesky Factorization

The Cholesky factorization, also known as Cholesky decomposition, is a process of breaking down of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is important for quick numerical solutions in linear algebra. André-Louis Cholesky discovered it for real matrices, and it was later published in 1924. For solving systems of linear equations, the Cholesky factorization is generally twice as efficient as the LU decomposition when it is feasible. We will learn the definition, proof, and examples of Cholesky factorization in this article.

Table of Contents:

• Definition
• How to Compute Cholesky Factorization?
  • Steps
• Applications
• Solved Examples
• FAQs

What is Cholesky Factorization?

The Cholesky factorization is exclusively defined for symmetric or Hermitian positive definite matrices, as previously stated.

As a result, the Cholesky factorization of a positive-definite Hermitian matrix A is a decomposition of the kind

A = LL*

where L* indicates the conjugate transpose of L, in which L is a lower triangular matrix with real and positive diagonal elements. A unique Cholesky decomposition exists for every Hermitian positive-definite matrix (and therefore every real-valued symmetric positive-definite matrix). The inverse is also true.

If A is a real matrix (and thus symmetric positive-definite), the factorization can be stated as follows:

A = LL^T

where L is a positive diagonal real lower triangular matrix.

How to Compute Cholesky Factorization?

Recall that a complex matrix A is positive definite if and only if the quadratic form x*Ax is real (that is, it has no complex part) for every vector x and x*Ax>0 only when x ≠ 0. We’ve shown that if a complex matrix is positive definite, it’s Hermitian as well.

When we just consider real vectors and matrices, we state that a real matrix A is positive definite if and only if it is symmetric and

x^TAx > 0

for any real vector x that is non-zero. It’s worth noting that symmetry is an explicit condition in the real world, rather than a result of positive definiteness. For a Cholesky factorization to exist, positive definiteness is both a sufficient and necessary requirement.

Steps for Solving Cholesky Factorization

By solving the equation directly, the Cholesky factorization of a k×k matrix A can be obtained.

A = LL*

Using the definition of matrix product, the latter equation suggests that

as for any A_tv element at the intersection of the t^th row and the vth column (where t = 1, 2, 3, …, k and v = 1, 2, 3,.., k).

L_vu=0 when u>v, because L is lower triangular. Hence

Following the principles, we can obtain the entries of L from the latter equation:

• We calculate one column at a time, starting with the first (v=1) and continuing our way down the list (v = 2, 3, .., k).
• In every column, we compute the diagonal entry L_vv first, followed by the other entries L_tv (only for t>v as L_tv = 0 when v>t).

We can determine the diagonal entries by solving equation (1).

We have to choose the positive root because the entries on L’s main diagonal must be real and strictly positive. Furthermore, if the number underneath the square root is not precisely positive, the process is terminated, and A is considered to be non-positive definite.

We can determine the other entries L_tv (for t>v) by solving equation (1) again.

where we have been using the truth that,

because the elements on the principal diagonal are real entries.

Applications of Cholesky Factorization

If A is Symmetric Positive Definite (SPD), the Cholesky factorization is employed to solve the linear system Ax = y:

When the components are substituted into the equation, the result is LL^Tx = y. Assuming z = L^Tx,

Thus, the desired answer z can be estimated by resolving the triangular system of equations Lz = y, and x may be computed by calculating the triangular linear system L^Tx = z.

Solved Example on Cholesky Factorization

Example 1:

Determine the cholesky factorization, whose lower triangular matrix is given by:

Solution:

Given that,the lower triangular matrix,

Hence, its conjugate transpose is

Hence, the matrix A is given by

Hence, according to the Cholesky factorization A = LL*

Example 2:

Find the lower triangular matrix used in Cholesky factorisation for the given 2×2 matrix:

Solution:

Given that, the matrix A is

We have to determine a matrix

Such that A = LL*

We will begin with the first column’s diagonal entry.

The first column’s following entry is

Now we will look at the second column’s diagonal entry.

As a result, the Cholesky decomposition’s lower triangular matrix is

Keep Visiting BYJU’S – The Learning App and download the app to quickly understand all Mathematical concepts by watching more videos.