LU-Zerlegung Rechner (Doolittle)

Berechne die LU-Zerlegung von 2×2- und 3×3-Matrizen mit Doolittles Methode. Lösung linearer Gleichungssysteme Ax=b, Determinante und ausführliche Schritte.

Berechnungsparameter
Scegli il tipo di calcolo.
Elemento a₁₁ della matrice A.
Elemento a₁₂.
Elemento a₁₃ (solo 3×3).
Elemento a₂₁.
Elemento a₂₂.
Elemento a₂₃ (solo 3×3).
Elemento a₃₁ (solo 3×3).
Elemento a₃₂ (solo 3×3).
Elemento a₃₃ (solo 3×3).
Primo elemento del vettore noto b (solo modo risolvi).
Secondo elemento b₂.
Terzo elemento b₃.
War dieser Rechner nützlich?

Die LU-Zerlegung

Die LU-Zerlegung (L = Lower, U = Upper) ist eine der wichtigsten Matrix-Faktorisierungen der numerischen linearen Algebra. Sie schreibt eine quadratische Matrix A als Produkt aus einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix U:

A = L · U

Doolittle: diag(L) = 1; Crout: diag(U) = 1. Der Rechner nutzt Doolittle, Standard in LAPACK.

Warum faktorisieren?

  1. Vorwärtseinsetzen: löst L·y = b, O(n²).
  2. Rückwärtseinsetzen: löst U·x = y, O(n²).

Bei vielen Vektoren b mit derselben A wird die teure Faktorisierung (O(n³/3)) nur einmal durchgeführt; jede weitere Lösung kostet dann 2n². Grundlage von MATLAB , NumPy, LAPACK, Eigen, R.

Die vier Modi

  1. LU 2×2: geschlossene Form.
  2. LU 3×3: mit expliziten Schritten.
  3. Ax=b 3×3 lösen: LU + Einsetzen.
  4. Determinante via LU: det(A) = u₁₁·u₂₂·u₃₃.

Doolittle-Algorithmus

Iterativ: berechnet Zeile k von U und Spalte k von L:

Ukj = Akj − Σ Lkp·Upj,    Lik = (Aik − Σ Lip·Upk) / Ukk

Kosten O(n³/3), genau wie Gauß-Elimination. n = 1000 → ~330 Mio. FLOP, < 0,1 s mit LAPACK.

Pivot-Problem

Ist ein Pivot Ukk null oder sehr klein, divergiert der Algorithmus. Partielles Pivotieren vertauscht die aktuelle Zeile mit derjenigen, die in der Spalte den betragsgrößten Eintrag hat: P·A = L·U. Der Rechner verwendet Doolittle ohne Pivotieren und erfordert nicht-null Hauptminoren.

Varianten

  • Cholesky: A symmetrisch positiv definit, A = L·LT. Halber Aufwand.
  • LDLT: symmetrisch, nicht positiv definit.
  • Band-LU: schwach besetzte Bandmatrizen der Breite w, Kosten O(n·w²). FEM.
  • ILU: Vorkonditionierer für GMRES, BiCGStab.

Vergleich

VerfahrenKostenStabilität
LU DoolittleO(n³/3)mittel
CholeskyO(n³/6)hoch
QRO(2n³/3)sehr hoch
SVDO(n³)maximal

Geschichte der LU-Zerlegung

Die LU-Zerlegung wurzelt in der Gauß-Elimination, dem seit Jahrhunderten bekannten Verfahren zum Lösen linearer Gleichungssysteme, das in impliziter Form bereits in der alten chinesischen Mathematik vorkam. Ihre moderne Formulierung als Matrixfaktorisierung A = L·U verdankt sich der Arbeit des 20. Jahrhunderts: 1948 gab Alan Turing im Kontext der ersten Rechner eine strenge Analyse und untersuchte ihre numerische Stabilität, während der Pole Tadeusz Banachiewicz in den 1930er Jahren eine verwandte Formulierung eingeführt hatte. Zu erkennen, dass die Gauß-Elimination der Zerlegung der Matrix in einen unteren Dreiecksfaktor L und einen oberen U entspricht, war ein entscheidender begrifflicher Schritt: er erlaubte, die aufwändige Faktorisierung, nur einmal ausgeführt, von der schnellen Lösung für verschiedene rechte Seiten zu trennen und ebnete den Weg zur modernen numerischen linearen Algebra.

Praktische Anwendungen der LU-Zerlegung

Die LU-Faktorisierung ist eines der Arbeitspferde des wissenschaftlichen Rechnens und der Technik. Sie bildet das Herz numerischer Standardbibliotheken wie LAPACK, die überall dort eingesetzt werden, wo große lineare Systeme gelöst werden: in der Finite-Elemente-Methode zur Strukturanalyse von Brücken und Gebäuden, in der Simulation elektrischer Schaltungen (SPICE), in der numerischen Strömungsmechanik, in der 3D-Grafik und in der Optimierung. Muss man Ax = b für viele verschiedene Vektoren b mit derselben Matrix A lösen, ist LU unschlagbar: A wird nur einmal faktorisiert, danach kostet jede Lösung nur O(n²) Operationen statt O(n³). Sie dient auch zur Berechnung der Determinante, der Inversen und zur Stabilitätsanalyse von Systemen.

Aktualisiert im Juli 2026

Häufig gestellte Fragen

Wann ist LU ohne Pivotieren möglich?

Eine Matrix erlaubt die LU-Faktorisierung ohne Zeilentausch, wenn alle ihre führenden Hauptminoren von null verschieden sind, das heißt wenn während der Gauß-Elimination kein Pivot null wird. Diagonaldominante und symmetrisch positiv definite Matrizen erfüllen diese Bedingung stets. Wird dagegen ein Pivot null, ist partielles Pivotieren nötig, also Zeilentausch, um ein von null verschiedenes Element in die Pivotposition zu bringen.

Doolittle vs. Crout?

Es sind zwei äquivalente Varianten der LU-Zerlegung, die sich nur darin unterscheiden, wo die Einheitsdiagonale steht. Bei der Doolittle-Methode hat die untere Dreiecksmatrix L eine Diagonale aus Einsen und die Diagonalelemente landen in U. Bei der Crout-Methode hat die obere Matrix U die Einheitsdiagonale und die Pivots gehen in L. Sie liefern dieselbe Faktorisierung bis auf eine Skalierung von Zeilen oder Spalten; dieser Rechner verwendet Doolittle.

Warum LU statt expliziter Invertierung?

Weil sie effizienter und numerisch stabiler ist. Um Ax = b zu lösen, muss man A nicht invertieren: man faktorisiert sie einmal in L·U (Aufwand O(n³)) und löst dann jedes System mit Vorwärts- und Rückwärtseinsetzen in O(n²). Die Inverse explizit zu berechnen kostet mehr, bringt zusätzliche Rundungsfehler und wird selten wirklich benötigt. Die praktische Regel: invertiere nie eine Matrix, wenn du sie faktorisieren kannst.

Was ist partielles Pivotieren?

Es ist die Strategie, während der Elimination Zeilen zu tauschen, um als Pivot das betragsgrößte Element der aktuellen Spalte zu wählen. Sie dient zwei Zwecken: die Division durch null zu vermeiden, wenn ein Pivot verschwindet, und Rundungsfehler zu verringern, indem durch große statt kleine Zahlen geteilt wird. Die resultierende Faktorisierung ist PA = LU, wobei P eine Permutationsmatrix ist, die die vorgenommenen Tausche festhält.

Wie berechne ich die Determinante per LU?

Die Determinante von A ist das Produkt der Diagonalelemente von U: det(A) = u₁₁·u₂₂·…·uₙₙ. Das liegt daran, dass det(A) = det(L)·det(U) ist und in der Doolittle-Variante L eine Einheitsdiagonale hat, also det(L) = 1. Mit Pivotieren muss man mit (−1) hoch der Anzahl der Zeilentausche multiplizieren. Es ist die Standardmethode, Determinanten effizient zu berechnen, in O(n³) statt O(n!).

Was passiert bei einer singulären Matrix?

Ist die Matrix singulär, hat also Determinante null, so wird während der Faktorisierung einer der Diagonalpivots von U null. Das System Ax = b hat dann keine eindeutige Lösung: es ist entweder unmöglich (keine Lösung) oder unbestimmt (unendlich viele Lösungen), je nach rechter Seite. Der Rechner erkennt den Nullpivot und meldet die Singularität, da die im Rückwärtseinsetzen erforderliche Division nicht möglich ist.

Funktioniert LU für nicht-quadratische Matrizen?

Die klassische LU-Zerlegung ist für quadratische Matrizen definiert. Für rechteckige Matrizen verwendet man andere Faktorisierungen: die QR-Zerlegung (in einen orthogonalen Faktor Q und einen dreieckigen R) für Ausgleichsprobleme oder die Singulärwertzerlegung (SVD) für die allgemeinere Analyse. Erweiterungen der LU auf rechteckige Matrizen existieren, doch in der Praxis bevorzugt man QR und SVD, die für diese Fälle stabiler sind.

Wer hat die LU-Zerlegung formalisiert?

Die Idee entstammt der seit Jahrhunderten bekannten Gauß-Elimination, doch die moderne Formulierung als Matrixfaktorisierung wurde im 20. Jahrhundert entwickelt. Alan Turing gab 1948 eine strenge Analyse der numerischen Stabilität im Hinblick auf die ersten Rechner, und Tadeusz Banachiewicz hatte in den 1930er Jahren eine verwandte Formulierung vorgeschlagen. Heute liegt sie den numerischen Standardbibliotheken wie LAPACK zugrunde.

Kommentare (0)

Noch keine Kommentare. Sei der Erste!