Kubisch Hermitescher Spline

Diese Baustelle befindet sich fälschlicherweise im Artikelnamensraum. Bitte verschiebe die Seite oder entferne den Baustein {{Baustelle}}.

In dem mathematischen Teilgebiet der Numerik wird unter einem kubisch hermitischen Spline (auch cSpline genannt) ein Spline dritten Grades verstanden, der nur aus Hermitischen Polynomen besteht.

Die hermitische Form besteht aus zwei Kontrollpunkten und ihren zugehörigen Tangenten, die jeweils durch ein Polynom ausgedrückt werden. Durch Verknüpfung mehrer dieser Segmente können Datenpunkte durch eine Kurve/Spline interpoliert werden.

Definition eines Segments

Im Einheitsintervall

Im Einheitsintervall $[0,1]$ ist ein Segment des kubisch hermitischen Splines wie folgt definiert:

{\begin{aligned}c(t)\ &=\ (2p_{0}+m_{0}-2p_{1}+m_{1})t^{3}+(-3p_{0}-2m_{0}+3p_{1}-m_{1})t^{2}+m_{0}t+p_{0}\\\ &=\ \underbrace {(2t^{3}-3t^{2}+1)} _{h_{00}}{\boldsymbol {p_{0}}}+\underbrace {(t^{3}-2t^{2}+t)} _{h_{01}}{\boldsymbol {m_{0}}}+\underbrace {(-2t^{3}+3t^{2})} _{h_{10}}{\boldsymbol {p_{1}}}+\underbrace {(t^{3}-t^{2})} _{h_{11}}{\boldsymbol {m_{1}}}{\text{, mit }}t\in [0,1]\end{aligned}}

Dabei ist $p_{0}$ der Startpunkt bei $t=0$ und $p_{1}$ der Endpunkt bei $t=1$ . Die Punkte können dabei mehrdimensional sein, und sind linear unabhängig voneinander. $m_{0}$ und $m_{1}$ sind die zugehörigen Tangenten am Start- und Endpunkt. Dabei ist anzumerken das die Tangente des Endpunktes im Gegensatz zur Bézierkurve in Richtung der Kurve liegt, also eine „echte“ Tangente in Fluchtrichtung ist.

{\begin{aligned}c(t)\ &=\ CM_{h}S\ =\ {\begin{bmatrix}p_{0}&m_{0}&p_{1}&m_{1}\end{bmatrix}}{\begin{bmatrix}2&-3&0&1\\1&-2&1&0\\-2&3&0&0\\1&-1&0&0\end{bmatrix}}{\begin{bmatrix}t^{3}\\t^{2}\\t\\1\end{bmatrix}}\ =\ {\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}{\begin{bmatrix}2&1&-2&1\\-3&-2&3&0\\0&1&0&0\\1&0&0&0\end{bmatrix}}{\begin{bmatrix}p_{0}\\m_{0}\\p_{1}\\m_{1}\end{bmatrix}}\end{aligned}}

$M_{h}$ wird dabei als hermitische Matrix bezeichnet.

Im Werteintervall

Im allgemeineren Intervall $[x_{k},x_{k+1}]$ wird die Funktion entsprechend gestreckt wodurch sich $t$ aus der Gleichung $t=(x-x_{k})/(x_{k+1}-x_{k})$ ergibt und die Tangenten im gleichen Verhältnis skaliert werden müssen. Dadurch kommt der Abstand des Intervalls als zusätzlicher Parameter $d$ hinzu, der sich aus $d=x_{k+1}-x_{k}$ ergibt.

{\begin{aligned}c(x)\ &=\ h_{00}(t){\boldsymbol {p_{k}}}+d\cdot h_{01}(t){\boldsymbol {m_{k}}}+h_{10}(t){\boldsymbol {p_{k+1}}}+d\cdot h_{11}(t){\boldsymbol {m_{k+1}}}{\text{, mit }}t=(x-x_{k})/(x_{k+1}-x_{k}){\text{ und }}d=x_{k+1}-x_{k}\end{aligned}}

Herleitung

Es seien die Punkte $p_{0}$ und $p_{1}$ und ihre zugehörigen Tangenten $m_{0}$ und $m_{1}$ gegeben. Ebenso soll die gesuchte Funktion in Polynom dritten Grades sein, dass sich allgemein als $x(t)=at^{3}+bt^{2}+ct+d$ darstellen lässt.

Zugleich wird vorausgesetzt das zwei aneinandergesetzte Segmente sich den Anfangs- und Endpunkt teilen und ein weicher Übergang besteht. Folglich sind die beiden $C0$ und $C1$ kontinuierlich. Wobei unter $C0$ der gleiche Anfangs- und Endpunkt verstanden wird, wohingegen die gleiche Ableitung an dieser Stelle als $C1$ bezeichnet wird. Dadurch entstehen vier Bedingungen die sich wie folgt beschreiben lassen:

{\begin{aligned}x(0)\ &=\ p_{0}\\x(1)\ &=\ p_{1}\\x'(0)\ &=\ m_{0}\\x'(1)\ &=\ m_{1}\\\end{aligned}}

Das Eingangs erwähnte Polynom lässt anschaulich in Matrixform schreiben:

x(t)={\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}{\begin{bmatrix}a\\b\\c\\d\end{bmatrix}}=TC

Daraus folgt für $t=0$ und $t=1$ :

{\begin{aligned}x(0)\ &=\ p_{0}\ &=\ {\begin{bmatrix}0&0&0&1\end{bmatrix}}C\\x(1)\ &=\ p_{1}\ &=\ {\begin{bmatrix}1&1&1&1\end{bmatrix}}C\end{aligned}}

Für die Tangenten muss die Funktion einmal nach $t$ abgeleitet werden, sodass sich folgende Gleichungen ergeben:

{\begin{aligned}x'(t)\ &=\ {\begin{bmatrix}3t^{2}&2t&1&0\end{bmatrix}}C\\x'(0)\ &=\ m_{0}\ =\ {\begin{bmatrix}0&0&1&0\end{bmatrix}}C\\x'(1)\ &=\ m_{1}\ =\ {\begin{bmatrix}3&2&1&0\end{bmatrix}}C\end{aligned}}

Die vier gewonnenen Beziehungen können wie folgt zusammengefasst werden:

{\begin{bmatrix}p_{0}\\m_{0}\\p_{1}\\m_{1}\end{bmatrix}}=\underbrace {\begin{bmatrix}0&0&0&1\\0&0&1&0\\1&1&1&1\\3&2&1&0\end{bmatrix}} _{A}C

Nun kann die Gleichung durch Multiplikation mit der Inversen $A^{-1}$ nach $C$ aufgelöst werden.

C\ =\ A^{-1}{\begin{bmatrix}p_{0}\\m_{0}\\p_{1}\\m_{1}\end{bmatrix}}\ =\ {\begin{bmatrix}2&1&-2&1\\-3&-2&3&0\\0&1&0&0\\1&0&0&0\end{bmatrix}}{\begin{bmatrix}p_{0}\\m_{0}\\p_{1}\\m_{1}\end{bmatrix}}

Eingesetzt in die allgemeine kubische Gleichung $x(t)$ ergibt sich die anfangs genannte Definition des Segments des kubisch hermitischen Splines.

Darstellungen und Verwandtschaft

Die hermitischen Basisfunktionen $h_{00},h_{01},h_{10},h_{11}$ lassen sich auf unterschiedliche Weise darstellen, wodurch sich jeweils direkt verschiedene Eigenschaften der Kurvensegmente ablesen lassen.

Darstellung	${\boldsymbol {h_{00}(t)}}$	${\boldsymbol {h_{01}(t)}}$	${\boldsymbol {h_{10}(t)}}$	${\boldsymbol {h_{11}(t)}}$
expandiert	$2t^{3}-3t^{2}+1$	$t^{3}-2t^{2}+t$	$-2t^{3}+3t^{2}$	$t^{3}-t^{2}$
faktorisiert	$(1+2t)(1-t)^{2}$	$t(1-t)^{2}$	$t^{2}(3-2t)$	$t^{2}(t-1)$
Bernstein	$B_{0}(t)+B_{1}(t)$	${\frac {1}{3}}B_{1}(t)$	$B_{2}(t)+B_{3}(t)$	$-{\frac {1}{3}}B_{2}(t)$

Die expandierte Form lässt sich direkt aus der Herleitung gewinnen und wird üblicherweise, wie auch hier, zur Definition benutzt.

Es ist direkt an der Faktorisierung ersichtlich das $h_{00}$ bei $t=1$ eine Nullstelle besitzt und der Anstieg gleich $0$ ist. Selbiges gilt für $h_{10}$ für $t=0$ . $h_{01}$ und $h_{11}$ besitzen hingegen eine Multiplizität von 2 und besitzen jeweils am Ende und Anfang des Definitionsbereichs von $t$ eine Nullstelle.

Bei der Betrachtung der Bernsteinpolynome der 3. Ordnung $B_{k}(t)={3 \choose k}t^{k}(1-t)^{3-k}$ wird die Analogie zur kubischen Bézierkurve ersichtlich, deren Bernsteinpolynome $B_{0}(t)$ , $B_{1}(t)$ , $B_{2}(t)$ und $B_{3}(t)$ sind. Entsprechend existiert eine direkte Verbindung zwischen beiden Gleichungen, aus der sich die folgenden Zusammenhänge ergeben,

{\begin{aligned}P_{0}\ &=\ p_{0},\\P_{1}\ &=\ p_{0}+{\frac {m_{0}}{3}},\\P_{2}\ &=\ p_{1}-{\frac {m_{1}}{3}},\\P_{3}\ &=\ p_{1},\end{aligned}}

wenn die Bézierkurve wie folgt definiert ist:

{\begin{aligned}C(t)\ &=\ (1-t)^{3}P_{0}+3t(1-t)^{2}P_{1}+3t^{2}(1-t)P_{2}+t^{3}P_{3}\\\end{aligned}}

.

Durch diesen Zusammenhang kann der De Casteljau-Algorithmus zu Berechnung von Interpolationen mittels kubisch hermitischer Splines benutzt werden. Ebenso ist ersichtlich das bei einer kubischen Bézierkurve die mittleren Kontrollpunkte die Richtung der Tangente an den Endpunkten definieren.

Einmaligkeit

Die Definition des Segments garantiert, dass der Pfad zwischen zwei Punkten einmalig ist. D.h. das keine zweite Darstellung für den gleichen Verlauf gefunden werden kann.

Beweis: Es sei $q(x)$ eine andere Funktion mit Polynomen dritten Grades, die die gleichen Randbedingungen besitzt. Die Funktion $r(x)$ sei definiert als $r(x)=q(x)-c(x)$ . Da sowohl $q$ und $c$ Polynome dritten Grades sind, kann auch $r$ höchstens ein Polynom dritten Grades sein.; Weiterhin soll gelten $r(0)=q(0)-c(0)=0$ und $r(1)=q(1)-c(1)=0$ , um die Randbedingungen einzuhalten.

Daraus folgt, das $r$ die folgende Form haben muss:

{\begin{aligned}r(x)\ &=\ ax(x-1)(x-R)\\r'(x)\ &=\ ax(x-1)+ax(x-R)+a(x-1)(x-R)\end{aligned}}

Weiterhin ist bekannt:

${\begin{aligned}r'(0)\ &=\ q'(0)-p'(0)\ =\ 0\\r'(0)\ &=\ aR\end{aligned}}$	$(1)$
${\begin{aligned}r'(1)\ &=\ q'(1)-p'(1)\ =\ 0\\r'(1)\ &=\ a(1-R)\end{aligned}}$	$(2)$

Aus $(1)$ und $(2)$ kann geschlussfolgert werden, dass $a=0$ sein muss. Daraus folgt jedoch auch, dass $r(x)=0$ ist und entsprechend der anfänglichen Definition sich $p(x)=q(x)$ ergibt.