A symmetric matrix A A A iff A A A
A = L L T A = LL^T A = L L T where L L L L L L
Computing L L L
Multiplying out A = L L T A = LL^T A = L L T k = 1 , 2 , … , n k = 1, 2, \ldots, n k = 1 , 2 , … , n
l k i = a k i − ∑ j = 1 i − 1 l i j l k j l i i , i = 1 , 2 , … , k − 1 l_{ki} = \frac{a_{ki} - \sum\limits_{j=1}^{i-1} l_{ij}l_{kj}}{l_{ii}}, \quad i = 1, 2, \ldots, k-1 l k i = l ii a k i − j = 1 ∑ i − 1 l ij l k j , i = 1 , 2 , … , k − 1 l k k = a k k − ∑ j = 1 k − 1 l k j 2 l_{kk} = \sqrt{a_{kk} - \sum\limits_{j=1}^{k-1} l_{kj}^2} l k k = a k k − j = 1 ∑ k − 1 l k j 2 Compute row k k k l k i l_{ki} l k i l k k l_{kk} l k k l k k l_{kk} l k k
Example
Apply Cholesky decomposition to
A = ( 6 15 55 15 55 225 55 225 979 ) A = \begin{pmatrix} 6 & 15 & 55 \\ 15 & 55 & 225 \\ 55 & 225 & 979 \end{pmatrix} A = 6 15 55 15 55 225 55 225 979 Row 1 1 1
l 11 = 6 ≈ 2.449 l_{11} = \sqrt{6} \approx 2.449 l 11 = 6 ≈ 2.449 Row 2 2 2
l 21 = a 21 l 11 = 15 2.449 ≈ 6.124 , l 22 = a 22 − l 21 2 = 55 − 6.124 2 ≈ 4.183 l_{21} = \frac{a_{21}}{l_{11}} = \frac{15}{2.449} \approx 6.124, \quad l_{22} = \sqrt{a_{22} - l_{21}^2} = \sqrt{55 - 6.124^2} \approx 4.183 l 21 = l 11 a 21 = 2.449 15 ≈ 6.124 , l 22 = a 22 − l 21 2 = 55 − 6.12 4 2 ≈ 4.183 Row 3 3 3
l 31 = a 31 l 11 = 55 2.449 ≈ 22.454 , l 32 = a 32 − l 31 l 21 l 22 = 225 − 22.454 × 6.124 4.183 ≈ 20.917 l_{31} = \frac{a_{31}}{l_{11}} = \frac{55}{2.449} \approx 22.454, \quad l_{32} = \frac{a_{32} - l_{31}l_{21}}{l_{22}} = \frac{225 - 22.454 \times 6.124}{4.183} \approx 20.917 l 31 = l 11 a 31 = 2.449 55 ≈ 22.454 , l 32 = l 22 a 32 − l 31 l 21 = 4.183 225 − 22.454 × 6.124 ≈ 20.917 l 33 = a 33 − l 31 2 − l 32 2 = 979 − 22.454 2 − 20.917 2 ≈ 6.110 l_{33} = \sqrt{a_{33} - l_{31}^2 - l_{32}^2} = \sqrt{979 - 22.454^2 - 20.917^2} \approx 6.110 l 33 = a 33 − l 31 2 − l 32 2 = 979 − 22.45 4 2 − 20.91 7 2 ≈ 6.110 L ≈ ( 2.449 0 0 6.124 4.183 0 22.454 20.917 6.110 ) L \approx \begin{pmatrix} 2.449 & 0 & 0 \\ 6.124 & 4.183 & 0 \\ 22.454 & 20.917 & 6.110 \end{pmatrix} L ≈ 2.449 6.124 22.454 0 4.183 20.917 0 0 6.110