## 4.1. Das Gauß'sche Eliminationsverfahren

Im Mathematikunterricht lernten wir, lineare Gleichungssysteme mit mehreren Unbekannten zu lösen. Allerdings beschränkten wir uns auf sogenannte 2x2-Systeme, d.h. Systeme mit zwei Gleichungen und zwei Unbekannten.

Solche Systeme konnten entweder keine, eine oder unendlich viele Lösungen haben. Der Einfachheit halber wollen wir uns im Folgenden mit den eindeutig lösbaren Systemen beschäftigen.

Wir haben bisher zwei Lösungsverfahren kennen gelernt: Das Einsetzverfahren und das Additionsverfahren.

Das Einsetzverfahren ist vielleicht leichter zu verstehen, aber leider ungeeignet, um lineare Gleichungsysteme mit mehr als 2 Gleichungen und 2 Unbekannten zu lösen. Die nötigen Rechnungen werden im Allgemeinen zu aufwendig. Deshalb wollen wir uns im Folgenden auf das Additionsverfahren konzentrieren.

Beim Additionsverfahren werden die einzelnen Unbekannten der Reihe nach eliminiert, bis nur noch eine übrig ist. Man nennt es deswegen auch das Eliminationsverfahren.

#### Beispiel: Lösung eines 3x3-Systems mit dem Additionsverfahren

Um die ersten Summanden in den Zeilen II und III zu eliminieren, müssen wir Additionen mit geeigneten Vorfaktoren durchführen:

Die Additionen und bringen uns ans Ziel.

Wir finden die gesuchten Vorfaktoren, indem wir jeweils den Koeffizienten von x1 der II. bzw. III. Gleichung durch den Koeffizienten von der I. Gleichung dividieren und mit einem Minuszeichen versehen.

Bemerkung: In unserem Beispiel ist glücklicherweise der erste Koeffizient der ersten Gleichung von Null verschieden, da sonst die geforderte Division nicht möglich wäre. Wir müssten die Gleichungen solange umsortieren, bis wir eine geeignete gefunden haben. Die Suche nach einem solchen von Null verschiedenen Koeffizienten heißt Pivotsuche, der Koeffizient selbst Pivotelement. Da wir nur eindeutig lösbare Systeme betrachten, können wir davon ausgehen, dass mindestens eine der drei Gleichungen die Bedingung erfüllt.

Um die Unbekannte bestimmen zu können, müssen wir noch die Variable in III' eliminieren.

Dies geschieht mit der Addition :

Damit hat unser Gleichungssystem eine besondere Form erhalten, die man obere Dreiecksform nennt. Aus ihr lässt sich die Lösung des Systems leicht berechnen:

Aus Zeile III" läßt sich sofort ablesen. Setzen wir den gefundenen Wert in II' ein, so erhalten wir . Mit den so gefundenen Werten und der Gleichung I lässt sich auch schnell berechnen.

Das Ziel eines Lösungsalgorithmus muss es also sein, durch fortgesetzte Addition der einzelnen Zeilen mit geeigneten Vorfaktoren das Gleichungssystem in die Dreiecksform überzuführen. Dabei muss aber immer darauf geachtet werden, dass die Koeffizienten, die zur Berechnung der Vorfaktoren herangezogen werden, von Null verschieden sind, sonst muss eine Pivotsuche durchgeführt werden. Der beschriebene Algorithmus ist nach dem berühmten Mathematiker Carl Friedrich Gauß benannt. | Carl Friedrich Gauß (1777 - 1855)

Die Umsetzung in ein PASCAL-Programm führen wir zunächst für ein 3x3-System durch. Dieses Programm lässt sich dann leicht auf n x n - Systeme verallgemeinern.

Außerdem gehen wir davon aus, dass eine Pivotsuche nicht nötig ist, sondern dass alle nötigen Koeffizienten immer von Null verschieden sind. Dies ist eine sehr starke und nicht haltbare Einschränkung, hilft uns jedoch sehr bei der Erstellung eines ersten Programms, da es den Algorithmus stark vereinfacht.

Musterlösung (einfache Version):

> `1: program Gauss_Algorithmus; { Einfache Version }
> 2: uses CRT;
> 3: const
> 4: Rang=3;
> 5: var
> 6: Koeff: array[1..Rang,1..Rang] of Real;
> 7: Erg: array[1..Rang] of Real;
> 8: x,y:Integer;
> 9: Faktor:Real;
> 10:
> 11: procedure Koeffizienteneingabe;
> 12: var
> 13: i,j:Integer;
> 14: begin
> 15: ClrScr;
> 16: for i:=1 to rang do
> 17: begin
> 18: Writeln('Zeilenweise Koeffizienteneingabe');
> 19: for j:=1 to rang do
> 20: begin
> 21: Write('a(',i,',',j,'): ');
> 22: Readln(koeff[i,j]);
> 23: end;
> 24: Writeln('Ergebniseingabe: ');
> 25: Write('b(',i,'): ');
> 26: Readln(Erg[i]);
> 27: end;
> 28: end;
> 29:
> 30: procedure Koeffizientenausgabe;
> 31: var
> 32: i,j:Integer;
> 33: begin
> 34: Writeln;
> 35: Writeln('Koeffizientenausgabe');
> 36: Writeln;
> 37: for i:=1 to rang do
> 38: begin
> 39: for j:=1 to rang do
> 40: begin
> 41: if koeff[i,j]<>0 then
> 42: Write(koeff[i,j]:8:4,' ':6)
> 43: else
> 44: Write(' ':8,' ':6);
> 45: end;
> 46: Write('=>');
> 47: Writeln(Erg[i]:8:4);
> 48: end;
> 49: Writeln;
> 50: end;
> 51:
> 52: procedure Zeilenaddition(Nr1,Nr2:integer;Faktor:Real);
> 53: var
> 54: i:Integer;
> 55: begin
> 56: for i:=1 to rang do
> 57: Koeff[Nr2,i]:=Koeff[Nr2,i]+Faktor*Koeff[Nr1,i];
> 58: Erg[Nr2]:=Erg[Nr2]+Faktor*Erg[Nr1];
> 59: end;
> 60:
> 61: begin
> 62: KoeffizientenEingabe;
> 63: for x:=1 to rang-1 do { Elimination aller Variablen bis auf }
> 64: begin { die letzte }
> 65: for y:=x+1 to rang do
> 66: begin { Elimination der x-ten Variable in }
> 67: { allen verbleibenden Zeilen }
> 68: Faktor:=-Koeff[y,x]/Koeff[x,x];
> 69: Zeilenaddition(x,y,Faktor);
> 70: end;
> 71: Koeffizientenausgabe;
> 72: if x=Rang-1 then
> 73: Write('Gauß-Algorithmus beendet, Dreiecksform erreicht!')
> 74: else
> 75: Write('Return...');
> 76: Readln;
> 77: end;
> 78: end.`

Für das Beispiel, anhand dessen wir den Algorithmus entwickelten, ergibt sich nach Eingabe der Koeffizienten folgender Programmablauf:

`Koeffizientenausgabe` `6.0000 2.0000 -1.0000 => 9.0000` `-2.0000 5.0000 => 7.0000` `1.0000 4.5000 => 3.5000` `Return...` `Koeffizientenausgabe` `6.0000 2.0000 -1.0000 => 9.0000` `-2.0000 5.0000 => 7.0000` `7.0000 => 7.0000` `Gauß-Algorithmus beendet, Dreiecksform erreicht!` ``

Gehen wir nun aber davon aus, dass nicht alle 3x3-Systeme so gebaut sind, dass bei ihrer schrittweisen Lösung niemals ein benötigter Koeffizient den Wert 0 annimmt, so müssen die Gleichungen so lange umsortiert werden, bis wir eine geeignete gefunden haben, bei der der entsprechende Koeffizient von Null verschieden ist.

Dieser Koeffizient selbst heißt Pivotelement, die Suche wird als Pivotsuche bezeichnet. Da wir nur eindeutig lösbare Systeme betrachten, können wir davon ausgehen, dass mindestens eine der drei Gleichungen die Bedingung erfüllt.

Erhalten wir also bei der Durchführung des Gauß’schen Algorithmus einen Koeffizienten mit dem Wert Null, so vertauschen wir einfach die entsprechende Zeile mit einer anderen, in der der Koeffizient ungleich Null ist.

Um dies in unserem Programm berücksichtigen zu können, ergänzen wir es um eine Prozedur Pivotsuche, die das Gleichungssystem für eine bestimmte Spalte nach Koeffizienten ungleich Null durchsucht und dann gegebenenfalls die entsprechenden Zeilen vertauscht.

Die entsprechende Prozedur lautet:

> `procedure Pivotsuche(Spalte:Integer);
> var
> i:Integer;
> begin
> i:=Spalte;
> while Koeff[i,Spalte]=0 do
> begin
> i:=i+1;
> if i>Rang then
> begin
> Writeln;
> Writeln('Das ',Rang,'x',Rang,'-System ist nicht eindeutig lösbar!');
> Readln;
> halt(1); { Programmabbruch }
> end;
> end;
> Zeilentausch(i,Spalte);
> end;`

Bemerkung:
Beschränkt man sich auf eindeutig lösbare Gleichungssysteme, so ist die Abfrage if i>Rang then ... nicht nötig. Sie wurde lediglich der Sicherheit halber eingefügt.

Musterlösung (erweiterte Version mit Pivotsuche):

> `1: program Gauss_Algorithmus; { erweiterte Version }
> 2: uses CRT;
> 3: const
> 4: Rang=3;
> 5: var
> 6: Koeff: array[1..Rang,1..Rang] of Real;
> 7: Erg: array[1..Rang] of Real;
> 8: x,y:Integer;
> 9: Faktor:Real;
> 10:
> 11: procedure Koeffizienteneingabe;
> 12: var
> 13: i,j:Integer;
> 14: begin
> 15: ClrScr;
> 16: for i:=1 to rang do
> 17: begin
> 18: Writeln('Koeffizienteneingabe');
> 19: for j:=1 to rang do
> 20: begin
> 21: Write('a(',i,',',j,'): ');
> 22: Readln(koeff[i,j]);
> 23: end;
> 24: Writeln('Ergebniseingabe: ');
> 25: Write('b(',i,'): ');
> 26: Readln(Erg[i]);
> 27: end;
> 28: end;
> 29:
> 30: procedure Koeffizientenausgabe;
> 31: var
> 32: i,j:Integer;
> 33: begin
> 34: Writeln;
> 35: Writeln('Koeffizientenausgabe');
> 36: Writeln;
> 37: for i:=1 to rang do
> 38: begin
> 39: for j:=1 to rang do
> 40: begin
> 41: if koeff[i,j]<>0 then
> 42: Write(koeff[i,j]:8:4,' ':6)
> 43: else
> 44: Write(' ':8,' ':6);
> 45: end;
> 46: Write('=>');
> 47: Writeln(Erg[i]:8:4);
> 48: end;
> 49: Writeln;
> 50: end;
> 51:
> 52: procedure Zeilentausch(Nr1,Nr2:Integer);
> 53: var
> 54: i:Integer;
> 55: h:real;
> 56: begin
> 57: if Nr1<>Nr2 then
> 58: begin
> 59: for i:=1 to Rang do
> 60: begin
> 61: h:=Koeff[Nr2,i];
> 62: Koeff[Nr2,i]:=Koeff[Nr1,i];
> 63: Koeff[Nr1,i]:=h;
> 64: end;
> 65: h:=Erg[Nr2];
> 66: Erg[Nr2]:=Erg[Nr1];
> 67: Erg[Nr1]:=h;
> 68: end;
> 69: end;
> 70:
> 71: procedure Pivotsuche(Spalte:Integer);
> 72: var
> 73: i:Integer;
> 74: begin
> 75: i:=Spalte;
> 76: while Koeff[i,Spalte]=0 do
> 77: begin
> 78: i:=i+1;
> 79: if i>Rang then
> 80: begin
> 81: Writeln;
> 82: Writeln('Das ',Rang,'x',Rang,'-System ist nicht eindeutig lösbar!');
> 83: Readln;
> 84: halt(1); { Programmabbruch }
> 85: end;
> 86: end;
> 87: Zeilentausch(i,Spalte);
> 88: end;
> 89:
> 90: procedure Zeilenaddition(Nr1,Nr2:integer; Faktor:Real);
> 91: var
> 92: i:Integer;
> 93: begin
> 94: for i:=1 to Rang do
> 95: begin
> 96: Koeff[Nr2,i]:=Koeff[Nr2,i]+Faktor*Koeff[Nr1,i];
> 97: end;
> 98: Erg[Nr2]:=Erg[Nr2]+Faktor*Erg[Nr1];
> 99: end;
> 100:
> 101: begin
> 102: KoeffizientenEingabe;
> 103: for x:=1 to Rang-1 do
> 104: begin
> 105: Pivotsuche(x);
> 106: for y:=x+1 to Rang do
> 107: begin
> 108: Faktor:=-Koeff[y,x]/Koeff[x,x];
> 109: Zeilenaddition(x,y,Faktor);
> 110: end;
> 111: KoeffizientenAusgabe;
> 112: if x=Rang-1 then
> 113: Writeln('Gauß-Algorithmus beendet, Dreiecksform erreicht!')
> 114: else
> 115: Writeln('Return drücken...');
> 116: Readln;
> 117: end;
> 118: end.`

Das Beispiel

macht eine Pivotsuche erforderlich. Schon beim ersten Schritt müsste durch den Koeffizienten der ersten Gleichung dividiert werden. In der vorliegenden Form ist dieser gleich Null und würde somit zu einem Programmabsturz führen. Abhilfe schafft z.B. das Vertauschen der Zeilen I und II.

Die erweiterte Version unseres Programmes führt dazu eine Pivotsuche und eine Zeilenvertauschung durch und löst das Gleichungssystem. Die einfache Version kann diese Beispiel nicht lösen (Ausprobieren!).

Programmablauf nach Eingabe der Koeffizienten:

`Koeffizientenausgabe` `1.0000 1.0000 => 1.0000` `2.0000 1.0000 => 2.0000` `9.0000 5.0000 => 8.0000` `Return drücken...` `Koeffizientenausgabe` `1.0000 1.0000 => 1.0000` `2.0000 1.0000 => 2.0000` `0.5000 => -1.0000` `Gauß-Algorithmus beendet, Dreiecksform erreicht!` ``

Erweiterung:

Soll das Programm nicht nur die Dreiecksform des Gleichungssystems anzeigen, sondern auch die Lösung selbst produzieren, so kann die folgende Prozedur verwendet werden. Sie muss mittels Loesesystem; aufgerufen werden. Der Aufruf erfolgt als letzte Anweisung vor dem alles beendenden end. Die Prozedur kann in beiden Programmen verwendet werden.

Musterlösung:

> `1': procedure LoeseSystem;
> 2': var
> 3': Lsg:array[1..Rang] of Real;
> 4': i,j:Integer;
> 5': begin
> 6': for i:=Rang downto 1 do
> 7': begin
> 8': lsg[i]:=erg[i];
> 9': for j:=i+1 to rang do
> 10': lsg[i]:=lsg[i]-Koeff[i,j]*lsg[j];
> 11': lsg[i]:=lsg[i]/Koeff[i,i];
> 12': end;
> 13': Writeln('Lösung des Systems: ');
> 14': Writeln;
> 15': for i:=1 to rang do
> 16': Writeln('x[',i,'] = ',lsg[i]:12:6);
> 17': end;`

Als weiteres Beispiel lösen wir nun ein 4x4-System. In beiden Musterprogrammen wurde die Größe des Systems lediglich durch die Konstante Rang festgelegt. Dies kommt uns nun beim Programmieren zugute. Ohne großen Aufwand erhalten wir ein Programm zur Lösung eines 4x4-Systems, indem wir lediglich die Konstante Rang auf den Wert 4 setzen. Rang kann beliebig erhöht werden und ist nur durch die Kapazität des verwendeten Rechners beschränkt.

Beispiel:

Nach Eingabe der Koeffizienten zeigt das so erweiterte Programm nicht nur das transformierte Gleichungssystem, sondern auch die tatsächliche Lösung an:

> > > `Koeffizientenausgabe` `-> 1.0000 -> 2.0000 -> 4.0000 -> -3.0000 => 43.0000` `-> -> 4.0000 -> -9.0000 -> 11.0000 => -54.0000` `-> -> -> -14.0000 -> 4.0000 => -102.0000` `-> -> 19.0000 -> 30.0000 -> -21.0000 => 326.0000` `Koeffizientenausgabe` `-> 1.0000 -> 2.0000 -> 4.0000 -> -3.0000 => 43.0000` `-> -> 4.0000 -> -9.0000 -> 11.0000 => -54.0000` `-> -> -> -14.0000 -> 4.0000 => -102.0000` `-> -> -> 72.7500 -> -73.2500 => 582.5000` `Koeffizientenausgabe` `-> 1.0000 -> 2.0000 -> 4.0000 -> -3.0000 => 43.0000` `-> -> 4.0000 -> -9.0000 -> 11.0000 => -54.0000` `-> -> -> -14.0000 -> 4.0000 => -102.0000` `-> -> -> -> -52.4643 => 52.4643` `Gauß-Algorithmus beendet, Dreiecksform erreicht!` `Lösung des Systems:` `x[1] = 2.000000` `x[2] = 5.000000` `x[3] = 7.000000` `x[4] = -1.000000`

Ausblick:

In diesem Kapitel entwickelten wir ein Programm zur numerischen Lösung von linearen Gleichungssystemen. Ein solches Programm ist für Mathematiker oder Ingenieure, aber auch für Schüler und Studenten ein wichtiges Hilfsmittel, da es aufwendige Rechnungen übernehmen kann.

Daher gibt es auf dem Software-Markt eine ganze Reihe von diesen Programmen.

Meistens können sie aber nicht nur lineare Gleichungssysteme lösen, sondern besitzen viel weiterreichende Fähigkeiten und können zur Lösung unterschiedlichster Probleme eingesetzt werden .

Für den Mathematikunterricht sind sogenannte Computeralgebrasysteme wie DERIVE, MuPad, MAPLE oder MATHEMATICA von Interesse. Sie erlauben uns die Lösung vielfältiger Probleme aus dem Bereich der Mathematik.

So können sie bei der Behandlung von linearen Gleichungssystemen nicht nur die numerischen Lösungen ermitteln, sondern sogar formal exakt berechnen. Dies ist vor allem dann erforderlich, wenn in einem Gleichungsssystem nicht nur Variablen, sondern noch Parameter enthalten sind.

Beispiel: Zu lösen ist das folgende Gleichungssystem, das außer den Variablen x und y noch den Parameter a enthält, wobei a eine reelle Zahl sein soll:

Zur Lösung beginnen wir mit der Subtrakion II - I. Daraus folgt:

Aus II' kann, unter der Voraussetzung, direkt x berechnet werden:

Mit der so bestimmten Lösung für x können wir durch Einsetzen in I auch y berechnen:

Wir erhalten also als Lösung unseres Gleichungssystems:

,
Das Computeralgebrasystem DERIVE nimmt uns die gesamte Arbeit ab und liefert uns das gewünschte Ergebnis nach einem Tastendruck:

Nach Eingabe der beiden Gleichungen in der Form [a x + y = 0.5 , x + y = 1]

berechnet DERIVE mittels des Befehls SOLVE SYSTEM direkt die Lösung unseres Gleichungssystems:

Abb.: Ausgabebildschirm des Compteralgebrasystems DERIVE zur Lösung des obigen Beispieles

Aufgaben:

1. Gegeben sind die folgenden linearen Gleichungssysteme:
   2x2 - System:
   3x3 - System:
   1. Löse die folgenden linearen Gleichungssysteme mit dem Einsetzverfahren mittels Bleistift und Papier. Was fällt dir auf ?
   2. Löse die beiden Gleichungssystem durch Transformation auf Dreiecksform ebenfalls mittels Bleistift und Papier.

   Hinweis: Falls die Aufgabe 3 des Kapitels 3.1.2 ausführlich bearbeitet wurde, so kann das dort erstellte Programm sehr hilfreich benutzt werden.

2. Löse mit einem PASCAL-Programm die folgenden 3x3-Systeme.
3. Ein lineares Gleichungssystem mit betragsmäßig sehr unterschiedlich großen Koeffizienten ist nicht so einfach zu lösen, da hier kleine Rundungsfehler schon zu großen Ungenauigkeiten des Ergebnisses führen. Man sagt, es neigt zu numerischer Instabilität.
   Zur Lösung solcher linearen Gleichungssysteme ist es notwendig, die Pivotsuche abzuändern. Eine solche verbesserte Pivotsuche ist in folgender Prozedur dargestellt:
   `1': procedure Pivotsuche(x:Integer);
   2': var
   3': i,MaxIndex:Integer;
   4': begin
   5': MaxIndex:=x;
   6': for i:=x to rang do
   7': begin
   8': if Abs(Koeff[i,x])>Abs(Koeff[Maxindex,x]) then MaxIndex:=i;
   9': end;
   10': if Koeff[MaxIndex,x]=0 then
   11': begin
   12': GotoXY(2,24);
   13': Write('Das ',Rang,'x',Rang,'-System ist nicht eindeutig lösbar!');
   14': halt(1);
   15': end;
   16': Zeilentausch(x,MaxIndex);
   17': end;
   `
   1. Erkläre kurz den Aufbau und Ablauf der Prozedur.
   2. Worin liegt der Unterschied zur einfachen Pivotsuche?
   3. Ersetze die im Musterprogramm verwendete Prozedur durch die neue Pivotsuche und teste ihre Wirkung an dem folgenden Gleichungssystem:
      Vergleiche die Ergebnisse des Lösungsprogrammes mit der alten Pivotsuche mit den Ergebnissen einer Version der neuen Pivotsuche.

      Zum Vergleich: Die exakten Lösungen des Programms sind:

      .

Fachbereich Informatik -- Fachbereiche
StR Gerhard März
maerz@fkg.wuerzburg.de