Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Gauss-Jordan
AXMD - Fr 26.11.04 21:50
Titel: Gauss-Jordan
Immer wieder, immer wieder... schön langsam gehen mir Matrizen echt aufn Zeiger. Naja... ich suche nach einer Möglichkeit, Gauss-Jordan zu optimieren. Am besten wär natürlich was in Assembler-Richtung; nur da ich von ASM keine Ahnung habe, hab ich mir gedacht, vielleicht kann mir mal jemand helfen :)
AXMD
sourcehunter - Fr 26.11.04 23:29
Hast du schon nen Code?
AXMD - Sa 27.11.04 10:23
Ja, hab ich gestern geschrieben. Allerdings hat der Code einen Bug, den ich nicht wegbekomme: hin und wieder hat z das falsche Vorzeichen und die Zeilen werden zB addiert statt subtrahiert, d.h. keine Nullen, wo eigentlich welche sein sollten. Hier der Code:
//EDIT: Code nicht mehr aktuell; aktueller Code siehe unten
Wobei ich zum Testen folgende Matrix verwendet habe:
1 3 -4
1 1 -2
-1 -2 5
und als Lösungsvektor:
8
2
-1
Keine Ahnung, ob das Teil wirklich Lösungsvektor heißt; meinen tu ich damit die Zahlen, die auf der rechten Seite der Gleichungen stehen.
AXMD
sourcehunter - Sa 27.11.04 12:26
Geht es dir nur um das berechnen von Lösungsmengen von linearen Gleichungssystemen mit 3 Gleichungen und 3 unbekannten?
AXMD - Sa 27.11.04 19:26
Ja genau. Ich find den Fehler einfach nicht :x
AXMD
sourcehunter - So 28.11.04 00:13
Hast du schon mal was von folgender Methode gehört?
A*x=b (A - Koeffizienten Matrix, b - Konstantenvektor)
=> x=A^-1*b
gesucht ist nur die inverse Matrix von A, dann skalar mit b multiplizieren und x ist dein Lösungsvektor.
AXMD - So 28.11.04 11:57
Die methode kenn ich; aber ich muss Gauss-Jordan programmieren ;)
AXMD
sourcehunter - So 28.11.04 15:06
Ich hab mir das mal angeguckt und bein auf folgenden Code gekommen:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24:
| procedure GaussJordan; var i,j,k:Integer; f:Extended; begin for i:=1 to 3 do begin f:=A[i,i]; for j:=1 to 4 do begin A[i,j]:=A[i,j]/f; end; for j:=1 to 3 do begin if j<>i then begin f:=A[j,i]; for k:=1 to 4 do begin A[j,k]:=A[j,k]-f*A[i,k]; end; end; end; end; end; |
A ist die erweiterte Koeffizienten-Matrix, also die Koeffizienten mit den konstanten Gliedern.
Bsp:
1 1 1 4 -> x+ y+z=4
2 1 1 5 -> 2x+ y+z=5
1 2 1 6 -> x+2y+z=6
Der Algorithmus gibt als Lösung
1 0 0 1 -> x=1
0 1 0 2 -> y=2
0 0 1 1 -> z=1
an.
Wie du vieleciht bemerkt hast brauche ich keine Vorzeichen ändern. Die Vorraussetzung, dass der Code funzt ist natürlich, dass kein Pivot-Element 0 wird. Wo der Fehler bei dir liegt kann ich nicht sagen.
AXMD - So 28.11.04 15:16
Ich hab mal die Abfrage mit z rausgetan und das Z gelassen wie es ist. Ich verwende das Beispiel von unserem Professor:
x+3y-4z=8
x+y-2z=2
-x-2y+5z=-1
Hier der komplette Programmcode mit Ausgabe der Zwischenschritte. Ich glaub jetzt gehts *nichtsicher* :?
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95:
| program gauss_jordan;
{$APPTYPE CONSOLE}
uses SysUtils;
var i, j, k: Integer; pivot, z: Integer; var matrix: Array [1..3] of Array [1..3] of Integer; loesungsvektor: Array [1..3] of Integer; ergebnis: Array [1..3] of Integer;
procedure ZwischenergebnisAnzeigen; var l, m: Integer; begin WriteLn; for l := 1 to 3 do begin WriteLn; for m := 1 to 3 do begin Write(matrix[l, m]: 12); end; Write(' |', loesungsvektor[l]: 12); end; WriteLn; WriteLn('z: ', z, ' pivot: ', pivot, ', j: ', j, ', k: ', k); end;
begin
WriteLn('Gleichungslösen nach Gauss-Jordan'); WriteLn('================================='); WriteLn;
WriteLn('Bitte geben Sie die Komponenten der Koeffizientenmatrix ein (Zeile, Spalte):'); WriteLn;
for i := 1 to 3 do begin for j := 1 to 3 do begin Write('Element ', i, ',', j, ': '); ReadLn(matrix[i, j]); end; end;
WriteLn; WriteLn('Bitte geben Sie die Komponenten des Lösungsvektors ein:'); WriteLn;
for i := 1 to 3 do begin Write('Komponente ', i, ': '); ReadLn(loesungsvektor[i]); end;
for i := 1 to 3 do begin pivot := matrix[i, i]; for j := 1 to 3 do begin if i <> j then begin z := matrix[j, i]; for k := 1 to 3 do begin ZwischenErgebnisAnzeigen; ReadLn; matrix[j, k] := pivot * matrix[j, k] - z * matrix[i, k]; end; loesungsvektor[j] := pivot * loesungsvektor[j] - z * loesungsvektor[i]; end; end; end;
ZwischenErgebnisAnzeigen;
for i := 1 to 3 do ergebnis[i] := loesungsvektor[i] div matrix[i][i];
WriteLn; WriteLn; WriteLn('Lösung der Gleichung:'); WriteLn;
for i := 1 to 3 do WriteLn('Unbekannte ', i, ': ', ergebnis[i]);
WriteLn; WriteLn('-----------------------------------------------------------------------------'); WriteLn('Gleichungslösen nach Gauss-Jordan - (c) by Dust Signs Andreas Unterweger 2004'); ReadLn;
end. |
//EDIT: Zur Eingabe des Beispiels meines Profs:
1
3
-4
1
1
-2
-1
-2
5
8
2
-1
(der Reihe nach)
AXMD
AXMD - So 28.11.04 15:20
Achja: jetzt wo der Algo einigermaßen funktioniert: wo und wie kann man da was optimieren?
AXMD
sourcehunter - So 28.11.04 17:06
Das ist eine gute Frage. Bei so kurzen Algos ist da nicht viel drin. Aber hier mal ein paar Ideen:
so wenig, wie möglich auf die Matrix zugreifen, If-Abfragen vermeiden. Falls du alles in ASM haben möchtest, dann frag bitte jemand anders, denn bei Schleifen weiß ich nicht, wie.
Du solltest das Readln und die Zwischenausgabe weglassen. :wink:
btw: Was hast du als Lösung bei deinem Beispiel?
Ich habe x=1, y=5, z=2.
AXMD - So 28.11.04 20:03
Das klingt gut :).
AXMD
sourcehunter - Sa 04.12.04 15:59
Mal noch ne Frage am Rande. Wozu willst das noch optimieren?
AXMD - Sa 04.12.04 19:57
Ganz einfach: das hier ist ein Beispiel mit drei Gleichungen, drei Unbekannten. In der Praxis (weiß ich aus der FH) ist es durchaus üblich, dass man mal ein paar mehr hat (1000 oder mehr sind keine Seltenheit). Und da ist das Verfahren dann nicht mehr so schnell (natürlich ohne Anzeigen des Zwischenergebnisses ^^)
AXMD
sourcehunter - Sa 04.12.04 23:51
Das ding auch auf mehr als 3 Gleichungen und 3 Unbekannte loslassen?
AXMD - Sa 04.12.04 23:56
Natürlich vorher die Array-Dimensionen ändern und das ganze in eien GUI schmeißen - das kann ja keiner mehr tippen ^^
AXMD
sourcehunter - Sa 04.12.04 23:59
Mein Paps hat gesagt, dass da nur noch was mit ASM geht und da kann ich dir leider nicht weiter helfen. Haste schon nach ASM-Tuts gegoogelt?
AXMD - So 05.12.04 00:02
Nö; für ASM hab ich keine Zeit; aber ich denke, es müsste doch möglich sein, das Verfahren zumindest ein bisschen effizienter zu programmieren (ich meine solche Details wie Inc(i) statt i := i + 1 o.ä.)
//EDIT: unterrichtet dein "Paps" Mathe oder Informatik ;)
AXMD
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!