Inhalt

Grundlagen der Mathematik

Diskrete Mathematik

Algebra

Lineare Algebra

Vektorräume

Matrizen

Lineare Gleichungssysteme

Lösbarkeitskriterien

Lösungsmenge

Gaußsches

Eliminationsverfahren

Determinanten

Eigenwerte

Geometrie

Analysis

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

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:

a₁ x + a₂ y + a₃ z = e₁ ;

b₁ x + b₂ y + b₃ z = e₂ ;

c₁ x + c₂ y + c₃ z = e₃ .

Der Algorithmus zur Berechnung der Variablen x, y und z lässt sich in zwei Etappen einteilen:

Vorwärtselimination,
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 b₁ , c₁ und c₂ eliminieren, in der dritten Zeile ist dann nur noch die Variable z. 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:

x + 2y + 3z = 2, hier: a₁ = 1, a₂ = 2, a₃ = 3 und e₁ = 2
x + y + z = 2
3x + 3y + z = 0

Es werden schematisch nur die Koeffizienten (a, b, c, e) geschrieben:

Jetzt wird so umgeformt, dass b₁ und c₁ 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 c₂ Null wird, wird ein Vielfaches von Zeile 2 zu Zeile 3 addiert, in diesem Fall das (-3)-fache:

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:

eindeutig lösbar, wenn kein Element der Diagonalen (hier: a₁ , b₂ , c₃ ) Null ist,
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 (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 .

Diese Gleichung ist einfach lösbar und z = 3.

Damit ergibt sich für die zweite Zeile

-1y - 2z = 0, also y = - 6

und weiter

x = 5 .

Damit sind alle "Variablen" (x, y, z) berechnet:

x = 5 y = - 6 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.

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.

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

A. Meister: Numerik linearer Gleichungssysteme, 2. Auflage, Vieweg 2005, ISBN 3528131357
A. Kielbasinski und H. Schwetlick: Numerische lineare Algebra Deutscher Verlag der Wissenschaften 1988 ISBN 3-326-00194-0

Die Mathematik muß man schon deswegen studieren, weil sie die Gedanken ordnet.

M. W. Lomonossow

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: