## You are here

HomeCholesky decomposition

## Primary tabs

# 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=LL^{T}$ 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 $L^{T}x=y$ for $x$.

A variant of the Cholesky decomposition is the form $A=R^{T}R$ , where $R$ is upper triangular.

Cholesky decomposition is often used to solve the normal equations in linear least squares problems; they give $A^{T}Ax=A^{T}b$ , in which $A^{T}A$ is symmetric and positive definite.

To derive $A=LL^{T}$, we simply equate coefficients on both sides of the equation:

$\begin{bmatrix}a_{{11}}&a_{{12}}&\cdots&a_{{1n}}\\ a_{{21}}&a_{{22}}&\cdots&a_{{2n}}\\ a_{{31}}&a_{{32}}&\cdots&a_{{3n}}\\ \vdots&\vdots&\ddots&\vdots\\ a_{{n1}}&a_{{n2}}&\cdots&a_{{nn}}\end{bmatrix}=\begin{bmatrix}l_{{11}}&0&% \cdots&0\\ l_{{21}}&l_{{22}}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ l_{{n1}}&l_{{n2}}&\cdots&l_{{nn}}\end{bmatrix}\begin{bmatrix}l_{{11}}&l_{{21}}% &\cdots&l_{{n1}}\\ 0&l_{{22}}&\cdots&l_{{n2}}\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&l_{{nn}}\end{bmatrix}$ |

Solving for the unknowns (the nonzero $l_{{ji}}$s), for $i=1,\cdots,n$ and $j=i-1,\ldots,n$, we get:

$\displaystyle l_{{ii}}$ | $\displaystyle=$ | $\displaystyle\sqrt{\left(a_{{ii}}-\sum_{{k=1}}^{{i-1}}l_{{ik}}^{2}\right)}$ | ||

$\displaystyle l_{{ji}}$ | $\displaystyle=$ | $\displaystyle\left(a_{{ji}}-\sum_{{k=1}}^{{i-1}}l_{{jk}}l_{{ik}}\right)/l_{{ii}}$ |

Because $A$ is symmetric and positive definite, the expression under the square root is always positive, and all $l_{{ij}}$ are real.

# References

- 1 Originally from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.html)

## Mathematics Subject Classification

62J05*no label found*65-00

*no label found*15-00

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Corrections

which square root ? by jduchon ✓

change ij to ji by jduchon ✘

where L is by jduchon ✓

Cholesky by karelkupka ✓

## Comments

## Fix

In the sentense:

Solving for the unknowns (the nonzero......

change

j=i-1,…,n

to

j=i+1,…,n