Lineares Gleichungssystem lösen

[Andreas13]

Ich sehe Kegasetu’s Problem ganz wo anders: Mit dem schön aufgemachten Programm von Fiete45 (#30) lassen sich lineare Gleichungssysteme auch bis zu 100 und mehr Unbekannten in Sekundenschnelle lösen. Das geht wunderbar gut, aber das Programm ist interaktiv und dialogorientiert: Man muß also die Koeffizienten seiner Gleichungen per Hand in die Maske eingeben oder reinkopieren. Und das ist bei großen Gleichungssystemen mühsam und fehleranfällig.

Kegasetu will – so vermute ich – seine Gleichungen direkt per Delphi-Code an die Lösungsroutinen übergeben. Und dazu muß man jedoch genau wissen, wohin man die einzelnen Koeffizienten packen soll. Und das ist bei einem – bisher etwas chaotischen Gleichungssystem – schwer zu realisieren. In der momentanen (fehlenden) Struktur seines Gleichungssystems kann man auch Fiete45’s tolle Programm nicht benutzen.
Zuerst muß man Ordnung in die Gleichungen bringen...

Gruß, Andreas

[Michael II]

Zitat von Andreas13:

Ich sehe Kegasetu’s Problem ganz wo anders: Mit dem schön aufgemachten Programm von Fiete45 (#30) lassen sich lineare Gleichungssysteme auch bis zu 100 und mehr Unbekannten in Sekundenschnelle lösen. Das geht wunderbar gut, aber das Programm ist interaktiv und
Zuerst muß man Ordnung in die Gleichungen bringen...

Gruß, Andreas

Hallo Andreas

das war ein allgemeiner Tipp für Leute, welche entweder mit Mathe und Info nicht soviel am Hut haben oder für Leute, welche gerade keinen Weg finden ein einfaches Mathe Problem zu lösen.

Wenn ich das Programm von Fiete45 richtig verstehe, dann kann es keine Algebra. Mit Maple und Co kannst du zum Beispiel für das LGS Ax=b allgemeine Formeln für x ausgeben lassen in Abhängigkeit von A, b (Werte von A, b u.U. noch nicht alle bekannt). In gewissen Fällen sind diese Formeln einfach und der Weg über (hier) Gauss und andere wird unnötig.

Wenn jeweils für A, b Werte vorliegen, dann ist natürlich ein "Löser" wie "Fietes45 Super Solver" topp.


Punkto Ordnung: K muss ja nur die Summanden mit ma und mj aus den Gleichungen 1 und 8 auf die rechte Seite schieben; dann herrscht bereits jene Ordnung, welche du bei der Darstellung von inhomogenen LGS erwartest.

Ich bin raus... ihr schafft das auch ohne mich .

Gruss
Michael

[Kegasetu]

Zitat von Andreas13:

Hallo,
wenn allerdings ma und mj bekannt sind, habe sie auf der linken Seite des Gleichungssystems (GLS) nichts verloren! Denn die konstanten Terme sind per Definition auf der rechten Seite. Sie müssen dann von den jeweiligen mma1[Zeile] abgezogen werden.

Damit wird allerdings nicht nur die Struktur Deiner Koeffizienten-Matrix (= linke Seite des GLS; A_Matrix) und der Rechte-Seite-Vektor (b_Vektor) chaotisch, sondern auch die Benennung Deiner Variablen: Der Vektor mma1[..] enthält sowohl konstante, also bekannte Terme, wie auch die zu bestimmenden Unbekannten!

Zwei Vermutungen habe ich hierbei:

1):
Wenn ma und mj wirklich bekannt sein sollen, dann darfst Du sie nicht mit den Unbekannten zusammen speichern, sondern separat, unter ganz anderen Namen, sonst ist das Chaos perfekt und Du kannst später Deinen Code weder verstehen, noch warten, geschweige denn weiterentwickeln.

2):
Daher vermute ich eher, daß Du hier wahrscheinlich einen Spezialfall Deines GLS mit ursprünglich 10 Unbekannten behandeln willst, wenn zwei Unbekannte ma und mj definierte Werte annehmen. In diesem Fall solltest Du für die beiden „momentan“ konstanten Variablen ma und mj zwei weitere Gleichungen hinzufügen:

Code:

ma = mma1[0]
mj = mma1[9]

Damit wird die in der Struktur der Matrix und des Vektors steckende Gesetzmäßigkeit gewahrt. Das ist extrem wichtig für die Belegung von A-Matrix und b_Vektor, damit Du diese mit einer einfachen For-Schleife füllen kannst und nicht jedes Element mühselig und vor allem fehleranfällig „zu Fuß“ hinzufügen mußt.

Wenn Du obige Ratschläge beherzigst, entsteht auf der linken Seite Deines Gleichungssystems eine sogenannte Bandmatrix, ganz speziell eine Tridiagonal-Matrix. Diese läßt sich wesentlich schneller – mit einem Bruchteil an Operationen – und genauer (weniger Operationen, weniger Rundungsfehler) berechnen, allerdings nicht mit dem Gaußschen Algorithmus, sondern mit speziell für Tridiagonal-Matrizen entwickelten Algorithmen der linearen Algebra. Aber das würde hier zu weit führen. Daher nur so viel: Gauß ist OK, aber er macht hier riesige unnötige Umwege. Aber der heutige PC ist schnell und es fällt daher gar nicht auf.

Summe Summarum: Bevor Du also weiter programmierst, überprüfe zunächst Dein Gleichungssystem und benenne Deine Variablen mit Bedacht, damit Du es beim Implementieren der Algorithmen und bei der späteren Pflege der Routinen leichter hast.

Gruß, Andreas

Also chaotisch sollte das eigentlich nicht werden. Die bekannten Werte würde ich einfach gegen die Konstanten auf der anderen Seite rechnen. Das klappt schon, da bin ich ganz euphorisch. Ich sitze jetzt wieder dran und hoffe, ich bin nachher schon so weit die ersten versuche zu starten.

[Fiete45]

Moin,
habe das Gaußverfahren als Prozedur geschrieben:

Delphi-Quellcode:

type
  TVektor=Array of Extended;
  TMatrix=Array of TVektor;

procedure TGauss.GaussLGS(A:TMatrix;B:TVektor;var X:TVektor;var Anzahl:Integer);
  var N,K,I,L:Integer;
      T,Summe:Extended;
  begin
   N:=Length(B);
   for K:=0 to N-1 do
    begin
     // Pivotsuche
     I:=K;
     for L:=K+1 to N-1 do
      if abs(A[L,K])>abs(A[I,K]) then I:=L;
     if I>K then // tauschen der Zeilen i und k
      begin
       for L:=K to N-1 do
        begin T:=A[I,L];A[I,L]:=A[K,L];A[K,L]:=T end;
       T:=B[I];B[I]:=B[K];B[K]:=T;
      end;
     if A[K,K]=0.0 then begin Anzahl:=0;break end // K - Schleife verlassen, da keine Lösung
     else
      // Elimination
      begin
       for I:=K+1 to N-1 do
        begin
         T:=A[I,K]/A[K,K];
         for L:=K to N-1 do A[I,L]:=A[I,L]-A[K,L]*T;
         B[I]:=B[I]-B[K]*T;
        end;
       end
    end;
   if (A[N-1,N-1]=0.0) and (B[N-1]=0.0) then
    begin
     Anzahl:=1000000; // unendlich viele Lösungen
     exit;
    end;
   // Rücksubstitution
   Anzahl:=1; // genau eine Lösung
   X[N-1]:=B[N-1]/A[N-1,N-1];
   for I:=N-2 downto 0 do
    begin
     Summe:=0.0;
     for K:=I+1 to N-1 do Summe:=Summe+A[I,K]*X[K];
     X[I]:=(B[I]-Summe)/A[I,I];
    end;
  end;

Aufruf der Prozedur, wobei A und B mit Werten gefüllt sein müssen: GaussLGS(A,B,X,Anzahl);
X ist der Lösungsvektor, Anzahl enthält die Lösungsanzahl.
0 - keine Lösung
1 - genau eine Lösung
1000000 - viele Lösungen

Gruß Fiete

[Michael II]

Was mir bereits bei deinem Programm aufgefallen ist:
Du unterscheidest keine oder eine Lösung oder "unendlich viele" Lösungen.

Schön wäre es, wenn dein Programm im Fall "unendlich viele Lösungen" den Lösungsraum angeben würde.

[Kegasetu]

Zitat von Fiete45:

Moin,
habe das Gaußverfahren als Prozedur geschrieben:

Delphi-Quellcode:

type
  TVektor=Array of Extended;
  TMatrix=Array of TVektor;

procedure TGauss.GaussLGS(A:TMatrix;B:TVektor;var X:TVektor;var Anzahl:Integer);
  var N,K,I,L:Integer;
      T,Summe:Extended;
  begin
   N:=Length(B);
   for K:=0 to N-1 do
    begin
     // Pivotsuche
     I:=K;
     for L:=K+1 to N-1 do
      if abs(A[L,K])>abs(A[I,K]) then I:=L;
     if I>K then // tauschen der Zeilen i und k
      begin
       for L:=K to N-1 do
        begin T:=A[I,L];A[I,L]:=A[K,L];A[K,L]:=T end;
       T:=B[I];B[I]:=B[K];B[K]:=T;
      end;
     if A[K,K]=0.0 then begin Anzahl:=0;break end // K - Schleife verlassen, da keine Lösung
     else
      // Elimination
      begin
       for I:=K+1 to N-1 do
        begin
         T:=A[I,K]/A[K,K];
         for L:=K to N-1 do A[I,L]:=A[I,L]-A[K,L]*T;
         B[I]:=B[I]-B[K]*T;
        end;
       end
    end;
   if (A[N-1,N-1]=0.0) and (B[N-1]=0.0) then
    begin
     Anzahl:=1000000; // unendlich viele Lösungen
     exit;
    end;
   // Rücksubstitution
   Anzahl:=1; // genau eine Lösung
   X[N-1]:=B[N-1]/A[N-1,N-1];
   for I:=N-2 downto 0 do
    begin
     Summe:=0.0;
     for K:=I+1 to N-1 do Summe:=Summe+A[I,K]*X[K];
     X[I]:=(B[I]-Summe)/A[I,I];
    end;
  end;

Aufruf der Prozedur, wobei A und B mit Werten gefüllt sein müssen: GaussLGS(A,B,X,Anzahl);
X ist der Lösungsvektor, Anzahl enthält die Lösungsanzahl.
0 - keine Lösung
1 - genau eine Lösung
1000000 - viele Lösungen

Gruß Fiete

Ich bin jetzt die Strategie gefahren alles, was ich brauche (und noch mehr...) aus dem Gauss Programm zu übernehmen und so die Gleichung zu lösen. Es funktioniert so weit, aber ich habe noch tiefgreifende Probleme an ganz anderen Stellen.