Hallo,
leider kann ich dir keinen konkreten Vorschlag in Python geben, aber dein Problem hat Ähnlichkeiten zu jenen aus der Signalverarbeitung (auch der digitalen). Ich würde an deiner Stelle versuchen dies mit einer Polynominterpolation zu lösen. Da hättest du die freiheit überall einzugreifen und genau für dein Problem zu konstruieren. Leider ist diese Thematik (mathematisch) sehr umfangreich, zur Übersicht könnte dir der dazugehörige Wikipediaartikel [1] helfen.
Oft lässt sich ein solches Problem als Minimierungsproblem verstehen.
Einfaches Beispiel für eine Gerade auf diskreten Datensetzen:
x_i = {-2, -1, 0, 1, 2}
y_i = {0.5, 0.5, 2, 3.5, 3.5}
Annäherung durch Gerade: y = a + bx
Als Basis dient eine Fehlerfunktion:
Q = SUM von i=1 bis N von (y_i - f(x_i))^2
=> SUM_i=1^N(y_i -(a + b*x_i))^2
Ziel ist es nun die Fehlerfunktion Q zu minimieren
Also dQ/da = 0 und dQ/db = 0
=> für dQ/da = SUM_i=1^N => SUM_i=1^N y_i = a * SUM_i=1^N 1 + b * SUM_i=1^N x_i
=> für dQ/db = SUM_i=1^N => SUM_i=1^N y_i * x_i = a * SUM_i=1^N x_i + b * SUM_i=1^N x_i^2
Dafür kann man nun auch einen Trick anwenden da Matrix A ([1, x_1],[1, x_2], ... , [1, x_n]) mit SUM...^N von ... gleichwertig.
Also:
A^T*A = ([1,1, ... ,1], [x_1, x_2, ... , x_n]) * ([1, x_1],[1, x_2], ... , [1, x_n]) => ([SUM y_i], [SUM x_i]) = A^T*A*([a],
)
Mit dem Beispiel von oben:
SUM y_i = 10
SUM x_i = 9
A = ([1, -2], [1, -1], [1, 0], [1, 1], [1, 2])
A^T*A = ([5, 0], [0, 10])
A^T*y = A^T*A*([a, b]) => ([a],) = (A^T*A)^-1 * A^T*y
Also:
([10], [9]) = ([5, 0], [0, 10]) * ([a], ) => a = 2 und b = 9/10
Die Koeffizienten kannste dann einsetzen und damit beliebig viele Punkte von der Ausgleichsfunktion bestimmen.
Für Parabeln kannst du die Basisfunktion dann erweitern:
y = f(x) = a + b*x + c*x^2 mit Matrix A := ([1, x_1, x_1^2],[..., ..., ...], [1, x_n, x_n^2)
Für ein Polynom 3. Grades dann:
y = a + bx + cx^2 + dx^3
etc.
Ich hoffe es wird klar was ich meine. Leider habe ich keine Funktion im Forum für Mathematische ausdrücke gefunden... Wenn mir die jemand zeigt, kann ich den Beitrag gerne auch noch editieren. Es hilft sicherlich wenn man sich die Formeln mal aufschreibt damit sie leserlich werden :)
Wenn du obrigen Weg nimmst kannst du viel der mathematischen Operationen mit numpy, scipy etc. abdecken. Müsstest also nur eine für dich günstige Basisfunktion finden (evtl. Kreisfunktion / Ellipse).
Was mir gerade noch einfällt:
Es gibt diverse Probleme bei der Polynominerpolation, wenn du z.B. den Grad des Polynoms zu hoch wählst können zwar alle Werte exakt approximiert werden, allerdings sind die Zwischenwerte nonsens. Stell dir z.B. nen Sinus vor und Messwerte der Form x = {pi*n} mit n entahlten in {0, 1, 2, ...}. Eine Gerade währe ausreichen ein Sinus entspricht aber ebenso dem Kriterium.
Weiterhin kannst du obriges Verfahren nochmals iterativ ausführen (Minimierung der Fehlerquadrate) mit einer gewichteten Funktion aus der ersten Berechnung um den tatsächlichen Abstand zu minimieren, nicht nur entlang der y-Achse.
Der Weg lässt sich leicht auch auf 2-Dimensionale Probleme erweitern.
Besten Gruß
Acuda
[1] http://de.wikipedia.org/wiki/Polynominterpolation
Edit: Ich hoffe so viel Mathe ist nicht unangebracht in einem Python-Forum?
