Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Cholesky-Zerlegung aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Cholesky-Zerlegung

Die Cholesky-Zerlegung (nach André-Louis Cholesky (1875-1918)) bezeichnet in der numerischen_Mathematik eine Zerlegung einer symmetrischen positiv_definiten Matrix.

Formulierung und Anwendung

Jede symmetrische positiv definite Matrix $A\; \backslash in\; \backslash mathbb\{R\}^\{n\backslash times\; n\}$ kann eindeutig in der Form

:$A=L\; D\; L^\{T\}$

geschrieben werden. Dabei ist $L$ eine untere Dreiecksmatrix, deren Diagonalelemente alle gleich 1 sind und $D$ eine Diagonalmatrix mit positiven Einträgen.
Mit der Matrix-"Wurzel" von $D$ und dem Matrix-Faktor $G$, definiert durch

:$D\; =\; D^\{1/2\}D^\{1/2\}$

und

:$G\; :=\; LD^\{1/2\}$,

wird die Cholesky-Zerlegung ? äquivalent ? auch formuliert als

:$A=G\; G^\{T\}$.

Liegt eine Berechnung der Cholesky-Zerlegung vor, so lässt sich das Gleichungssystem $Ax=b$ effizient durch Vorwärts-_und_Rückwärtseinsetzen lösen:

* Durch Vorwärtseinsetzen Lösung des linearen Gleichungssystems $G\; y\; =\; b$

* Durch anschließendes Rückwärtseinsetzen Lösung des linearen Gleichungssystems $G^\{T\}\; x\; =\; y.$

Berechnung

Setzt man $A=GG^T$ so erhält man für die Elemente von A:

$a\_\{ij\}=\backslash sum\backslash limits\_\{k=1\}^jg\_\{ik\}\; g\_\{jk\}\; \backslash quad\; i\backslash ge\; j$

Dieser Zusammenhang führt direkt auf die folgenden Formeln.

:
\sqrt{a_{ii} - \sum\limits_{k=1}^{i-1}g_{ik}^2 } & \mathrm{f\ddot{u}r}\ i = j\\
\frac{1}{g_{jj}} \left( a_{ij}-\sum\limits_{k=1}^{j-1}g_{ik} g_{jk} \right) & \mathrm{f\ddot{u}r}\ i > j
\end{cases}

Aufwand und Stabilität

Die Cholesky-Zerlegung ist numerisch_stabil. 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 G, sondern zwei Faktoren L und R berechnet werden müssen. Der Algorithmus benötigt ca. $\backslash frac\{1\}\{3\}n^3$ Operationen.

Pseudocode

In Pseudocode sieht das Cholesky-Verfahren zur Zerlegung der Matrix A in die Form $GG^T$ so aus:

For i = 1 To n
Summe = a(i, i)
For k = 1 To i-1
Summe = Summe - a(i, k) * a(i, k)
Next k
If Summe <= 0 Then EXIT // A ist nicht positiv definit
else a(i, i) = Sqrt(Summe) // Summe ist positiv
End If
For j = 1 To i-1
Summe = a(i, j)
For k = 1 To i-1
Summe = Summe - a(i, k) * a(j, k)
Next k
a(i, j) = Summe / a(i, i)

Next j
Next i

Die Indizes der Matrix A entsprechen der mathematischen Notierung i=1..n, j=1..n, n ist die Anzahl der Zeilen und gleichzeitig die Anzahl der Spalten der Matrix A, Hilfsvariablen sind i, j, k und Summe. Der Algorithmus arbeitet am Ort, d.h. er modifiziert die Matrix A so, dass sie die untere Dreiecksmatrix G enthält.

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

Einsatzbereiche

Bei der Anwendung der Gaußschen_Fehlerquadratmethode, 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 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.

Literatur

* Hans Rudolf Schwarz & Nobert Köckler: Numerische Mathematik. Stuttgart: Teubner, 2004 (5. Auflage) ISBN 3-519-42960-8
* Gene H. Golub & Charles F. Van Loan: Matrix computations. Johns Hopkins University Press, 1996 (3rd edition) ISBN 0-80185414-8

       VIDEO-NEWS UND ANGEBOTE