Cholesky Decomposition Explanation.

gistfile1.txt

############################################################
How to solve a matrix equation with Cholesky Decomposition
############################################################

We want to solve the matrix equation Ax=b. So we want x. The Cholesky decomposition of A is just
the matrix product A = L(L^T). Where L is some lower triangular matrix, and L^T is its transpose. 
So L^T is upper triangular. See wikipedia an example of such a decomposition:
https://en.wikipedia.org/wiki/Cholesky_decomposition#Example

If we now substitute our decomposition of A into our equation we get

L (L^T) x = b

Now define the vector y to be y = (L^T)x. Then we have

L y = b

Since L is lower triangular, we can solve for y by simple forward substitution.
But note now that

(L^T)x = y

and we know y, because we just solved for it. And we know that L^T is upper triangular,
so we can easily solve for x by back substitution. And with that we have found x, and so we are happy,
because finding x was our original goal :)


See more info on wikipedia:
https://en.wikipedia.org/wiki/Cholesky_decomposition#Applications

And note that we can find the Cholesky decomposition with a modified Gaussian Elimination Algorithm. Read
more on wikipedia.