AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

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 4  1 23     Letzte » 
Benutzerbild von Danny92
Danny92

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

Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 04:40
Hallo.
Nachdem mein Algorithmus zur Erstellung einer Dreiecksmatrix endlich fertig ist, muss ich nun leider feststellen, dass dieser bei größeren Matrizen (>12 Unbekannte/Zeilen) schon einige Minuten in Anspruch nimmt. (Selbstverständlich nimmt der Rechenaufwand mit der dritten Potenz der Anzahl der Unbekannten zu)

Wer sich meinen Code im Anhang anschauen wird, wird feststellen, dass dies aufgrund der aufwändigen Umsetzung mit Stringrechnung nicht verwunderlich ist.
Allerdings bin ich auf den Datentyp string umgestiegen, da ich einen ganzzahligen Datentypen benötige, und der größte Ordinaldatentyp, den es in Delphi gibt, ist in erster Linie erst einmal nur Integer. Da dieser jedoch nur bis 2^31-1 (also nur ca. 2,1 Mrd.) reicht, ist man da im mathematischen Sinne sehr schnell an den informationstechnischen Grenzen angelangt. (Wie groß ist in der Mathematik schon eine Zahl mit nur 10 Dezimalstellen, im Vergleich zu einer mit z. B. 1000 Stellen?)

Gleitkommazahlen wie extended sind in der Hinsicht ein gutes Vorbild, jedoch für meine Zwecke nicht zu gebrauchen, da ich Operationen Div und Modulo (Divisison mit Rest) benötige, die mit Kommazahlen leider Gottes nicht funktionieren...Also habe ich meine eigenen Methoden (+, -, *, /) implementiert, die mit (unbegrenzten) Strings rechnen und das jeweilige Ergebnis als String wieder ausgeben können. (z. B. function APlusB(A, B: TPoint): TPoint; //TPoint als Bruch (X Zähler, Y Nenner zu verstehen)

Code:
type
  TPunkt = Packed Record //Bruch mit X als Zähler und Y als Nenner
X: String;
Y: String;
end;

function APlusB(A, B: TPunkt): TPunkt; //Addiere zwei Brüche
begin
 //und so weiter
end;
Lange Rede, kurzer Sinn:
Ist es möglich und wenn ja wie, den Code hinsichtlich der Effizienz und des Rechenaufwandes zu optimieren um bei großen Matrizen schneller ans Ziel zu kommen?
Es sollte doch möglich sein, bis zu 40x40 große Matrizen in einer passablen Laufzeit zu lösen.
Am einfachsten wäre es sicherlich, einfach auf extended umzusteigen, aber
1. können da durch die vielen Rechenschritte enorme Rundungsfehler auftreten (nur Brüche sind exakt und eindeutig, extended ist leider nicht beliebig genau) und
2. wird mir extended für z.B. Modulo und damit für die Bestimmung des ggT oder kgV nichts nützen.

Praktisch ist mein Taschenrechner bei der Lösung von Matrizen in die Dreiecksmatrix mittels Gauß mindestens 10x so schnell...aber dennoch exakt!
Ich möchte keine Kompromisse eingehen - schnell UND exakt.

Ist es vielleicht doch ohne viel Aufwand möglich, einen eigenen, viel größeren ganzzahligen Datentypen - in der Größenordnung wie extended - zu implementieren? Und wenn ja, wie? Dann könnte ich mir das ganze aufwändige Gedattel mit den Strings sparen, denn ich bin sicher da liegt die größte Bremse.

Schon mal lieben Dank für die weisen Antworten

PS: Code und Programm im Anhang, bei diesem würde die Lösung einer 40x41 Ref Matrix mindestens unübertrieben Stunden dauern!!
Angehängte Dateien
Dateityp: zip Matrizenrechnung1.zip (295,4 KB, 23x aufgerufen)
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#2

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 08:54
Ich würde ein Datenformat wählen, welches Zahlen beliebiger Größe handhaben kann. Dann tauschst Du das aus und solltest zufrieden(er) sein.
Hier ist ein Datentyp für 512-bit Integer.
Und Hier sogar für beliebig große Zahlen (bis 2 Mio Stellen).

Ich fände es interessant, Deine Ergebnisse zu sehen.

Klar ist aber auch: Ein Algorithmus vom Aufwand O(n^3) wird bei großen n immer langsam.
  Mit Zitat antworten Zitat
Bjoerk

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

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 10: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
 
#4

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 11: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
 
#5

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 11: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
 
#6

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 11: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
 
#7

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 12: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
 
#8

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 12: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
 
#9

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 13: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.578 Beiträge
 
#10

AW: Gauß-Verfahren - Matrix lösen

  Alt 29. Aug 2015, 14: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
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

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 14:15 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf