Skip to content

Instantly share code, notes, and snippets.

@Erkaman
Created January 29, 2017 13:10
Show Gist options
  • Save Erkaman/84403e52ce194a168e5112b13ca4e85a to your computer and use it in GitHub Desktop.
Save Erkaman/84403e52ce194a168e5112b13ca4e85a to your computer and use it in GitHub Desktop.
Cholesky Decomposition Explanation.
############################################################
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment