Gaußsches Eliminationsverfahren

Eigenschaften des Verfahrens

Genauigkeit

Damit die Berechnung von x ausreichend genau ist, darf zum einen die Kondition der Matrix nicht zu schlecht und die verwendete Maschinengenauigkeit nicht zu gering sein. Zum anderen benötigt man ein Lösungsverfahren, das ausreichend stabil ist. Ein guter Algorithmus zeichnet sich also durch eine hohe Stabilität aus.

Im Allgemeinen ist das Verfahren ohne Pivotisierung instabil. Daher wird meist Spaltenpivotisierung zur Lösung verwendet. Damit ist das Verfahren für die meisten Matrizen stabil durchführbar, wie insbesondere durch die Arbeiten von James H. Wilkinson nach dem Zweiten Weltkrieg klar wurde. Es lassen sich allerdings Matrizen angeben, für welche die Stabilitätskonstante exponentiell mit der Dimension der Matrix wächst. Mit vollständiger Pivotisierung lässt sich die Stabilität noch verbessern, allerdings steigt dann auch der Aufwand für die Pivotsuche auf O(n³ ), daher wird diese selten verwendet. Generell bessere Stabilität haben QR-Zerlegungen, die allerdings auch aufwändiger zu berechnen sind.

Bei strikt diagonaldominanten oder positiv definiten Matrizen (siehe auch Cholesky-Zerlegung) ist das Gauß-Verfahren stabil und ohne Pivotisierung durchführbar, es treten also keine Nullen auf der Diagonale auf.

Nachiteration

Ein praktischer Ansatz zum Ausgleich dieser Rechenungenauigkeiten besteht aus einer Nachiteration mittels Splitting-Verfahren, da über die LR-Zerlegung eine gute Näherung der Matrix A zur Verfügung steht, die leicht invertierbar ist. Dazu startet man mit der berechneten Lösung x₀ = x und berechnet in jedem Schritt das Residuum

r_k = b - Ax_k

Danach berechnet man unter Verwendung der LR-Zerlegung die Lösung z_k des Gleichungssystems

Az_k = r_k

und setzt

x_{k + 1} = x_k + z_k

Da es meistens nur um kleine Korrekturen geht, reichen oft wenige Iterationsschritte. Im Allgemeinen ist für die Berechnung des Residuums r_k allerdings eine höhere Genauigkeit notwendig. Reicht auch die Nachiteration nicht aus, um auf die gewünschte Genauigkeit zu kommen, bleibt nur die Wahl eines anderen Verfahrens oder eine Umformung des Problems, um eine günstigere Matrix zu erhalten, etwa eine mit kleinerer Kondition.

Die Nachiteration wird beispielsweise in der LAPACK-Routine DSGESV angewandt. In dieser Routine wird die LR-Zerlegung in einfacher Genauigkeit ermittelt und die doppelte Genauigkeit der Lösung durch Nachiteration mit doppeltgenau berechnetem Residuum erreicht.

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