Gaußsches Eliminationsverfahren

Das Gaußsche Eliminationsverfahren ist ein Algorithmus aus den mathematischen Teilgebieten der linearen Algebra und der Numerik. Es ist ein wichtiges Verfahren zum Lösen von linearen Gleichungssystemen. Das Verfahren wurde um 1850 von Carl Friedrich Gauß bei Arbeiten auf dem Gebiet der linearen Gleichungssysteme entwickelt, allerdings hatte der chinesische Mathematiker Liu Hui bereits im Jahr 263 eine Beschreibung des Lösungsschemas veröffentlicht.

Erklärung

Ein lineares Gleichungssystem mit drei Variablen bzw. Unbekannten (x,y,z) und den jeweiligen Koeffizienten a,b,c,e hat die Form:
a1x+a2y+a3z=e1a_1x+a_2y+a_3z = e_1;
b1x+b2y+b3z=e2b_1x+b_2y+b_3z = e_2;
c1x+c2y+c3z=e3c_1x+c_2y+c_3z = e_3.
Der Algorithmus zur Berechnung der Variablen x, yx,\, y und zz lässt sich in zwei Etappen einteilen:
  1. Vorwärtselimination,
  2. Rückwärtseinsetzen (Rücksubstitution).
Im ersten Schritt wird das Gleichungssystem durch Äquivalenzumformungen, bei denen die Informationen des Gleichungssystems nicht geändert werden, in die Stufenform gebracht. Stufenform heißt, dass pro Zeile mindestens eine Variable weniger auftritt, also mindestens eine Variable eliminert wird, indem die Zeile so umgeformt wird, dass der Koeffizient der Variablen Null ist. Im obigen Beispiel würde man b1,c1b_1, c_1 und c2c_2 eliminieren, in der dritten Zeile ist dann nur noch die Variable zz. Zum Erreichen der Stufenform sind drei Umformungen zulässig: Es können (komplette) Zeilen vertauscht werden, eine Zeile kann mit einer von Null verschiedenen Zahl multipliziert werden oder es darf, wie beim Additionsverfahren, eine Zeile oder das Vielfache einer Zeile zu einer anderen Zeile addiert werden. Im zweiten Schritt werden ausgehend von der letzten Zeile, in der sich nur noch eine Variable befindet, die Variablen ausgerechnet und in die darüberliegende Zeile eingesetzt.
Ein lineares Gleichungssystem kann eine, mehrere oder keine Lösung haben. Diese Unterscheidung kann schon nach der Vorwärtselimination getroffen werden, indem die letzte Zeile betrachtet wird (siehe weiter unten).
Beispiel:
  1. xx + 2yy + 3zz = 2, hier: a1=1, a2=2, a3=3a_1 = 1,\, a_2 = 2,\, a_3 = 3 und e1=2e_1 = 2
  2. xx + yy + zz = 2
  3. 3xx + 3yy + zz = 0
Es werden schematisch nur die Koeffizienten (a, b, c, e)(a,\, b,\, c,\, e) geschrieben:
Gausselimlgs.PNG
Jetzt wird so umgeformt, dass b1b_1 und c1c_1 Null werden, indem man geeignete Vielfache der ersten Gleichung zur zweiten und dritten Gleichung addiert. Den Multiplikator, mit dem man die Zeile multiplizieren muss, erhält man, indem man die erste Zahl der Zeile, aus der das Element elimiert werden soll, durch die Zahl teilt, die sich in der Zeile darüber an der gleichen Position befindet (hier: 1/1=1, 3/1=3). Da das Element verschwinden soll, muss die Zahl noch mit (-1) multipliziert werden, so dass sie negativ wird.
Zu Zeile 2 wird das (-1)-fache und zu Zeile 3 das (-3)-fache von Zeile 1 addiert. Damit c2c_2 Null wird, wird ein Vielfaches von Zeile 2 zu Zeile 3 addiert, in diesem Fall das (-3)-fache:
Gausseliminierung.PNG
Falls die Zahl, durch die zur Berechnung des Multiplikators dividiert wird (hier für die ersten beiden Zeilen die Zahl 1, beim dritten Mal die Zahl (-1) ), Null ist, wird diese Zeile mit einer weiter unten liegenden vertauscht.
Am Ende kann durch Betrachten der letzten Zeile über die Lösbarkeit entschieden werden. Das Gleichungssystem ist:
  1. eindeutig lösbar, wenn kein Element der Diagonalen (hier: a1,b2,c3a_1, b_2, c_3) Null ist,
  2. nicht eindeutig oder unlösbar, wenn ein Element der Diagonalen Null ist
Befindet sich die einzige Null auf der Diagonalen in der letzten Zeile, ist das System unlösbar, wenn auf der rechten Seite (ex)(e_x) eine Zahl ungleich Null steht, da es sich dann um eine falsche (unerfüllbare) Aussage handelt (z. B. 0=1); hingegen hat das System unendlich viele Lösungen und ist nicht eindeutig lösbar, wenn dort eine Null steht, da es sich um eine wahre Aussage (0=0) handelt.
Weiter im Beispiel:
Die letzte Zeile bedeutet
−2z=−6-2z = -6 .
Diese Gleichung ist einfach lösbar und z=3z = 3.
Damit ergibt sich für die zweite Zeile
−1y−2z=0-1y-2z = 0, also y=−6y = -6
und weiter
x=5x = 5 .
Damit sind alle "Variablen" (x, y, z)(x,\, y,\, z) berechnet:
x=5y=−6z=3x = 5 \quad y = -6 \quad z = 3 .
Wird im ersten Schritt die Matrix weiter umgeformt, bis die Lösung direkt abgelesen werden kann, nennt man das Verfahren Gauß-Jordan-Algorithmus.

Kontrolle durch Zeilensumme

Die Umformungen können durch das Berechnen der Zeilensumme kontrolliert werden.
Gausselimzeilensum.PNG
Hier wurde in der letzten Spalte die Summe aller Elemente der jeweiligen Zeile addiert. Für die erste Zeile ist die Zeilensumme 1+2+3+2 = 8. Da an der ersten Zeile keine Umformungen durchgeführt werden ändert sich ihre Zeilensumme nicht. Bei der ersten Umformung dieses Gleichungssystems wird zur zweiten Zeile das (-1)-fache der ersten addiert. Macht man das auch für die Zeilensumme dann gilt 5 + (-1)*8 = -3. Dieses Ergebnis ist die Zeilensumme der umgeformten zweiten Zeile -1 - 2 + 0 = -3. Zur Überprüfung der Rechnungen kann man also die Umformungen an der Zeilensumme durchführen, sind alle Rechnungen korrekt, muss sich die Zeilensumme der umgeformten Zeile ergeben.

System mit unendlich vielen Lösungen

(I) x + 4y = 8
(II) 3x + 12y = 24
Da die Gleichung (II) ein vielfaches der Gleichung (I) ist, hat das Gleichungssystem unendlich viele Lösungen. Bei der Elimination von x in Gleichung (II) verschwindet diese vollständig, übrig bleibt die Gleichung (I). Löst man diese nach x auf kann man die Lösungsmenge in Abhängigkeit von y angeben:
x = 8 - 4y
L={8 - 4y|y}

Pivotisierung

Der gaußsche Algorithmus ist im Allgemeinen nicht ohne Zeilenvertauschungen durchführbar. Es ist zumindest notwendig, dass an der entsprechenden Stelle keine Null steht. Dieses zum Erzeugen der Nullen in diesem Schritt genutzte Element der Matrix wird Pivot genannt. Um das zu illustrieren, wurden die Pivots des obigen Beispiels markiert. Zeilenvertauschungen waren hier nicht nötig.
Gausseliminierung_Pivotisierung.PNG
Für die Rechnung per Hand ist es sicher sinnvoll, eine 1 oder minus 1 als Pivot zu wählen. Um einen möglichst stabilen Algorithmus zu erhalten, wählt man das betragsgrößte Element als Pivot. Wählt man das Pivot in der aktuellen Spalte, spricht man von Spaltenpivotisierung (analog Zeilenpivotisierung).

Literatur

 
 

Die Mathematik als Fachgebiet ist so ernst, daß man keine Gelegenheit versäumen sollte, dieses Fachgebiet unterhaltsamer zu gestalten.

Blaise Pascal

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Gaußsches Eliminationsverfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Lineare Algebra