LDLT Factorization – Detailed Numerical Examples
Dr. Brajesh Kumar Jha
General Formula
For symmetric matrix $A$:
$$ A = L D L^T $$ $$ d_k = a_{kk} - \sum_{j=1}^{k-1} l_{kj}^2 d_j $$ $$ l_{ik} = \frac{1}{d_k} \left( a_{ik} - \sum_{j=1}^{k-1} l_{ij} l_{kj} d_j \right) $$Example 1
$$ A = \begin{bmatrix} 4 & 2 & 2 \\ 2 & 5 & 1 \\ 2 & 1 & 3 \end{bmatrix} $$Step 1
$$ d_1 = 4 $$ $$ l_{21} = \frac{2}{4} = \frac{1}{2}, \quad l_{31} = \frac{2}{4} = \frac{1}{2} $$Step 2
$$ d_2 = 5 - \left(\frac{1}{2}\right)^2(4) $$ $$ = 5 - 1 = 4 $$ $$ l_{32} = \frac{1}{4} \left( 1 - \frac{1}{2}\cdot\frac{1}{2}\cdot 4 \right) = \frac{1}{4}(1-1)=0 $$Step 3
$$ d_3 = 3 - \left(\frac{1}{2}\right)^2(4) $$ $$ = 3 - 1 = 2 $$Final Matrices
$$ L = \begin{bmatrix} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ \frac{1}{2} & 0 & 1 \end{bmatrix} $$ $$ D = \begin{bmatrix} 4 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 2 \end{bmatrix} $$Example 2
$$ A = \begin{bmatrix} 2 & -1 & 1 \\ -1 & 2 & -1 \\ 1 & -1 & 2 \end{bmatrix} $$Step 1
$$ d_1 = 2 $$ $$ l_{21} = -\frac{1}{2}, \quad l_{31} = \frac{1}{2} $$Step 2
$$ d_2 = 2 - \left(-\frac{1}{2}\right)^2(2) $$ $$ = 2 - \frac{1}{2} = \frac{3}{2} $$ $$ l_{32} = \frac{1}{\frac{3}{2}} \left( -1 - \left(\frac{1}{2}\right)\left(-\frac{1}{2}\right)(2) \right) $$ $$ = \frac{2}{3}\left(-1+\frac{1}{2}\right) = -\frac{1}{3} $$Step 3
$$ d_3 = 2 - \left(\frac{1}{2}\right)^2(2) - \left(-\frac{1}{3}\right)^2\left(\frac{3}{2}\right) $$ $$ = 2 - \frac{1}{2} - \frac{1}{6} = \frac{4}{3} $$Example 3
$$ A = \begin{bmatrix} 9 & 3 & 6 \\ 3 & 5 & 4 \\ 6 & 4 & 10 \end{bmatrix} $$Step 1
$$ d_1 = 9 $$ $$ l_{21} = \frac{3}{9}=\frac{1}{3}, \quad l_{31} = \frac{6}{9}=\frac{2}{3} $$Step 2
$$ d_2 = 5 - \left(\frac{1}{3}\right)^2(9) $$ $$ = 5 - 1 = 4 $$ $$ l_{32} = \frac{1}{4} \left( 4 - \frac{2}{3}\cdot\frac{1}{3}\cdot9 \right) = \frac{1}{2} $$Step 3
$$ d_3 = 10 - \left(\frac{2}{3}\right)^2(9) - \left(\frac{1}{2}\right)^2(4) $$ $$ = 10 - 4 - 1 = 5 $$Indefinite Matrix Example
$$ A = \begin{bmatrix} 1 & 2 & 0 \\ 2 & 1 & 2 \\ 0 & 2 & 1 \end{bmatrix} $$Step 1
$$ d_1 = 1 $$ $$ l_{21} = 2, \quad l_{31}=0 $$Step 2
$$ d_2 = 1 - (2)^2(1) $$ $$ = 1 - 4 = -3 $$ $$ l_{32} = \frac{1}{-3}(2) = -\frac{2}{3} $$Step 3
$$ d_3 = 1 - \left(-\frac{2}{3}\right)^2(-3) $$ $$ = 1 + \frac{4}{3} = \frac{7}{3} $$Since $d_2 < 0$, the matrix is indefinite.
Comparison: LDLT vs Cholesky
| LDLT | Cholesky |
|---|---|
| $A = L D L^T$ | $A = L L^T$ |
| No square roots | Uses square roots |
| Works for indefinite matrices | Only positive definite |
Conclusion
- If all $d_i > 0$ → Positive definite matrix
- If some $d_i < 0$ → Indefinite matrix
- LDLT avoids square roots
No comments:
Post a Comment