Beispiele

Ist ${\displaystyle A}$ eine 3x3-Matrix, dann sieht die Cholesky-Zerlegung wie folgt aus:

${\displaystyle {\begin{aligned}A=LDL^{T}&={\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&L_{32}&1\\\end{pmatrix}}{\begin{pmatrix}D_{11}&0&0\\0&D_{22}&0\\0&0&D_{33}\\\end{pmatrix}}{\begin{pmatrix}1&L_{21}&L_{31}\\0&1&L_{32}\\0&0&1\\\end{pmatrix}}\\&={\begin{pmatrix}D_{11}&L_{21}D_{11}&L_{31}D_{11}\\L_{21}D_{11}&L_{21}^{2}D_{11}+D_{22}&L_{31}L_{21}D_{11}+L_{32}D_{22}\\L_{31}D_{11}&L_{31}L_{21}D_{11}+L_{32}D_{22}&L_{31}^{2}D_{11}+L_{32}^{2}D_{22}+D_{33}\end{pmatrix}}\end{aligned}}}$

${\displaystyle {\begin{aligned}A=GG^{T}&={\begin{pmatrix}G_{11}&0&0\\G_{21}&G_{22}&0\\G_{31}&G_{32}&G_{33}\\\end{pmatrix}}{\begin{pmatrix}G_{11}&G_{21}&G_{31}\\0&G_{22}&G_{32}\\0&0&G_{33}\end{pmatrix}}\\&={\begin{pmatrix}G_{11}^{2}&G_{21}G_{11}&G_{31}G_{11}\\G_{21}G_{11}&G_{21}^{2}+G_{22}^{2}&G_{31}G_{21}+G_{32}G_{22}\\G_{31}G_{11}&G_{31}G_{21}+G_{32}G_{22}&G_{31}^{2}+G_{32}^{2}+G_{33}^{2}\end{pmatrix}}\end{aligned}}}$

Mit konkreten Zahlen:

${\displaystyle {\begin{aligned}A={\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}&={\begin{pmatrix}1&0&0\\3&1&0\\-4&5&1\\\end{pmatrix}}{\begin{pmatrix}4&0&0\\0&1&0\\0&0&9\\\end{pmatrix}}{\begin{pmatrix}1&3&-4\\0&1&5\\0&0&1\\\end{pmatrix}}=LDL^{T}\\&={\begin{pmatrix}2&0&0\\6&1&0\\-8&5&3\\\end{pmatrix}}{\begin{pmatrix}2&6&-8\\0&1&5\\0&0&3\\\end{pmatrix}}=GG^{T}\end{aligned}}}$

Aufwand und Stabilität

Die Cholesky-Zerlegung ist numerisch stabil. Im Vergleich erfordert das Eliminationsverfahren nach Gauß mit seiner algorithmischen Umsetzung, der LR-Zerlegung, etwa doppelt so viele Operationen, da nicht nur eine Matrix ${\displaystyle G}$, sondern zwei Faktoren ${\displaystyle L}$ und ${\displaystyle R}$ berechnet werden müssen. Bei der Cholesky-Zerlegung treten ${\displaystyle {\tfrac {1}{3}}\cdot n^{3}+O(n^{2})}$ arithmetische Operationen auf, davon ${\displaystyle {\tfrac {1}{6}}\cdot n^{3}}$ Multiplikationen, ${\displaystyle {\tfrac {1}{2}}\cdot n^{2}}$ Divisionen und ${\displaystyle n}$ Wurzeloperationen.

Pseudocode

Die Berechnungen in obigen Formeln können in verschiedener Weise durchgeführt werden. Die nach Tadeusz Banachiewicz benannte Variante berechnet die untere Dreiecksmatrix zeilenweise. In Pseudocode sieht das Verfahren zur Zerlegung der Matrix ${\displaystyle A}$ in die Form ${\displaystyle GG^{T}}$ so aus:

    For i = 1 To n
        For j = 1 To i
            Summe = a(i, j)
            For k = 1 To j-1
                Summe = Summe - a(i, k) * conj(a(j, k))
            If i > j Then
                a(i, j) = Summe / a(j, j)   // Untere Dreiecksmatrix
            Else If Summe > 0 Then          // Diagonalelement
                a(i, i) = Sqrt(Summe)       // … ist immer größer Null
            Else
                ERROR                       // Die Matrix ist (wenigstens numerisch) nicht symmetrisch positiv definit

Die Laufindexe ${\displaystyle i,j=1,\ldots ,n}$ im Pseudocode entsprechen der mathematischen Notierung von Elementen der Matrix ${\displaystyle A=\left(a_{ij}\right)_{ij}}$. Dabei ist ${\displaystyle n}$ die Anzahl der Zeilen und gleichzeitig die Anzahl der Spalten der Matrix ${\displaystyle A}$, Hilfsvariablen sind ${\displaystyle k}$ und Summe. Der Algorithmus arbeitet in situ: Er modifiziert die Matrix ${\displaystyle A}$ so, dass diese zur unteren Dreiecksmatrix ${\displaystyle G}$ wird. Es entsteht also für die Matrix ${\displaystyle G}$ kein neuer Speicherplatzbedarf.

Der obige Algorithmus bearbeitet nur die linke untere Dreiecksmatrix von ${\displaystyle A=\left(a_{ij}\right)_{ij}}$, die Elemente ${\displaystyle a_{ij}}$ für ${\displaystyle i<j}$ brauchen nicht mit Werten belegt zu werden, da die Matrix ${\displaystyle A}$ nach Voraussetzung symmetrisch ist, und wenn sie Werte enthalten, werden diese nicht verändert. Sucht man also nach der Cholesky-Zerlegung ${\displaystyle G}$ gemäß ${\displaystyle A=GG^{T}}$, so sind die Elemente ${\displaystyle a_{ij}}$ von ${\displaystyle A}$ oberhalb der Diagonalen noch auszunullen.