Lineare Gleichungssysteme
Gauss-Elimination
Bringe die Matrix [A|b] in obere Dreiecksform durch Zeilenoperationen, dann Rückwärtseinsetzen.
Aufwand: O(n³/3) Multiplikationen. Für n = 1000 sind das ca. 333 Millionen — heute in Millisekunden.
LR-Zerlegung
Statt Gauss bei jedem neuen b zu wiederholen, zerlege A = L·R einmal. Dann lösen sich Ly = b und Rx = y in O(n²).
| Schritt | Aufwand |
|---|---|
| Zerlegung A = L·R | O(n³/3) |
| Vorwärtseinsetzen Ly = b | O(n²/2) |
| Rückwärtseinsetzen Rx = y | O(n²/2) |
| k mal Lösen mit verschiedenen b | O(n³ + k·n²) statt k·O(n³) |
Pivotisierung
Bei kleinen Diagonalelementen droht Auslöschung. Spaltenpivot: Vor jedem Eliminationsschritt das betragsgrößte Element der Spalte als Pivot wählen. Verhindert numerische Katastrophen.
Iterativ vs. direktDirekte Verfahren (Gauss) für mittelgroße dichte Matrizen. Iterative (Jacobi, Gauss-Seidel, CG) für riesige dünn besetzte Matrizen — sonst frisst der Speicher alles.