Einführung in das Programmieren mit DELPHI  

17. Lineare Gleichungssysteme

Die neuen grafikfähigen Taschenrechner verfügen über eine Funktion rref, mit der die Koeffizientenmatrix eines Linearen Gleichungssystems auf die reduzierte Dreiecksform gebracht wird. Danach stehen in der Hauptdiagonalen nur noch Einsen, das heißt in der letzten Spalte können die Lösungen abgelesen werden. Wir wollen diesen Algorithmus "nachprogrammieren".

Vorher:
 Nachher:
Folgende Schritte müssen ausgeführt werden:

  • Matrix einlesen
  • Matrix auf Dreiecksform bringen
  • Matrix auf reduzierte Dreiecksform bringen
  • Matrix anzeigen
 

Den ersten und den letzten Schritt, das heißt die beiden leichtesten Teile, erledigen wir sofort.

Danach machen wir uns daran, die Matrix auf Dreiecksform zu bringen.

 

 

1. Teil: Matrix auf Dreiecksform bringen

Grobformulierung:

Das Verfahren wird Carl-Friedrich-Gauß zugeschrieben
und heißt deshalb Gauß-Eliminationsverfahren.

 
interface

type
  TMatrix = array[1..9,1..10] of real;

var
  Form1: TForm1;
  n    : integer;
  x    : TMatrix;

implementation

procedure TForm1.Button1Click(Sender: TObject);
begin
    Einlesen;
    Dreiecksform;
    Reduzieren;
    Anzeigen;
end;

procedure TForm1.Einlesen;
var z,s:integer;
begin
  n:= Min(StrToInt(Edit1.Text),5);
  for z:=1 to n do
    for s:=1 to n+1 do
      if Trim(sgKoeff.Cells[s-1,z-1])<>'' then
        x[z,s]:= StrToFloat(sgKoeff.Cells[s-1,z-1])
      else
        x[z,s]:= 0;
end;

procedure TForm1.Anzeigen;
var z,s:integer;
begin
  for z:=0 to 5 do
    for s:=0 to 6 do
      sgKoeff.Cells[s,z]:='';
  for z:=1 to n do
    for s:=1 to n+1 do
      sgKoeff.Cells[s-1,z-1]:= FloatToStr(x[z,s]);
end;

1. Verfeinerung:

    Der Zeilentausch ist nötig, da auch bei lösbaren LGS einzelne xii Null sein können.

2. Verfeinerung:

 
procedure TForm1.Dreiecksform;
var i:integer;
begin
    for i:=1 to n-1 do
        Eliminieren(i); 
end;

procedure TForm1.Eliminieren(i:integer);
var z,s:integer;
begin
    Zeilentausch(i);
    if x[i,i]<>0 then
       for z:=i+1 to n do
           ZeileSubtr(x[z,i]/x[i,i],z,i);
end;

procedure TForm1.ZeileSubtr(c:real;z,i:integer);
var s:integer;
begin
    for s:=1 to n+1 do
        x[z,s]:= x[z,s] - c*x[i,s];
    x[z,i]:= 0; // gegen Rundungsfehler
end;

procedure TForm1.Zeilentausch(i:integer);
var z,s,m: integer;
    h: real;
begin
    m:=i;
    for z:=i+1 to n do  // max. Koeff. bestimmen
        if Abs(x[z,i])>Abs(x[m,i]) then m:=z;
    if m<>i then
    for s:=1 to n+1 do
        begin
          h:= x[i,s];
          x[i,s]:= x[m,s];
          x[m,s]:= h;
        end;
end;

2. Teil: Matrix auf reduzierte Dreiecksform bringen

 
procedure TForm1.Reduzieren;
var i:integer;
begin
    for i:=n downto 1 do
        if x[i,i]<>0 then begin
           Kuerzen(i,x[i,i]);
           AufwaertsEliminieren(i)
        end;
end;

procedure TForm1.Kuerzen(i:integer; c:real);
var s:integer;
begin
    for s:=1 to n+1 do
        x[i,s]:= x[i,s]/c;
end;

procedure TForm1.AufwaertsEliminieren(i:integer);
var z:integer;
begin
    for z:=i-1 downto 1 do
        ZeileSubtr(x[z,i],z,i);
end;

Aufgaben :

  1. Wo muss bei unlösbaren Gleichungssystemen ein Fehler abgefangen werden?
  2. Bei der Prozedur Eliminieren macht es Sinn, den Zeilentausch immer durchzuführen. Warum?
  3. Wie lässt sich das Programm auf unterdeterminierte Gleichungssysteme erweitern?

» Lösung

© 2009 : Bernd Schultheiss