Algorithmus des Lösers

In diesem Forum Fragen und Diskussionen in Deutsch
Forum rules
Foren-Regeln und hilfreiche Informationen

WICHTIG: Bitte zuerst lesen, bevor Sie posten
holdi
Posts: 232
Joined: Mon Dec 05, 2016 3:00 pm
Contact:

Algorithmus des Lösers

Postby holdi » Tue Mar 14, 2017 12:45 pm

Wo steht darüber etwas geschrieben? Ich möchte gerne bei Wiki-Tutorials darüber etwas Genaueres einfügen.

mfGn holdi
User avatar
r-frank
Posts: 1960
Joined: Thu Jan 24, 2013 6:26 pm
Location: Möckmühl, Germany
Contact:

Re: Algorithmus des Lösers

Postby r-frank » Wed Mar 15, 2017 6:37 am

Meinst Du den Solver des Sketchers ?

Du kannst das Glossary heranziehen.
In der 0.16 wurde ja Advanced Solver Control eingeführt (siehe Abschnitt 2 der release notes) - Forum Diskussionen hier und hier.

Je nachdem was Du ergänzen willst kannst Du auf der Sketcher Workbench Seite ansetzen ...
Deutsche FreeCAD Tutorials auf Youtube
My GrabCAD FreeCAD-Projects
FreeCAD lessons for beginners in english

Native german speaker - so apologies for my english, no offense intended :)
holdi
Posts: 232
Joined: Mon Dec 05, 2016 3:00 pm
Contact:

Re: Algorithmus des Lösers

Postby holdi » Wed Mar 15, 2017 11:04 am

r-frank wrote:Meinst Du den Solver des Sketchers ?
Ja, offensichtlich meine ich den (Solver = Löser), der wohl nur(?) beim Zeichnen (Sketch) vorkommt.

In der 0.16 wurde ja Advanced Solver Control eingeführt (siehe Abschnitt 2 der release notes) - Forum Diskussionen hier und hier.
Ob modernisiert (advanced) oder nicht, ist für mich erst einmal sekundär. Primär möchte ich die Abgrenzung zwischen der geometrischen Mathematik (Beispiel: 32 Lösungen für die 5er-Rosette https://www.freecadweb.org/wiki/Sketcher_tutorial/de; Zwischenbogenlänge < bzw. > 180°) und der Rechenarbeit des Lösers (z.B. Umkippen eines aus zwei Geraden bestehenden Winkels https://www.freecadweb.org/wiki/Sketche ... wei_Linien )* als ein Fall für ungenügende Rechenarbeit des FreeCAD-Lösers) derart herausarbeiten, dass dem Benutzer wenigstens der Unterschied von Mathematik hier und einer bestimmten mathematischen PC-Arbeit dort klar wird, und er (und auch ich) etwas mehr weiß als, dass im Löser ein größeres Gleichungssystem gelöst (eine hier im Forum öfters vorkommende Aussage) wird. Wie sieht dieses System aus?

mfGn holdi

)* Nebenfrage: Wie erzeugt man die Icons in diesen und anderen Wikis alle in gleicher, moderater Größe?
ickby
Posts: 2414
Joined: Wed Oct 05, 2011 7:36 am

Re: Algorithmus des Lösers

Postby ickby » Wed Mar 15, 2017 11:53 am

Es kommen mherere Verfahren zum einsatz. Normalerweise DogLeg (ein Trust-Region Verfahren) zur Lösung und ein Sequential Quadratic Programming Verfahren zum Ziehen per Maus.

Das Gleichungssystem ist leicht vorzustellen: Jede Constraint wird in eine mathematische Fehler-Funktion umgewandelt die nur bei Erfüllung der Beschränkung 0 wird.
chrisb
Posts: 1630
Joined: Tue Mar 17, 2015 9:14 am

Re: Algorithmus des Lösers

Postby chrisb » Wed Mar 15, 2017 1:52 pm

Wenn ich das richtig sehe, dann steckt an Mathematik eine Jacobi-Matrix dahinter.
(Falls Du eine Seite in der Dokumentation über den Algorithmus schreibst, ersetze bitte das "y" des Titels dieses Themas durch ein "i").
holdi
Posts: 232
Joined: Mon Dec 05, 2016 3:00 pm
Contact:

Re: Algorithmus des Lösers

Postby holdi » Wed Mar 15, 2017 3:12 pm

ickby wrote:Es kommen mherere Verfahren zum einsatz. Normalerweise [url=http://www.numerical.rl.ac.uk/people/nimg/course/lectures/r[aphael/lectures/lec7slides.pdf]DogLeg[/url] (ein Trust-Region Verfahren) zur Lösung und ein Sequential Quadratic Programming Verfahren zum Ziehen per Maus.

Das Gleichungssystem ist leicht vorzustellen: Jede Constraint wird in eine mathematische Fehler-Funktion umgewandelt die nur bei Erfüllung der Beschränkung 0 wird.
Beim Gleichungssystem bitte ich Dich, noch ein wenig tiefer zu gehen, und dabei allgemein zu bleiben, denn welche (PC-programmierte) mathematische Verfahren/Werkzeuge beim Lösen angewendet werden, wäre m.E. vorerst noch nicht wichtig. Eine Festlegung/Beschränkung (constraint) ist doch zuerst einmal eine jeweilige Einzelaktion und als solche nicht zu prüfen/kontrollieren. M.E. wird dabei lediglich ein Parameter namentlich kreiert und ihm ein Wert zugewiesen. Damit eine Zeichnung (sketch) eindeutig erstellt (fully constraint) ist, braucht es m.E. einen zusammen fassenden Al­go­rith­mus. Wie ist die Fragestellung dafür, herauszufinden, ob der Zeichnende genügend Angaben (constraints) gemacht hat? Kannst Du einmal einen (meinethalben bereits in Programm-Code geschriebenen) Al­go­rith­mus für die Prüfung einer einfachen Zeichnung, die z.B. nur eine Gerade, nur einen Kreis o.ä enthält, zitieren? Daraus möchte ich dann gerne erkennen, wie und warum beim Ändern eines Parameter-Wertes eine andere (z.B. umgeklappte Figur) entstehen kann.

mfGn holdi
Last edited by holdi on Thu Mar 16, 2017 9:20 am, edited 1 time in total.
ickby
Posts: 2414
Joined: Wed Oct 05, 2011 7:36 am

Re: Algorithmus des Lösers

Postby ickby » Wed Mar 15, 2017 4:25 pm

Da gibt es nicht viel mehr zu sagen als bereits geschrieben. Jede Constraint wir in eine Gleichung umgewandelt. Als Beispiel die horizontale Distanz zwischen zwei Punkten:

0 = sqrt(x1^2-x2^2) - d

Alle Gleichungen zusammen ergeben das Gleichungssystem, dieses wird mit den genannten Verfahren gelöst. Das ist alles. Zur Bestimmung der Freiheitsgrade nutzt man die Differenz zwischen Parametern im System und dem Rank der Jacobimatrix des linearisierten Gleichungssystems.

Das Verhalten des Sketchers ergibt sich aus einer detaillierten Studie der genannten Lösungsalgorithmen.
chrisb
Posts: 1630
Joined: Tue Mar 17, 2015 9:14 am

Re: Algorithmus des Lösers

Postby chrisb » Wed Mar 15, 2017 5:33 pm

ickby wrote:Als Beispiel die horizontale Distanz zwischen zwei Punkten:

0 = sqrt(x1^2-x2^2) - d
Es spielt hier eigentlich keine Rolle, aber hat sich in der Formel ein kleiner Tippfehler eingeschlichen und es müsste eher 0=abs(x1-x2) - d sein?

Im englischen Forum wies NormandC darauf hin, dass der FreeCAD-Solver den Vergleich mit den teuren professionellen Systemen nicht zu scheuen braucht, im Gegenteil, die zeigen gar nicht mal alle die Zahl der noch verbleibenden Freiheitsgrade an, eine Eigenschaft, die ich sehr schätze. Das zeigt mir, dass der Solver weit davon entfernt ist, trivial zu sein. Und das was mathematisch dahintersteckt ist es auch nicht.

Die Jacobi-Matrix kann man sich als eine Darstellung eines Gleichungssystems vorstellen (also ähnlich wie das, was wir von Gauß kennen), das auch Ableitungen umfasst. Es ist eben kein lineares Gleichungssystem mehr und daher auch nicht so vergleichsweise trivial zu lösen wie ein solches.
Wenn man sich das vorstellen möchte, dann kommt genau das heraus was man am Bildschirm sieht: Eine Zeichnung die die vorgegebenen geometrischen Eigenschaften hat. Wenn man jetzt noch die Meta-Eigenschaft hinzunimmt, dass ein System als gelöst gilt, wenn es nicht mehr unendlich viele Lösungen gibt, dann ist man bei der recht einfachen anschaulichen Beschreibung der nicht ganz so anschaulichen Mathematik dahinter.

P.S. Es heißt wirklich Algorithmus, nach Al Kwarizmi (und nicht Kwaryzmy)
Last edited by chrisb on Fri Mar 17, 2017 6:28 pm, edited 1 time in total.
ickby
Posts: 2414
Joined: Wed Oct 05, 2011 7:36 am

Re: Algorithmus des Lösers

Postby ickby » Wed Mar 15, 2017 6:29 pm

Ja stimmt, ich habe da zwei Formeln vertauscht und zusammengewürfelt :)
holdi
Posts: 232
Joined: Mon Dec 05, 2016 3:00 pm
Contact:

Re: Algorithmus des Lösers

Postby holdi » Thu Mar 16, 2017 10:45 am

chrisb wrote:
ickby wrote:Als Beispiel die horizontale Distanz zwischen zwei Punkten: ...
....0=abs(x1-x2) - d

Sind meine daraus resultierenden Überlegungen richtig?

Meine Zeichnung enthält 2 Versuche:
1. eine horizontale und
2. eine schräge Linie,
deren horizontalen Abstand ihrer Endpunkte ich horizontal festgelegt (constrained) habe.

Den Objekten wird bereits beim Zeichnen ein Name zugeordnet: 1-Linie und 2-Linie.
Die Koordinaten der Endpunkte sind bekannt, aber noch nicht in Beziehung zueinander gebracht.

Beim Vermassen des horizontalen Abstands (Eingabe von d) wird für jede Linie gesondert die Gleichung 0=abs(x1-x2) - d aufgestellt: Constaint1 (..) und Constaint2 (..)
Linien-Name und Endpunkt-x-Koordinaten dieser Linie gehören zusammen, was aber in der Dialog-Box (Combo-Box) nicht erkennbar ist.

Wird ein Endpunkt angeklickt und verschoben, so wird die Gleichung permanent gelöst. Die erforderliche Veränderung der x-Koordinate des anderen Endpunktes wird berechnet und ausgegeben (auf dem Bikdschirm wandert der andere Endpunkt mit, wobei die Distanz d=50 mm beibehalten wird).

Die Linie kann beliebig schräg gestellt werden. Eine Festlegung (constraint) in y-Richtung wurde ja (noch) nicht vorgenommen, und der Unterschied der Ausgangslagen 1. u. 2. ist somit irrelevant. Da der andere Endpunkt nicht angefasst wird, bleibt unter diesen Umständen seine y-Koordinate erhalten. Nur seine x-Koordinate ist genötigt (wörtlich für to be constrained).

Wie sieht es bei geometrischen Verknüpfungen (geometric constaints) aus? Gebt doch bitte auch ein entsprechendes Formel-Beispiel an.

mfGn holdi
Attachments
algorithmus.jpg
algorithmus.jpg (31.91 KiB) Viewed 118 times