\section{Spline Interpolation}
%
\underline{Idee:} Anstatt Polynome zu verwenden zur Interpolation,
verwende st\"uckweise Polynome. Spline kommt aus Schiffbau.

Latte um Schiffsrumpf

\begin{center}
\unitlength 1cm
\begin{picture}(8,7)
% \put(0,0){\epsfig{file=includeps/spline.ps,width=8cm,clip=}}
\put(0,0){\includegraphics[width=0.60\linewidth,height=0.45\linewidth]{includeps/spline}}
\end{picture}
\end{center}


Anwendungen:
CAD, numerische L\"osung partieller + gew\"ohnlicher Differentialgleichungen.
Mehr in Numerik III, Numerik IV; hier nur Grundlagen.


\subsection{Allgemeine Eigenschaften}

Durch $\bigtriangleup := \{ a = x_0 < x_1 \cdots < x_n = b \}$ sei
Unterteilung von $[a,b]$ gegeben.
%
\begin{definition}\label{4.3.1}
Unter einer zu $\bigtriangleup$ geh\"orenden Spline--Funktion $S_\bigtriangleup$
versteht man eine reelle Funktion $S_\bigtriangleup : [a,b] \to \R$ mit
%
\begin{itemize}
\item [a)] $S_\bigtriangleup \in {\cal C}^{2k} [a,b]$
\quad ($2k$ mal stetig differenzierbar).
\item [b)] Auf jedem Teilintervall $[x_i, x_{i+1}]$ stimmt
$S_\bigtriangleup$ mit Polynom $2k+1$--ten Grades \"uberein.
\end{itemize}
\end{definition}
 Hier im
folgenden $k=1$, kubische Splines. Fast alles l\"a{\ss}t sich \"ubertragen.
%
\begin{definition}\label{4.3.2}
\[
\kappa^n (a,b) := \left\{ f: [a,b] \to \R;
%
\begin{array}{l}
 f^{(i)},\; i = 1, \dots, n-1, \mbox { existiert und ist absolut stetig, }\\
 f^{(n)} \mbox { ~existiert fast \"uberall auf } [a,b] \mbox  { und }
 f^{(n)} \in L^2 [a,b]
\end{array}\right\}
\]
%
($f$ absolut stetig, falls zu jedem $\epsilon > 0$ ein $\delta > 0$ so da{\ss}
f\"ur jedes endliche System von Intervallen $[a_i, b_i]$ mit
$a \le a_1 < b_1 \le a_2 < b_2 \cdots \le a_m < b_m\le b$ mit
%
$\sum\limits_i |b_i - a_i| < \delta$ gilt:  $\sum\limits_i |f(b_i) - f(a_i) | < \epsilon$.) 
%
\begin{eqnarray*}
 \kappa^n_p (a,b) & = & \{ f\in \kappa^n (a,b), f,f', \dots, f^{(n-1)}, b-a
  \mbox { periodisch, d.h. }\\
 & & f^{(i)} (a) = f^{(i)} (b) \quad i = 0,\dots,n-1\}.
\end{eqnarray*}
%
Es folgt, da{\ss} $S_\bigtriangleup \in \kappa^{2k+1} (a,b).$\\
Eine Spline--Funktion hei{\ss}t periodisch falls 
%
\[
 S_\bigtriangleup \in \kappa^{2k+1}_p (a,b).
\]
Wir wollen mit Splines interpolieren, d.h. wir wollen, da{\ss}
$S_\bigtriangleup(x_i)  =  f_i =  f(x_i),\; i = 0,\dots, n$.
Dann $S_\bigtriangleup^f.$
F\"uhre Ma{\ss} $w(f) := \int\limits^b_a |f'' (x)|^2\, dx$ ein.\\
$w(f) \ge 0$ jedoch $w(f) = 0 \quad \forall f=cx+1.$
\end{definition}
%
\begin{theorem}\label{4.3.3}
Sei $f\in \kappa^2 (a,b), \bigtriangleup = \{ a = x_0 < \cdots < x_n = b\}$
und $S_\bigtriangleup$ kubischer Spline zu $\bigtriangleup$. Dann gilt
%
\[
 w(f-S_\bigtriangleup) = w(f) - w(S_\bigtriangleup) -2 \left[ \left.(f'-S'_\bigtriangleup)S_\Delta''
 \right|^b_a - \sum\limits^n_{i=1} \left.(f-S_\bigtriangleup)S'''_\bigtriangleup 
 \right|^{x^-_i}_{x^+_{i-1}} \right].
\]
%
\end{theorem}            
%
\proof
\begin{eqnarray*}
 w(f-S_\bigtriangleup) 
 & = & \int\limits^b_a |f'' - S_\bigtriangleup'' |^2\, dx\\
 &=& \int\limits^b_a |f''|^2\, dx 
  -2 \int\limits^b_a f''S_\bigtriangleup'' dx + \int\limits^b_a |S_\bigtriangleup''|^2\, dx\\
%
 & = & w(f) - 2 \int\limits^b_a (f'' - S''_\bigtriangleup ) S''_\bigtriangleup \, dx - w(S_\bigtriangleup).
\end{eqnarray*}
Partielle Integration in Teilintervallen.
%
\begin{eqnarray*}
 \int\limits^{x_i}_{x_{i-1}} (f''-S''_\bigtriangleup) S''_\bigtriangleup
 dx & = & \left.(f'-S'_\bigtriangleup)S''_\bigtriangleup \right|^{x_i}_{x_{i-1}} - \int\limits^{x_i}_{x_{i-1}} (f'-S'_\bigtriangleup) S'''_\bigtriangleup dx\\
%
 & = & \left.(f' - S'_\bigtriangleup) S''_\bigtriangleup \right|^{x_i}_{x_{i-1}}
 - \left.(f-S_\bigtriangleup) S'''_\bigtriangleup \right|^{x_i^-}_{x^+_{i-1}} + \int\limits^{x_i}_{x_{i-1}} (f-S_\bigtriangleup) S^{(4)}_\bigtriangleup\,
   dx. 
\end{eqnarray*}
$S^{(4)} \equiv 0$ auf allen $[x_{i-1}, x_i]$ und 
\[
\sum\limits^n_{i=1} \left.(f' - S'_\bigtriangleup )S''_\bigtriangleup 
 \right|^{x_i}_{x_{i-1}} = \left.(f'-S_\Delta') S''_\bigtriangleup \right|^b_a
\]
%
impliziert Beh.
\eproof
%
Dies ist Grundlage f\"ur Minimaleigenschaft der Splines.
%
\begin{theorem}\label{4.3.4}
Sei $\bigtriangleup = \{a=x_0<x_1 \cdots < x_n = b\}$.\\
$F = \{ f_0,\dots,f_n\}, f \in \kappa^2 (a,b)$ mit $f(x_i) = f_i, \;
i = 0, \dots, n$. Dann gilt
%
\eq{4.3.5}
 w(f-S^f_\bigtriangleup) = w(f) - w(S^f_\bigtriangleup) \ge 0
\en
%
f\"ur alle interpolierenden $S^f_\bigtriangleup$ die einer der 3 folgenden
Bedingungen erf\"ullen. 
%
\eq{4.3.6}
 a) \quad S''_\bigtriangleup (a) = S''_\bigtriangleup (b) = 0.
\en
%
\eq{4.3.7}
\mbox { oder } b) \quad f \in \kappa^2_p (a,b) \quad S_\bigtriangleup \mbox { periodisch }.
\en
%
\eq{4.3.8}
\mbox { oder } c) \quad f'(a) = S'_\bigtriangleup (a), f'(b) = S'_\bigtriangleup (b).
\en
F\"ur jeden dieser F\"alle ist $S_\bigtriangleup$ eindeutig bestimmt.
\end{theorem}
%
\proof
In jedem dieser F\"alle verschwindet
\[
 \left.\left( (f' - S'_\bigtriangleup) S''_\bigtriangleup \right) \right|^a_b -
 \sum\limits^n_{i=1} \left.(f-S_\bigtriangleup) S'''_\bigtriangleup 
 \right|^{x^-_i}_{x^+_{i-1}} = 0.
\]
%
Eindeutigkeit folgt so. Angenommen es g\"abe $\tilde{S}_\bigtriangleup^f$
mit den gleichen Eigenschaften. Dann kann ich $f(x) = \tilde{S}^f_\bigtriangleup (x)$
setzen. $\Longrightarrow$\\
$w(\tilde{S}_\bigtriangleup^f (x) - S_\bigtriangleup^f (x) )= 
w (\tilde{S}_\bigtriangleup^f (x)) - w(S_\bigtriangleup^f (x)) \ge 0$
und genauso $w(S_\bigtriangleup^f (x)) - w(\tilde{S}_\bigtriangleup^f (x)) \ge 0$\\
also $\int\limits_a^b (\tilde{S}''_\bigtriangleup - S''_\bigtriangleup )^2 dx=0$
beide $\tilde{S}'', S''$ stetig $\Longrightarrow \tilde{S}''_\bigtriangleup =
S''_\bigtriangleup \Longrightarrow \tilde{S}^f_\bigtriangleup = S^f_\bigtriangleup
+ cx + d$, wegen $\tilde{S}^f_\bigtriangleup (x) = S^f_\Delta (x)$ f\"ur $a,b$ folgt
$c=d=0.$
\eproof
%
Dieser Satz besagt, da{\ss} die Splines unter allen Funktionen aus
$\kappa^2 (a,b)$ die interpolierende Funktion mit der geringsten Kr\"ummung
sind. \\
$\kappa (x) = \frac{f''(x)}{\sqrt{1+f'(x)^2}^3} \approx f''(x)$ f\"ur $f'(x)$
klein.


Analoge Eigenschaften f\"ur gelten andere Splines.

\subsection{Berechnung der Splines}

Setze $h_{j+1} = x_{j+1} - x_j, \; j=0,\dots,n-1$ und
\eq{4.3.9}
 M_j = S''_\bigtriangleup (x_j),\; j=0,\dots,n.
\en
%
$M_j$ hei{\ss}en Momente (aus Physik 2. Ableitungen).
Berechne Splines die (\ref{4.3.6}), (\ref{4.3.7}) oder (\ref{4.2.8})
erf\"ullen mit Hilfe der Momente.\\
Da $S_\bigtriangleup$ kubisch in $[x_i, x_{i+1}]$ ist, folgt da{\ss} 
$S''_\bigtriangleup$ linear in $[x_i, x_{i+1}]$ und es gilt
%
\eq{4.3.10}
 S''_\bigtriangleup (x) = M_j \frac{x_{j+1}-x}{h_{j+1}} +
 M_{j+1} \frac{x-x_j}{h_{j+1}}, \;  x \in [x_j, x_{j+1}] \; \mbox { (2 Punkte Formel) }
\en
%
Integration
%
\eqa
 S'_\bigtriangleup (x) & = & - M_j \frac{(x_{j+1}-x)^2}{2h_{j+1}} +
 M_{j+1} \frac{(x-x_j)^2}{2h_{j+1}} + \alpha_j\\
%
 S_\bigtriangleup (x) & = &  M_j \frac{(x_{j+1}-x)^3}{6h_{j+1}} +
 M_{j+1} \frac{(x-x_j)^3}{6h_{j+1}} + \alpha_j (x-x_j) + \beta_j.
\ena
%
Interpolationsbedingungen
%
\begin{eqnarray*}
 S_\Delta (x_j)&=&f_j\\
\Longrightarrow M_j\frac{h^2_{j+1}}{6}+\beta_j&=&f_j\Longrightarrow\beta_j=f_j-M_j\frac{h^2_{j+1}}{6}, \\
S_\Delta (x_{j+1})&=&f_{j+1}\\
\Longrightarrow M_{j+1}\frac{h^2_{j+1}}{6}+\alpha_jh_{j+1}+\beta_j&=&f_{j+1}\Longrightarrow\alpha_j=\frac{f_{j+1}-f_j}{h_{j+1}}-\frac{h_{j+1}}{6} (M_{j+1} - M_j),
\end{eqnarray*}
%
und damit
%
\eq{4.3.13}
 S_\Delta (x) = a_j + b_j (x-x_j) + c_j (x-x_j)^2 + d_j (x-x_j)^3
\en
%
mit
%
\eqa \label{4.3.14}
 a_j & = & f_j, c_j = \frac{M_j}{2}, b_j = - \frac{M_j h_{j+1}}{2} + \alpha_j =
 S'_\Delta (x_j)\\
 & = & \frac{f_{j+1}-f_j}{h_{j+1}} - \frac{2M_j + M_{j+1} h_{j+1}}{6}, d_j =
 \frac{M_{j+1}-M_j}{6h_{j+1}} = \frac{S'''_\Delta (x^+_j)}{6} \nonumber
\ena
%
Wir brauchen also nur die $M_j$ zu berechnen. Wir haben gefordert, da{\ss}
$S'_\Delta (x)$ an den Knoten $x=x_j, \; j = 1, \dots, n-1$
stetig sein soll. $\Longrightarrow n-1$
Gleichungen. Es gilt
%
\eqa\label{4.3.15}
 S'_\Delta (x) & = & -M_j \frac{(x_{j+1}-x)^2}{2h_{j+1}}
 + M_{j+1} \frac{(x-x_j)^2}{2h_{j+1}} +
 \frac{f_{j+1}-f_j}{h_{j+1}} \\
 & & -\frac{h_{j+1}}{6} (M_{j+1}-M_j) \nonumber
\ena
%
wenn man die Werte einsetzt. Damit ergibt sich f\"ur
$j=1,\dots,n-1$
%
\eqa\label{4.3.16}
 S'_\Delta (x_{j}^-) & = & \frac{f_j - f_{j-1}}{h_j} + \frac{h_j}{3}
 M_j + \frac{h_j}{6} M_{j-1} \\
 S'_\Delta (x_{j}^+) & = & \frac{f_{j+1} - f_j}{h_{j+1}} - 
 \frac{h_{j+1}}{3} M_j - \frac{h_{j+1}}{6} M_{j+1} \nonumber
\ena
%
Gleichsetzen wegen Stetigkeit $\Longrightarrow$
%
\eqa\label{4.3.17}
 \frac{h_j}{6} M_{j-1} + \frac{h_j+h_{j+1}}{3} M_j +
 \frac{h_{j+1}}{6} M_{j+1} &=& \frac{f_{j+1}-f_j}{h_{j+1}} -
 \frac{f_j - f_{j-1}}{h_j} \\
  &=&  f[x_j,x_{j+1}] - f[x_{j-1},x_j], \;  j = 1,\dots,n-1 \nonumber
\ena
%
Das sind $n-1$ Gleichungen f\"ur $M_0, \dots, M_n.$\\
Die zwei weiteren notwendigen Bedingungen erh\"alt man aus (\ref{4.3.6}),
(\ref{4.3.7}), (\ref{4.3.8}).\\
Aus (\ref{4.3.6})
\[
S''_\Delta (a) = M_0 = M_n = S''_\Delta (b) = 0.
\]
%
Aus (\ref{4.3.7})
\begin{eqnarray*}
 S''_\Delta (a)  = S''_\Delta (b) & \Longrightarrow & M_0 = M_n.\\
 S'_\Delta (a)  = S'_\Delta (b)  & \Longrightarrow &
 \frac{h_n}{6} M_{n-1} + \frac{h_n + h_1}{3} M_n + \frac{h_1}{6} M_1\\
 & & = \frac{f_1 - f_n}{h_1} - \frac{f_n - f_{n-1}}{h_n}
\end{eqnarray*}
%
Aus $f_n=f_0$ und mit der Setzung \\
$h_{n+1}:=h_1 \,\, M_{n+1} := M_1, \,\, f_{n+1} :=f_1$ erh\"alt man
wieder Gleichung (\ref{4.3.17}).\\
Aus (\ref{4.3.8}) 
%
\begin{eqnarray*}
 S'_\Delta (a) = f'_0 & \Longrightarrow &
 \frac{h_1}{3} M_0 + \frac{h_1}{6} M_1
 = \frac{f_1 - f_0}{h_1} - f'_0\\
%
 S'_\Delta (b) = f'_n & \Longrightarrow &
 \frac{h_n}{6} M_{n-1} + \frac{h_n}{3} M_n
 = f'_n - \frac{f_n - f_{n-1}}{h_n}.
\end{eqnarray*}
%
F\"uhre nun folgende Abk\"urzungen ein:
\[
 \lambda_j := \frac{h_{j+1}}{h_j+h_{j+1}}, \; \mu_j := 
  1 - \lambda_j = \frac{h_j}{h_j+h_{j+1}}
\]
%
Dann erh\"alt man das System von linearen Gleichungen 
%
\eq{4.3.19}
 \mu_j M_{j-1} + 2M_j + \lambda_j M_{j+1} = 6f[x_{j-1}, x_j, x_{j+1}]=:d_j
\en
%
d.h. die folgenden Gleichungssysteme:
%
\eq{4.3.20}
 \left[ \begin{array}{ccccc}
  2 & \lambda_0 & & & \\
  \mu_1 & 2 & \lambda_1 & & \\
  & \ddots & \ddots & \ddots & \\
  & & \ddots & \ddots & \lambda_{n-1}\\
  & & & \mu_n & 2 \end{array}\right] 
%
 \left[ \begin{array}{c}
  M_0 \\ \vdots\\ \vdots\\ \vdots\\ M_n \end{array}\right] = 
%
 \left[ \begin{array}{c}
  d_0 \\ \vdots\\ \vdots\\ \vdots\\ d_n \end{array}\right]
\en
%
im Fall von Bedingung (\ref{4.3.6}), wobei\\
$\lambda_0 := 0, d_0 = 0, \mu_n := 0, d_n := 0$ gesetzt wurde.
%
\eq{4.3.21}
 \left[ \begin{array}{cccccc}
  2 & \lambda_1 &         &        &        & \mu_1\\
  \mu_2 & 2     &\lambda_2&        &        & \\
        & \mu_3 & \ddots  & \ddots &        & \\
        &       & \ddots  & \ddots & \ddots & \\
        &       &         &        &        & \lambda_{n-1} \\
  \lambda_n &   &         &        & \mu_n  & 2
\end{array}\right]
%
 \left[ \begin{array}{c}
  M_1 \\ \vdots\\ \vdots\\ \vdots\\ M_n \end{array}\right]=
%
 \left[ \begin{array}{c}
  d_1 \\ \vdots\\ \vdots\\ \vdots\\ d_n \end{array}\right]  
\en
%
im Fall von Bedingung (\ref{4.3.7}), wobei
%
\[
 \lambda_n := \frac{h_1}{h_n+h_1},
 \mu_n = 1 - \lambda_n, d_n = 6f [x_{n-1}, x_n, x_1]
\]
%
Im Fall von Bedingung (\ref{4.3.8}) erh\"alt man wiederum System (\ref{4.3.20})
nur mit 
%
\[
\begin{array}{l}
 \lambda_0=1, \mu_n=1, d_0 = \frac{6}{h_1} \left( f[x_0,x_1]-f'_0 \right), 
  d_n = \frac{6}{h_n} \left( f'_n - f[x_{n-1}, x_n] \right).
\end{array}
\]
F\"ur alle 3 Gleichungssysteme gilt $\lambda_i \ge 0, \mu_i \ge 0, 
\lambda_i + \mu_i \leqslant 1$ und der Satz
%
\begin{theorem}\label{4.3.22}
Die Matrizen der Systeme (\ref{4.3.20}), (\ref{4.3.21}) sind f\"ur jede
Zerlegung $\Delta$ von $[a,b]$ nichtsingul\"ar.
\end{theorem}
%
\proof
Sei
\[
 A = \left[\begin{array}{cccc}
  2 & \lambda_0 & & \\
  \mu_1 & \ddots & \ddots & \\
  & \ddots & \ddots & \lambda_{n-1} \\
  & & \mu_n & 2 \end{array}\right]
\]
%
Sei $x,y \in \R^{n+1}$ mit $Ax = y$ und setze $\lambda_n=\mu_0=0$. Dann  gilt 
\[
 \max\limits_i |x_i| \le \max\limits_i |y_i| \quad
 \mbox { (A ist monoton)}.
\]
Denn sei $r$ der Index f\"ur den $\max\limits_i |x_i|$ angenommen wird.\\
Dann gilt
%
\begin{eqnarray*}
 \mu_r x_{r-1} + 2x_r + \lambda_r x_{r+1} & = & y_r \\
%
 \Longrightarrow \max\limits_i |y_i| \ge |y_r| & \ge & 
 2|x_r| - \mu_r|x_{r-1}|-\lambda_r|x_{r+1}|\\
%
 & \ge & 2|x_r| - (\mu_r+\lambda_r)|x_r|\\
%
 & \ge & |x_r| = \max\limits_i |x_i|.
\end{eqnarray*}
Angenommen $A$ singul\"ar $\Longrightarrow x \neq 0$ mit $Ax=0$.\\
Monotonie f\"uhrt sofort zum Widerspruch. Anderes System analog.
\eproof
%
\underline{L\"osung der Gleichungssysteme:}\\
$\longrightarrow$ \"Ubung: Gau{\ss} ohne Pivot (Diagonaldominanz).\\
Zyklische Reduktion, Sherman--Morrison, 
iterative Verfahren; alles geht sehr gut.\\
$\longrightarrow$ \"Ubung!

Typischerweise werden jedoch Bandl\"oser benutzt, da die Matrizen
diagonal\"ahnlich zu einer positiv definiten Matrix sind.

\subsection{Fehlerabsch\"atzung und Konvergenz bei Interpolation mit Splines}

Sei $\Delta_m = \{ a = x^{(m)}_0 < x^{(m)}_1 < \cdots
< x^{(m)}_{n_m} = b \}$ eine
Folge von Unterteilungen von $[a,b]$ und sei 
$\sigma_m = \max\limits_i (x^{(m)}_{i+1} - x^{(m)}_i).$
%
\begin{theorem}\label{4.3.23}
Sei $f\in {\cal C}^4 [a,b]$ und $|f^{(4)} (x) | \le L \,\,
\forall x \in [a,b], \Delta_m$ wie oben mit
$\sup\limits_{m,j} \frac{\sigma_m}{x^{(m)}_{j+1} - x_j^{(m)}}
\le \kappa < \infty.$ 
Seien $S_{\Delta_m}$ die zu $f$ geh\"origen Splines, die
die Interpolationsbedingungen
%
\eq{4.3.24}
\begin{array}{rcll}
 S_{\Delta_m} (\zeta) &= &f(\zeta) & \mbox { f\"ur } 
 \zeta \in \Delta_m \\
 S'_{\Delta_m} (x) &=& f'(x) & \mbox { f\"ur }  x = a,b 
\end{array}
\en
%
erf\"ullen. Dann gibt es von $\Delta_m$ unabh\"angige Konstanten $C_i \le 2$, so da{\ss}
f\"ur alle $x \in [a,b]$
%
\eq{4.3.25}
 \left| f^{(i)} (x) - S^{(i)}_{\Delta_m} (x) \right|
 \le C_i L\kappa \sigma^{4-i}_m,\; i = 0,1,2,3.
\en
%
\end{theorem}
%
\proof
Betrachte feste Zerlegung $\Delta$ von $[a,b]$. Die
Momente $M_j$ erf\"ullen f\"ur den Fall den wir hier haben, das 
Gleichungssystem
%
\[
\left[\begin{array}{cccc}
  2 & \lambda_0 & & \\
  \mu_1 & 2 & \ddots & \\
  & \ddots & \ddots & \lambda_{n-1} \\
  & & \mu_n & 2 \end{array}\right]
%
\left[ \begin{array}{c}
 M_0 \\ \vdots \\ \vdots \\ M_n \end{array}\right]
%
\left[ \begin{array}{c}  d_0 \\ \vdots \\ \vdots \\ d_n \end{array}\right]
\]
%
\[
 \lambda_0 = \mu_n = 1, \lambda_j = \frac{h_{j+1}}{h_j + h_{j+1}},
 \mu_j = 1-\lambda_j, \; j = 1, \dots, n-1
\]
%
\[
\begin{array}{rcl}
 d_j &=& 6f [x_{j-1}, x_j, x_{j+1}], \; j = 1, \dots, n-1\\
 d_0 &= &\displaystyle\frac{6}{h_1} \left( f[x_0, x_1] - f'_0 \right), \\
 d_n &=&\displaystyle \frac{6}{h_n} \left( f'_n - f[x_{n-1},x_n] \right).
\end{array}
\]
%
Definiere
\[
 F = \left[ \begin{array}{c}
 f''(x_o) \\
 \vdots \\
 f'' (x_n) \end{array}\right], r = d-AF, M = \left[ \begin{array}{c}
 M_0 \\ \vdots \\ M_n \end{array}\right].
\]
%
Dann gilt $r_0 = d_0 - 2f'' (x_0) - f''(x_1)$. Sch\"atze
zuerst $\|r_0\|_\infty$ ab. Taylorentwicklung um $x_0$ liefert
%
\begin{eqnarray*}
 r_0 & = & \frac{6}{h_1} \left( f[x_0,x_1]-f'_0 \right)
           - 2f''(x_0) - f''(x_1)\\
 & = & \frac{6}{h_1} \left(f'(x_0) + \frac{h_1}{2} f''(x_0)
       + \frac{h^2_1}{6} f''' (x_0) + \frac{h^3_1}{24} f^{(4)} (\tau_1)
    -  f'(x_0) \right)\\
 & & - 2f'' (x_0) - \left( f'' (x_0) + h_1 f''' (x_0) + \frac{h^2_1}{2} f^{(4)}
       (\tau_2) \right)\\
 & = & \frac{h^2_1}{4} f^{(4)}(\tau_1) - \frac{h^2_1}{2} f^{(4)} (\tau_2),
 \mbox { f\"ur } \tau_1, \tau_2 \in [x_0, x_1]
\end{eqnarray*}
%
\eq{4.3.26}
\Longrightarrow  |r_0| \le \frac{3}{4} L \sigma^2_m.
\en
%
Analog gilt f\"ur $r_n = d_n - f'' (x_{n-1}) - 2f'' (x_n)$ die Absch\"atzung
%
\eq{4.3.27}
 |r_n| \le \frac{3}{4} L \sigma^2_m.
\en
%
und f\"ur $j=1,\dots, n-1$ mit Taylorentwicklung um $x_j$.
%
\begin{eqnarray*}
 r_j & = & d_j - \mu_j f'' (x_{j-1}) - 2f'' (x_j) - \lambda_j f'' (x_{j+1})\\
     & = & 6f [x_{j-1}, x_j, x_{j+1}] - \frac{h_j}{h_j + h_{j+1}} f''(x_{j-1})
- 2f'' (x_j)           - \frac{h_{j+1}}{h_j + h_{j+1}} f'' (x_{j+1})\\
%
& = & \frac{1}{h_j + h_{j+1}} \left\{ 6\left(f'(x_j) + \frac{h_{j+1}}{2}
f'' (x_j) + \frac{h^2_{j+1}}{6} f''' (x_j) + \frac{h^3_{j+1}}{24}
f^{(4)} (\tau_{j_1}) \right.\right. \\
%
& & \phantom{\frac{1}{h_j + h_{j+1}}6~~~}\left. - f' (x_j) + \frac{h_j}{2} f'' (x_j) - \frac{h^2_j}{6} f''' (x_j)
+ \frac{h^3_j}{24} f^{(4)} (\tau_{j_2}) \right)\\
%
& & \phantom{\frac{1}{h_j + h_{j+1}}}- h_j \left( f''(x_j) - h_j f''' (x_j) + 
 \frac{h^2_j}{2} f^{(4)} (\tau_{j_3}) \right)\\
%
& & \phantom{\frac{1}{h_j + h_{j+1}}}- 2f'' (x_j) (h_j + h_{j+1})\\
& & \phantom{\frac{1}{h_j + h_{j+1}}} - \left. h_{j+1} 
 \left( f'' (x_j) + h_{j+1} f'''(x_j)+\frac{h^2_{j+1}}{2} f^{(4)} (\tau_{j_4}) \right)\right\}\\
%
& = & \frac{1}{h_j + h_{j+1}} \left( \frac{h^3_{j+1}}{4} f^{(4)} (\tau_{j_1}) +
 \frac{h^3_j}{4} f^{(4)} (\tau_{j_2}) - \frac{h^3_j}{2} f^{(4)} (\tau_{j_3}) 
 - \frac{h^3_{j+1}}{2} f^{(4)} (\tau_{j_4}) \right),
\end{eqnarray*}
%
mit $\tau_{j_i} \in [x_{j-1}, x_{j+1}], \; i = 1,2,3,4$.
%
\[
 \Longrightarrow  |r_j| \le \frac{3}{4} L \frac{h^3_{j+1} + h^3_j}{h_j + h_{j+1}} 
   \le \frac{3}{4} L \sigma^2_m.
\]
Insgesamt gilt 
\[
 \| r \|_\infty \le \frac{3}{4} L \sigma^2_m \Longrightarrow
\]
%
\eq{4.3.28}
 \|A (M-F) \|_\infty \le \frac{3}{4} L \sigma^2_m \Longrightarrow \| M-F\|_\infty
 \le \frac{3}{4} L \sigma^2_m,
\en
da $A$ monoton.

%
Sei $x \in [x_{j-1}, x_j].$ Dann folgt
%
\begin{eqnarray*}
 S'''_\Delta - f'''(x) & = & \frac{M_j - M_{j-1}}{h_j} - f''' (x) \\
%
 & = & \frac{M_j - f'' (x_j)}{h_j} - \frac{M_{j-1} - f'' (x_{j-1})}{h_j}\\
 & & + \frac{\left[ f''(x_j) - f''(x) \right] -
       \left[ f''(x_{j-1}) - f'' (x) \right]}{h_j} - f'''(x).
\end{eqnarray*}
%
Taylorentwicklung um $x$ und (\ref{4.3.28}) $\Longrightarrow$
%
\begin{eqnarray*}
 |S'''_\Delta (x) - f'''(x) | &\le& \frac{3}{2} L \frac{\sigma_m^2}{h_j}+
 \frac{1}{h_j} \left| (x_j-x) f''' (x) + \frac{(x_j-x)^2}{2} f^{(4)} (\eta_1)-
 (x_{j-1} - x) f'''(x) \right.\\
&&
\qquad \qquad \qquad \left. - \frac{(x_{j-1}-x)^2}{2} f^{(4)} (\eta_2) - h_j f'''(x) \right| \\
%
&\le& \frac{3}{2} L \frac{\sigma_m^2}{h_j} + \frac{1}{2} \frac{\sigma^2_m}{h_j}L, \; \tau_1, \tau_2 \in [x_{j-1}, x_j] \\
%
&\le& 2 L \kappa \sigma_m, \mbox { wegen Vor. } \frac{\sigma_m}{h_j} \le \kappa.
\end{eqnarray*}
Hierbei wurde noch $\max_{x\in[x_{j-1},x_j]}\{(x_j-x)^2+(x-x_{j-1})^2\}=h_j^2$
benutzt.
%
Nun gibt es f\"ur jedes $x \in (a,b)$ ein $x_j$ mit
%
\begin{eqnarray*}
  |x_j - x | &\le& \frac{1}{2} \sigma_m  \\
 %
\Longrightarrow  f'' (x) - S''_\Delta (x) & = & f'' (x_j) - S''_\Delta (x_j)
 %
  + \int\limits^x_{x_j} \left( f''' (t) - S'''_\Delta (t) \right) dt
\end{eqnarray*}
%
$\Longrightarrow$ mit der Absch\"atzung f\"ur 
$f''' - S'''_\Delta \Longrightarrow$
%
\begin{eqnarray*}
 \left| f'' (x) - S''_\Delta (x) \right| & \le &
 \frac{3}{4} L \sigma^2_m + \frac{1}{2} \sigma_m \cdot 2L\kappa \sigma_m\\
%
 & \le & \frac{7}{4} L\kappa \sigma^2_m,  \mbox { da } \kappa \ge 1.
\end{eqnarray*}
%
Damit haben wir die Absch\"atzung f\"ur $f'' - S''_\Delta.$\\
Es gilt $f(x_{j-1}) = S_\Delta (x_{j-1}), f(x_j) = S_\Delta (x_j).$ Au{\ss}er den
Randpunkten $\alpha_0 = a, \alpha_{n+1} = b$ gibt es also noch den Satz von Rolle
$n$ Stellen $\alpha_j \in (x_{j-1}, x_j)$ mit 
\[
 f'(\alpha_j) = S'_\Delta (\alpha_j) \quad j = 0, \dots, n+1.
\]
%
Es gilt also f\"ur jedes $x \in [a,b]$ ein $\alpha_j$ mit
$|\alpha_j - x| < \sigma_m.$ Daher gilt f\"ur alle $x \in [a,b]:$
%
\begin{eqnarray*}
  f'(x) - S'_\Delta (x) &= &\int\limits^x_{\alpha_j(x)} \left( 
  f'' (t) - S''_\Delta (t) \right) dt\\
  \Longrightarrow 
 \left| f'(x) - S'_\Delta (x) \right| &\le& \frac{7}{4} L\kappa \sigma^2_m \cdot \sigma_m
 = \frac{7}{4} L\kappa \sigma^3_m.
\end{eqnarray*}
%
Analog folgt f\"ur $x \in [a,b]$ (Hier wieder $|x-x_j|\le \frac{1}{2}\sigma_m$)
\[
 f(x) - S_\Delta (x) = \int\limits^x_{x_j} f' (t) - S'_\Delta (t) dt
\]
%
und damit
%
\[
 \left| f(x) - S_\Delta (x) \right| \le \frac{7}{4} L\kappa \sigma^3_m \frac{1}{2}
 \sigma_m = \frac{7}{8} L\kappa \sigma^4_m.
\]
\eproof
Es g\"abe noch viel mehr zu Splines zu sagen. 
