kubische Spline Interpolation

06.09.2007, 12:00

dominik.rauch

kubische Spline Interpolation

Hallo Jungs und Mädels,

ich versuche gerade mit folgenden Werten eine kubische Spline Interpolation durchzuführen.

0,00 23,60
5,00 24,35
10,00 22,20

Komme hierbei aber nicht wirklich weiter.
Es wäre nett wenn mir jemand einen Tipp geben könnte,
wie ich so etwas anstellen soll.

MfG

Dominik

06.09.2007, 12:45

tigerbine

Auf diesen Beitrag antworten »

RE: kubische Spline Interpolation
Ja nun. Mehr als 3 Knoten hast Du ja nicht genannt.

$\begin{eqnarray*} x_0=0.00,~y_0 = 23.60 \end{eqnarray*}$

$\begin{eqnarray*} x_1=5.00,~y_1 = 24.35 \end{eqnarray*}$

$\begin{eqnarray*} x_2=10.00,~y_2= 22.20 \end{eqnarray*}$

Welcher kubische Spline solle es denn sein?

06.09.2007, 12:57

dominik.rauch

Auf diesen Beitrag antworten »

RE: kubische Spline Interpolation
Es sind eigentlich mehrere Knoten. Mir würde allerdings ein Rechenbeispiel für die zwei genannten Polynome reichen reichen.

Ich habe schon selbst gerechnet allerdings stimmen meine Ergebnisse für mit den Ergebnissen auf der folgender Website:

http://www.arndt-bruenner.de/mathe/scripts/kubspline.htm

nicht überein.

06.09.2007, 13:00

tigerbine

Auf diesen Beitrag antworten »

RE: kubische Spline Interpolation
Ohne dass Du konkreter wirst, z.B. welcher Typ vom kub Spline, werde ich Dir nicht helfen können. Die Brünner Seiten sind eigentlich gut.

Zeig doch mal deine Rechnung.

06.09.2007, 13:20

dominik.rauch

Auf diesen Beitrag antworten »

RE: kubische Spline Interpolation
In unserem Fall gilt ja $\begin{eqnarray*} n=2 \end{eqnarray*}$ (2 Abschnitte)
Somit muss $\begin{eqnarray*} c1=c2=0 \end{eqnarray*}$ Gelten.

Es müsste sich also folgendes allgemeines Gleichungssystem ergeben.

$\begin{eqnarray*} c1 \end{eqnarray*}$
$\begin{eqnarray*} 4h.....\frac{6}{h}(y2-2y1+y0) \end{eqnarray*}$

ergeben.

Da der Abstand zwischen den einzelnen Knoten 0,5 LE beträgt
entspricht h=0,5.

Mit den gegeben Punkten errechnet sich für c1 also ein Wert
von -8,7

06.09.2007, 13:24

dominik.rauch

Auf diesen Beitrag antworten »

RE: kubische Spline Interpolation
Weiter gilt ja: $\begin{eqnarray*} ai=yi \end{eqnarray*}$

$\begin{eqnarray*} di=(2ci+1-ci) \end{eqnarray*}$

und

$\begin{eqnarray*} bi=(2yi+1-yi)-\frac{1}{2}ci*0,5-\frac{1}{6}di*0,25 \end{eqnarray*}$

06.09.2007, 13:28

tigerbine

Auf diesen Beitrag antworten »

RE: kubische Spline Interpolation
Willst Du meine Frage nicht verstehen? Welcher Typ von kubischen Spline

Wir brauchen 2 Polynome vom Max-Grad 3. Das macht 2*4 = 8 Unbekannte. Ich hatte es auch schon verlinkt.

Zitat:

Stetigkeits- und Glattheitsbedingungen

Es sollen folgende Bedingungen erfüllt sein:

$\begin{eqnarray*} \text{(4a)} \end{eqnarray*}$

$\begin{eqnarray*} 1. \quad S(t_j)=f_j \qquad \qquad \qquad \quad \qquad \qquad j = 0,2,...,n \qquad \quad \text{Interpolationsbedingung 1} \end{eqnarray*}$

$\begin{eqnarray*} 2. \quad R_{j-1}(t_j) = R_j(t_j)=:u_j \qquad \qquad j = 1,2,...,n-1 \quad \text{Stetigkeit in den S-Knoten} \end{eqnarray*}$

$\begin{eqnarray*} 3. \quad R'_{j-1}(t_j) = R_j'(t_j)=:s_j \qquad \qquad j = 1,2,...,n-1 \quad \text{1x stetig differenzierbar in den S-Knoten} \end{eqnarray*}$

$\begin{eqnarray*} 4. \quad R''_{j-1}(t_j) = R_j''(t_j) \quad \qquad \qquad \qquad j = 1,2,...,n-1 \quad \text{2x stetig differenzierbar in den S-Knoten} \end{eqnarray*}$
____________________________________________________

$\begin{eqnarray*} - \qquad \qquad 4n-2 \quad \text{Bedingungen} \end{eqnarray*}$

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

06.09.2007, 13:41

dominik.rauch

Auf diesen Beitrag antworten »

Richtig

Woraus wir dann folgende Gleichung erhalten:

$\begin{eqnarray*} h_i c_i+2(h_(i+1)+h_i ) c_(i+1)+h_(i+1) c_(i+2)=6(\frac{y_i+_2-y_i+_1}{h_i+_1}+\frac{y_i+_1-y_i}{h_i}) \end{eqnarray*}$

06.09.2007, 13:42

tigerbine

Auf diesen Beitrag antworten »

Was heißt hier richtig. Erstaunt1

Kannst oder willst du meine Frage nicht beantworten?

06.09.2007, 13:46

dominik.rauch

Auf diesen Beitrag antworten »

Jetzt verstehe ich: Natürlicher kubischer Spline

06.09.2007, 13:49

Dual Space

Auf diesen Beitrag antworten »

RE: kubische Spline Interpolation

Zitat:

Original von dominik.rauch
Ich habe schon selbst gerechnet allerdings stimmen meine Ergebnisse für mit den Ergebnissen auf der folgender Website:

http://www.arndt-bruenner.de/mathe/scripts/kubspline.htm

nicht überein.

Ist nicht verwunderlich. Tigerbine hat dir schon erklärt, dass bei nur 3 Knoten noch Freiheitsgrade übrig sind. Somit gibt es beliebig viele kubische Splines, die durch diese Punkte gehen.

06.09.2007, 13:52

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Wahl der Eindeutigkeit

$\begin{eqnarray*} \text{(4b)} \end{eqnarray*}$

* Natürlicher Spline

$\begin{eqnarray*} S''(t_0) = R_0''(t_0) = 0 \text{ und } S''(t_n) = R_{n-1}''(t_n) = 0 \end{eqnarray*}$

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

Finally... Bruenner bietet die Möglichkeit, die zweite Ableitung einzugeben. Hast Du da alles korrekt gemacht?

*In die Mittagspause geh*

http://www.smileygarden.de/smilie/Food/essen31-001.gif

06.09.2007, 13:54

dominik.rauch

Auf diesen Beitrag antworten »

RE: kubische Spline Interpolation
Stimmt schon aber wenn ich eben wie auf der Website beschrieben folgende Bedingungen erfülle nämlich:

Die zweite Ableitung des Splines am Anfangs- und Endpunkt wird Null gesetzt. Das bewirkt, dass der Spline eine minimale Gesamtkrümmung hat.

Die erste Ableitung am Anfangs- und Endpunkt wird vorgegeben.

Die 1. und 2. Ableitung sowie die eigentlichen Werte sollen am Anfangs- und Endpunkt gleich sein.

müsste ich doch auf die gleichen Ergebnisse kommen.

06.09.2007, 21:28

tigerbine

Auf diesen Beitrag antworten »

Probe bruenner

Zitat:

bruenner
x aus [0; 5]

S0(x) = -29/5000·x^3 + 59/200·x + 118/5
= -29/5000·x^3 + 59/200·x + 118/5

x aus [5; 10]

S1(x) = 29/5000·(x-5)^3 - 87/1000·(x-5)^2 - 7/50·(x-5) + 487/20
= 29/5000·x^3 - 87/500·x^2 + 233/200·x + 443/20

****************************************************
x aus [0; 5]

S0(x) = -0,0058x^3 + 0,295x + 23,6
= -0,0058x^3 + 0,295x + 23,6

x aus [5; 10]

S1(x) = 0,0058(x-5)^3 - 0,087(x-5)^2 - 0,14(x-5) + 24,35
= 0,0058x^3 - 0,174x^2 + 1,165x + 22,15

Mal schauen, ob das stimmt.

$\begin{eqnarray*} R_0(x)=-0.0058x^3 + 0.295x + 23.6 \end{eqnarray*}$

$\begin{eqnarray*} R_0'(x)=-0.0174x^2 + 0.295 \end{eqnarray*}$

$\begin{eqnarray*} R_0''(x)=-0.0348x \end{eqnarray*}$

$\begin{eqnarray*} R_0(0) = 23.6,~R_0(5) =24.35 \end{eqnarray*}$

$\begin{eqnarray*} R_0'(5)=-0.14 \end{eqnarray*}$

$\begin{eqnarray*} R_0''(0)=0 \end{eqnarray*}$

$\begin{eqnarray*} R_1(x)=0.0058x^3 - 0.174x^2 + 1.165x + 22.15 \end{eqnarray*}$

$\begin{eqnarray*} R_1'(x)=0.0174x^2 -0.348x+1.165 \end{eqnarray*}$

$\begin{eqnarray*} R_1''(x)=0.0348x-0.348 \end{eqnarray*}$

$\begin{eqnarray*} R_1(5) = 24.35 \end{eqnarray*}$

$\begin{eqnarray*} R_1'(5)=-0.14 \end{eqnarray*}$

$\begin{eqnarray*} R_1''(10)=0 \end{eqnarray*}$

to be continued

06.09.2007, 23:49

tigerbine

Auf diesen Beitrag antworten »

Newton-Darstellung
Wie würde das in der Newton-Form aussehen:

$\begin{eqnarray*} R_0(x)=f_{0,0}+f_{0,1}\cdot (x-0) +f_{0,2}\cdot (x-0)^2 + f_{0,3}\cdot(x-0)^2(x-5) \end{eqnarray*}$

$\begin{eqnarray*} R_0(x)=f_{0,0}+f_{0,1}\cdot x +f_{0,2}\cdot x^2 + f_{0,3}\cdot x^3- 5 \cdot f_{0,3}\cdot x^2 \end{eqnarray*}$

$\begin{eqnarray*} R_0(x)=f_{0,3}\cdot x^3 + (f_{0,2} - 5\cdot f_{0,3})\cdot x^2 +f_{0,1}\cdot x + f_{0,0} \end{eqnarray*}$

$\begin{eqnarray*} R_0(x)=-0.0058x^3 + 0.295x + 23.6 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,0} = 23.6 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,1} = 0.295 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,2} = -0.029 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,3} = -0.0058 \end{eqnarray*}$

$\begin{eqnarray*} R_1(x)=f_{0,0}+f_{0,1}\cdot (x-5) +f_{0,2}\cdot (x-5)^2 + f_{0,3}\cdot(x-5)^2(x-10) \end{eqnarray*}$

$\begin{eqnarray*} R_1(x)=f_{0,0}+f_{0,1}\cdot x-f_{0,1}\cdot5 + f_{0,2}\cdot x^2-10 \cdot f_{0,2}\cdot x + f_{0,2}\cdot 25 + f_{0,3}\cdot (x^3-20x^2+125x-250) \end{eqnarray*}$

$\begin{eqnarray*} R_1(x)=f_{0,3}\cdot x^3 + (f_{0,2}-20\cdot f_{0,3})x^2 + (f_{0,1} - 10 \cdot f_{0,2} + 125 \cdot f_{0,3})\cdot x +(f_{0,0}-5\cdot f_{0,1} + 25\cdot f_{0,2} - 250 \cdot f_{0,3}) \end{eqnarray*}$

$\begin{eqnarray*} R_1(x)=0.0058x^3 - 0.174x^2 + 1.165x + 22.15 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,0} =24.35 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,1} = -0.14 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,2} = -0.058 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,3} = 0.0058 \end{eqnarray*}$

07.09.2007, 02:40

tigerbine

Auf diesen Beitrag antworten »

Die Berechnung
Datensatz

$\begin{eqnarray*} t_0=~0, \quad f(t_0)=23.60 \end{eqnarray*}$

$\begin{eqnarray*} t_1=~5, \quad f(t_1)=24.35 \end{eqnarray*}$

$\begin{eqnarray*} t_2=10, \quad f(t_2)=22.20 \end{eqnarray*}$

$\begin{eqnarray*} \vartriangle f_0 =+0.75 \end{eqnarray*}$

$\begin{eqnarray*} \vartriangle f_1 =-2.15 \end{eqnarray*}$

$\begin{eqnarray*} \vartriangle t_0 =5 \end{eqnarray*}$

$\begin{eqnarray*} \vartriangle t_1 =5 \end{eqnarray*}$

$\begin{eqnarray*} \frac{\vartriangle f_0}{\vartriangle t_0} = +0.15 \end{eqnarray*}$

$\begin{eqnarray*} \frac{\vartriangle f_1}{\vartriangle t_1} = -0.43 \end{eqnarray*}$

$\begin{eqnarray*} s_0 &&= 1.5 \cdot \frac{\vartriangle f_0}{\vartriangle t_0} - 0.5 \cdot s_1 \\&& = 0.225 - 0.5 \cdot s_1 \end{eqnarray*}$

$\begin{eqnarray*} s_2 &&= 1.5 \cdot \frac{\vartriangle f_{1}}{\vartriangle t_{1}} - 0.5 \cdot s_{1} \\&& =-0.645-0.5\cdot s_1 \end{eqnarray*}$

$\begin{eqnarray*} \vartriangle t_j\cdot s_{j-1}+2(\vartriangle t_{j-1} + \vartriangle t_j)\cdot s_j + \vartriangle t_{j-1}\cdot s_{j+1} = 3(\frac{\vartriangle f_j}{\vartriangle t_j}\vartriangle t_{j-1} + \frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}} \vartriangle t_j) \end{eqnarray*}$

$\begin{eqnarray*} \beta_1 \cdot s_0 = \vartriangle t_1 \cdot (0.225 - 0.5\cdot s_1) = 1.125 - 2.5 \cdot s_1 \end{eqnarray*}$

$\begin{eqnarray*} \gamma_1 \cdot s_2 = \vartriangle t_0 \cdot (-0.645 - 0.5\cdot s_1) = -3.225 - 2.5 \cdot s_1 \end{eqnarray*}$

$\begin{eqnarray*} \alpha_1 =2(\vartriangle t_0 +\vartriangle t_1) = 20 \end{eqnarray*}$

$\begin{eqnarray*} y_1=3(\frac{\vartriangle f_1}{\vartriangle t_1}\vartriangle t_{0} + \frac{\vartriangle f_{0}}{\vartriangle t_{0}} \vartriangle t_1)=-4.2 \end{eqnarray*}$

$\begin{eqnarray*} \hat \alpha_1 = \alpha_1 - 2.5 - 2.5 = 15 \end{eqnarray*}$

$\begin{eqnarray*} r_1 = y_1 - 1.125 + 3.225 = -2.1 \end{eqnarray*}$

Nun haben wir es geschafft. Es lassen sich nun alle Größen berechnen.

$\begin{eqnarray*} s_1 = -\frac{2.1}{15} = -0.14 \end{eqnarray*}$

$\begin{eqnarray*} s_0 = +0.295 \end{eqnarray*}$

$\begin{eqnarray*} s_2 = -0.575 \end{eqnarray*}$

Zitat:

$\begin{eqnarray*} R_{j}(t) = f_{j}+s_{j} \cdot (t-t_{j}) + \frac{\frac{\vartriangle f_{j}}{\vartriangle t_{j}} - s_{j}}{\vartriangle t_{j}}(t-t_{j})^2 + \frac{s_{j+1} + s_{j} -2\frac{\vartriangle f_{j}}{\vartriangle t_{j}}}{\vartriangle t_{j}^2}\cdot (t-t_{j})^2(t-t_{j+1}) \end{eqnarray*}$

Erste Restriktion

$\begin{eqnarray*} f_{0,0} = f(t_0) = 23.60 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,1} = s_0 = 0.295 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,2} =\frac{\frac{\vartriangle f_{0}}{\vartriangle t_{0}} - s_{0}}{\vartriangle t_{0}} =-0.029 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,3} =\frac{s_{1} + s_{0} -2\frac{\vartriangle f_{0}}{\vartriangle t_{0}}}{\vartriangle t_{0}^2}=-0.0058 \end{eqnarray*}$

Zweite Restriktion

$\begin{eqnarray*} f_{0,0} = f(t_1) = 24.35 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,1} = s_1 = -0.14 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,2} =\frac{\frac{\vartriangle f_{1}}{\vartriangle t_{1}} - s_{1}}{\vartriangle t_{1}} =-0.058 \end{eqnarray*}$

$\begin{eqnarray*} f_{0,3} =\frac{s_{2} + s_{1} -2\frac{\vartriangle f_{1}}{\vartriangle t_{1}}}{\vartriangle t_{1}^2}=0.0058 \end{eqnarray*}$

Und damit schließt sich der Kreis. Der Rest steht ja schon im vorherigen Post.

07.09.2007, 02:42

tigerbine

Auf diesen Beitrag antworten »

Für größere Datensätze

Zitat:

Workshop in Progress

$\begin{eqnarray*} k = 4 \text { und } R_j \in \Pi_3 \end{eqnarray*}$

Stetigkeits- und Glattheitsbedingungen

Es sollen folgende Bedingungen erfüllt sein:

$\begin{eqnarray*} \text{(4a)} \end{eqnarray*}$

$\begin{eqnarray*} 1. \quad S(t_j)=f_j \qquad \qquad \qquad \quad \qquad \qquad j = 0,2,...,n \qquad \quad \text{Interpolationsbedingung 1} \end{eqnarray*}$

$\begin{eqnarray*} 2. \quad R_{j-1}(t_j) = R_j(t_j)=:u_j \qquad \qquad j = 1,2,...,n-1 \quad \text{Stetigkeit in den S-Knoten} \end{eqnarray*}$

$\begin{eqnarray*} 3. \quad R'_{j-1}(t_j) = R_j'(t_j)=:s_j \qquad \qquad j = 1,2,...,n-1 \quad \text{1x stetig differenzierbar in den S-Knoten} \end{eqnarray*}$

$\begin{eqnarray*} 4. \quad R''_{j-1}(t_j) = R_j''(t_j) \quad \qquad \qquad \qquad j = 1,2,...,n-1 \quad \text{2x stetig differenzierbar in den S-Knoten} \end{eqnarray*}$
____________________________________________________

$\begin{eqnarray*} - \qquad \qquad 4n-2 \quad \text{Bedingungen} \end{eqnarray*}$

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

Wahl der Eindeutigkeit

$\begin{eqnarray*} \text{(4b)} \end{eqnarray*}$

Natürlicher Spline

$\begin{eqnarray*} S''(t_0) = R_0''(t_0) = 0 \text{ und } S''(t_n) = R_{n-1}''(t_n) = 0 \end{eqnarray*}$

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

Sie erweist sich allerdings als schlecht, da hier dann z.B. die Funktion $\begin{eqnarray*} f(t) = t^3 \end{eqnarray*}$ nicht durch einen kubischen Spline reproduziert wird.
Periodischer Spline

$\begin{eqnarray*} S'(t_0) = S'(t_n) \text{ und } S''(t_0) = S''(t_n) \end{eqnarray*}$
Vollständiger Spline

$\begin{eqnarray*} s_0:=S'(t_0)=f'(t_0) \text{ und } s_n:=S'(t_n)=f'(t_n) \end{eqnarray*}$

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:

Aufstellen der Hermite-Newton-Form der Restriktionen $\begin{eqnarray*} R_{j-1} \end{eqnarray*}$ und $\begin{eqnarray*} R_{j} \end{eqnarray*}$

$\begin{eqnarray*} R_{j-1}(t)=f[t_{j-1}]+f[t_{j-1},t_{j-1}]\cdot(t-t_{j-1})+f[t_{j-1},t_{j-1},t_{j}]\cdot(t-t_{j-1})^2+f[t_{j-1},t_{j-1},t_{j},t_{j}]\cdot(t-t_{j-1})^2(t-t_{j}) \end{eqnarray*}$

$\begin{eqnarray*} R_{j}(t)=f[t_{j}]+f[t_{j},t_{j}]\cdot(t-t_{j})+f[t_{j},t_{j},t_{j+1}]\cdot(t-t_{j})^2+f[t_{j},t_{j},t_{j+1},t_{j+1}]\cdot(t-t_{j})^2(t-t_{j+1}) \end{eqnarray*}$

Dabei bestimmt man die Koeffizienten (dividierte Differenzen) mit dem Neville-Hermite-Schema und setzt für die ersten Ableitungen die Variable $\begin{eqnarray*} s_j \end{eqnarray*}$ . Damit sind die Bedingungen (1)-(3) umgesetzt.

$\begin{eqnarray*} R_{j-1}'(t)=f[t_{j-1},t_{j-1}]+2\cdot f[t_{j-1},t_{j-1},t_{j}]\cdot(t-t_{j-1})+2\cdot f[t_{j-1},t_{j-1},t_{j},t_{j}]\cdot (t-t_{j-1})(t-t_{j}) +f[t_{j-1},t_{j-1},t_{j},t_{j}]\cdot (t-t_{j-1})^2 \end{eqnarray*}$

$\begin{eqnarray*} R_{j}'(t)=f[t_{j},t_{j}]+2\cdot f[t_{j},t_{j},t_{j+1}]\cdot(t-t_{j})+2\cdot f[t_{j},t_{j},t_{j+1},t_{j+1}]\cdot (t-t_{j})(t-t_{j+1}) +f[t_{j},t_{j},t_{j+1},t_{j+1}]\cdot (t-t_{j})^2 \end{eqnarray*}$
Gleichsetzen von $\begin{eqnarray*} R_{j-1}''(t_j) = R_{j}''(t_j) \end{eqnarray*}$ (4) führt dann wieder auf ein LGS zur Bestimmung der Werte $\begin{eqnarray*} s_1,...,s_{n-1} \end{eqnarray*}$ . 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.
Mit den vorgegebenen Werten $\begin{eqnarray*} s_0 \end{eqnarray*}$ und $\begin{eqnarray*} s_n \end{eqnarray*}$ 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 $\begin{eqnarray*} R_{j-1} \end{eqnarray*}$ folgendes Schema der dividierten Differenzen:

$\begin{eqnarray*} \begin{array} {|r||r|r|r|r|} \hline t_{j-1}& f_{j-1} & s_{j-1} & \frac{\frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}}-s_{j-1}}{\vartriangle t_{j-1}} & \frac{s_{j} +s_{j-1}-2\frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}}}{\vartriangle t_{j-1}^2} \\ \hline t_{j-1} & f_{j-1} & \frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}} & \frac{s_{j}-\frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}}}{\vartriangle t_{j-1}} &\\ \hline t_{j} & f_{j} & s_{j} & & \\ \hline t_{j} & f_{j} & & & \\ \hline \end{array} \end{eqnarray*}$

Damit erhält man für das IP:
$\begin{eqnarray*} R_{j-1}(t) = f_{j-1}+s_{j-1} \cdot (t-t_{j-1}) + \frac{\frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}} - s_{j-1}}{\vartriangle t_{j-1}}(t-t_{j-1})^2 + \frac{s_{j} + s_{j-1} -2\frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}}}{\vartriangle t_{j-1}^2}\cdot (t-t_{j-1})^2(t-t_{j}) \end{eqnarray*}$

Und für das Interpolationspolynoms $\begin{eqnarray*} R_{j} \end{eqnarray*}$ folgendes Schema der dividierten Differenzen:

$\begin{eqnarray*} \begin{array} {|r||r|r|r|r|} \hline t_j& f_j & s_j & \frac{\frac{\vartriangle f_j}{\vartriangle t_{j}}-s_j}{\vartriangle t_j} & \frac{s_{j+1} +s_j-2\frac{\vartriangle f_j}{\vartriangle t_j}}{\vartriangle t_j^2} \\ \hline t_j & f_j & \frac{\vartriangle f_j}{\vartriangle t_j} & \frac{s_{j+1}-\frac{\vartriangle f_j}{\vartriangle t_j}}{\vartriangle t_j} &\\ \hline t_{j+1} & f_{j+1} & s_{j+1} & & \\ \hline t_{j+1} & f_{j+1} & & & \\ \hline \end{array} \end{eqnarray*}$

Damit erhält man für das IP:
$\begin{eqnarray*} R_{j}(t) = f_{j}+s_{j} \cdot (t-t_{j}) + \frac{\frac{\vartriangle f_{j}}{\vartriangle t_{j}} - s_{j}}{\vartriangle t_{j}}(t-t_{j})^2 + \frac{s_{j+1} + s_{j} -2\frac{\vartriangle f_{j}}{\vartriangle t_{j}}}{\vartriangle t_{j}^2}\cdot (t-t_{j})^2(t-t_{j+1}) \end{eqnarray*}$

Ableitungsbedingung (4.)

$\begin{eqnarray*} R_{j-1}''(t_j) = R_{j}''(t_j) ~(*) \end{eqnarray*}$

$\begin{eqnarray*} \frac{-6\frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}} +2s_{j-1} + 4s_j}{\vartriangle t_{j-1}}=\frac{6\frac{\vartriangle f_j}{\vartriangle t_j}-4s_j -2s_{j+1}}{\vartriangle t_j} \end{eqnarray*}$

Daraus erhält man:

$\begin{eqnarray*} \vartriangle t_j\cdot s_{j-1}+2(\vartriangle t_{j-1} + \vartriangle t_j)\cdot s_j + \vartriangle t_{j-1}\cdot s_{j+1} = 3(\frac{\vartriangle f_j}{\vartriangle t_j}\vartriangle t_{j-1} + \frac{\vartriangle f_{j-1}}{\vartriangle t_{j-1}} \vartriangle t_j) \end{eqnarray*}$

Formal vereinfacht schreibt man:

$\begin{eqnarray*} \beta_{j} \cdot s_{j-1} + \alpha_j \cdot s_j + \gamma_{j} \cdot s_{j+1} = y_j \qquad j = 1,2,...,n-1 \end{eqnarray*}$

Dies kann man als LGS der Form $\begin{eqnarray*} Ms = r \end{eqnarray*}$ schreiben. Für die Matrix M gilt:

$\begin{eqnarray*} \begin{pmatrix} \alpha_1 & \gamma_1 & & \\ \beta_2 & \alpha_2 &\gamma_2 && \\ &\beta_3 & \alpha_3 & \gamma_3 & \\ &&\ddots & \ddots \ddots &\gamma_{n-2} \\ & & & \beta_{n-1} &\alpha_{n-1}\end{pmatrix} \end{eqnarray*}$

Nun erklärt sich auch die Wahl der Zwischenvariable y. Denn für den Vektor r gilt:

$\begin{eqnarray*} \begin{pmatrix} r_1 \\ r_2 \\ \vdots \\ r_{n-2} \\ r_{n-1} \end{pmatrix} := \begin{pmatrix} y_1-\beta_1\cdot s_0\\ y_2 \\ \vdots \\ y_{n-2} \\ y_{n-1} - \gamma_{n-1} \cdot s_n \end{pmatrix} \end{eqnarray*}$

Der Vektor s sieht dann also wie folgt aus:

$\begin{eqnarray*} \begin{pmatrix} s_1 \\ s_2 \\ \vdots \\ s_{n-2} \\ s_{n-1} \end{pmatrix} \end{eqnarray*}$

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

$\begin{eqnarray*} &&\vartriangle t_{j-1} = t_j-t_{j-1} > 0,\\&& \vartriangle t_{j} = t_{j+1}-t_{j} > 0,\\&&j=1,...,n-1 \end{eqnarray*}$
$\begin{eqnarray*} \alpha_1 - \gamma_1 &&= 2(\vartriangle t_{0} + \vartriangle t_1)- \vartriangle t_{0}\\&&=\vartriangle t_{0} + 2\vartriangle t_{1} > 0 \end{eqnarray*}$
$\begin{eqnarray*} \alpha_j-\beta_{j}-\gamma_{j}&& = 2(\vartriangle t_{j-1} + \vartriangle t_j) - \vartriangle t_j - \vartriangle t_{j-1} \\&&=\vartriangle t_j ~+\vartriangle t_{j-1} >0 \end{eqnarray*}$
$\begin{eqnarray*} \alpha_{n-1} - \beta_{n-1} &&= 2(\vartriangle t_{n-2} + \vartriangle t_{n-1})-\vartriangle t_{n-1} \\&&=2\vartriangle t_{n-2} + \vartriangle t_{n-1} > 0 \end{eqnarray*}$

Aus dem Beweis im vorherigen Abschnitt folgt daher die Existenz und Eindeutigkeit der Lösung des LGS $\begin{eqnarray*} Ms=r \end{eqnarray*}$ und somit existiert der gesuchte kubische "Teil-Spline" eindeutig.

Zur Lösung des Systems benötigen wir allerdings noch die Randbedingungen (siehe 4b), also die Werte für $\begin{eqnarray*} s_0,~s_n \end{eqnarray*}$

Natürlicher Spline

Aus den Forderungen $\begin{eqnarray*} S''(t_0) = R_0''(t_0) = 0 \text{ und } S''(t_n) = R_{n-1}''(t_n) = 0 \end{eqnarray*}$ erhält man mit (*):

$\begin{eqnarray*} s_0 = 1.5 \cdot \frac{\vartriangle f_0}{\vartriangle t_0} - 0.5 \cdot s_1 \end{eqnarray*}$

$\begin{eqnarray*} s_n = 1.5 \cdot \frac{\vartriangle f_{n-1}}{\vartriangle t_{n-1}} - 0.5 \cdot s_{n-1} \end{eqnarray*}$

Vollstandiger Spline

$\begin{eqnarray*} s_0=f'(t_0) \end{eqnarray*}$

$\begin{eqnarray*} s_n=f'(t_n) \end{eqnarray*}$

Fehlerabschätzung

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

$\begin{eqnarray*} |\varepsilon(t)|=|f(t)-S(t)|\leq \frac{5}{384}\cdot h^4 \cdot \max_{t\in [a,b]} |f^{(4)}(t)| \qquad f\in C^4([a,b]) \end{eqnarray*}$

Neue Frage »

Antworten »

kubische Spline Interpolation

Verwandte Themen