Confirming an $LDL^t$ factorization

Question

Hoping someone can confirm my work here. I'm trying to find the $LDL^t$ factorization (http://www.mathworks.com/help/dsp/ref/ldlfactorization.html) of the matrix

$$ A = \left(\begin{array}{ccc} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{array}\right). $$

I'm omitting my work because it's really long, but I got

$$ A = \overbrace{\left(\begin{array}{ccc} 1 & 0 & 0 \\ -1/2 & 1 & 0 \\ 0 & -2/3 & 1 \end{array}\right)}^{L} \overbrace{\left(\begin{array}{ccc} 2 & 0 & 0 \\ 0 & 3/2 & 0 \\ 0 & 0 & 4/3 \end{array}\right)}^{D} \overbrace{\left(\begin{array}{ccc} 1 & -1/2 & 0 \\ 0 & 1 & -2/3 \\ 0 & 0 & 1 \end{array}\right)}^{L^t}. $$

Any chance could confirm my work? Thanks!

Answer 1

The goal is to factorize:

$$A = LDL^T$$

We want:

$$\begin{bmatrix}2 & -1 & 0\\-1 & 2 & -1 \\ 0 & -1 & 2\end{bmatrix} = \begin{bmatrix}1 & 0 & 0\\l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1\end{bmatrix} \begin{bmatrix}d_{11} & 0 & 0\\ 0 & d_{22} & 0 \\ 0 & 0 & d_{33}\end{bmatrix} \begin{bmatrix}1 & l_{21} & l_{31}\\0 & 1 & l_{32} \\ 0 & 0 & 1\end{bmatrix}$$

The basic iteration (you can find in numerical analysis texts or "Matrix Computations" by Golub and Van Loan) we want for an $LDL^T$ factorization is given by:

$$\displaystyle d_{jj} = a_{jj} - \sum_{k=1}^{j-1} l^2_{jk}d_{kk} \\ \displaystyle l_{ij} = \left(a_{ij} - \sum_{k=1}^{j-1} l_{ik}d_{kk}l_{jk}\right) \times \dfrac{1}{d_{jj}}$$

We have:

• $d_{11} = a_{11} = 2$
• $l_{11} = 1$
• $l_{21} = \dfrac{a_{21}}{d_{11}} = -\dfrac{1}{2}$
• $l_{31} = \dfrac{a_{31}}{d_{11}} = \dfrac{0}{2} = 0$
• $\displaystyle d_{22} = a_{22} - \sum_{k=1}^{1} l_{jk}^2d_{kk} = 2 - l^2_{21}d_{11} = 2 - \left(-\dfrac{1}{2}\right)^2(2) = \dfrac{3}{2}$
• $l_{22} = 1$
• $\displaystyle l_{32} = \left(a_{32} - \sum_{k=1}^{1}l_{3k}^2d_{kk}l_{2k} \right ) \times \dfrac{1}{d_{22}} = (-1 - 0) \times \dfrac{2}{3} = -\dfrac{2}{3}$
• $\displaystyle d_{33} = a_{33} - \sum_{k=1}^{2} l_{jk}^2d_{kk} = a_{33} - (l_{31}^2d_{11} + l_{32}^2d_{22}) = 2-\left(0 + \left(-\dfrac{2}{3}\right)^2\left(\dfrac{3}{2}\right)\right) = \dfrac{4}{3}$

This gives us:

$$\begin{bmatrix}2 & -1 & 0\\-1 & 2 & -1 \\ 0 & -1 & 2\end{bmatrix} = \begin{bmatrix}1 & 0 & 0\\-\dfrac{1}{2} & 1 & 0 \\ 0 & -\dfrac{2}{3} & 1\end{bmatrix} \begin{bmatrix} 2 & 0 & 0\\ 0 & \dfrac{3}{2} & 0 \\ 0 & 0 & \dfrac{4}{3}\end{bmatrix} \begin{bmatrix}1 & -\dfrac{1}{2} & 0\\0 & 1 & -\dfrac{2}{3} \\ 0 & 0 & 1\end{bmatrix}$$

This agrees with your result and also was verified to produce your original matrix when multiplied out.