LU-Zerlegung Schritt für Schritt

Eine Matrix in untere und obere Dreiecksanteile zerlegen, warum das schneller ist als erneutes Eliminieren und wie Cholesky den Sonderfall abdeckt.

Die LU-Zerlegung schreibt eine quadratische Matrix als Produkt einer unteren und einer oberen Dreiecksmatrix: A = L·U. Die Faktoren fallen direkt aus der Gauß-Elimination ab — U ist die Zeilenstufenform, und L hält die Multiplikatoren fest, mit denen Sie dorthin gekommen sind.

Wozu das gut ist

Weil die Zerlegung wiederverwendbar ist. Ax = b von Grund auf zu lösen kostet etwa n³/3 Operationen. Liegen L und U vor, kostet jede weitere rechte Seite nur noch n²: erst Ly = b durch Vorwärtseinsetzen, dann Ux = y durch Rückwärtseinsetzen. Bei Dutzenden rechten Seiten ist das ein großer Gewinn.

Die Determinante gibt es gratis dazu — sie ist das Produkt der Diagonale von U, mal −1 für jeden durchgeführten Zeilentausch.

Pivotisierung

Nicht jede Matrix erlaubt ein einfaches A = L·U: Eine Null an der Pivotstelle bricht das Verfahren. Abhilfe schafft eine Permutationsmatrix, also P·A = L·U. In der Praxis wird ohnehin pivotisiert, weil das größte verfügbare Pivot die Rundungsfehler in Schach hält.

Cholesky: der symmetrische Fall

Ist A symmetrisch und positiv definit, zerfällt sie in A = L·Lᵀ — ein Dreiecksfaktor genügt. Cholesky ist rund doppelt so schnell wie LU und numerisch sehr stabil; deshalb dominiert sie in Optimierung, Ausgleichsrechnung und Statistik (Kovarianzmatrizen sind konstruktions- bedingt symmetrisch positiv definit).

Verlangt der Algorithmus irgendwann die Wurzel aus einer negativen Zahl, war die Matrix nicht positiv definit — Cholesky taugt damit zugleich als Test dieser Eigenschaft.