Cholesky decomposition
1 Cholesky Decomposition
A symmetric and positive definite matrix can be efficiently decomposed into a lower and upper triangular matrix
. For a matrix of any type, this is achieved by the LU decomposition
which factorizes A=LU. If A satisfies the above criteria, one can decompose more efficiently into A=LLT where L is a lower triangular matrix with positive diagonal elements. L is called the Cholesky triangle.
To solve Ax=b, one solves first Ly=b for y, and then LTx=y for x.
A variant of the Cholesky decomposition is the form A=RTR , where R is upper triangular.
Cholesky decomposition is often used to solve the normal equations in linear least squares problems; they give ATAx=ATb , in which ATA is symmetric and positive definite
.
To derive A=LLT, we simply equate coefficients on both sides of the equation:
[a11a12⋯a1na21a22⋯a2na31a32⋯a3n⋮⋮⋱⋮an1an2⋯ann]=[l110⋯0l21l22⋯0⋮⋮⋱⋮ln1ln2⋯lnn][l11l21⋯ln10l22⋯ln2⋮⋮⋱⋮00⋯lnn] |
Solving for the unknowns (the nonzero ljis), for i=1,⋯,n and j=i-1,…,n, we get:
lii | = | √(aii-i-1∑k=1l2ik) | ||
lji | = | (aji-i-1∑k=1ljklik)/lii |
Because A is symmetric and positive definite, the expression under the square root is always positive, and all lij are real.
References
- 1 Originally from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)
Title | Cholesky decomposition |
Canonical name | CholeskyDecomposition |
Date of creation | 2013-03-22 12:07:38 |
Last modified on | 2013-03-22 12:07:38 |
Owner | gufotta (12050) |
Last modified by | gufotta (12050) |
Numerical id | 16 |
Author | gufotta (12050) |
Entry type | Definition |
Classification | msc 62J05 |
Classification | msc 65-00 |
Classification | msc 15-00 |
Synonym | Cholesky factorization |
Synonym | matrix square root |
Related topic | SquareRootOfPositiveDefiniteMatrix |
Defines | Cholesky triangle |