Choleskyzerlegung

Warum kein Zeilentausch nötig ist

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

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

Für eine Matrix mit dieser Eigenschaft kommt die LU-Zerlegung ohne Zeilenvertauschung aus. Bei exakter Rechnung ist $jeder Eliminationspivot 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:

\begin{aligned} A &= A^T \\ &= (L \cdot U)^T \\ &= (L \cdot D \cdot \tilde{U})^T \\ &= \tilde{U}^T \cdot D \cdot L^T \end{aligned}

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

\tilde{U} = \begin{pmatrix} 1 & \frac{u_{12}}{u_{11}} & \cdots & \frac{u_{1n}}{u_{11}} \\ & \ddots & \ddots & \vdots \\ & & 1 & \frac{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 $\mathrm{LU}$ -Zerlegung eindeutig. Der Vergleich der beiden Faktorisierungen ergibt

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

Wir definieren die diagonale Wurzelmatrix wie folgt.

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

Diese Matrix erfüllt $D^{\frac{1}{2}} \cdot D^{\frac{1}{2}} = D$ .

Ein eindeutiger Faktor mit positiver Diagonale

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&\cdots&0\\\tilde l_{21}&\tilde l_{22}&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\\tilde l_{n1}&\tilde l_{n2}&\cdots&\tilde l_{nn}\end{pmatrix}

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

Choleskyalgorithmus

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}-\sum_{k=1}^{i-1}\tilde l_{ik}^2}

Berechne zunächst den verbleibenden Eintrag:

r_{ji}=a_{ji}-\sum_{k=1}^{i-1}\tilde l_{jk}\tilde l_{ik}

Die zweite Rekursionsformel gilt für $j = i + 1, \ldots, n$ .

Der $Ausdruck unter jeder Quadratwurzel$ muss positiv bleiben. Ein Wert von null oder kleiner bedeutet, dass die Eingabe nicht positiv definit ist oder dass Rundungsfehler ein nahezu singuläres Problem beeinflusst haben. Der Betrag dieses Werts würde die Rekursion verändern und kann einen Faktor erzeugen, der $A=LL^T$ nicht erfüllt.

Nach dem Algorithmus erhalten wir den unteren Dreiecksfaktor von Cholesky:

\tilde L=\begin{pmatrix}\tilde l_{11}&0&\cdots&0\\\tilde l_{21}&\tilde l_{22}&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\\tilde l_{n1}&\tilde l_{n2}&\cdots&\tilde l_{nn}\end{pmatrix}

Eine positiv definite Matrix zweiter Ordnung faktorisieren

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$ .

Komplexität des Choleskyalgorithmus

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}

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 $\mathrm{LU}$ -Zerlegung für eine allgemeine dichte Matrix. Cholesky spart Arbeit, weil die $Symmetrie genutzt$ und nur eine Dreieckshälfte der Faktorisierung gespeichert wird.