Hallo, ich habe vier Meßpunkte in der Ebene und möchte zwischen dem zweiten und dritten einen weiteren Punkt möglichst gut interpolieren. Hat zufällig jemand so etwas schon mal gemacht, mit etwas besserem als nur linearer Interpolation. Wenn ich mir die Formel in Wikipedia zu Splines, Langrane-Interpolation, etc. anschaue, verstehe ich nur noch Bahnhof. Muß man da wirklich erstmal riesen Gleichungssysteme lösen. Hat jemand so etwas schon mal mit einem AVR gemacht? Grüsse Kalle
Ach ja, vergessen. Die Messpunkte / Messwerte liegen als uint16_t vor.
Kein Wunder, daß alles andere als lineare Interpolation aufwändiger ist - du musst ja auch mehr als 2 Punkte verwursten. Wenn du mehr als die zwei verwenden willst, musst du dir erst mal klar werden, ob die Punkte (z.B. 4) exakt sind. Falls ja, kannst du entsprechend interpolieren (dann halt nicht mit einer Geraden wie bei lin. Int., sondern 3. O.). Falls nein, geht es nicht um Interpolieren, sondern Approximieren; ganz anderes Thema.
mh, Ja. Aber was ist daran bitte so schwer? Spline Interpolation gehört zu den mathematischen Grundlagen eines technischen Studiums ... In deinem Fall zwar nicht ganz angebracht, aber das solltest du beim eifrigen Studium der Materie selber rausfinden. Und die Methode der kleinsten Quadrate ist wohl auch kein Geheimnis.
>Muß man da wirklich erstmal riesen Gleichungssysteme lösen.
Nein. Holzbrett, Nägel, biegsame Latte.
Daher kommt ja die Bezeichnung Spline-Interpolation.
Hallo, Kleinste Quadarate ist aber keine Interpolation. Und es hat nicht jeder ein Mathe-Studium absolviert. Hat jemand evt. Links, auf Seiten zu dem Thema, wie die Gleichungssysteme effizient auf einem MC löst? Oder evt. sogar ein Stück COde zum Abschauen? Grüsse Kalle
Da drin versteckt findest du eine sehr verständliche Darstellung für Splines
Les n Mathebuch ! Und die Methode der kleinsten Quadrate hat sehrwohl was mit Interpolation sowie dem Lösen nichtlinearer Gleichungssystem zu tun ... pfosten ...
Fuer solche Geschichten hat man vorteilhafter Weise ein Mathe oder aehnliches Studium absolviert. Zuerst sollte man sich im klaren werden, ob man nun etwas Approximierendes oder etwas Interpolierendes haben will. Falls das System ueberbestimmt ist, wird's etwas Approximierendes werden.
Du hast ja die Punkte [0] [1] [2] [3] ^ ^ [x] ^ Diese zwei Punkte willst du interpolieren, wenn ich dich richtig verstanden habe. Dann nimm doch die erste Formel aus Wikipedia ;-) Spline Interpolation s(x) = m * x + b m = (y2 - y1) / (x2 - x1) b = y1 - m * x1 x - Also die Abtastachse ist hier das "Problem", denn dieser Werte liegen ja vermutlich in einem Puffer und der neue interpolierte Wert soll ja bei der "doppelten Abtastrate" liegen. (x2 - x1) ist bei einer konstanten Abtastung immer 1. Also x müsste man dann eine gebrochene Zahl verwenden. Du kannst auch deinen Eingangspuffer vergroessern (also zwischen jeden Wert eine Null einfügen) dann benötigst du keine gebrochene Zahl zur Interpolation. ciao
Hallo AVRNeuling, was Du beschreibst ist doch genau die lineare Interpolation, die der Thread-Starter nicht wollte. Wer mehr will, muss halt auch mehr rechnen... Nils.
Hi Zefix (Gast) schrieb: >Aber was ist daran bitte so schwer? Spline Interpolation gehört >zu den mathematischen Grundlagen eines technischen Studiums ... Dann kannst du das ja auch mal allgemein verständlich darlegen MfG Spess
Kennt eigentlich jemand ein gutes Verfahren um Splines zu retikulieren?
Die Frage ist eigentlich, was willst Du eigentlich darstellen? Splines ist das apropate Mittel um schwingungsverläufe Abzubilden. Wenn Du aber ein linears System abbilden willst, dann ist eine lineare Regression ggf. das wo nach Du suchst: http://de.wikipedia.org/wiki/Regressionsanalyse
Passt auch eventuell dazu (eigene Frage): Ich habe eine (grobe) Tabelle, welche mir zu gegebenen ADC-Werten (AVR-ADC) eines NTC, Temperaturen ausgibt. Ich habe in der Tabelle aus Platzgründen nicht jeden möglichen Zwischenwert abgelegt. Nun möchte ich aus einem ADC-Wert, der zufällig nicht in der Tabelle liegt (jedoch zwei anschließende) in einen Temperaturwert "umrechnen". Wie mache ich das am geschicktesten. Linear oder mittels Spline? Ersteres ist sicherlich viel schneller machbar, birgt aber Ungenauigkeiten. Sind Splines dazu geeignet und vor allen, auf einem AVR sinnvoll anzuwenden? Ich hatte zwar mal Mathe studiert, habe aber noch vor den Splines das Fach gewechselt. Angestaubtes Grundwissen in irgendwelchen Fachbüchern ist nicht mehr erreichbar, da ich nach Ende meines IT-Studiums fast alles verschenkt hatte. Ich würde es mir aber gerne einfach machen und auf ein fertiges Konzept (gerne auch Programm in C) zurückgreifen, ohne weit zu fahren und Mathe Biblotheken zu besuchen.
Das ist doch ein Kurve, bei der nichts spannendes passiert! Da reicht lineare Int. allemal denke ich. Jeder Mehraufwand lohnt frühestens, wenn die Kurve auch eine ordentliche Krümmung hat. Mal doch mal die Punkte auf und schau dir die Abweichung an zwischen den geraden Linien und einer glatt durchgezogenen Kurve. Schon mit wenigen Stützpunkten wird die Abweichung akzeptabel sein.
?? schrieb: > Fuer solche Geschichten hat man vorteilhafter Weise ein Mathe oder > aehnliches Studium absolviert. Nicht wirklich > Zuerst sollte man sich im klaren werden, > ob man nun etwas Approximierendes oder etwas Interpolierendes haben > will. Das ist ok. Das sollte man. Man sollte aber auch die Aufgabenstellung lesen. Gegeben sind 4 Punkte, gesucht ist eine Gleichung (Gleichungssystem), so dass die 4 Punkte auf der Kurve liegen, die durch diese 4 Punkte beschrieben werden kann. Nun gibt es natürlich viele Gleichungsfamilien, mit denen man so etwas lösen kann. Also kann man zb. Polynome als Grundlage nehmen. zb. eine Gleichung 3. Grades Y = a*X^3 + b*X^2 + c*X + d Wo kriegt man die 4 Koeffizienten a, b, c, d her? Ganz einfach, wir haben 4 Punkte P1, P2, P3, P4. Jeder mit einem X und dem zugehörigen Y Wert. D.h. wir haben P1y = a*P1x^3 + b*P1x^2 + c*P1x + d P2y = a*P2x^3 + b*P2x^2 + c*P2x + d P3y = a*P3x^3 + b*P3x^2 + c*P3x + d P4y = a*P4x^3 + b*P4x^2 + c*P4x + d ... ein lineares Gleichungssystem aus 4 Gleichungen in 4 Unbekannten. Und das kann man lösen (zb. Gauss Verfahren). Damit hat man dann die Koeffizienten und eine Gleichung in die ich einen beliebiegen X-Wert einsetzen kann und den zugehörigen Y Wert rausbekomme. Spline ist das noch keiner. Da müsste man nach X und Y aufdröseln, jeweils für X und Y ein eigenständiges Gleichungssystem aus 4 Gleichungen aufbauen und einen Parameter t von 0 bis 1 laufen lassen (0 = der eine Endpunkt, 0.33 der erste Zwischenpunkt, 0.66 der nächste Zwischenpunkt und schliesslich t gleich 1 der andere Endpunkt) X = at^3 + bt^2 + ct + d y = et^3 + ft^2 + gt + h d.h. P1x = a*0^3 + b*0^2 + c*0 + d P2x = a*0.33^3 + b*0.33^2 + c*0.33 + d P3x = a*0.66^3 + b*0.66^2 + c*0.66 + d P4x = a*1^3 + b*1^2 + c*1 + d P1y = e*0^3 + f*0^2 + g*0 + h P2y = e*0.33^3 + f*0.33^2 + g*0.33 + h P3y = e*0.66^3 + f*0.66^2 + g*0.66 + h P4y = e*1^3 + f*1^2 + g*1 + h Beide linearen Gleichungssysteme lösen um die Koeffizienten a, b, c, d bzw. e, f, g, h zu bestimmen.
So weit, so gut. Es geht hier aber um 4 Meßpunkte laut OP. Je nach (Un-) Genauigkeit kann ein Polynom dritten Grades da schon ziemlich unruhig werden. Möglicherweise ist das dann nicht das Grüne vom Ei.
Ob das linear ist oder nicht muss man daran sehen, welcher Natur die Meßwerte sind. Wenn das Wort Meßwerte fällt und einen Verlauf anzunähern, ist eine Interpolation nicht das Richtige: Meßwerte enthalten Fehler, Abweichungen zum Ideal. Wenn nun interpoliert wird, dann läuft diese exakt durch diese Fehler, was wohl nicht gewünscht ist. Statt dessen soll der Idealverlauf gefunden werden Und hier hat schon jemand gesagt wie das funktioniert: Lineares Ausgleichsproblem mit dem Verfahren der minimalen Fehlerquadrate. Du stellst eine Annahme auf, wie der Verlauf auszusehen hat. Vielleicht eine Gerade, eine Hyperbel, Polynom etc ... Die Parameter dieser Form werden nun bestimmt, in dem du ein entsprechendes (überbestimmtes) Gleichungssystem A und den Meßwerten b aufbaust (|Ax-b| -> min), dieses mit der Transponierten multiplizierst (entspricht der ersten Ableitung der 2. euklidischen Norm der Matrix) und das löst. 0-Stelle -> Extremstelle (Minimum) des Fehlers des überbestimmten Gleichungssystems. Nun kannst du die gewonnen Parameter in den angenommenen Verlauf einsetzen und hast das was du suchst: Eine Annäherung an den fehlerkorrigierten Werteverlauf.
Hallo, erstmal Danke an Karl heinz Buchegger für seine grundsätzlichen Ausführungen. Ich bin mir schon im klaren, was die Unterschiede zwischen den verschiedenen Imnterpolationsverfahren sind. Und nein, ich "Kleinste Quadrate" ist keine Interpolation. Das weiss ich auch ohne Mathe-Studium. Vieleicht noch etwas zur Anwendung. Ein Tastkopf fährt eine Bauteil ab. Die Position des Tastkopfs wird an einen AR übermittelt, der einen Plotter ansteuert. Alle 1 kommt eine Position des Tastkopfs. Der plotter benötigt aber alle 500ms einen Position. Da wären Splines IMHO angebarcht, da lt. Wiki, ja Unstetigkeiten in Ableitungen gößer zwei nicht mehr wahr nimmt. Hab#' das ganze mal mit Corel Draw probiert. Die Meßpunkte eingezeichnet und dann einen Spline-Zug über die Punkte gelegt. Grüsse Kalle
Kalle schrieb: > Da wären Splines IMHO angebarcht, da lt. Wiki, ja Unstetigkeiten > in Ableitungen gößer zwei nicht mehr wahr nimmt. Den letzten Satzteil versteh ich zwar nicht, aber Da könntest du genausogut die letzte gemessene Position 2-mal hintereinander ausgeben. Ist genauso gelogen, wie wenn du da jetzt einen Spline reinlegst. Nur weniger Arbeit :-)
Ich hätte besser schreiben sollen: Splines sehen so schön glatt aus, da Unstetigkeiten erst ab der dritten Ableitung auftreten können. Und besser gelogen als jeden Wert zweimal zu nehmen, sind Spline IMHO allemal, wenn - wie in meinem Fall - die abzutastenden Linie von einem Kurvenlineal stammt. ;-) Grüsse Kalle
Kalle schrieb: > Ich hätte besser schreiben sollen: > > Splines sehen so schön glatt aus, da Unstetigkeiten erst ab der dritten > Ableitung auftreten können. Das hast du nicht wirklich verstanden. Bei der beschriebenen Problematik geht es darum, was passiert, wenn 2 Splines zusammenstossen. Meistens geht man nämlich her und legt nicht einen Spline durch 20 Punkte, sondern man konstruiert in diese 20 Punkte zb 18 Splines rein, die an den gegebenen Punkt zusammenstossen. Dabei gibt es jetzt aber Unterschiede * haben die Splines an den Zusammenstosspunkten nur die Position gemeinsam, dann spricht man an diesem 'Schnittpunkt' von einer Kontunität (engl. Continuity) C(0). Der Splinezug aus den beiden einzelnen Splines kann an diesem Punkt durchaus einen scharfen 86,5° Knick haben. Wenn du in einem Wägelchen sitzt, dass diesen Verbindungspunkt als Schiene in einer Achterbahn durchfährst, dann knallst du gewaltig gegen die Seitenwand. * ist an den gemeinsamen Punkten gewährleistet, dass die Richtung der Tangenten der beiden Splines (die erste Ableitung) übereinstimmt, dann hat man einen C(1) Übergang. Der Übergang ist zwar nicht mehr so abrupt, wie bei C(0), die Kurve läuft schön durch, aber dem Auge fällt immer noch auf, dass etwas nicht stimmt. In der Achterbahn wäre das: Die Kurve der Bahn ist zwar durchgehend. Aber an einem Punkt der Bahn nimmt die Fliehkraft urplötzlich sprunghaft zu * eine C(2) Continuity erreicht man, wenn am Verbindungspunkt auch noch die 2-te Ableitung übereinstimmt. Geometrisch gesprochen: wenn der Kurvenradius identisch ist. In der Achterbahn bedeutet das, dass die Fliehkraft sich gleichmässig auf bzw. abbaut. Das alles kommt aber nur dann zum Tragen, wenn der komplette Spline aus mehreren Teilstücken zusammengesetzt werden muss. Du hast sowieso nur 4 Punkte, bei dir spielt das so gut wie keine Rolle. Einzige Ausnahme: wenn du in deine 4 Punkte 3 Parabeln hineinkonstruierst. Mit 4 Punkten könntest du zb einen Bezier Spline erreichten oder aber den schon weiter oben angesprochenen kubischen Spline. (Wobei der Einwand natürlich berechtigt ist, dass ein polynomialer Spline unter gewissen Umständen heftig um die gewünschte Kurve pendelt. Bei kubischen Abschnitten ist die Gefahr noch nicht so gross, dazu hat eine Kurve 3. Grades einfach zuwenig Freiheitsgrade als zb eine Kurve 10-ten Grades. Aber möglich ist es, und die Überschwinger sind dann heftig) > Und besser gelogen als jeden Wert zweimal zu nehmen, sind > Spline IMHO allemal, wenn - wie in meinem Fall - die abzutastenden > Linie von einem Kurvenlineal stammt. ;-) Na dann. Im Übrigen: Wenn eine deiner beiden Koordinatenachsen monotan wachsend abgenommen wird (und bis jetzt hört sich alles danach an), dann wärst du besser beraten, eine Funktion y = f(x) zu bauen, als einen Spline. Spline sind zwar wunderschön anzuschauen, aber sie sind Krüppel wenn es darum geht zb equidistante Punkte auf dem Spline zu finden.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.