Solving Linear Equations using Cholesky Decomposition

Cholesky decomposition is a very important matrix factorization technique which is used to solve a linear equation. This technique originally derives from very popular LU decomposition and very suitable for higher order matrices. In Cholesky decomposition, the co-efficient matrix $A$ has to be a symmetric positive definite matrix. But in general, the co-efficient matrix can be rectangular or square and it may not be symmetric. Thus, traditional linear equation is not suitable for Cholesky based techniques. In order to solve the linear equations by Cholesky based technique, the traditional linear equation is multiplied by $A^T$ in both sides. New equation becomes

(1)

where $y_{new} = A^Ty$ and $C = A^T\times A$ . Now, matrix $C$ is symmetric positive definite of size $n\times n$ . This matrix can be factored using Cholesky decomposition as

(2)

Here, $L$ is a lower triangular matrix having positive diagonal elements. Cholesky decomposition is said to be efficient than LU decomposition. Inverse of the matrix $C$ can be computed as

(3)

The elements of the $L$ matrix are computed by the following equations.

(4)

Here, variable $j$ can be varied from 1 to $n$ and variable $i$ can be varied from $j+1$ to $n$ . The inverse of a triangular matrix can be computed by the following equations.

(5)

The computation of elements of the lower triangular matrix involves arithmetic operations like addition, multiplication, square root, and division. Involvement of both division and square root operation is one of the disadvantages of this technique. Another problem with this technique is that the co-efficient matrix has to be converted to a positive definite matrix.

Matlab Code for Cholesky Decomposition (3794 downloads )

Related Posts