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 \in \mathbb{R}^{n\times n}$ ist orthogonal diagonalisierbar und kann daher eindeutig in der Form

A = L D L T

geschrieben werden, wobei $L$ eine untere Dreiecksmatrix ohne Diagonale und $D$ eine positive Diagonalmatrix ist. Mit der Matrix-"Wurzel" $D$ und dem Matrix-Faktor $G$ , definiert durch

D = D 1 / 2 D 1 / 2

und

G : = L D 1 / 2

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

A = G G T

Liegt eine Berechnung der Cholesky-Zerlegung vor, so läßt sich beispielsweise die Multiplikation der Matrixinversen $A - 1$ mit einem Vektor $b$ effizient durch Vorwärts- und Rückwärtseinsetzen berechnen:

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

Durch Rückwärtseinsetzen Lösung des linearen Gleichungssystems $G T x = y$

Damit kann die Choleskyzerlegung auch zur Gewinnung eines Präkonditionierungsverfahrens für lineare Gleichungssysteme mit positiv definiter Matrix benutzt werden; zu diesem Zweck gibt es speziell die Variante der unvollständigen Cholesky-Zerlegung. Es wird dabei ausgenutzt, daß man durch Cholesky-Zerlegung recht effizient eine (Näherungs-)Inverse der Matrix berechnen kann.

Berechnung

Für alle k = 1..n; $g_{kk} = \sqrt{a_{kk} - \sum_{i=1}^{k-1}g_{ki}^2 }$

für l=k+1..n; $g_{lk} = \frac{1}{g_{kk}}\left( a_{lk}-\sum_{i=1}^{k-1}g_{li} g_{ki} \right)$

Den Aufwand der Berechnung betreffend muß 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 eine Pivotisierung, d.h. Spalten- und/oder Zeilenpermutation, durchgeführt werden muß, einerseits um Division durch Null zu vermeiden, andererseits aus Stabilitätsgründen. Beide Gründe zur Pivotisierung entfallen bei positiv definiten Matrizen - dies ist die Ursache des geringeren Rechenaufwandes der Cholesky-Zerlegung. Die Cholesky-Zerlegung kann somit als eine Variante des Gauß-Verfahrens ohne Pivotisierung aufgefaßt werden.

Bei klassischen Lösern linearer Gleichungssysteme stellt die Pivotisierung wiederum ein Hindernis für Algorithmen dar, welche die Bandbreite oder Hüllgröße des Faktors $G$ aus Gründen der Speichereffizienz minimieren sollen (etwa Cuthill-McKee- oder Minimum-Grad-Algorithmus). Demnach ist die Cholesky-Zerlegung auch besonders geeignet für die Zerlegung dünnbesetzter Matrizen.

Cholesky-Zerlegung

Formulierung und Anwendung

Berechnung

See also: Cholesky-Zerlegung, André-Louis Cholesky, Diagonalisierung, Diagonalmatrix, Dreiecksmatrix, Gaußsches Eliminationsverfahren, Inverse Matrix, LR-Zerlegung, Matrix (Mathematik), Numerische Mathematik