Robert Sedgewick: Algorithmen

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


37. Gaußsches Eliminationsverfahren



Ein einfaches Beispiel

Nehmen wir an, daß drei Variablen x, y und z und die folgenden drei Gleichungen vorliegen:

x + 3y - 4z = 8,
x + y - 2z = 2,
-x - 2y + 5z = -1.

Unser Ziel ist es, diejenigen Werte der Variablen zu berechnen, die gleichzeitig allen Gleichungen genügen. In Abhängigkeit von den Gleichungen ist es möglich, daß dieses Problem keine Lösung hat (wenn sich beispielsweise zwei der Gleichungen widersprechen, wie etwa x + y = 1, x + y = 2), oder daß viele Lösungen existieren (zum Beispiel wenn zwei Gleichungen übereinstimmen oder wenn mehr Variablen als Gleichungen vorhanden sind). Wir wollen voraussetzen, daß die Anzahl der Gleichungen und der Variablen gleich ist, und einen Algorithmus betrachten, der eine eindeutige Lösung findet, falls eine existiert.

Um die Verallgemeinerung der Formeln auf den Fall von mehr als nur drei Variablen zu erleichtern, benennen wir zunächst die Variablen um, indem wir Indizes benutzen:

x1 + 3x2 - 4x3 = 8,
x1 + x2 - 2x3 = 2,
-x1 - 2x2 + 5x3 = -1.

Um ein wiederholtes Schreiben der Variablen zu vermeiden, ist es zweckmäßig, eine Matrixschreibweise zu verwenden, um das Gleichungssystem auszudrücken. Die obigen Gleichungen entsprechen exakt der folgenden Matrixgleichung:

Formel

Es gibt verschiedene Operationen, die mit solchen Gleichungen ausgeführt werden können, ohne daß sie die Lösung ändern:

Es erfordert einiges Nachdenken, um sich klarzumachen, daß diese Operationen, insbesondere die letztgenannte, die Lösung nicht beeinflussen. Zum Beispiel erhalten wir ein zu dem obigen äquivalentes Gleichungssystem, indem wir die zweite Gleichung durch die Differenz der ersten beiden Gleichungen ersetzen:

Formel

Beachten Sie, daß dadurch x1 aus der zweiten Gleichung eliminiert wird. In ähnlicher Weise können wir x1 aus der dritten Gleichung eliminieren, indem wir diese Gleichung durch die Summe der ersten und der dritten Gleichung ersetzen:

Formel

Nunmehr ist die Variable x1 aus allen Gleichungen außer der ersten eliminiert worden. Indem wir systematisch in dieser Weise vorgehen, können wir das ursprüngliche Gleichungssystem in ein System mit der gleichen Lösung umwandeln, das sich wesentlich leichter lösen läßt. In unserem Beispiel ist dafür nur noch ein weiterer Schritt erforderlich, der zwei der obigen Operationen kombiniert: das Ersetzen der dritten Gleichung durch die Differenz der zweiten Gleichung und der mit 2 multiplizierten dritten Gleichung. Dadurch wird erreicht, daß alle Elemente unterhalb der Hauptdiagonale zu null werden, und Gleichungssysteme dieser Form lassen sich besonders leicht lösen. Die gleichzeitig zu erfüllenden Gleichungen, die sich in unserem Beispiel ergeben, lauten:

x1 + 3x2 - 4x3 = 8,
2x2 - 2x3
= 6,
-4x3
= -8.

Die dritte Gleichung kann nun sofort gelöst werden: x3 = 2. Wenn wir diesen Wert in die zweite Gleichung einsetzen, können wir den Wert von x2 berechnen:

2x2 - 4 = 6,
x2 = 5.

In ähnlicher Weise gibt das Einsetzen dieser beiden Werte in die erste Gleichung die Möglichkeit, den Wert von x1 zu berechnen:

x1 + 15 - 8 = 8,
x1 = 1,

womit die Lösung des Gleichungssystems vollständig ist.

Dieses Beispiel veranschaulicht die beiden Hauptetappen des Gaußschen Eliminationsverfahrens. Die erste ist die Etappe der Vorwärts-Elimination, während der das ursprüngliche System durch systematische Elimination von Variablen aus Gleichungen in ein System umgewandelt wird, das unterhalb der Hauptdiagonale nur Nullen aufweist. Dieser Prozeß wird manchmal Triangulation genannt. Die zweite Etappe ist die Etappe des Rückwärts-Einsetzens, während der unter Benutzung der während der ersten Etappe erzeugten Dreiecksmatrix die Werte der Variablen berechnet werden.


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