Geben Sie eine quadratische Matrix ein, öffnen Sie den Reiter Zerlegungen und klicken Sie auf LU(A). Weil das Ergebnis ein Matrizenpaar und keine einzelne Matrix ist, lebt es ganz im Rechenweg, der sich von selbst öffnet und am Ende L und U nebeneinander zeigt. Cholesky(A) liegt im selben Reiter, für den unten erklärten symmetrischen Fall.
Was die Faktoren sind
Die LU-Zerlegung schreibt A = L·U, mit L untere und U obere Dreiecksmatrix. Keine von beiden ist geheimnisvoll: U ist genau die Zeilenstufenform, die die Gauß-Elimination liefert, und L hält die Multiplikatoren fest, die Sie unterwegs verwendet haben. Eine Elimination liefert beide.
Beispiel
| 4 | 3 |
| 6 | 3 |
| 1 | 0 |
| 3/2 | 1 |
| 4 | 3 |
| 0 | −3/2 |
Die 3/2 in L ist der Multiplikator, der die 6 unter dem Pivot beseitigt hat. Beachten Sie, dass die Determinante nun gratis ist: das Produkt der Diagonale von U, also 4 · (−3/2) = −6, mal −1 für jeden durchgeführten Zeilentausch.
Warum sich das lohnt
Weil die Zerlegung wiederverwendbar ist. Ax = b von Grund auf zu lösen kostet etwa n³/3 Operationen. Hat man L und U, kostet jede weitere rechte Seite nur noch n²: Ly = b per Vorwärtseinsetzen, dann Ux = y per Rückwärtseinsetzen. Wenn Sie dasselbe System gegen viele verschiedene b-Vektoren lösen — der Normalfall in Technik und Simulation — ist die Ersparnis enorm. Bei einer 100×100-Matrix und fünfzig rechten Seiten ist das eine Zerlegung plus fünfzig billige Durchläufe statt fünfzig vollständiger Eliminationen.
Vorwärts- und Rückwärtseinsetzen, durchgerechnet
Nehmen Sie die oben geladene 3×3-Matrix. Eine Elimination liefert beide Faktoren:
| 2 | 1 | 1 |
| 4 | −6 | 0 |
| −2 | 7 | 2 |
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| −1 | −1 | 1 |
| 2 | 1 | 1 |
| 0 | −8 | −2 |
| 0 | 0 | 1 |
Die Einträge von L sind genau die Multiplikatoren aus der Elimination: 2 beseitigte die 4, −1 die −2, und −1 das, was in der zweiten Spalte übrig war. Lösen Sie nun Ax = b für b = (4, −2, 7). Zuerst Ly = b, von oben nach unten, wobei jede Zeile sofort einen neuen Wert liefert, weil rechts von ihr alles null ist:
y₁ = 4; dann 2·4 + y₂ = −2, also y₂ = −10; dann −4 + 10 + y₃ = 7, also y₃ = 1.
Dann Ux = y, von unten nach oben: x₃ = 1; dann −8x₂ − 2 = −10, also x₂ = 1; dann 2x₁ + 1 + 1 = 4, also x₁ = 1. Die Lösung ist (1, 1, 1), erreicht ohne eine einzige Division durch etwas anderes als einen Diagonaleintrag. Die Determinante fällt aus denselben Faktoren ab: 2 · (−8) · 1 = −16.
Pivotisierung
Nicht jede Matrix erlaubt ein schlichtes A = L·U: Eine Null in der Pivotposition macht es unmöglich. Abhilfe schafft eine Permutationsmatrix, also P·A = L·U. In der Praxis wird ohnehin pivotisiert, weil die Wahl des größten verfügbaren Pivots Rundungsfehler unter Kontrolle hält. Die Zerlegung ist eindeutig, sobald eine Konvention feststeht; dieser Rechner verwendet die von Doolittle, die Einsen auf die Diagonale von L setzt.
Cholesky: der symmetrische Fall
Ist A symmetrisch und positiv definit, zerfällt sie in A = L·Lᵀ — eine Quadratwurzel für Matrizen, mit nur einem Dreiecksfaktor. Symmetrisch heißt A = Aᵀ; positiv definit heißt, jeder Eigenwert ist größer als null. Das klingt einschränkend, doch die so beschriebenen Matrizen sind überall: Kovarianzmatrizen, Gram-Matrizen, die Normalgleichungen der kleinsten Quadrate und die Steifigkeitsmatrizen der Finite-Elemente-Methode sind alle von Natur aus symmetrisch positiv definit.
| 4 | 2 |
| 2 | 5 |
| 2 | 0 |
| 1 | 2 |
| 2 | 1 |
| 0 | 2 |
Jeder Diagonaleintrag von L ist eine Quadratwurzel — hier √4 = 2 und √(5 − 1²) = 2 — und deshalb verlangt das Verfahren, dass der Ausdruck unter jeder Wurzel positiv bleibt. Genau diese Bedingung ist die positive Definitheit, und sie macht den Algorithmus zu einem Test: Läuft die Zerlegung durch, ist die Matrix positiv definit; stößt sie unter einer Wurzel auf einen nicht positiven Wert, ist sie es nicht. Cholesky ist rund doppelt so schnell wie LU, braucht halb so viel Speicher und ist ohne Pivotisierung stabil — deshalb prüfen Löser zuerst auf Symmetrie und greifen darauf zurück, wann immer sie können.
Häufige Fehler
- Annehmen, jede Matrix zerfalle. Eine Null in der Pivotposition verhindert die einfache LU-Zerlegung. Abhilfe schafft eine Permutationsmatrix:
P·A = L·U. - Cholesky auf eine nicht symmetrische Matrix anwenden. A = L·Lᵀ ist von Bauart symmetrisch, eine nicht symmetrische Eingabe hat also keine solche Zerlegung. Nehmen Sie LU.
- Symmetrie für ausreichend halten. Eine symmetrische Matrix mit negativem Eigenwert ist indefinit und scheitert mitten im Algorithmus.
- Ganzzahlige Faktoren erwarten. Die Cholesky-Diagonale enthält Quadratwurzeln, L ist also meist irrational, auch wenn A es nicht ist.
- Die Zeilentausche in der Determinante vergessen. Jeder Tausch kehrt ihr Vorzeichen um.