Cholesky-Zerlegung

LU-Zerlegung für positiv definite Matrizen

Cholesky-Zerlegung

LU-Zerlegung für positiv definite Matrizen

Sei $A\in\mathbb{R}^{n\times n}$ symmetrisch positiv definit, also

x^TAx>0\qquad\text{für jedes }x\neq0

Diese Bedingung sorgt für eine besonders gutartige Faktorisierung. Die LU-Zerlegung kommt ohne Zeilenvertauschung aus, und jeder Pivot der exakten Gauß-Elimination ist positiv.

Dies bedeutet, dass wir eine Faktorisierung in der Form $A = L \cdot U$ erhalten, wobei die Diagonalelemente von $U$ positive Pivotelemente für alle Diagonalindizes sind.

Aus $A = A^T$ folgt außerdem:

A = A^T = (L \cdot U)^T = (L \cdot D \cdot \tilde{U})^T = \tilde{U}^T \cdot D \cdot L^T

wobei $\tilde{U}$ eine Matrix ist, deren Hauptdiagonale auf $1$ normiert ist, und $D$ eine Diagonalmatrix ist:

\tilde{U} = \begin{pmatrix} 1 & u_{12}/u_{11} & \cdots & u_{1n}/u_{11} \\ & \ddots & \ddots & \vdots \\ & & 1 & u_{n-1,n}/u_{n-1,n-1} \\ 0 & & & 1 \end{pmatrix}

Wenn $L$ und $\tilde U$ Einsen auf der Diagonale besitzen, ist diese LU-Zerlegung eindeutig. Der Vergleich der beiden Faktorisierungen ergibt

A = L \cdot U = \tilde{U}^T \cdot (D \cdot L^T)

Wenn wir definieren:

D^{\frac{1}{2}} = \begin{pmatrix} \sqrt{u_{11}} & & 0 \\ & \ddots & \\ 0 & & \sqrt{u_{nn}} \end{pmatrix}

dann $D^{\frac{1}{2}} \cdot D^{\frac{1}{2}} = D$ .

Cholesky-Zerlegung

Jede reelle symmetrische positiv definite Matrix $A \in \mathbb{R}^{n \times n}$ besitzt einen eindeutigen Cholesky-Faktor mit positiven Diagonaleinträgen:

A = L \cdot D \cdot L^T = \tilde{L} \cdot \tilde{L}^T

Dabei ist $\tilde{L} = L \cdot D^{\frac{1}{2}}$ eine invertierbare untere Dreiecksmatrix. Die positiven Quadratwurzeln der Pivots legen die Vorzeichen der Diagonale fest und machen den Faktor eindeutig.

Die Berechnung der Matrix $\tilde{L}$ erfolgt mit:

\tilde{L} = \begin{pmatrix} \tilde{l}_{11} & 0 \\ \vdots & \ddots \\ \tilde{l}_{n1} & \cdots & \tilde{l}_{nn} \end{pmatrix}

aus der Beziehung $\tilde{L} \cdot \tilde{L}^T = A$ . Der folgende Algorithmus erzeugt den Cholesky-Faktor.

Cholesky-Algorithmus

Gegeben sei eine positiv definite Matrix $A \in \mathbb{R}^{n \times n}$ .

\tilde{l}_{11} := \sqrt{a_{11}}

Für $i = 2, \ldots, n$ :

\tilde{l}_{ii} := \sqrt{a_{ii} - \tilde{l}_{i1}^2 - \tilde{l}_{i2}^2 - \ldots - \tilde{l}_{i,i-1}^2}

für $j = i + 1, \ldots, n$ .

Der Ausdruck unter jeder Quadratwurzel muss positiv bleiben. Ein Wert von null oder kleiner darf nicht durch einen Betrag kaschiert werden: Er zeigt, dass die Eingabe nicht positiv definit ist oder dass die Rechnung mit endlicher Genauigkeit eine sorgfältigere numerische Behandlung verlangt.

Nach dem Algorithmus erhalten wir den unteren Dreiecksfaktor von Cholesky:

\tilde{L} = \begin{pmatrix} \tilde{l}_{11} & 0 \\ \vdots & \ddots \\ \tilde{l}_{n1} & \cdots & \tilde{l}_{nn} \end{pmatrix}

Durchgerechnetes Beispiel

Wir faktorisieren die Matrix

A=\begin{pmatrix}4&2\\2&5\end{pmatrix}

Die Einträge des unteren Dreiecksfaktors folgen unmittelbar aus dem Algorithmus:

\tilde l_{11}=\sqrt4=2

Damit gilt

\tilde L=\begin{pmatrix}2&0\\1&2\end{pmatrix}

Ist der Faktor bekannt, lösen wir $Ax=b$ mit zwei Dreieckssystemen statt mit einer Inversen: zuerst $\tilde Ly=b$ , danach $\tilde L^Tx=y$ .

Cholesky-Algorithmus-Komplexität

Der Cholesky-Algorithmus zur Berechnung des Cholesky-Faktors $\tilde{L}$ aus $A \in \mathbb{R}^{n \times n}$ erfordert:

\frac{1}{3}n^3 + O(n^2)\quad\text{flops}

Gleitkommaoperationen.

Der führende Term enthält ungefähr $n^3/6$ Multiplikationen und $n^3/6$ Additionen. Zusammen sind das etwa $n^3/3$ Gleitkommaoperationen und damit ungefähr die Hälfte des führenden Aufwands $2n^3/3$ einer LU-Zerlegung für eine allgemeine dichte Matrix. Cholesky spart Arbeit, weil die Symmetrie genutzt und nur eine Dreieckshälfte der Faktorisierung gespeichert wird.