Cholesky-Zerlegung

Cholesky-Zerlegung

Die Cholesky-Zerlegung (auch Cholesky-Faktorisierung) (nach André-Louis Cholesky, 1875–1918) bezeichnet in der numerischen Mathematik eine Zerlegung einer symmetrischen positiv definiten Matrix. Sie wurde von Cholesky vor 1914 im Zuge der Triangulation Kretas durch den Service géographique de l'armée entwickelt.

Inhaltsverzeichnis

Einsatzbereiche

Bei der Anwendung der Methode der kleinsten Quadrate ist eine Möglichkeit, die auftauchenden Minimierungsprobleme über die Normalgleichungen zu lösen, die eine symmetrisch positiv definite Systemmatrix haben. Dies ist mit Hilfe der Cholesky-Zerlegung möglich und dies war die Motivation von Cholesky, die Zerlegung zu entwickeln. Beim Gauß-Newton-Verfahren ist damit bei jedem Iterationsschritt ein Gleichungssystem zu lösen, das sich mit dem Cholesky-Verfahren bestimmen lässt.

Die Cholesky-Zerlegung 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. Die Cholesky-Zerlegung lässt sich auch zur Bestimmung der Determinanten der Matrix A verwenden, denn es gilt \det A = \prod_{i=1}^n G_{ii}^2.

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.

Formulierung und Anwendung

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

A = LDLT

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 = D1 / 2D1 / 2

und

G: = LD1 / 2,

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

A = GGT.

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 Gy = b
  • Durch anschließendes Rückwärtseinsetzen Lösung des linearen Gleichungssystems GTx = y.

Berechnung

Setzt man A = GGT so erhält man für die Elemente von A:

a_{ij}=\sum\limits_{k=1}^jg_{ik} g_{jk} \quad i\ge j

Dieser Zusammenhang führt direkt auf die folgenden Formeln.

g_{ij} = \begin{cases}0 & \mathrm{f\ddot{u}r}\ i < j\\
\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 sie 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. Bei der Cholesky-Zerlegung treten ungefähr \tfrac{1}{6}n^3 Multiplikationen, Divisionen und Wurzeloperationen auf.[1]

Pseudocode

In Pseudocode sieht das Cholesky-Verfahren zur Zerlegung der Matrix A in die Form GGT so aus:

    For i = 1 To n
        For j = 1 To i-1
            Summe = a(i, j)
            For k = 1 To j-1
                Summe = Summe - a(i, k) * a(j, k)
            Next k
            a(i, j) = Summe / a(j, j)
        Next j
        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
    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 in-place, das heißt 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 ai, 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 = CGT, so sind die Matrixelemente von A oberhalb der Diagonalen (i < j) gleich Null zu setzen.

Literatur

  • Hans Rudolf Schwarz, Norbert Köckler: Numerische Mathematik. 5. Auflage. Teubner, Stuttgart 2004, ISBN 3-519-42960-8.
  • Gene H. Golub, Charles F. Van Loan: Matrix computations. Johns Hopkins University Press, 1996 (3rd edition) ISBN 0-8018-5414-8.
  • Michael Saunders: Commentary – Major Cholesky Would Feel Proud. In: ORSA Journal on Computing 6, 1994. S. 23-27.

Einzelnachweise

  1. Andreas Meister: Numerik linearer Gleichungssysteme. 2. Auflage. Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7, S. 46

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Unvollständige Cholesky-Zerlegung — Als ILU Zerlegung (von incomplete LU Decomposition) oder unvollständige LU Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen… …   Deutsch Wikipedia

  • Zerlegung — bezeichnet in der Mathematik: Primfaktorzerlegung, die Zerlegung von natürlichen Zahlen in Primfaktoren Partition (Mengenlehre), die Zerlegung (Partitionierung) einer Menge in mehrere, kleinere Mengen die Zerlegung eines Intervalls, siehe Riemann …   Deutsch Wikipedia

  • Cholesky-Verfahren — Die Cholesky Zerlegung (nach André Louis Cholesky (1875 1918)) bezeichnet in der numerischen Mathematik eine Zerlegung einer symmetrischen positiv definiten Matrix. Inhaltsverzeichnis 1 Einsatzbereiche 2 Formulierung und Anwendung 3 …   Deutsch Wikipedia

  • Cholesky — André Louis Cholesky (* 15. Oktober 1875 in Montguyon; † 31. August 1918 in Nordfrankreich) war ein französischer Mathematiker. Cholesky stammte aus einer ukrainischen Familie, die während der napoleonischen Zeiten nach Frankreich einwanderte. Er …   Deutsch Wikipedia

  • Unvollständige LR-Zerlegung — Als ILU Zerlegung (von incomplete LU Decomposition) oder unvollständige LU Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen… …   Deutsch Wikipedia

  • Unvollständige LU-Zerlegung — Als ILU Zerlegung (von incomplete LU Decomposition) oder unvollständige LU Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen… …   Deutsch Wikipedia

  • ILU-Zerlegung — Als ILU Zerlegung (von incomplete LU Decomposition) oder unvollständige LU Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen… …   Deutsch Wikipedia

  • Andre-Louis Cholesky — André Louis Cholesky (* 15. Oktober 1875 in Montguyon; † 31. August 1918 in Nordfrankreich) war ein französischer Mathematiker. Cholesky stammte aus einer ukrainischen Familie, die während der napoleonischen Zeiten nach Frankreich einwanderte. Er …   Deutsch Wikipedia

  • André-Louis Cholesky — (* 15. Oktober 1875 in Montguyon; † 31. August 1918 in Nordfrankreich) war ein französischer Mathematiker. Cholesky studierte an der École polytechnique und trat dann in die Armee ein, wo er Vermessungsoffizier (Commandant d Artillerie) wurde. Er …   Deutsch Wikipedia

  • Choleskyzerlegung — Die Cholesky Zerlegung (nach André Louis Cholesky (1875 1918)) bezeichnet in der numerischen Mathematik eine Zerlegung einer symmetrischen positiv definiten Matrix. Inhaltsverzeichnis 1 Einsatzbereiche 2 Formulierung und Anwendung 3 …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”