Cholesky-Zerlegung

Die Cholesky-Zerlegung ist ein numerisches Verfahren zur Zerlegung einer symmetrischen positiv definiten Matrix in das Produkt einer unteren Dreiecksmatrix und ihrer Transponierten.

Formulierung

Jede symmetrische positiv definite Matrix A∈Rn×nA \in \mathbb{R}^{n\times n} kann eindeutig in der Form
A=LDLTA=L D L^{T}
geschrieben werden. Dabei ist LL eine untere Dreiecksmatrix, deren Diagonalelemente alle gleich 11 sind und DD eine Diagonalmatrix mit positiven Einträgen. Mit der Matrix-"Wurzel" von DD und dem Matrix-Faktor GG, definiert durch
D=D1/2D1/2D = D^{1/2}D^{1/2}
und
G:=LD1/2G := LD^{1/2},
wird die Cholesky-Zerlegung - äquivalent - auch formuliert als
A=GGTA=G G^{T}.
Liegt eine Berechnung der Cholesky-Zerlegung vor, so lässt sich das Gleichungssystem Ax=b Ax=b effizient durch Vorwärts- und Rückwärtseinsetzen lösen:
 
 

Berechnung

Formeln

gik={0fu¨r i<kakk−∑j=1k−1gkj2fu¨r i=k1gkk(aik−∑j=1k−1gijgkj)fu¨r i>kg_{ik} = \begin{cases}0 & \text{für}\ i < k\\ \sqrt{a_{kk} - \sum\limits\limits_{j=1}^{k-1}g_{kj}^2 } &\text{für}\ i = k\\ \dfrac{1}{g_{kk}} \left( a_{ik}-\sum\limits\limits_{j=1}^{k-1}g_{ij} g_{kj} \right) & \text{für}\ i > k \end{cases}

Aufwand

Den Aufwand der Berechnung betreffend muss die Cholesky-Zerlegung mit dem Eliminationsverfahren nach Gauß und seiner algorithmischen Umsetzung, der LR-Zerlegung, verglichen werden. Letzteres erfordert etwa doppelt so viele Operationen, da nicht nur eine Matrix LL, sondern zwei Faktoren LL und RR berechnet werden müssen. Der Algorithmus benötigt ca. 13n3\dfrac{1}{3}n^3 Operationen.

Beispiel

A=GGTA=G G^{T}
mit
A=(420252025) A= \begin{pmatrix} 4 & 2 & 0 \\ 2 & 5 & 2 \\ 0 & 2 & 5 \end{pmatrix}
und
G=(g1100g21g220g31g32g33) G= \begin{pmatrix} g_{11} & 0 & 0 \\ g_{21} & g_{22} & 0 \\ g_{31} & g_{32} & g_{33} \end{pmatrix} und
GT=(g11g21g310g22g3200g33) G^{T}= \begin{pmatrix} g_{11} & g_{21} & g_{31} \\ 0 & g_{22} & g_{32} \\ 0 & 0 & g_{33} \end{pmatrix} ergibt sich
GGT=(g112g11g21g11g31g21g11g212+g222g21g31+g22g32g31g11g31g21+g22g32g312+g322+g332) G G^{T}= \begin{pmatrix} g_{11}^2 & g_{11}g_{21} & g_{11}g_{31} \\ g_{21}g_{11} & g_{21}^2+g_{22}^2 & g_{21}g_{31}+g_{22}g_{32} \\ g_{31}g_{11} & g_{31}g_{21}+g_{22}g_{32} & g_{31}^2+g_{32}^2+g_{33}^2 \end{pmatrix}=(a11a21a31a21a22a32a31a32a33)=A =\begin{pmatrix} a_{11} & a_{21} & a_{31} \\ a_{21} & a_{22} & a_{32} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}=A
Durch Gleichsetzen der Matrixelemente folgt:
g112=a11=4⇒g11=2g_{11}^2 = a_{11} = 4 \qquad \Rightarrow \qquad g_{11}=2
g21⋅g11=a21=2⇒g21=1g_{21} \cdot g_{11}= a_{21} = 2 \qquad \Rightarrow \qquad g_{21}=1
So wird für die restlichen ggs weiterverfahren. Schließlich ergibt sich
G=(200120012) G= \begin{pmatrix} 2 & 0 & 0 \\ 1 & 2 & 0 \\ 0 & 1 & 2 \end{pmatrix}
und
GT=(210021002) G^{T}= \begin{pmatrix} 2 & 1 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{pmatrix} .

Einsatzbereiche

Bei der Anwendung der Methode der kleinsten Quadrate, ist eine Möglichkeit, in jedem Schritt die Normalgleichungen, die eine symmetrisch positiv definite Matrix haben, mit dem Cholesky-Verfahren zu lösen. Dies war die Motivation von Cholesky. Beim Gauß-Newton-Verfahren ist damit bei jedem Iterationsschritt ein Gleichungssystem zu lösen, welches sich mit dem Cholesky-Verfahren bestimmen lässt.
Die Choleskyzerlegung kann auch zur Gewinnung eines Vorkonditionierungsverfahrens für lineare Gleichungssysteme mit positiv definiter Matrix benutzt werden; zu diesem Zweck gibt es speziell die Variante der unvollständigen Cholesky-Zerlegung sowie der modifizierten unvollständigen Cholesky-Zerlegung.
Gleichzeitig stellt die Zerlegung einen Test dar, ob eine gegebene symmetrische Matrix positiv definit ist. Andernfalls ist nämlich einer der Einträge auf der Diagonalen negativ, so dass die Wurzel nicht gezogen werden kann, oder Null, so dass nicht durch den Eintrag geteilt werden kann. In beiden Fällen bricht der Algorithmus ab.
Außerhalb der Mathematik findet die Cholesky-Zerlegung auch Anwendung in der ökonometrischen Erforschung makroökonomischer Zusammenhänge. Hierbei wird bei sogenannten Vektorautoregressiven Modellen (VAR) die Reihenfolge der Beeinflussung der endogenen Variablen untereinander festgelegt.
Darüber hinaus wird sie auch bei der Monte-Carlo-Simulation eingesetzt, um vorgegebene Korrelationen in unabhängig generierte Zufallszahlenfolgen (als Diskretisierung stochastischer Prozesse) zu bringen.

Das Buch der Natur ist mit mathematischen Symbolen geschrieben.

Galileo Galilei

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Cholesky-Zerlegung aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Numerische Verfahren