Choleski decomposition :
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.
To illustrate Choleski decomposition, let’s consider the following 3×3 matrix:
A = [5, 2, 1]
[2, 5, 1]
[1, 1, 4]
This matrix is symmetric because it is equal to its transpose, i.e. A = A^T. It is also positive definite, which means that for any non-zero vector x, the scalar product x^TAx is positive.
To perform Choleski decomposition, we first need to calculate the Choleski factors L and L^T. The lower triangular matrix L is calculated as follows:
L = [l_11, 0, 0]
[l_21, l_22, 0]
[l_31, l_32, l_33]
where l_11, l_22 and l_33 are the diagonal elements of L and l_21, l_31, and l_32 are the off-diagonal elements.
We can calculate the diagonal elements of L by taking the square root of the diagonal elements of A, i.e. l_11 = sqrt(a_11), l_22 = sqrt(a_22) and l_33 = sqrt(a_33).
To calculate the off-diagonal elements of L, we need to solve the following system of equations:
l_11 * l_21 + l_22 * l_31 = a_21
l_11 * l_31 + l_22 * l_32 = a_31
l_11 * l_32 + l_22 * l_33 = a_32
Solving this system of equations, we get l_21 = a_21/l_11, l_31 = (a_31 – l_21 * l_31) / l_22 and l_32 = (a_32 – l_21 * l_32) / l_22.
Therefore, the lower triangular matrix L for the matrix A is:
L = [sqrt(5), 0, 0]
[2/sqrt(5), sqrt(3), 0]
[1/sqrt(5), 1/sqrt(3), sqrt(4)]
The transpose of L, denoted as L^T, is:
L^T = [sqrt(5), 2/sqrt(5), 1/sqrt(5)]
[0, sqrt(3), 1/sqrt(3)]
[0, 0, sqrt(4)]
Therefore, the Choleski decomposition of matrix A is:
A = L * L^T = [5, 2, 1]
[2, 5, 1]
[1, 1, 4]
This decomposition allows us to solve systems of linear equations efficiently and accurately. For example, if we have a system of linear equations:
Ax = b
where A is the matrix A, x is the vector of unknowns, and b is the vector of known constants, we can use Choleski decomposition to solve for x.
First, we decompose A into L and L^T as shown above. Then, we can solve for x by first solving the following system of equations:
Ly = b
where y is a vector of intermediate values that we can use to solve for x. We can solve for y by using forward substitution, which is a numerical method that allows us to solve for the unknowns in a system of equations by substituting known values in the equations.
Once we have solved for y, we can solve for x by solving the following system of equations:
L^Tx = y
We can solve for x by using backward substitution, which is similar to forward substitution but works in the opposite direction.
Overall, Choleski decomposition is a useful numerical method for solving systems of linear equations efficiently and accurately.