Gaußsches Eliminationsverfahren

Eigenschaften des Verfahrens

Rechenaufwand und Speicherplatzbedarf

Die Anzahl arithmetischer Operationen für die LR-Zerlegung ist bei einer -Matrix ca. . Der Aufwand für das Vorwärts- und Rückwärtseinsetzen ist quadratisch (O(n² )) und daher insgesamt vernachlässigbar. Da der Aufwand kubisch mit der Dimension der Matrix wächst, kann man jedoch anhand der Rechenzeit für eine Matrix die Rechenzeit für eine andere Matrix abschätzen. Benötigt der Algorithmus also auf einem bestimmten Rechner für eine Matrix der Dimension n = 1000 etwa 10 Sekunden, so benötigt er für eine Matrix der Dimension auf demselben Rechner ungefähr Sekunden also ca. 3 Stunden. Damit ist das gaußsche Eliminationsverfahren ein schnelles direktes Verfahren zur Lösung linearer Gleichungssysteme, für eine QR-Zerlegung benötigt man mindestens doppelt so viele Rechenoperationen. Dennoch sollte der Algorithmus nur für Gleichungssysteme kleiner bis mittlerer Dimension verwendet werden (bis etwa n = 10000). Für Matrizen höherer Dimension steigt die Rechenzeit jedoch schnell an und iterative Verfahren sind oft besser. Diese nähern die Lösung schrittweise an und benötigen in jedem Schritt für eine vollbesetzte Matrix O(n² ) Rechenoperationen. Die Konvergenzgeschwindigkeit solcher Verfahren hängt jedoch stark von den Eigenschaften der Matrix ab und man kann die konkret benötigte Rechenzeit nur schwer vorhersagen.

Die Rechnung kann auf dem Speicher der Matrix A durchgeführt werden, so dass außer der Speicherung von A selbst kein zusätzlicher Speicherbedarf entsteht. Für eine vollbesetzte Matrix der Dimension n = 1000 müsste man eine Million Koeffizienten abspeichern. Dies entspricht im IEEE 754-Format double in etwa 8 Megabyte. Bei iterativen Verfahren, die mit Matrix-Vektor-Multiplikationen arbeiten, kann allerdings eine explizite Speicherung von A selbst nicht nötig sein, so dass diese Verfahren ggf. vorzuziehen sind.

Für Spezialfälle lassen sich Aufwand und Speicherplatz deutlich reduzieren, indem spezielle Eigenschaften der Matrix und ihrer LR-Zerlegung ausgenutzt werden können. So benötigt die Cholesky-Zerlegung für symmetrische positiv definite Matrizen nur die Hälfte an Rechenoperationen und Speicher. Ein anderes Beispiel sind Bandmatrizen mit fester Bandbreite m, da hier die LR-Zerlegung die Bandstruktur erhält und sich so der Aufwand auf O(nm² ) reduziert. Für wenige spezielle dünnbesetzte Matrizen ist es möglich, die Besetzungsstruktur auszunutzen, so dass die LR-Zerlegung ebenfalls dünnbesetzt bleibt. Beides geht einher mit einem verringerten Speicherbedarf.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Gaußsches Eliminationsverfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung