Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


37. Gaußsches Eliminationsverfahren



Variationen und Erweiterungen

Das soeben beschriebene Verfahren ist am besten für NxN-Matrizen geeignet, bei denen die meisten der N2 Elemente von null verschieden sind. Wie wir bei anderen Problemen gesehen haben, sind für lichte Matrizen, bei denen die meisten Elemente den Wert null haben, spezielle Methoden zweckmäßig. Diese Situation entspricht einem Gleichungssystem, in dem jede Gleichung nur aus wenigen Gliedern besteht.

Wenn die von null verschiedenen Elemente keine spezielle Struktur haben, ist die in Kapitel 36 betrachtete Darstellung mit Hilfe einer verketteten Liste geeignet, mit einem Knoten für jedes von null verschiedene Element der Matrix, wobei die Knoten sowohl durch die Zeile als auch durch die Spalte miteinander verkettet sind. Das standardmäßige Verfahren kann für diese Darstellungsart implementiert werden, wobei die üblichen zusätzlichen Komplikationen auftreten, die sich aus der Notwendigkeit ergeben, von null verschiedene Elemente zu erzeugen und zu beseitigen. Die Anwendung dieses Verfahrens dürfte sich kaum lohnen, wenn man genügend Speicherplatz hat, um die gesamte Matrix zu speichern, da es wesentlich komplizierter ist als das standardmäßige Verfahren. Außerdem werden lichte Matrizen im Verlaufe des Prozesses der Gaußschen Elimination erheblich weniger licht.

Manche Matrizen enthalten nicht nur lediglich ein paar von null verschiedene Elemente, sondern haben außerdem eine einfache Struktur, so daß verkettete Listen nicht erforderlich sind. Das typische Beispiel dafür ist eine »Bandmatrix«, bei der die von null verschiedenen Elemente alle sehr nahe bei der Diagonale liegen. In solchen Fällen müssen die inneren Schleifen des Algorithmus der Gaußschen Elimination nur wenige Male durchlaufen werden, so daß die Gesamtlaufzeit (und der Speicherbedarf) proportional zu N ist, nicht zu N3.

Ein interessanter Spezialfall einer Bandmatrix ist eine «tridiagonale« Matrix, bei der nur Elemente direkt auf, direkt über oder direkt unter der Diagonale von null verschieden sind. Zum Beispiel ist die allgemeine Form einer tridiagonalen Matrix für N = 5:

Formel

Bei derartigen Matrizen reduziert sich sowohl die Vorwärts-Elimination als auch das Rückwärts-Einsetzen auf eine einfache for-Schleife:

    for i:=1 to N-1 do
      begin
      a[i+1,N+1]:=a[i+1,N+1]-a[i,N+1]*a[i+1,i]/a[i,i];
      a[i+1,i+1]:=a[i+1,i+1]-a[i,i+1]*a[i+1,i]/a[i,i]
      end;
    for j:=N downto 1 do
      x[j]:=(a[j,N+1]-a[j,j+1]*x[j+1])/a[j,j];

Bei der Vorwärts-Elimination muß nur der Fall j=i+1 und k=i+1 betrachtet werden, da für k > i + 1 a[i,k] = 0 gilt. (Der Fall k = i kann weggelassen werden, da hierbei ein Element des Feldes auf null gesetzt wird, das niemals wieder betrachtet wird; die gleiche Änderung könnte beim einfachen Gaußschen Eliminationsverfahren vorgenommen werden.)

Eigenschaft 37.2 Ein tridiagonales Gleichungssystem kann in linearer Zeit gelöst werden.

Natürlich würde man für eine tridiagonale Matrix kein zweidimensionales Feld der Größe N2 verwenden. Es läßt sich erreichen, daß der für das obige Programm benötigte Speicherplatz linear in N ist, indem man anstelle der Matrix a vier Felder verwendet: eins für jede der drei nicht aus Nullen bestehenden Diagonalen und eins für die (N+1)-te Spalte. Beachten Sie, daß dieses Programm nicht unbedingt das größte zur Verfügung stehende Element als Pivotelement benutzt, so daß nicht garantiert werden kann, daß eine Division durch null oder die Akkumulation von Fehlern aus der Berechnung ausgeschlossen ist. Für manche häufig auftretende Typen von tridiagonalen Matrizen kann jedoch bewiesen werden, daß dies kein Grund zur Besorgnis ist. w.z.b.w.

Das Gauß-Jordansche Reduktionsverfahren kann mit vollständigem Pivotieren so implementiert werden, daß eine Matrix in einem Durchlauf durch sie durch die zu ihr inverse Matrix ersetzt wird. Die zu einer Matrix A inverse Matrix, mit A-1 bezeichnet, hat die Eigenschaft, daß ein Gleichungssystem Ax = b gelöst werden kann, indem einfach mit dieser Matrix die Multiplikation x = A-1b ausgeführt wird. Nach wie vor sind N3 Operationen erforderlich, um x zu berechnen, wenn b gegeben ist. Es gibt jedoch eine Methode, wie eine Matrix »vorverarbeitet« und durch »Dekomposition« in Bestandteile zerlegt werden kann, wodurch es möglich wird, das entsprechende Gleichungssystem mit beliebiger gegebener rechter Seite in einer zu N2 proportionalen Zeit zu lösen, was gegenüber der Alternative, jedesmal das Gaußsche Eliminationsverfahren anzuwenden, die Einsparung eines Faktors N bedeutet. Grob gesagt ist es dazu erforderlich, sich an die Operationen zu erinnern, die während der Etappe der Vorwärts-Elimination mit der (N+1)-ten Spalte ausgeführt werden, so daß das Ergebnis der Vorwärts-Elimination für eine neue erste Spalte effizient berechnet und das Rückwärts-Einsetzen dann wie üblich vorgenommen werden kann.

Es ist gezeigt worden, daß die Lösung linearer Gleichungssysteme zur Multiplikation von Matrizen numerisch äquivalent ist, so daß Algorithmen existieren (zum Beispiel der Algorithmus zur Matrizen-Multiplikation von Strassen), mit denen Systeme von N Gleichungen mit N Variablen in einer zu N2,81... proportionalen Zeit gelöst werden können. Wie im Falle der Multiplikation von Matrizen lohnt sich die Anwendung einer solchen Methode (wenn überhaupt) nur dann, wenn regelmäßig sehr umfangreiche Gleichungssysteme zu verarbeiten sind. Wie zuvor ist die tatsächliche Laufzeit des Gaußschen Eliminationsverfahrens, ausgedrückt über die Anzahl der Eingabedaten, proportional zu N3/2, was sich in der Praxis schwer verbessern läßt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]