AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Gauß-Verfahren - Matrix lösen

Ein Thema von Danny92 · begonnen am 29. Aug 2015 · letzter Beitrag vom 1. Sep 2015
Antwort Antwort
Seite 1 von 2  1 2      
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#1

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 09:11
Ein Gauß 40 x 40 dürfte bei Floats so 1 sec. brauchen. Das Problem hier dürfte dein Zahlenformat sein. Wie wäre es hingegen, mit Floats zu arbeiten und zur Ausgabe sich eine FloatToFrac zu schreiben. Hier das wäre mal ein Anfang.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#2

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 10:02
Es ist eigentlich üblich, bei der Lösung von Gleichungssystemen mit Gleitkommazahlen zu arbeiten. Es gibt bestimmte Verfahren, um Rundungsfehler zu minimieren (beispielsweise QR-Zerlegung). Weshalb brauchst du Ganzzahlen? Du hast es begründet mit GGT und KGV, aber ich finde das in deinem Code nur im Zusammenhang mit den Bruch-Berechnungen. Die bräuchtest du mit Gleitkommazahlen ja gar nicht mehr. Was soll am Ende wirklich berechnet werden?
  Mit Zitat antworten Zitat
Benutzerbild von frankyboy1974
frankyboy1974

Registriert seit: 7. Apr 2015
Ort: SH
169 Beiträge
 
Delphi XE7 Professional
 
#3

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 10:16
Hallo,

ich würde das Problem auch in Abbildung des Gauß-Verfahrens sehen. Wenn ich dir jetzt als Beispiel das LGS 2,59X+ 7,657Y= 874584 und 4,55X + 18,456Y=44837 gebe, sucht du jetzt den kgVF von 2,59 und 4,55, nur um das LGS zu lösen?

mfg

frank
Java ist auch eine Insel.
Ist Delphi von Oracle?
In meiner Buchstabensuppen fehlt das C++!
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#4

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 10:24
Ein Gauß 40 x 40 dürfte bei Floats so 1 sec. brauchen.
Das wird sehr schnell ungenau, sofern man das klassische Eliminationsverfahren verwendet. Die LUP-Dekomposition (Cormen) ist hier besser, jedenfalls bei meinen Versuchen.
  Mit Zitat antworten Zitat
Benutzerbild von frankyboy1974
frankyboy1974

Registriert seit: 7. Apr 2015
Ort: SH
169 Beiträge
 
Delphi XE7 Professional
 
#5

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 11:01
Hallo,

Zitat:
Die LUP-Dekomposition (Cormen) ist hier besser
Ja mag ja sein(ich habs nur mal überflogen), aber der TE wollte

Zitat:
Gauß-Verfahren - Matrix lösen
mfg
Java ist auch eine Insel.
Ist Delphi von Oracle?
In meiner Buchstabensuppen fehlt das C++!
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#6

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 11:38
Ich dachte, er meint das Gaußsche Eliminationsverfahren, um Gleichungssysteme zu lösen. Weil: Eine 'Matrix lösen' kann nur Neo.
  Mit Zitat antworten Zitat
Benutzerbild von frankyboy1974
frankyboy1974

Registriert seit: 7. Apr 2015
Ort: SH
169 Beiträge
 
Delphi XE7 Professional
 
#7

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 12:00
hallo,

als ich Neo laß, dachte ich zuerst an den Fisch (aber der heißt nemo).

mfg
Java ist auch eine Insel.
Ist Delphi von Oracle?
In meiner Buchstabensuppen fehlt das C++!
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#8

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 13:30
Ein Gauß 40 x 40 dürfte bei Floats so 1 sec. brauchen. Das Problem hier dürfte dein Zahlenformat sein. Wie wäre es hingegen, mit Floats zu arbeiten und zur Ausgabe sich eine FloatToFrac zu schreiben. Hier das wäre mal ein Anfang.
Du musst aber einen langsamen Computer haben. Steht da TI-57 oder so drauf?
Ich habe mal MATLAB angeworfen auf meinem Desktop-PC von 2008. Ein 40x40 Gleichungssystem wird in 0,15ms gelöst. Eingabe "x = A\b;" entspricht anschaulich A^(-1)*b benutzt aber LU-Zerlegung.
Eine Gauss-Implementierung von Github schafft es immer noch in 0,6ms. Bei 400 Elementen ist es auffälliger, da braucht der Gauß 400ms und linsolve() 20ms.

Zum Thema: Du musst auf jeden Fall mit dem String-gerechne aufhören Vll. als erste Maßnahme mal Int64 für Zähler/Nenner hernehmen, oder wenn es WIRKLICH rational bleiben muss, dann auf Byte-Arrays für Zähle/Nenner gehen. Oder halt etwas Gehirnschmalz in eine eigene Div/Mod Funktion für Extended stecken und doch Gleitkommazahlen verwenden.
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#9

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 15:04
Japp. Selbst mein Blödgauss aus den 80gern schafft in 1 sec eine Matrix 500 x 500. Ich denke mal TE würde sowas womöglich schon reichen. Etwas umformuliert, erste Tests, die Quelle hab ich oben angegeben.
Delphi-Quellcode:
function FloatToFracStr(const Value: Extended): string; // Quelle "delfiphan"
const
  Eps = 1E-12; // Fehlertoleranz
var
  P, LastP, Q, LastQ, TempP, TempQ, U, A, D: Extended;
  Numerator, Denominator: int64;
begin
  Numerator := 0;
  Denominator := 0;
  // Initialisierung
  A := 1;
  P := 1;
  Q := 0;
  LastP := 0;
  LastQ := 1;
  U := Value;
  // Abbruchkriterien
  while (CompareValue(U, 0) <> 0) and (CompareValue(Value + A, Value) <> 0) and (CompareValue(A, Eps) >= 0) do
  begin
    // Einen ganzzahligen Anteil abspalten
    D := Round(U);
    U := U - D;
    // Update von P und Q: Kettenbruch nachführen. Es gilt: P / Q ~= Value
    TempP := P * D + LastP;
    TempQ := Q * D + LastQ;
    LastP := P;
    LastQ := Q;
    P := TempP;
    Q := TempQ;
    // Approximationsfehler
    A := 0.25 * Abs(P / Q - Value);
    // Bruch umkehren
    if U <> 0 then U := 1 / U;
  end;
  // Vor Integerkonversion auf Bereich überprüfen
  if (P > High(int64)) or (Q > High(int64)) or (P < Low(int64)) or (P < Low(int64)) then
    raise EIntOverflow.Create('FloatToFrac: int64 overflow.');
  // Vorzeichen von Nenner zum Zähler
  if Q < 0 then
    Numerator := -Trunc(P)
  else
    Numerator := Trunc(P);
  Denominator := Abs(Trunc(Q));
  if Denominator = 1 then
    Result := IntToStr(Numerator)
  else
    Result := Format('%d/%d', [Numerator, Denominator]);
end;
  Mit Zitat antworten Zitat
Benutzerbild von Danny92
Danny92

Registriert seit: 18. Aug 2014
55 Beiträge
 
Delphi 10.2 Tokyo Starter
 
#10

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 17:04
Zum Thema: Du musst auf jeden Fall mit dem String-gerechne aufhören Vll. als erste Maßnahme mal Int64 für Zähler/Nenner hernehmen, oder wenn es WIRKLICH rational bleiben muss, dann auf Byte-Arrays für Zähle/Nenner gehen. Oder halt etwas Gehirnschmalz in eine eigene Div/Mod Funktion für Extended stecken und doch Gleitkommazahlen verwenden.
Natürlich ist es möglich, eigene Div und Modulo-Funktionen mit extended zu schreiben, wie:

Code:
function AModB(A, B: extended): integer;
begin
  result := Trunc(A-Trunc(A/B)*B);
end;
Dieser ist zwar mit bis auf extended ausdehnbare Zahlen anwendbar, aber auch nicht zu gebrauchen, da er mir bei Zahlen A und B jenseits von integer leider falsche Ergebnisse liefert, z. B. ist A=1000000000733131 MOD B=429596729935 = 328410174386, jedoch liefert mir diese Funktion in diesem Falle einen falschen Rest von result=1992659890.

Ich hätte außerdem doch von Anfang an mit extended gerechnet und mir die aufwändigen Strings gespart, wenn ich da die Ungenauigkeit nicht hätte, denn spätestens ab der 19-20ten Nachkommastelle ist bei extended Schluss.
Habe ich eine 40x40-Dreiecksmatrix, deren 40 Einträge in der Hauptdiagonalen alle 1/40 sind, ist die Determinante D=(1/40)^40 bzw. 1/40^40, und da sind wir schon weit unterhalb von 20 Nachkommastellen. Extended würde mir dann also Null liefern, was ja aber nicht richtig ist, und 1/40 ist eindeutig nicht Nichts sondern immerhin 0,025!

Ich schätze ich bin einfach auf einen ganzzahligen Datentypen angewiesen, insofern hoffe ich, dass ich mit BigInt mehr erreichen kann.
Wie gesagt sind nur Brüche exakt, Gleitkommazahlen nützen mir nichts.
Und mit extended zu rechnen, um diese dann mittels FloatToFrac (Eps = 1E-12) in Brüche umzuformen nützt mir ebenfalls nichts, denn aus falschen Dezimalzahlen entstehen falsche Brüche!
Brüche in Dezimalzahlen umwandeln ist problemlos, sofern es die Genauigkeit zulässt - umgekehrt aber nicht.
Je größer die Matrizen, umso wichtiger scheint die Rechengenauigkeit zu werden.
Relativ Schnell, (scheinbar) beliebig groß, aber vor allem eindeutig UND exakt - das ist das Problem.

Integer (2^31-1) ist zu klein - und extended ist ungenau. There is a need of an data type with a range of extended - paired with a precision of integer.

In diesem Sinne sagt Fritz zu seinen Freund Karl: "Ich kann ganz schnell multiplizieren. Nenne mir zwei Zahlen!" Da fragt Karl ihn: "Was ist 17*13?" Da antwortet Fritz: "200." Nach kurzem Überlegen meint Karl: "Das ist aber falsch!" "Na und?", meint Fritz, "aber schnell."

Und ja, Richtigkeit sollte eine höhere Priorität haben als Schnelligkeit.

Geändert von Danny92 (29. Aug 2015 um 17:42 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      

 

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 20:22 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz