Editing Cholesky decomposition (section)

=== The Cholesky algorithm ===
The '''Cholesky algorithm''', used to calculate the decomposition matrix {{math|'''L'''}}, is a modified version of [[Gaussian elimination]].

The recursive algorithm starts with {{math|1=''i'' := 1}} and
:{{math|1='''A'''<sup>(1)</sup> := '''A'''}}.

At step {{mvar|i}}, the matrix {{math|'''A'''<sup>(''i'')</sup>}} has the following form:
<math display=block>\mathbf{A}^{(i)}=
\begin{pmatrix}
\mathbf{I}_{i-1} & 0              & 0 \\
0                & a_{i,i}        & \mathbf{b}_{i}^{*} \\
0                & \mathbf{b}_{i} & \mathbf{B}^{(i)}
\end{pmatrix},
</math>
where {{math|'''I'''<sub>''i''−1</sub>}} denotes the [[identity matrix]] of dimension {{math|''i'' − 1}}.

If the matrix {{math|'''L'''<sub>''i''</sub>}} is defined by
<math display=block>\mathbf{L}_{i}:=
\begin{pmatrix}
\mathbf{I}_{i-1} & 0                                  & 0 \\
0                & \sqrt{a_{i,i}}           & 0 \\
0                & \frac{1}{\sqrt{a_{i,i}}} \mathbf{b}_{i} & \mathbf{I}_{n-i}
\end{pmatrix},
</math>
(note that {{math|''a''<sub>''i,i''</sub> > 0}} since  {{math|'''A'''<sup>(''i'')</sup>}} is positive definite),
then {{math|'''A'''<sup>(''i'')</sup>}} can be written as
<math display=block>\mathbf{A}^{(i)} = \mathbf{L}_{i} \mathbf{A}^{(i+1)} \mathbf{L}_{i}^{*}</math>
where
<math display=block>\mathbf{A}^{(i+1)}=
\begin{pmatrix}
\mathbf{I}_{i-1} & 0 & 0 \\
0                & 1 & 0 \\
0                & 0 & \mathbf{B}^{(i)} - \frac{1}{a_{i,i}} \mathbf{b}_{i} \mathbf{b}_{i}^{*}
\end{pmatrix}.</math>
Note that {{math|'''b'''<sub>''i''</sub> '''b'''<sub>''i''</sub>*}} is an [[outer product]], therefore this algorithm is called the ''outer-product version'' in (Golub & Van Loan).

This is repeated for {{mvar|i}} from 1 to {{mvar|n}}. After {{mvar|n}} steps, {{math|1='''A'''<sup>(''n''+1)</sup> = '''I'''}} is obtained, and hence, the lower triangular matrix {{mvar|L}} sought for is calculated as

<math display=block>\mathbf{L} := \mathbf{L}_{1} \mathbf{L}_{2} \dots \mathbf{L}_{n}.</math>