[WS] Spline-Interpolation - Theorie

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Spline-Interpolation - Theorie
Gliederung

  1. Definitionen

  2. Lineare Splines

  3. Quadratische Splines

    Beweis der Regularität einer strikt diagonaldominaten Tridiagonalmatrix

  4. Kubische Splines

  5. Lokale Splines

  6. Spline-Vektorraum

    6a. Eine erste Basis

    6b. Und noch eine Basis

    6c. B-Splines - Teil 1

    6d. B-Splines - Teil 2

    6e. B-Splines - Teil 3

    6f. Ableitung von B-Splines

  7. Berechnung des interpolierenden B-Splines

    7a. linearer B-Spline

    7b. quadratischer B-Spline

    7c. kubischer B-Spline

  8. Ausblick
tigerbine Auf diesen Beitrag antworten »
1. Definitionen
Bei der Betrachtung der Interpolation ([Workshop]) durch ein Polynom wurden 2 Abschätzungen, je nach Knotenwahl, des Interpolationsfehlers erhalten. Es wurden dabei 2 Probleme offensichtlich:

  • i.A. keine Konvergenz , siehe Runges Beispiel

  • Langsame Konvergenzgeschwindigkeit,


Es soll nun ein Verfahren gezeigt werden, das diese Probleme beseitigt.


Experimentelle Konvergenzgeschwindigkeit









Intervall, Gitter und Knoten









Bitte die Doppelverwendung der Variable h beachten. Ergibt sich aus den Quellen. In den Fehlerabschätzungen ist die Maschenweite gemeint!



Spline

Jede Funktion heißt Spline, wenn die Restriktionen, Polynome sind. Splines sind also stückweise polynomiale Funktionen, mit den Knoten als Bruchstellen.

Spline-Ordnung

Ein Spline hat die Ordnung k, wenn gilt:




Spline-Vektorräume

Die Splines spannen den Raum auf. Dabei bezeichnet k die Ordnung der Splines und t ist der Knotenvektor.

Unstetigkeit

Es gilt , was aufgrund der Polynomgestalt von unproblematisch ist. Es gilt aber nicht notwendigerweise

Glattheit

Das Gitter hat n Teilintervalle. Ein Spline der Ordung k hat also freie Parameter. Nun soll erreicht werden, dass ein Spline - mal stetig differenzierbar ist. So erhalten wir für jeden der (n-1) inneren Knoten - Bedingungen. Insgesamt also:




Vektorraum der -mal stetig diff'baren Splines

Die Menge der Splines der Ordnung k bilden den Vektorraum mit der Dimension:




Im den folgenden Beiträgen soll gelten:








Interpolationsknoten

Es wird sich herausstellen, dass je nach Ordnung des Splines - gerade oder ungerade - die Interpolationsknoten von den Splineknoten abweichen können.
tigerbine Auf diesen Beitrag antworten »
2. Lineare Splines


Interpolationsaufgabe









Die Lösungen, also die Restriktionen, sind in diesem Fall einfach zu bestimmen. Für die Newton-Polynome gilt:






Fehlerabschätzung und Konvergenz

Für kann man auf die Abschätzung (9c) des Interpolationsfehlers zurückgreifen. Damit gilt in jedem Teilintervall mit 2 ( ="n") Interpolationsknoten:




Somit erhält man:



D.h. gleichmäßige Konvergenz von für für alle mit der Fehlerordnung .


Es sind auch Fehlerabschätzungen für nur stetige, aber nicht differenzierbare Funktionen f , möglich. Hierzu benötigt man das Stetigkeitsmodul und es kann die gleichmäßige Konvergenz von S gegen f gezeigt werden.
tigerbine Auf diesen Beitrag antworten »
3. Quadratische Splines



Splineknoten und Interpolationsknoten


Ein quadratischer, stetiger Spline mit den Splineknoten ist auf jedem Teilintervall ein quadratisches Polynom, das wieder mit bezeichnet werden soll.

Quadratische Polynome haben 3 Koeffizienten, sind also z.B. durch 3 paarweise verschiedene Interpolationsbedingungen eindeutig bestimmt. Nahe liegend wäre dies wie folgt zu realisieren:






Dieser Spline wäre zwar stetig in den Splineknoten, aber i.A. nicht differenzierbar in diesen.

Deswegen geht man hier einen anderen Weg. Man hat (n+1)-Splineknoten und n-Interpolationsknoten also:



Jetzt werden an den Splineknoten, keine Werte vorgeschrieben, sondern man versucht, die Werte an diesen Stellen so zu bestimmen, dass der Spline insgesamt differenzierbar wird. Dies gelingt wie folgt:








____________________________________________________



Für die benötigten 3n-Koeffizienten fügt man also noch 2 Bedingungen hinzu:





mit vorgegebenen Werten



Dividierte Differenzen für quadr. Splines

Damit erhält man bei der Anwendung der Newton-Form des Interpolationspolynoms folgendes Schema der dividierten Differenzen:



Damit erhält man für das IP:




Ableitungsbedingung (3.)






Daraus erhält man mit:









Formal vereinfacht schreibt man:




Lineares Gleichungssystem

Dies kan man als LGS der Form schreiben. Für die Matrix M gilt:



Die Matrix M ist strikt-Spalten-diagonaldominant, denn es gilt:





da

Aus dem Beweis im nächsten Abschnitt folgt daher die Existenz und Eindeutigkeit der Lösung des LGS und somit existiert der gesuchte quadratische Spline eindeutig.


Fehlerabschätzung

tigerbine Auf diesen Beitrag antworten »
Regularität von Tridiagonalmatrizen
1. Algorithmus zur Lösung von A = LR für Tridiagonalmatrizen (Doolittle + Crout)













2. Strikt diagonaldominante Tridiagonalmatrix

  • Zeilenweise:






  • Spaltenweise:








3. Regularität und Wohldefiniertheit

Sei A eine strikt Zeilen diagonaldominate Tridiagonalmatrix. Dann sind A und alle Hauptabschnittsmatrizen A[k] regulär und der in (1) definierte Algorithmus ist wohldefiniert.

Beweis: Induktion über j










Sei die Behauptung richtig für j, d.h.







(*)




Einsetzen liefert:




Umstellen:

(**)


Es gilt zu zeigen, dass gilt:






Abschätzungen (Dreiecksungleichungen):

(*)













Damit ist (**) wohl definiert und es gilt:

(**)






Wegen der strikt. Zeilen-Diagonaldominanz folgt:








Da die Regularität einer Matrix die Regularität ihrer transponierten Matrix impliziert, gilt der Satz auch für strikt Spalten-dominate Tridiagonalmatrizen.
tigerbine Auf diesen Beitrag antworten »
4. Kubische Splines



Stetigkeits- und Glattheitsbedingungen

Es sollen folgende Bedingungen erfüllt sein:










____________________________________________________



Da insgesamt 4n Freiheitsgrade vorhanden sind, müssen noch 2 Bedingungen hinzugefügt werden, um Eindeutigkeit zu erhalten.


Wahl der Eindeutigkeit


  • Natürlicher Spline



    Die Bedingung wird deswegen als natürlich bezeichnet, weil die zweite Ableitung im Wesentlichen die Krümmung einer Funktion darstellt. Daher hat dieser Spline die geringste Krümmung.

    Sie erweist sich allerdings als schlecht, da hier dann z.B. die Funktion nicht durch einen kubischen Spline reproduziert wird.

  • Periodischer Spline



  • Vollständiger Spline



    Sofern diese Werte bekannt sind, wird ein kubisches Polynom durch den Spline reproduziert.




Algorithmus zur Spline Berechnung

Ähnlich wie beim quadratischen Spline hat man bei der Berechnung wie folgt vorzugehen:

  1. Aufstellen der Hermite-Newton-Form der Restriktionen und






    Dabei bestimmt man die Koeffizienten (dividierte Differenzen) mit dem Neville-Hermite-Schema und setzt für die ersten Ableitungen die Variable . Damit sind die Bedingungen (1)-(3) umgesetzt.







  2. Gleichsetzen von (4) führt dann wieder auf ein LGS zur Bestimmung der Werte . Dabei ist die erzeugte Matrix wieder tridiagonal, diesmal aber strikt Zeilen-diagonaldominant. Daher ist auch diese Matrix regulär und das LGS eindeutig lösbar.

  3. Mit den vorgegebenen Werten und können die Restriktionen eindeutig bestimmt werden.



Dividierte Differenzen für kubische Splines

Damit erhält man bei der Anwendung der Newton-Hermite-Form des Interpolationspolynoms folgendes Schema der dividierten Differenzen:




Damit erhält man für das IP:





Und für das Interpolationspolynoms folgendes Schema der dividierten Differenzen:




Damit erhält man für das IP:



Ableitungsbedingung (4.)







Daraus erhält man:




Formal vereinfacht schreibt man:




Diese Zwischenergebnisse fassen wir zusammen:

Dies kann man als LGS der Form schreiben.




Die Matrix M ist strikt-Zeilen-diagonaldominant, denn es gilt:









Aus dem Beweis im vorherigen Abschnitt folgt daher die Existenz und Eindeutigkeit der Lösung des LGS und somit existiert der gesuchte kubische "Teil-Spline" eindeutig. Dabei werden wir nun - da ja noch 2 Bedingungen offen sind - die unterstrichenen Einträge noch überarbeiten und müssen für diese Zeilen dann auch die Dominanz erneut prüfen. Der Übersichtlichkeit halber wurde der Existenz und Eindeutigkeitsvermerk aber hier gesetzt.

Um das endgültige LGS aufstellen zu können benötigt man allerdings noch die Randbedingungen (siehe 4b), also die Werte für . Es ergibt sich somit:

Zwei weitere Bedingungen:

Natürlicher Spline

Aus den Forderungen erhält man mit (*):




Das setzen wir nun in den Ansatz (s.o.) ein:







Und erhalten somit die neuen Werte für das LGS:








Es muss nun jedoch wieder auf strikte Diagonaldominanz geprüft werden.






Für die nächsten beiden Fälle liegt dann eigentlich die Betrachtung Spline als Darstellung einer Funktion zu Grunde, nicht zu Interpolation einer Datenmenge.


Vollständiger Spline





Das setzen wir nun in den Ansatz (s.o.) ein:






Und erhalten somit die neuen Werte für das LGS








Wieder die Überprüfung der strikten Diagonaldominanz. Da die hier erhalten bleiben, muss nichts mehr gezeigt werden.


Fehlerabschätzung

Für vollständige kubische Splines lässt sich die folgende Fehlerordnung herleiten:

 
 
tigerbine Auf diesen Beitrag antworten »
5. Lokale Splines
Um kubische Splines zu berechnen, musste ein LGS gelöst werden. D.h. die einzelnen Restiktionen können nicht unabhängig voneinander berechnet werden. Nun sollen Splines behandelt werden, die intervallweise berechnet werden können.

Unter einem lokalen Spline - der Ordnung k - auf dem Gitter , versteht man einen Spline der Ordnung k, bei dem die einzelnen Restriktionen eindeutig allein aus Werten und Ableitungen in bestimmt werden können.



Lokal Linearer Spline

Die linearen Splines sind bereits stückweise durch die Vorgabe der Werte in den Randknoten von eindeutig bestimmt.


Lokal quadratischer Spline

Egal wie man hier die benötigten Interpolationsknoten wählt, wird man i.a. keinen Spline mehr erhalten.


Lokal kubischer Spline

Vorgabe von Funktionswerten und Werten der ersten Ableitung in den Splineknoten liefern einen lokalen - Spline.

Berechnung:



Dabei benötigen wir wieder die dividierten Differenzen, deren Gestalt wir aus 4. übernehmen können. Somit gilt:










Konvergenzverhalten

Insgesamt kann gleichmäßige Konvergenz für Splines der Ordnung 2k gezeigt werden. Dabei werden die Werte



gesetzt. Es ist dann
tigerbine Auf diesen Beitrag antworten »
6. Spline-Vektorraum
Bislang wurde mehr ein Augenmerk darauf gelegt, dass sich durch die Splinegestalt der interpolierenden Funktion ergebende Lineare Gleichungssystem zu lösen. Ganz am Anfang wurde erwähnt, dass auch Splines einen Vektorraum bilden. Es stellen sich sofort zwei Fragen:

  • Welche Dimension hat der Vektorraum?

  • Wie sieht eine Basis aus?


Wir wollen uns mit dem VR befassen. (siehe). Dabei haben die Restriktionen die Ordnung k, sind also Polynome vom Maximalgrad (k-1). Ferner soll der Spline an den Übergangen der Restriktionen (k-2)-mal stetig Differenzierbar sein, also maximale Glattheit besitzen. Das Gitter habe die Länge (n+1), es wird also das zu betrachtende Intervall [a,b] wie folgt unterteilt:

tigerbine Auf diesen Beitrag antworten »
6a. Eine erste Basis
k=1

Hier sind die Restriktionen also konstante Funktionen. Es ist daher eine nahe liegende Möglichkeit, die Splines bzgl folgender charakteristischen Funktionen anzugeben:




Diese Funktionen sind also nur auf einen der disjunkten Teilintervalle von 0 verschieden. Das sie somit eine Basis des bilden ist offensichtlich. Die Dimension dieses Raumes beträgt n.



Auf dem Intervall [0,4] mit äquidistanten Knoten würde diese Basis dann wie folgt aussehen:





k=2

Die Restriktionen sind nun lineare Funktionen. Schauen wir uns folgende Funktionen an für eine Zerlegung mit (n+1) Knoten an. Dabei hängen die Funktionen p von der Ordnung k ab, die Funktionen q von dem Gitter.








Zur Veranschaulichung wählen wir wieder das obige Gitter.
[attach]8837[/attach]

Dieses Mal soll die Basiseigenschaft nachgewiesen werden. Zunächst die lineare Unabhängigkeit. Dazu betrachten wir die Linearkombination, wobei 0 für die Nullfunktion stehen soll.



Diese Gleichung soll für alle erfüllt sein. Insbesondere muss dies dann auch auf dem ersten Intervall gelten. Dort bleibt nur noch diese Forderung übgrig, die Terme mit q verschwinden.





Aufgrund der linearen Unabhängigkeit der p-Polynome (Polynome aus mit unterschiedlichem Maximalgrad), liefert dies liefert die Forderung:



Damit reduziert sich die obige Forderung auf:





Der Trick liegt nun darin, spezielle Werte für t zu wählen. Dann ergibt sich



Aus der Definition der q Funktionen ergibt sich dass die hintern beiden Summanden verschwinden so wie die Forderung:



Wiederholte Argumentation mit liefert schließlich:



Und damit ist die lineare Unabhängigkeit der Polynome vom Typ p und q bewiesen. Ferner liegen diese Polynome offensichtlich in .

An dieser Stelle soll zu einem Allgemeinen Beweis für übergegangen werden. Die lineare Unabhängigkeit der n+(k-1) Polynome p und q läßt sich analog nachweisen. Es soll die Behauptung über die Dimension des Vektorraums gezeigt werden, woraus unmittelbar die Basiseigenschaft folgt. Bislang haben wir gezeigt:



Lässt sich nun jedes Element von als Linearkombination der Polynome p und q darstellen, so folgt und damit letztendlich die gewünschte Gleichheit:




Wählen wir nun beliebig, so sind die Restriktionen Polynome vom Maximalgrad (k-1). Die Restriktionen (der existierenden!) (k-1) Ableitung sind dann konstante Funktionen, es ist also . Für diesen Vektorraum haben wir oben die Basis (*) eingeführt. Diese Definition bringen wir nun mit den p und q zur Deckung. Dazu definieren wir die p auch noch allgemein.








Für die Ableitung der q gilt:



Somit läßt sich ein Vielfaches von als Differenz von jeweils 2 Funktionen der folgenden Menge schreiben:



[attach]8838[/attach]

Somit können wir schreiben:



Nun integrieren wir beide Seiten insgesamt (k-1)-mal, so folgt:



Dabei kann p offensichtlich durch Linearkombination aus den Polynomen gebildet werden, so dass wir insgesamt festhalten können (und damit die den Beweis geliefert haben)

tigerbine Auf diesen Beitrag antworten »
6b. Und noch eine Basis
Mit der eben eingeführten Basis konnten wir als den Nachweis der Dimension des Vektorraums liefern. Jedoch ist diese Basis für numerische Zwecke nicht geeignet. Es soll deswegen eine andere Basis hergeleitet werden, deren Basisvektoren jeweils nur auf einem kleinen Intervall von Null verschieden sind. Steigern wir wieder langsam die Dimension.

k=1



Für unsere Beispielzerlegung bedeutet dies bildlich folgendes.

[attach]8840[/attach]

Man erkennt sofort, dass in diesem Fall die Basis identisch ist mit der von der Funktion erzeugten im vorherigen Abschnitt. Erhöhen wir nun aber k, so sind die Wertemengen der vorherigen Basisfunktion allerdings nicht mehr beschränkt. Das wollen wir hier anders gestalten (Zerlegung der Eins). Ferner möchten wir die Teilintervalle, auf denen die Funktionswerte von 0 verschieden sind, möglichst klein halten (minimaler Träger).


k=2



Wir erkennen, dass die Träger hier schon länger (3 Knoten) sind als bei k=1 (2 Knoten). Das bedeutet, dass die Knoten auf dem Intervall [a,b] also nicht ausrechen, für die n+(1) benötigten Basisfunktionen. Wir müssen also das Gitter erweitern.

[attach]8865[/attach]
tigerbine Auf diesen Beitrag antworten »
6c. B-Splines - Teil 1
Die im letzten Abschnitt angedeutete Idee soll nun allgemein umgesetzt werden. Wir haben schon gesehen, dass die Funktionen p und q eine Basis des bilden.





Es lässt sich also jedes Element von als LK dieses Basispolynome darstellen.



Da wir uns später ja nur für die Interpolation einer Funktion auf dem Intervall [a,b] interessieren, suchen wir nur eine neue Basis. Ein darin liegender Splines s soll zunächst nur einem auf einem kleinen Teilintervall (Träger) von 0 verschieden sein. Damit ist in der Linearkombination von s sicherlich kein Polynom vom Typ p vorhanden.




Wie sieht es mit Typ q aus? Da s für alle verschwinden soll, folgt . Für verschwinden die auf dem Intervall . Somit bleibt:



Nun soll auch gelten . Damit ergibt aus der Definition von q (wo sind diese Funktionen von 0 verschieden!) sofort die Bedingung:



Nun benötigen wir den binomischen Lehrsatz. Damit können wir die Forderung umschreiben.



Nun ordnen wir die Summe um.



Damit steht auf der rechten Seite i Grunde die LK Polynome verschiedenen Grades zum Nullpolynom. Da diese linear unabhängig sind, können wir die äquivalente Forderung notieren:



Die Binomialkoeffizienten sind positiv, somit bleibt zum Schluss die Forderung



Da die paarweise verschiedenen Knoten bekannt sind, handelt es sich hier um ein homogenes LGS bestehend aus k Gleichungen für die (p+1) unbekannten . Was können wir über die Lösungen sagen? ( [WS] Polynominterpolation - Theorie ). Ziel ist es nun, p so zu bestimmen, dass wir eine nichttriviale Lösung erhalten, denn sonst wäre unser s die Nullfunktion.

Im Falle ist die zugehörige Matrix gerade die Vandermonde-Matrix, also regulär. D.h. wir erhalten nur nicht-triviale Lösungen, wenn gilt:



Ferner bestimmt p ja die Länge des Teilinvervalls , dass möglichst klein sein soll. Also gilt es auch p möglichst klein zu wählen. Daher macht man den Ansatz:





Wie sieht eine nichttriviale Lösung dieses Systems aus? Damit beschäftigen wir uns im nächsten post.
tigerbine Auf diesen Beitrag antworten »
6d. B-Splines - Teil 2
Aufgabe ist es nun Koeffizienten derart zu finden, dass gilt:




Stellen wir uns zunächst einer anderen Aufgabe. Wir definieren die Funktion:



Und statten unsere Knoten mit Funktionswerten aus, so dass uns der folgende Datensatz der Länge (k+1) vorliegt.



Wir können also durch diese Punkte eindeutig ein Interpolationspolynom vom Maximalgrad k legen. Dieses wollen wir uns bzgl. der Lagrangebasis notieren. Dabei passen wir die Indizies an den Datensatz an.



Eine Eigenschaft der Lagrange Basis ist, dass alle Basispolynome den gleichen Maximalgrad haben. Daher wollen wir uns so ein Basispolynom einmal genauer anschauen:



Die Monom-Darstellung würde wie folgt aussehen /beginnen:



Aufgrund der Eindeutigkeit des Interpolationspolynoms und der Konstruktion von f als Polynom vom Maximalgrad r<k ergibt sich die Identität:



Links liegt Schreibweise in Monom-Basis, rechts in Lagrange-Basis vor. Schreiben wir nun die rechte Seite auch in Monom-Schreibweise um, so ergibt der Vergleich der Koeffizienten des Basispolynoms



oder anders geschrieben:



Somit wären wir wieder am Anfang (*) angekommen und können nun eine Lösung angeben:





Mit dieser Lösung ist auch jedes Vielfache eine Lösung des homogenen Linearen Gleichungssystems. Wählt man nun den speziellen Vorfaktor so erhalten wir den gesuchten B-Spline



Der Träger ist . Der Spline hat den Grad (k-1).
tigerbine Auf diesen Beitrag antworten »
6e. B-Splines - Teil 3
Für k=1 erhalten wir die schon bekannten Splines.




Rekursionsformel




Träger

Der Träger des linken Terms ergibt sich aus den beiden Trägern der rechten Seite.




Zerlegung der Eins

Nun erklärt sich auch die gewählte Normierung. Somit erhält man eine Zerlegung der ein, d.h. es gilt:




Die Dreitermrekusion läßt erkennen, dass man so nicht genügend Basisvektoren erhalten wird. Daher erweitert man das Gitter allgemein auf




Beweise werden in diesem Absatz nicht mehr geliefert, vielmehr wollen wir uns noch mit der "Gestalt" der B-Splines auseinandersetzten.



Wir betrachten konkret das Gitter

k=1







[attach]8867[/attach]


k=2









[attach]8868[/attach]


k=3












[attach]8873[/attach]

Graphisch reicht es hier (äquidistante Zerlegung) also aus, einen Spline der Basis zu berechnen. Die anderen Ergeben sich dann durch Verschiebung längs der x-Achse. Als letztes wollen wir uns kubische Basissplines anschauen.

[attach]8874[/attach]

Und hier die aufgeschlüsselte Variante eines Basis-Splines:

tigerbine Auf diesen Beitrag antworten »
6f. Ableitungen von B-Splines
Wir wissen nun, dass der gesuchte Spline die folgende Darstellung besitzen wird:



Allerdings wissen wir noch nicht, wie wir Koeffizienten a bestimmen können, damit der Spline den zu beginn dieses WS geforderten Eigenschaften genügt. Bei einem linearen Spline ist dies noch einfach, da nur Interpolation an den Spline-Knoten gefordert wird (Beispiel). Wie setzen wir aber die Glattheitsbedingungen um?

Das führt uns zum einen zu der Frage, wie man die Ableitung eines Splines in der obigen Darstellung berechnet.

Da es sich um stückweise polynomiale Funktionen handelt, ist die Ableitung eines Splines Element von und besetzt bezüglich der bereits bekannten Basis die Darstellung



Dabei gilt für die neuen Koeffizienten:



Für die Berechnung der Ableitung gibt es wieder eine Drei-Term-Rekursion:





Wie sieht es mit der zweiten Ableitung aus?






Eine andere Frage ist, wie glatt sind eigentlich die durch die Rekursionsformel konstruierten Splines?

Die Basissplines mit einem Träger der Länge k sind (k-2)-fach stetig differenzierbar, also Element von . D.h. zum Beispiel dass die quadratischen Basissplines einmal stetig differenzierbar in den Knoten sind.


Kann man den Träger des interpolierenden Splines auch auf das Intervall [a,b] beschränken?

Ja, dann sind aber Mehrfachknoten notwendig, die sich auf die Differenzierbarkeit in des Splines in diesen Knoten auswirken. In einem m-fachen Knoten ist ein B-Spline der Ordnung k nur noch Element von . Für einen einfachen Knoten (m=1) erhalten wir also wieder obige Glattheit.

In der Rekursionsformel zur Konstruktion der B-Splines treten allerdings dividierte Differenzen auf, die nun im Nenner gleich 0 werden. Daher müssen wir diese Formel anpassen. Daher zieht man die Brüche heraus, im Zähler steht 1, im Nenner die Differenz. Man definiert eine Funktion , die im Falle der Knotengleichheit den Wert 0 annehmen soll.
tigerbine Auf diesen Beitrag antworten »
7a. Interpolierender linearer Spline
Gesuch ist ein linearer Spline, der eine Funktion f auf dem Intervall in den Knoten interpoliert ( und sind 2-fach Knoten). In jedem Intervall sind nur die Basissplines von Null verschieden. Als einzige Forderung an den gesuchten linearen Spline s stellen wir die Stetigkeit in den Splineknoten. Der Träger eines linearen Basisspline beträgt zwei Knotenintervalle .


Die Dimension des . Damit ergibt sich für den gesuchten Spline als LK der Basisvektoren:



Übertragen wir nun die Interpolationsforderung in ein lineares Gleichungssystem:




Schauen wir noch einmal in die Definition der Basissplines, so löst sich hier alles in Wohlgefallen auf, da die Einträge in der Matrix nur aus Nullen und Einsen besteht.



Somit lautet die Lösung:

tigerbine Auf diesen Beitrag antworten »
7b. Interpolierender quadratischer B-Spline
Hier stellen wir an den Spline folgende Anforderrungen (siehe Anfang)

Zitat:








____________________________________________________



Für die benötigten 3n-Koeffizienten fügt man also noch 2 Bedingungen hinzu:





mit vorgegebenen Werten



In jedem Intervall sind nur die Basissplines von Null verschieden. Von den quadratischen Splines fordern also Stetigkeit in den Splineknoten und Interpolation an den Stellen r. Der Träger eines Quadratischen Basisspline beträgt drei Knotenintervalle .

Die Dimension des . Damit ergibt sich für den gesuchten Spline als LK der Basisvektoren:




Hier wollen wir nun einmal den Ansatz verfolgen Mehrfachknoten am Rand des Intervalls [a,b] zu verwenden. Damit hält man den Träger des interpolierenden Splines minimal. Allerdings verliert man am Rande die Glattheit des Splines. Da wir hier aber nur auf an den inneren Splineknoten bestehen, hat dies keine Bedeutung. Die Wahl von Interpolationsstellen, die von den Splineknoten abweichen, begründen wir in diesem Falle mit dem Satz von Schoenberg und Whitney (siehe Anhang). Dann ist das erhaltene LGS eindeutig lösbar, insbesondere die Matrix regulär.



Insbesondere ist wieder die Zeilensumme der Matrix gleich 1.
tigerbine Auf diesen Beitrag antworten »
7c. Kubische Splineinterpolation
Zitat:

Stetigkeits- und Glattheitsbedingungen

Es sollen folgende Bedingungen erfüllt sein:










____________________________________________________



Da insgesamt 4n Freiheitsgrade vorhanden sind, müssen noch 2 Bedingungen hinzugefügt werden, um Eindeutigkeit zu erhalten.


Wahl der Eindeutigkeit



* Natürlicher Spline



Die Bedingung wird deswegen als natürlich bezeichnet, weil die zweite Ableitung im Wesentlichen die Krümmung einer Funktion darstellt. Daher hat dieser Spline die geringste Krümmung.

Sie erweist sich allerdings als schlecht, da hier dann z.B. die Funktion nicht durch einen kubischen Spline reproduziert wird.

* Periodischer Spline



* Vollständiger Spline



Sofern diese Werte bekannt sind, wird ein kubisches Polynom durch den Spline reproduziert.


Wir haben n+3 Unbekannte, aber nur n+1 Interpolationsstellen. Die restlichen 2 Bedingungen sollen wie am Anfang unter den Namen "natürlicher" bzw. "vollständiger" Spline zusammengefasst werden. Wir wollen hier einen Minimalen Gesamtträger verwenden, daher sind und 4-fach Knoten. Gesucht ist am Ende



  • vollständiger kubischer B-Spline



    Die Ableitung eines kubischen Splines:



    Dabei gilt für die neuen Koeffizienten:



    Aufgrund der Werte der B-Splines an den Mehrfachknoten:





    Somit ergeben sich die erste und letzte Zeile des LGS wie folgt:





    Die restlichen Zeilen ergeben sich aus den Werten der B-Splines an den Interpolationsstellen (siehe lin, quad B-Spline). Diese werden mit der Drei-Term-Rekursionsformel berechnet.


  • natürlicher kubischer B-Spline




    Die zweite Ableitung eines kubischen Splines:



    Dabei gilt für die neuen Koeffizienten:



    Dies wollen wir nun auf die gesuchten Koeffizienten c zurückführen.



    Aufgrund der Werte der B-Splines an den Mehrfachknoten:





    Somit ergeben sich die erste und letzte Zeile des LGS wie folgt:





    Die restlichen Zeilen ergeben sich aus den Werten der B-Splines an den Interpolationsstellen. Diese werden mit der Drei-Term-Rekursionsformel berechnet.
tigerbine Auf diesen Beitrag antworten »
8. Ausblick
Wie auch bei der numerischen Integration wird man beim letztendlichen Einsatz der Splines die Wahl des Gitters dynamisch gestalten, vor allem wenn man die Funktion f kennt. Man bedient sich also einer Adaption, um auf die Gestalt der Funktion f einzugehen.

Konkrete Berechnung von Splines finden sich im [Workshop-Spline-Interpolation-Beispiele]


Des weiteren schließen sich hier folgende Fragen an:

Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »