AVR: Interpolation? Splines?

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.

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.

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 :-)

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.