I'm attempting to understand the Cholesky decomposition via the following site: http://en.wikipedia.org/wiki/Cholesky_decomposition
If I have a matrix, say
$$A = \begin{bmatrix} 2 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 2\end{bmatrix},$$ then I'd like to use the Cholesky Algorithm to find a matrix $D$ such that $A = LDL^{T}$.
I left blank the parts of this example that I do not understand how to find.
The Cholesky Algorithm for this example follows:
Skipping a few steps since we don't need to derive how they get $L$, we know that $L = L_{1}L_{2}L_{3}$ since $n=3$.
For $i=1$, $$L_1 = \begin{bmatrix} I_{1-1} & 0 & 0\\ 0 & \sqrt{a_{1,1}} & 0\\ 0 & b_1/\sqrt{a_{1,1}} & I_{3-1}\end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & \sqrt{2} & 0 & 0\\ 0 & b_1/\sqrt{2} & 1 & 0\\ 0 & 0 & 0 & 1\end{bmatrix}$$
For $i=2$, $$L_ = \begin{bmatrix} I_{2-1} & 0 & 0\\ 0 & \sqrt{a_{2,2}} & 0\\ 0 & b_2/\sqrt{a_{2,2}} & I_{3-2}\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \sqrt{2} & 0\\ 0 & b_2/\sqrt{2} & 1\end{bmatrix}$$
For $i=n = 3$, $$L_3 = \begin{bmatrix} I_{3-1} & 0 & 0\\ 0 & \sqrt{a_{3,3}} & 0\\ 0 & b_3/\sqrt{a_{3,3}} & I_{3-3}\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & \sqrt{2} & 0\\ 0 & 0 & b_3/\sqrt{2} & 0\end{bmatrix}$$.
Thus, \begin{align} L &:= L_1\cdot L_2\cdot L_3\\\notag &= \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & \sqrt{2} & 0 & 0\\ 0 & b_1/\sqrt{2} & 1 & 0\\ 0 & 0 & 0 & 1\end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \\ 0 & \sqrt{2} & 0\\ 0 & b_2/\sqrt{2} & 1\end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & \sqrt{2} & 0\\ 0 & 0 & b_3/\sqrt{2} & 0\end{bmatrix}\\\notag &= ? \end{align}
I guess $b_i$ and $b_i^*$ come from $B$. But how do I find the non-Hermitian matrix $B$ to finish this process?
Wikipedia’s probably not the ideal place to learn about the Cholesky decomposition or of the various algorithms that can be used to generate the decomposition. I’d recommend reading a textbook on numerical linear algebra or general book on numerical mathematics. That being said, I’ve gone ahead and fixed up your steps in the outer-product Cholesky algorithm example that you’ve chosen to follow.
For the record, I’m using the notation from the following snapshot of the Wikipedia article on the Cholesky decomposition:
https://en.wikipedia.org/w/index.php?title=Cholesky_decomposition&oldid=711015429
Before I run through the algorithm, however, note that $I_i$ denotes the $i \times i$ identity matrix. $I_0$, in particular, refers to a $0 \times 0$ matrix, so when it occurs in an algorithm step it gets omitted from the matrix block partition. Also, all matrices $A^{(i)}$ and $L_i$ should have the same size as the original matrix $A$. Last, all elements $a_{ii}$, $b_i$, and $B$ are pulled directly from matrix $A^{(i)}$ using the partitioning described at the Wikipedia article.
$A = A^{\left( 1 \right)} = \left( {\begin{array}{*{20}c} 2 & { - 1} & 0 \\ { - 1} & 2 & { - 1} \\ 0 & { - 1} & 2 \end{array}} \right)$, so $a_{11} = 2$, $b_1^T = \left( {\begin{array}{*{20}c} { - 1} & 0\end{array}} \right)$, and $B^{(1)} = \left( {\begin{array}{*{20}c} 2 & { - 1} \\ { - 1} & 2 \end{array}} \right)$.
Therefore, $L_1 = \left( {\begin{array}{*{20}c} {\sqrt 2 } & 0 & 0 \\ {\frac{{ - 1}}{{\sqrt 2 }}} & 1 & 0 \\ 0 & 0 & 1\end{array}} \right)$ and $A^{\left( 2 \right)} = \left( {\begin{array}{*{20}c} 1 & 0 & 0 \\ 0 & {\frac{3}{2}} & { - 1} \\ 0 & { - 1} & 2\end{array}} \right)$.
Continuing on, we see that $a_{22} = \frac{3}{2}$, $b_2 = -1$, and $B^{(2)} = 2$, so
$L_2 = \left( {\begin{array}{*{20}c} 1 & 0 & 0 \\ 0 & {\sqrt {\frac{3}{2}} } & 0 \\ 0 & { - \sqrt {\frac{2}{3}} } & 1\end{array}} \right)$ and $A^{\left( 3 \right)} = \left( {\begin{array}{*{20}c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & {\frac{4}{3}}\end{array}} \right)$.
From $A^{\left( 3 \right)}$ we immediately write down $L_3 = \left( {\begin{array}{*{20}c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & {\sqrt {\frac{4}{3}} }\end{array}} \right)$.
Therefore, $L = L_1 L_2 L_3 = \left( {\begin{array}{*{20}c} {\sqrt 2 } & 0 & 0 \\ {\frac{{ - 1}}{{\sqrt 2 }}} & {\sqrt {\frac{3}{2}} } & 0 \\ 0 & { - \sqrt {\frac{2}{3}} } & {\sqrt {\frac{4}{3}} }\end{array}} \right)$ which you can confirm satisfies $LL^T = A$.