Algorithmen um optimalen Graph herauszufinden

[Maik Görgens]

Hallo!

Ich arbeite derzeit an einem physikalischen Programm, und da stellte sich mir nun folgendes Problem:

Ich habe zehn und mehr Punkte, die etwa auf einer quadratischen Kurve liegen. Nun will ich herausfinden, welche Funktionsvorschrift am besten geeignet ist, um eine Kurve durch die Punkte zu zeichnen.
Ich hab mir folgendes überlegt:
(Bei drei Punkten ist es ja nicht schwer, da findet sich ja immer eine passende Funktion)

Ich hab die Punkte
A(a/z) B(b/y) C(c/x) D(d/w)
und will auf eine Funktion der Sorte f(x) = p*x^2 + q*x + r kommen.

Nun könnte ich doch sagen, der Abstand eines Punktes (m/n) zur Kurve ist gleich
p*m^2 + q*m + r - n

Das wende ich nun auf alle Punkte an:
abstand(p,q,r) = p*a^2 + q*a + r - z + p*b^2 + q*b + r - y + p*c^2 + q*c + r - x + p*d^2 + q*d + r - w

Nun müßte ich einen Weg finden, p, q und r so zu bestimmen, das abstand(p,q,r) möglichst klein wird. Und hier ist nun mein Problem, ich hab eine Gleichung mit 3 unbekannten, die annähernd 0 werden soll.

Gibt es eine Möglichkeit, sowas zu berechnen, oder gibt es eine völlig andere Möglichkeit, Kurven zu finden, die am besten an vorgegebenen Punkten vorbeigehen? Es gibt ja bereits Programme, die sowas machen, weiß jemand eine Seite im Netz, wo entsprechende Algorithmen beschrieben sind?

Vielen Dank im Vorraus
Maik Görgens

PS: Ich hoffe, das ich mein Problem mit all den Formeln nicht zu theoretisch erklärt hab... ;)

[backbone]

hi,

sehe momentan zwar noch nicht 100 pro durch aber eins weiss ich:
wenn du die formel so: "abstand(p,q,r) = p*a^2 + q*a + r - z + p*b^2 + q*b + r - y + p*c^2 + q*c + r - x + p*d^2 + q*d + r - w" damm wirds nix denn da fehlen doch ne menge klammern oder irre ich??!? so, und zu dem algo: ich glaub nicht da du sowas frei im netz finden wirst weil die leute die das entwickeln wolln ja auch bissel was verdienen oder? *G*

aber sowas müsste nicht schwer zu entwickeln sein. ne formel mit 3 unbekannten kann man doch recht einfach (mathematisch) umstellen. frag mich nicht wie denn ich hab schon kleine probleme mit 2 unbekannten ;D aber es ist, glaube ich , recht einfach. schau doch mal bei google... http://www.google.de/search?hl=de&ie=UTF-8&oe=UTF-8&q=formel+mit+3+unbekannten+mathematisch&meta=

tschau

[Henryk Plötz]

Moin,

Ich habe zehn und mehr Punkte, die etwa auf einer quadratischen Kurve liegen. Nun will ich herausfinden, welche Funktionsvorschrift am besten geeignet ist, um eine Kurve durch die Punkte zu zeichnen.

Da werf' ich doch mal die alte Physikerweisheit ein: Willst du eine Grade, dann miss zweimal, willst du eine Ursprungsgrade, dann miss nur einmal.

Aber nun gut: Dein Google-Stichwort lautet Interpolation bzw. Regression. Da gibt es tonnenweise Literatur mit fertigen und guten Algorithmen zu.

Nun müßte ich einen Weg finden, p, q und r so zu bestimmen, das abstand(p,q,r) möglichst klein wird. Und hier ist nun mein Problem, ich hab eine Gleichung mit 3 unbekannten, die annähernd 0 werden soll.

Das wäre dann eine Minimierungsaufgabe: Ableitung nullsetzen. Bei 3 Unbekannten will man das aber wohl eher nicht machen.

[Andreas Korthaus]

Hallo!

Nun müßte ich einen Weg finden, p, q und r so zu bestimmen, das abstand(p,q,r) möglichst klein wird. Und hier ist nun mein Problem, ich hab eine Gleichung mit 3 unbekannten, die annähernd 0 werden soll.

Das wäre dann eine Minimierungsaufgabe: Ableitung nullsetzen. Bei 3 Unbekannten will man das aber wohl eher nicht machen.

IMHO ist das genau das was bei der (nicht) linearen Regression gemacht wird, es wird die Summe der kleinsten Quadrate zw. Punkt, Regressions-"Gerade" und y-achse ermittelt, er denkt also in der richtigen Richtung, aber auf diesem Level wird es langsam schieriger "selber das Rad neu zu erfinden"..., also googlen und auf alt Bewährtes zurückgreifen ;-)

Grüße
Andreas

PS: ich habe das z.B. in Statistik machen müssen, könnte das aber jetzt nicht so wirklich aus dem Handgelenk ;-)

[Henryk Plötz]

Moin,

IMHO ist das genau das was bei der (nicht) linearen Regression gemacht wird, es wird die Summe der kleinsten Quadrate zw. Punkt, Regressions-"Gerade" und y-achse ermittelt, er denkt also in der richtigen Richtung, aber auf diesem Level wird es langsam schieriger "selber das Rad neu zu erfinden"..., also googlen und auf alt Bewährtes zurückgreifen ;-)

Ja, das ist mir dann auch eingefallen. Was mir noch eingefallen ist, wenn man das Problem nur einfach irgendwie lösen will und nicht garantiert optimal: Einfach alle möglichen Kombinationen von 3 Punkten aus seinen 10 Punkten nehmen (dürften 120 sein, wenn ich mich nicht verrechnet habe). Für diese Kombinationen dann jeweils p, q und r ausrechnen (müsste jeweils genau aufgehen) und dann den Mittelwert über alle diese p, q und r bilden.

[Frank Schönmann]

hi!

Ich habe zehn und mehr Punkte, die etwa auf einer quadratischen
Kurve liegen. Nun will ich herausfinden, welche Funktionsvorschrift
am besten geeignet ist, um eine Kurve durch die Punkte zu zeichnen.

Wenn es eine quadratische Funktion ist, dann wird die schon durch
drei Punkte eindeutig beschrieben. Daher bekommst du mit deinen zehn
Punkten eher ein 9-gradiges Polynom.

Falls dir der Grad des Polynoms egal ist, dann suche mal nach
Lagrange-Interpolation in den einschlägigen Quellen. Das ist IMHO
das Standard-Verfahren, um Polynome aus gegebenen Punkt-Werte-Paaren
zu interpolieren.

Ansonsten hast du in der Tat mit einem Minimierungsproblem zu kämpfen.
Allerdings sind meine Kenntnisse in Numerik weit weniger vorhanden
als ich gerne hätte. Möglicherweise findest du aber in irgendwelchen
Numerik-Büchern oder -Skripten nach einer Lösung für dein Problem.

Es gibt da noch Splines, mit denen man Kurven aus Punkten machen kann.
Allerdings bin ich momentan unschlüssig, ob das dann noch Polynome
sind. Aber was du genau vorhast, hast du ja auch nicht verraten.

bye, Frank!

[Peter Kaufmann]

Hallo Maik,

Ich habe zehn und mehr Punkte, die etwa auf einer quadratischen Kurve liegen. Nun will ich herausfinden, welche Funktionsvorschrift am besten geeignet ist, um eine Kurve durch die Punkte zu zeichnen.

wenn du google (oder die Suchfunktion deiner Lieblings Uni Bib.) bemühen möchtest solltest dun es mit "nonlineare regression" bzw. "nonlinear fitting" versuchen.
Soweit ich weiß läuft die Lösung des Problems letztendlich auf die Lösung des "Normalgleichungssystems" hinaus (Stichwort: Cholesky-Verfahren).

Ich hab mir folgendes überlegt:

Ich hab die Punkte
A(a/z) B(b/y) C(c/x) D(d/w)
und will auf eine Funktion der Sorte f(x) = p*x^2 + q*x + r kommen.

[...]

abstand(p,q,r) = p*a^2 + q*a + r - z + p*b^2 + q*b + r - y + p*c^2 + q*c + r - x + p*d^2 + q*d + r - w
Nun müßte ich einen Weg finden, p, q und r so zu bestimmen, das abstand(p,q,r) möglichst klein wird.

In der Praxis nimmt man die Abstandsquadrate der bekannten Punkte von der theoretischen Kurve (ich glaube seit Newton).

Gibt es eine Möglichkeit, sowas zu berechnen, oder gibt es eine völlig andere Möglichkeit, Kurven zu finden, die am besten an vorgegebenen Punkten vorbeigehen? Es gibt ja bereits Programme, die sowas machen, weiß jemand eine Seite im Netz, wo entsprechende Algorithmen beschrieben sind?

Nein weiß ich leider nicht, aber es gibt ja Freie Software deren Source Code du mal anschauen könntest:

(xm)grace : http://plasma-gate.weizmann.ac.il/Grace/
gnuplot : http://www.gnuplot.info/

PS: Ich hoffe, das ich mein Problem mit all den Formeln nicht zu theoretisch erklärt hab... ;)

Bin schlimmeres gewohnt ;-)

Grüße,

Peter

[Reiner]

Hallo,

wenn Du irgendwie an den Bronstein gelangen könntest, da ist irgendwo im letzten Drittel ein komplettes Kapitel über Regressionsverfahren.

Gruß
Reiner