# Cholesky-Zerlegung > For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`. URL: https://nakafa.com/de/faecher/ki-und-data-science/lineare-methoden-der-ki/cholesky-zerlegung Source: https://raw.githubusercontent.com/nakafaai/aksara/16d6b8e869d1a277313c65bbfc4b4a83efe77a46/packages/corpus/material/lesson/ai-ds/linear-methods/cholesky-decomposition/de.mdx Lerne die Cholesky-Zerlegung für positiv definite Matrizen anhand des Algorithmus, eines durchgerechneten Beispiels und einer korrekten Aufwandsschätzung. --- ## LU-Zerlegung für positiv definite Matrizen Sei $$A\in\mathbb{R}^{n\times n}$$ symmetrisch positiv definit, also Visible text: Sei symmetrisch positiv definit, also ```math x^TAx>0\qquad\text{für jedes }x\neq0 ``` Diese Bedingung sorgt für eine besonders gutartige Faktorisierung. Die [LU-Zerlegung](/de/faecher/ki-und-data-science/lineare-methoden-der-ki/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. Visible text: Dies bedeutet, dass wir eine Faktorisierung in der Form erhalten, wobei die Diagonalelemente von positive Pivotelemente für alle Diagonalindizes sind. Aus $$A = A^T$$ folgt außerdem: Visible text: Aus folgt außerdem: Component: MathContainer Children: ```math 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: Visible text: wobei eine Matrix ist, deren Hauptdiagonale auf normiert ist, und eine Diagonalmatrix ist: Component: MathContainer Children: ```math \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} ``` ```math D = \begin{pmatrix} u_{11} & & 0 \\ & \ddots & \\ 0 & & u_{nn} \end{pmatrix} ``` Wenn $$L$$ und $$\tilde U$$ Einsen auf der Diagonale besitzen, ist diese LU-Zerlegung eindeutig. Der Vergleich der beiden Faktorisierungen ergibt Visible text: Wenn und Einsen auf der Diagonale besitzen, ist diese LU-Zerlegung eindeutig. Der Vergleich der beiden Faktorisierungen ergibt Component: MathContainer Children: ```math A = L \cdot U = \tilde{U}^T \cdot (D \cdot L^T) ``` ```math L = \tilde{U}^T \quad \text{und} \quad U = D \cdot L^T ``` Wenn wir definieren: ```math 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$$. Visible text: dann . ## Cholesky-Zerlegung Jede reelle symmetrische positiv definite Matrix $$A \in \mathbb{R}^{n \times n}$$ besitzt einen eindeutigen Cholesky-Faktor mit positiven Diagonaleinträgen: Visible text: Jede reelle symmetrische positiv definite Matrix besitzt einen eindeutigen Cholesky-Faktor mit positiven Diagonaleinträgen: ```math 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. Visible text: Dabei ist 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: Visible text: Die Berechnung der Matrix erfolgt mit: ```math \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. Visible text: aus der Beziehung . Der folgende Algorithmus erzeugt den Cholesky-Faktor. ## Cholesky-Algorithmus Gegeben sei eine positiv definite Matrix $$A \in \mathbb{R}^{n \times n}$$. Visible text: Gegeben sei eine positiv definite Matrix . Component: MathContainer Children: ```math \tilde{l}_{11} := \sqrt{a_{11}} ``` ```math \tilde{l}_{j1} := \frac{a_{j1}}{\tilde{l}_{11}}, \quad j = 2, \ldots, n ``` Für $$i = 2, \ldots, n$$: Visible text: Für : Component: MathContainer Children: ```math \tilde{l}_{ii} := \sqrt{a_{ii} - \tilde{l}_{i1}^2 - \tilde{l}_{i2}^2 - \ldots - \tilde{l}_{i,i-1}^2} ``` ```math \tilde{l}_{ji} := \tilde{l}_{ii}^{-1} \cdot \left( a_{ji} - \tilde{l}_{j1}\tilde{l}_{i1} - \tilde{l}_{j2}\tilde{l}_{i2} - \ldots - \tilde{l}_{j,i-1}\tilde{l}_{i,i-1} \right) ``` für $$j = i + 1, \ldots, n$$. Visible text: für . 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: ```math \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 ```math A=\begin{pmatrix}4&2\\2&5\end{pmatrix} ``` Die Einträge des unteren Dreiecksfaktors folgen unmittelbar aus dem Algorithmus: Component: MathContainer Children: ```math \tilde l_{11}=\sqrt4=2 ``` ```math \tilde l_{21}=\frac2{\tilde l_{11}}=1 ``` ```math \tilde l_{22}=\sqrt{5-\tilde l_{21}^2}=2 ``` Damit gilt Component: MathContainer Children: ```math \tilde L=\begin{pmatrix}2&0\\1&2\end{pmatrix} ``` ```math \tilde L\tilde L^T=\begin{pmatrix}2&0\\1&2\end{pmatrix}\begin{pmatrix}2&1\\0&2\end{pmatrix}=\begin{pmatrix}4&2\\2&5\end{pmatrix}=A ``` 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$$. Visible text: Ist der Faktor bekannt, lösen wir mit zwei Dreieckssystemen statt mit einer Inversen: zuerst , danach . ## Cholesky-Algorithmus-Komplexität Der Cholesky-Algorithmus zur Berechnung des Cholesky-Faktors $$\tilde{L}$$ aus $$A \in \mathbb{R}^{n \times n}$$ erfordert: Visible text: Der Cholesky-Algorithmus zur Berechnung des Cholesky-Faktors aus erfordert: ```math \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. Visible text: Der führende Term enthält ungefähr Multiplikationen und Additionen. Zusammen sind das etwa Gleitkommaoperationen und damit ungefähr die Hälfte des führenden Aufwands 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.