Hi zusammen,
Kurz-Fassung: Ich löse ein Nicht-Lineares 6D Gleichungssystem mit Hilfe des Newton-Verfahrens. Allerdings habe ich Schwierigkeiten die Anfangswerte sinnvoll zu bestimmen, so dass die Lösung in etwa 8% der Fälle nicht konvergiert. Daher suche ich nach Möglichkeiten entweder die Anfangswerte besser zu wählen, im Falle der Nichtkonvergenz die Anfangswerte besser zu manipulieren oder den Konvergenzradius des Newtonverfahrens zu vergrößern / bzw. ein „zuverlässigeres“ Verfahren zu verwenden (z.b. Homotopie-Verfahren?).
Lang-Fassung:
ich bin leider auf ein Problem gestoßen, das ich analytisch nicht zu lösen vermag (auch nicht mittels Computer, zumindest nicht nach zwei Tagen Rechenzeit). Da ich diese Berechnungen jedoch mittels Java durchführen möchte brauche ich entweder die analytische Lösung oder ein (für mich verständliches 
) numerisches Verfahren.
Jetzt aber erstmal anschauliche das Problem:
Ich habe zwei Objekte A und B, die sich in 2D frei bewegen können. Wir wählen Objekt A als Ursprung des Koordinatensystems, damit es in Selbigem ruht. Wir haben nun aus Ausgangssituation Objekt B das sich im Abstand (x,y) von Objekt A befindet und zu diesem die Relativgeschwindigkeit (vx,vy) hat. Des Weiteren beschleunigt es mit (axB,ayB). Die Fragestellung ist nun:
Wie lange und in welche Richtung muss Objekt A beschleunigen und danach wie lange und in welche Richtung „verzögern“, um Objekt B einzuholen UND die gleiche Geschwindigkeit zu besitzen. Dabei gilt als Randbedingung, dass die maximale Beschleunigung von Objekt A gegeben ist durch axA²+ayA² = aMaxA² (= const. dürfte als Näherung vorerst reichen).
Soweit so gut, Formeln aufstellen ist kein Problem:
\frac{1}{2} \cdot (ax_{A1} \cdot t_{1}^2 + ax_{A2} \cdot t_{2}^2) + ax_{A1} \cdot t_1 \cdot t_2 = x + vx \cdot (t_1 + t_2) + \frac{1}{2} \cdot ax_B \cdot (t_1 + t_2)^2
\frac{1}{2} \cdot (ay_{A1} \cdot t_{1}^2 + ay_{A2} \cdot t_{2}^2) + ay_{A1} \cdot t_1 \cdot t_2 = y + vy \cdot (t_1 + t_2) + \frac{1}{2} \cdot ay_B \cdot (t_1 + t_2)^2
ax_{A1} \cdot t_1 + ax_{A2} \cdot t_2 = vx + ax_B \cdot (t_1 + t_2)
ay_{A1} \cdot t_1 + ay_{A2} \cdot t_2 = vy + ay_B \cdot (t_1 + t_2)
ax_{A1}^2 + ay_{A1}^2 = a_{max}^2
ax_{A2}^2 + ay_{A2}^2 = a_{max}^2
Das ist also mein Gleichungs-System.
Wie schon erwähnt, mit Newton-Verfahren zu lösen funktioniert in etwa 92% der Fälle und wenn er es lösen kann, dann braucht er auch nur akzeptable (34 ± 25) Iterationen für eine relative Genauigkeit von 0.001. Ansonsten ist mein aktuelles Vorgehen, dass, wenn nach 100 Iterationen keine Lösung gefunden wurde die Anfangsbedinungen manipuliert werden und das Verfahren neu gestartet wird. Sollten 2000 Neustarts nicht zur Lösung führen bricht er ab. Dementsprechend ließe sich die Zuverlässigkeit durch ein Anpassen der Zahl der Neustarts und des Grenzwerts für den Abbruch zwar erhöhen, allerdings auf Kosten der Rechendauer, wobei für mich die Schmerzgrenze bei den genannten Werten erreicht ist (Bis zu 150ms bis er ohne Lösung abbricht).
Der sinnvollste Angriffs-Punkt sind somit die Anfangswerte, denn um das System zu lösen benötige ich im Mittel (115 ± 300) Neustarts, so dass sich hier nicht nur die Zuverlässigkeit sondern auch die mittlere Rechendauer deutlich verbessern lässt.
Was meine bisherigen Schätzungen angeht:
Die Zeit-Schätzungen funktionieren relativ gut mit einer mittleren Abweichung von (14 ± 10)% von der Lösung.
Die bekomm ich als Kombination der eindimensionalen Lösungen:
- X bzw. Y-Richtung wird einfach ignoriert, Lösungssystem wird einfacher, lässt sich analytisch lösen
-> es ergibt sich daraus ein t1x und ein t1y
–> Der Zeit-Schätzwert ergibt sich als
t_{1,0} = \sqrt{t_{1,x}^2 + t_{1,y}^2} .
Das Problem sind eher die Werte für die Beschleunigungen:
Hier ermittle ich eine erste Näherung a0, indem ich die Bewegung von Objekt B ignoriere und nur zum Ort sx gehe. Die Näherung ist allerdings nur gut, wenn s >> v,a. Das ist leider bei nicht immer der Fall, weshalb ich versucht habe das anzupassen aber auf keinen grünen Zweig komme.
Zur Manipulation der Anfangswerte verwende ich immer Zufallswerte zwischen 50% und 150% für die Beschleunigungen bzw. ±10% für die Zeiten.
Wenn also jemand Ideen hat, wie ich die Anfangswerte sinnvoll ermitteln kann, oder herausbekomme welche Anfangswerte ich wie ändern muss um die Konvergenz zu erreichen, dann wär ich dankbar für Hinweise.
Ansonsten bin ich auch offen für alternative Verfahren zum Lösen, allerdings war das Newton-Verfahren bis jetzt das einzige, bei dem ich verstanden habe, wie ich es auf mehrdimensionale Gleichungssysteme anwende.
Zum Abschluss habe ich noch ein vielversprechend klingendes, mir aber leider nicht viel sagendes Verfahren gefunden, das von der Beschreibung her das Newton-Verfahren globalisiert, das Homotopie-Verfahren.
http://de.wikipedia.org/wiki/Homotopieverfahren oder was ich deutlich hilfreicher fand:
http://books.google.de/books?id=l45jSrRdL7AC&pg=PA21…
Allerdings hab ich auch hier das Problem, dass ich zwar den mathematischen Grundgedanken verstehe, aber nicht die geringste Ahnung habe, wie ich das im konkreten Fall tatsächlich anwenden soll.
Ansonsten vielen Dank für’s Mitdenken 
Schigum
