Cholesky-Zerlegung

Matrix-Zerlegung für Gauss Newton Verfahren

Die Cholesky-Zerlegung (auch Cholesky-Faktorisierung) (nach André-Louis Cholesky, 1875–1918) bezeichnet in der linearen Algebra eine Zerlegung einer symmetrischen positiv definiten Matrix in ein Produkt aus einer unteren Dreiecksmatrix und deren Transponierten. Die Zerlegung existiert für jede solche Matrix und ist nur bei der erweiterten Zerlegung mit Diagonalmatrix D eindeutig. Die Cholesky-Zerlegung selbst ist nicht eindeutig. Sie wurde von Cholesky vor 1914 im Zuge der Triangulation Kretas durch den französischen Service géographique de l’armée entwickelt. Das Konzept kann auch allgemeiner für hermitesche Matrizen definiert werden.

Anwendungen

Bearbeiten

Bei der Anwendung der Methode der kleinsten Quadrate ist eine Möglichkeit, die auftauchenden Minimierungsprobleme über die Normalgleichungen zu lösen, die eine symmetrische 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 Varianten der unvollständigen Cholesky-Zerlegung und der modifizierten unvollständigen Cholesky-Zerlegung.

Gleichzeitig stellt die Zerlegung einen Test dar, ob eine gegebene symmetrische Matrix positiv definit ist. Andernfalls ist eines der Elemente auf der Hauptdiagonalen negativ, sodass die Quadratwurzel nicht gezogen werden kann, oder gleich  , sodass durch das Element nicht dividiert werden kann. In beiden Fällen bricht der Algorithmus ab. Die Cholesky-Zerlegung lässt sich auch zur Bestimmung der Determinante der Matrix   verwenden, denn es gilt  .

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

Bearbeiten

Jede symmetrische, positiv definite Matrix   kann eindeutig in der Form

 

geschrieben werden. Dabei ist   eine normierte untere Dreiecksmatrix und   eine Diagonalmatrix mit positiven Elementen. Mit der Quadratwurzel von   und dem Matrix-Faktor  , definiert durch

 

und

 ,

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

 .

Liegt eine Berechnung der Cholesky-Zerlegung vor, so lässt sich das Gleichungssystem   effizient durch Vorwärts- und Rückwärtseinsetzen lösen:

  • Durch Vorwärtseinsetzen: Lösen des linearen Gleichungssystems  
  • Durch anschließendes Rückwärtseinsetzen: Lösen des linearen Gleichungssystems  

Für die Elemente   der Diagonalmatrix   gilt

 

und für die Elemente   der normierte untere Dreiecksmatrix   gilt

 

Beispiele

Bearbeiten

Ist   eine 3x3-Matrix, dann sieht die Cholesky-Zerlegung wie folgt aus:

 
 

Mit konkreten Zahlen:

 

Berechnung

Bearbeiten

Setzt man  , so erhält man für die Elemente von  :

 

Dieser Zusammenhang führt direkt auf die folgenden Formeln für  :

 

Bei diesem Algorithmus ist es wichtig, die Elemente in der richtigen Reihenfolge zu berechnen. Die Elemente werden spaltenweise berechnet und beginnend mit dem niedrigsten Zeilenindex.

Die Berechnung der Zerlegung   erfolgt in analoger Art und Weise für   und  :

 

Auch bei diesen Algorithmen ist es wichtig, die Reihenfolge der berechneten Elemente richtig zu wählen. Zuerst muss man zum Index   das Element   berechnen und anschließend die Spalte   der Matrix  , also:   für  .

Aufwand und Stabilität

Bearbeiten

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  , sondern zwei Faktoren   und   berechnet werden müssen. Bei der Cholesky-Zerlegung treten   arithmetische Operationen auf, davon   Multiplikationen,   Divisionen und   Wurzeloperationen.[1]

Pseudocode

Bearbeiten

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   in die Form   so aus:

 
Zugriffe (weiß) und Schreibvorgänge (gelb).
    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   im Pseudocode entsprechen der mathematischen Notierung von Elementen der Matrix  . Dabei ist   die Anzahl der Zeilen und gleichzeitig die Anzahl der Spalten der Matrix  , Hilfsvariablen sind   und Summe. Der Algorithmus arbeitet in situ: Er modifiziert die Matrix   so, dass diese zur unteren Dreiecksmatrix   wird. Es entsteht also für die Matrix   kein neuer Speicherplatzbedarf.

Der obige Algorithmus bearbeitet nur die linke untere Dreiecksmatrix von  , die Elemente   für   brauchen nicht mit Werten belegt zu werden, da die Matrix   nach Voraussetzung symmetrisch ist, und wenn sie Werte enthalten, werden diese nicht verändert. Sucht man also nach der Cholesky-Zerlegung   gemäß  , so sind die Elemente   von   oberhalb der Diagonalen noch auszunullen.

Literatur

Bearbeiten
  • 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. 3rd edition. Johns Hopkins University Press, 1996, ISBN 0-8018-5414-8.
  • Michael Saunders: Commentary – Major Cholesky Would Feel Proud. In: ORSA Journal on Computing, 6, 1994, S. 23–27.
Bearbeiten
  • taramath Online-Tool zur Berechnung der Cholesky-Zerlegung symmetrischer und positiv definiter Matrizen.

Einzelnachweise

Bearbeiten
  1. Andreas Meister: Numerik linearer Gleichungssysteme. 5. Auflage. Vieweg, Wiesbaden 2015, ISBN 3-528-13135-7, S. 49.