Direkt zum Inhalt

Lexikon der Mathematik: Cholesky-Verfahren

direktes Verfahren zur Lösung eines linearen Gleichungssytems Ax = b mit einer symmetrischen, positiv definiten Koeffizientenmatrix A ∈ ℝn×n. Es muß also für A gelten: A = AT und \begin{eqnarray}{x}^{T}Ax\gt 0\end{eqnarray} für alle x ∈ ℝn, x ≠ 0.

Für eine symmetrische, positiv definite Matrix A kann das Gauß-Verfahren ohne Pivotisierung durchgeführt werden. Dabei berechnet man die eindeutige Zerlegung von A in ein Produkt der Form A = LLT, wobei L eine untere Dreiecksmatrix mit positiven Diagonaleinträgen ist: \begin{eqnarray}\text{L}=\left(\begin{array}{llll}{\ell }_{11} & & & \\ {\ell }_{21} & {\ell }_{22} & & \\ \vdots & \vdots & \ddots & \\ {\ell }_{n1} & {\ell }_{n2} & \cdots & {\ell }_{nn}\end{array}\right),\,\,\,{\ell }_{jj}\gt 0.\end{eqnarray}

Eine solche Zerlegung nennt man Cholesky-Zerlegung von A.

Man kann nun eine, nach Cholesky benannte, kompakte Variante der Berechnung von L durchführen, diese lautet:

  1. Schritt: Berechne \({\ell }_{11}:=\sqrt{{a}_{11}}\), und für i = 2,…, n: \begin{eqnarray}{\ell }_{i1}:={a}_{i1}/{\ell }_{11}.\end{eqnarray}
  2. Schritt: Für j = 2,…,n: berechne \({\ell }_{j}{}_{j}:=\sqrt{{a}_{j}{}_{j}-\displaystyle {\sum }_{k=1}^{j-1}{\ell }_{jk}^{2}},\) und für i = j + 1,…,n: \begin{eqnarray}{\ell }_{ij}:=({a}_{ij}-\displaystyle {\sum }_{k=1}^{j-1}{\ell }_{ik}{\ell }_{jk})/{\ell }_{jj}.\end{eqnarray}

Dieses Verfahren heißt Cholesky-Verfahren.

Zur Lösung der linearen Gleichungssystems Ax = b führt man nun einen Hilfsvektor \begin{eqnarray}c={L}^{T}x\end{eqnarray} ein und löst zunächst Lc = b durch einfaches Vorwärtseinsetzen.

Dann bestimmt man den Lösungsvektor x aus LTx = c durch Rückwärtseinsetzen.

Für große Werte von n ist der Aufwand für das Verfahren von Cholesky etwa halb so groß wie beim Gauß-Verfahren.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos