Gaußsches Eliminationsverfahren

Erklärung

Ein lineares Gleichungssystem Ax = b mit drei Gleichungen und drei Unbekannten x = (x₁ , x₂ , x₃ )^T und rechter Seite b = (b₁ , b₂ , b₃ )^T hat die Form:

Der Algorithmus zur Berechnung der Variablen x₁ , x₂ und x₃ lässt sich in zwei Etappen einteilen:

1. Vorwärtselimination,
2. Rückwärtseinsetzen (Rücksubstitution).

Im ersten Schritt wird das Gleichungssystem auf Stufenform gebracht. Stufenform heißt, dass pro Zeile mindestens eine Variable weniger auftritt, also mindestens eine Variable eliminiert wird. Im obigen Gleichungssystem würde man a₂₁ , a₃₁ und a₃₂ eliminieren, in der dritten Zeile ist dann nur noch die Variable x₃ :

Zum Erreichen der Stufenform werden elementare Zeilenumformungen benutzt, mit Hilfe derer das Gleichungssystem in ein neues transformiert wird, welches aber dieselbe Lösungsmenge besitzt. Ausreichend sind zwei Arten von elementaren Zeilenumformungen:

1. Eine Zeile oder das Vielfache einer Zeile zu einer anderen Zeile dazu addieren.
2. Vertauschung von zwei Zeilen.

Das Verfahren besteht dann darin, angefangen in der ersten Spalte mit Umformungen der ersten Art durch geschicktes Dazuaddieren der ersten Zeile alle Einträge bis auf den ersten zu Null zu machen. Dies wird dann in der so modifizierten zweiten Spalte fortgesetzt, wobei diesmal Vielfache der zweiten Zeile zu den folgenden Zeilen addiert werden und so weiter. Dieser Schritt funktioniert nur, wenn das Diagonalelement der aktuellen Spalte nicht Null ist. In so einem Fall ist die zweite Art der Zeilenumformung nötig, da durch eine Zeilenvertauschung ein Nichtnulleintrag auf der Diagonale erzeugt werden kann. Mit Hilfe dieser beiden Arten von Umformungen ist es möglich, jedes lineare Gleichungssystem auf Stufenform zu bringen.

right

Eine weitere Art der elementaren Zeilenumformung ist das Vertauschen von Spalten. Diese wird zur Durchführung des Algorithmus nicht benötigt, aber manchmal in Computerprogrammen aus Stabilitätsgründen eingesetzt. Dabei wird die Position der Variablen im Gleichungssystem geändert. Beim Rechnen per Kopf ist manchmal noch die Multiplikation einer Zeile mit einer Zahl nützlich, etwa um komplizierte Brüche zu vermeiden. Dies verursacht zusätzlichen Rechenaufwand und ist deswegen in Computerprogrammen keine Option und ändert ferner die Determinante der Koeffizientenmatrix, was theoretische Nachteile mit sich bringt.

Im zweiten Schritt des Verfahrens, dem Rückwärtseinsetzen, werden ausgehend von der letzten Zeile, in der nur noch eine Variable auftaucht, die Variablen ausgerechnet und in die darüberliegende Zeile eingesetzt.

Eine Alternative hierzu ist der Gauß-Jordan-Algorithmus, bei dem nicht nur die unteren Teile eliminiert werden, sondern auch die oberen, so dass eine Diagonalform entsteht, bei der dann der oben genannte zweite Schritt entfällt.

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