Konvergenz mehrdimensionales Newtonverfahren verbessern

Neue Frage »

cawa132 Auf diesen Beitrag antworten »
Konvergenz mehrdimensionales Newtonverfahren verbessern
Meine Frage:
Hi Leute,

ich erkläre kurz die Aufgabe, wie ich es zu lösen Versuche und wo dann das Problem liegt.

Aufgabe:
Es ist ein beliebiges (konvexes) Viereck gegeben. Nennen wir dieses VE1. Dies ist unveränderlich und durch vier Punkte definiert.
Als nächste Schritt wird irgendwo in der Ebene ein zweites konvexes Viereck erstellt, VE2. Es ist ebenfalls durch seine Punkte definiert.

Ziel: VE2 so verschieben und drehen, dass die Summe der Fehlerquadrate der Abstände der Punkte beider Vierecke (VE1 und VE2) minimal wird.
Bildlich gesprochen: "Die Vierecke sollen gut übereinander liegen."

Problem: Die Konvergenz soll optimiert werden, da es nicht gegen ein Minimum strebt.
Hier ein Diagramm dazu für 10000 Iterationsschritte:

[attach]47936[/attach]

Rot - Summe Fehlerquadrate, die gegen Minimum streben soll
Blau - numerische Ableitung von "rot"

Meine Ideen:
Lösungsansatz:
Das ganze löse ich zur Zeit numerisch mit dem "Newton Verfahren", allerdings mehrdimensional mit der Jacobimatrix.
Ich habe mir überlegt, dass ich genau drei Dinge ändern kann:
- Position Punkt 1 (x1, y1) von VE2 in x und y
- Drehung (phi) von Punkt 2 von VE2 relativ zu Punkt 1

Daraus definiere ich einen Vektor Z(x1, y1, phi). Die anderen Punkte sind damit automatisch definiert über die Seitenlänge bzw. Winkel.

Da ich nun meine drei Parameter kenne, kann ich einen Vektor F erstellen, der die partiellen, numerischen Ableitungen des Gesamtfehlerquadrates nach x1, y1, phi beinhaltet. Über die numerische Ableitung von F wieder in alle drei Richtungen (x1, y1 und phi) erhalte ich die Jacobimatrix.
Die Inverse der Jacobimatrix wird in jedem Rechenschritt (Zeitoptimierung dahingehend ist erstmal egal) neu ausgerechnet und zwar über die Determinante/-n und die adjunkte Matrix.
Zusätzlich habe ich Versucht über einen Faktor K (K < 1) die Konvergenz zu verbessern.

Dann erhalte ich Z(n+1) = Z(n) - InverseJacobimatrix * F * K
(n entspricht dem aktuellen Iterationsschritt)

Das wiederhole ich so lange, bis meine Gesamtfehlerquadrate gegen ein Minimum gehen.

Was ich überprüft habe:
- das Anpassen von "K" brachte keinen Erfolg
- meine Matrizenmultiplikation mit der von Excel (MMULT) verglichen, selbe Ergebnisse
- Inverse Matrix mit der von Excel (MINV) berechneten und verglichen, passt
- numerische Ableitung bestätigt, dass sie (im Rahmen der Genauigkeit) funktioniert
- Funktion F, sprich Ableitung Summe Fehlerquadrate in alle drei Dimensionen tendenziell "mit dem Auge" überprüft, sprich Werte erscheinen logisch, selbes für Jacobimatrix

Tendenziell Verschiebt sich das Viereck in die richtige Richtung usw. nur hat jedes Minimum eine andere Qualität vom "Überdeckungsgrad".

Wie kann ich das Verhalten verbessern? Sollte es nicht automatisch konvergieren und sich nicht wieder von einem Minimum entfernen (selbst, wenn mehrere Minima exitieren sollten)? Mache ich prinzipiell etwas falsch?

Danke für eure Hilfe smile

Zwei Beiträge zusammengefasst, damit es nicht so aussieht, als ob schon jemand antwortet. Außerdem Bild aus externem Link als Anhang eingefügt. Bitte keine externen Links verwenden.
Viele Grüße
Steffen
Elvis Auf diesen Beitrag antworten »

Das scheint mir vom Ansatz her ein wenig kompliziert zu sein. Was passiert, wenn du zunächst einmal (z.B.) die Schnittpunkte der Diagonalen der Vierecke nach 0 verschiebst und dann die Fehlerquadratsumme durch Drehung eines Vierecks minimierst ? Das gibt zumindest ein lösbares Problem, und es wäre zu untersuchen (1.) ob das allgemeine Problem wesentlich bessere Lösungen hat und (2.) ob du ein Verfahren findest, das einigermaßen stabil bessere Lösungen berechnet. (Es soll praktische Anwendungen geben, bei denen man mit einer guten und berechenbaren Lösung zufrieden ist.)

Wenn das nicht gut genug ist, würde ich den Diagonalenschnittpunkt von Viereck2 auf einem diskreten quadratischen Gitter im Viereck1 variieren und jeweils obige Minimierung durchführen.
 
 
cawa132 Auf diesen Beitrag antworten »

Danke, ich habe es jetzt mal gemacht, wie du es gesagt hast: ich habe die Schwerpunkte übereinander gelegt und dann mit der Drehung die Fehlerquadrate minimiert. Hat super geklappt. Anschließend minimiere ich noch mal separat mit der Verschiebung in x und y.
Elvis Auf diesen Beitrag antworten »

Wenn das mein Numerik-Professor wüsste, dass ich jemals in die Lage versetzt war, einen akzeptablen Rat für eine numerische Anwendung zu erteilen, hätte ihn das sicher ebenso verwundert wie gefreut. smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »