Mathe: Splines und Hermite-Interpolation

[Possetitjel (Gast)]

Hallo allerseits,

eine Frage an die Mathe-Cracks. Das folgende Problem ist
mir im Zusammenhang mit der Interpolation von Bilddaten
untergekommen; ich bin für jeden Denkanstoß dankbar.

Hier erstmal die Frage in Kurzfassung; bei Interesse gern
auch mehr Hintergrund. - Gegeben sei eine endliche,
äquidistante Folge von Stützstellen (mit beschränktem
Wertebereich). Gegeben sei weiter ein kubischer Spline,
der diese Folge interpoliert.

Jetzt betrachten wir die n-te Stützstelle, die "irgendwo
in der Mitte" der Folge liegen möge. Die ersten Ableitungen
der beiden interpolierenden Funktionen, die in dieser
Stützstelle zusammenstoßen, stimmen ja lt. Definition
überein. Um die Koeffizienten der Polynome tatsächlich
angeben zu können, muss ich aber das gesamte Gleichungssystem
lösen; es gibt m.W. keine Möglichkeit, die Koeffizienten
durch scharfes Ansehen der umliegenden Stützstellen zu
bestimmen.

Jetzt meine Frage: Welchen Fehler mache ich, wenn ich den
Wert dieser ersten Ableitung in der n-ten Stützstelle
einfach vorschreibe - nämlich anhand des zentralen
Differenzenquotienten (f(n+1)-f(n-1))/(2*h) ?

Dieser Wert gilt ja für beide Polynome, die Glattheit sollte
also erhalten bleiben wie bisher.

Geht das überhaupt so? Wenn nein - wo liegt mein Denkfehler?

[Sebastian (Gast)]

Possetitjel schrieb:
> Um die Koeffizienten der Polynome tatsächlich
> angeben zu können, muss ich aber das gesamte Gleichungssystem
> lösen; es gibt m.W. keine Möglichkeit, die Koeffizienten
> durch scharfes Ansehen der umliegenden Stützstellen zu
> bestimmen.
Du brauchst nur ein paar Stützstellen anschauen. Bei einem kubischen 
Spline ungefähr 3 Knotenpunkte in jede Richtung (kann auch einer mehr 
oder weniger sein, weiß nicht mehr so genau).
Hat mich damals, vor knapp 15 Jahren, in der Vorlesung beeindruckt, dass 
es Algorithmen gibt, die die Interpolation (sogar least squares 
approximation) mit konstantem Speicherverbrauch machen (wenn man die 
Eingabe der unbegrenzt vielen Stützstellen nicht als Speicher sieht, 
sondern sie sortiert sequentiell einliest, ebenso für die unbegrenzt 
vielen Koeffizienten, die man ausgibt).
Hing damit zusammen, dass im Gleichungssystem nur in einem schmalen Band 
um die Diagonale der Matrix keine Nullen sind.
Ging irgendwie mit Householder-Transformationen.
Buch: Lawson-Hanson

Nur um Missverständnisse zu vermeiden:
Unterschied Stützstellen/Knotenpunkte:
Die Knotenpunkte sind die, wo der Spline zusammengesetzt ist.
Die Stützstellen sind die Stellen, wo du beim Interpolieren durch 
willst.
Ein kubischer Spline kann viele Knotenpunkte haben. Und damit es dann 
eindeutig wird, braucht man natürlich noch mehr Stützstellen.

Du hast Recht mit deiner Vermutung, wenn du mit "ein kubischer Spline" 
nur ein einzelnes Stück (ein Polynom 3. Grades, nicht zusammengesetzt) 
meinst.

> Die ersten Ableitungen der beiden interpolierenden Funktionen, die in dieser 
Stützstelle zusammenstoßen, stimmen ja lt. Definition überein.
Nicht unbedingt. Wenn du willst, dass sie nicht übereinstimmen, kannst 
du mehrere Knotenpunkte an die gleiche Stelle legen.
Wenn du das nicht tust, dann - ja.

> Geht das überhaupt so?
Dem Gefühl nach, ja.

[Possetitjel (Gast)]

Sebastian schrieb:

> Du brauchst nur ein paar Stützstellen anschauen. Bei einem
> kubischen Spline ungefähr 3 Knotenpunkte in jede Richtung
> (kann auch einer mehr oder weniger sein, weiß nicht mehr
> so genau). [...]
> Hing damit zusammen, dass im Gleichungssystem nur in einem
> schmalen Band um die Diagonale der Matrix keine Nullen sind.
> Ging irgendwie mit Householder-Transformationen.
> Buch: Lawson-Hanson

Vielen Dank für Deine Hinweise. - Ich beziehe mein solides
Viertelwissen aus H.R. Schwarz "Numerische Mathematik". Dort
werden, obwohl das Buch ansonsten ein Muster an Klarheit in
der Darstellung ist, Splines etwas stiefmütterlich behandelt.

Manches habe ich mir vielleicht auch nur falsch eingeprägt;
habe das Buch im Moment nicht da und kann also nicht nachsehen.

> Nur um Missverständnisse zu vermeiden:
> Unterschied Stützstellen/Knotenpunkte:
> Die Knotenpunkte sind die, wo der Spline zusammengesetzt
> ist. Die Stützstellen sind die Stellen, wo du beim
> Interpolieren durch willst.

Ah. Danke, wusste ich nicht.

>> Die ersten Ableitungen der beiden interpolierenden Funktionen,
>> die in dieser Stützstelle zusammenstoßen, stimmen ja lt.
>> Definition überein.
>
> Nicht unbedingt. Wenn du willst, dass sie nicht übereinstimmen,
> kannst du mehrere Knotenpunkte an die gleiche Stelle legen.
> Wenn du das nicht tust, dann - ja.

Da scheint der Hase im Pfeffer zu liegen.
Schwarz diskutiert in seinem Buch - soweit ich mich erinnere - nur
Splines, bei denen Stützstellen und Knotenpunke zusammenfallen und
außerdem die Ableitungen benachbarter Polynome übereinstimmen. Mir
war nicht klar, dass diese Festlegungen nicht zwingend sind, sondern
nur eine von vielen Möglichkeiten ist.

Die Wikipädie liefert unter dem Stichwort "Kubisch Hermitesche
Splines" auch Aussagen zur Verwandschaft zu den kubischen
Bezierkurven; das kommt dem, was ich suche, schon ziemlich nahe.

Danke für Deinen Input; das hilft mir weiter.