%
\section{Polynominterpolation}
Notation $\Pi_n = \{$ reelle oder komplexe Polynome vom Grad $\le n\}.$
%
\begin{theorem}[Lagrange Interpolation] \label{4.1.1}
Seien $n+1$ St\"utzpunkte $(x_i, f_i),\; i = 0, \dots, n$
beliebig mit $x_i \neq x_k$ f\"ur $i \neq k$. Dann gibt es ein eindeutiges
Polynom $P \in \Pi_n$, mit
%
\eq{4.1.2}
 P(x_i) = f_i \quad i = 0, \dots, n.
\en
%
\end{theorem}
%
\proof
Wir zeigen zuerst die Eindeutigkeit. Angenommen es g\"abe $P_1, P_2 \in \Pi_n$
\[
 P_1 (x_i) = P_2 (x_i) = f_i \quad i = 0, \dots, n.
\]
%
Sei $P = P_1 - P_2 \in \Pi_n.$ $P$ hat grad $\le n$ und mindestens
$n+1$ verschiedene Nullstellen
$x_i, i = 0, \dots, n. \Longrightarrow P \equiv 0 \Longrightarrow
 P_1 = P_2.$

%
Die Existenz folgt per Konstruktion. Sei
%
\eq{4.1.3}
 L_i (x) = \prod^n_{j = 0 \atop j \neq i} \frac{(x-x_j)}{(x_i-x_j)}.
\en
%
Es gilt wegen a), da{\ss} $L_i$ die eindeutigen L\"osungen der Aufgabe
%
\eq{4.1.4}
 L_i (x_k) = \delta_{ik} = \left\{ \begin{array}{cl}
                                 1 & i = k\\
                                 0 & i \neq k \end{array} \right., k = 0,\,\,\dots,n
\en
%
sind. Dann folgt
%
\eq{4.1.5}
 P(x) = \sum\limits^n_{i=0} f_i L_i (x) = \sum\limits^n_{i=0}
 f_i \prod^n_{j = 0 \atop j \neq i} \left( \frac{x-x_j}{x_i - x_j} \right)
\en
%
l\"ost die Interpolationsaufgabe.
\eproof
%
$L_i (x)$ in \ref{4.1.3} hei{\ss}en Lagrange--Interpolations--Polynome. Sie bilden
Basis f\"ur $\Pi_n.$\\
Andere Basis $x^0, x^1, \dots, x^n.$\\
F\"ur die praktische Berechnung sind die $L_i (x)$ nicht geeignet, genauso wie die
Standardbasis. F\"ur numerische Zwecke besser Neville-Aitken--Methode
oder Newton'sche Interpolationsformel. Dazu f\"uhre zuerst dividierte Differenzen ein.
%
\begin{definition}\label{4.1.6}
Seien $(x_i, f_i),\; i = 0, \dots, n$ gegeben. Der Ausdruck
\[
 f[x_i, x_{i+1} , \dots, x_{i+k}],
\]
welcher durch die Rekursionen 
%
\eq{4.1.7}
 f[x_i] = f_i
\en
%
\eq{4.1.8}
 f[x_i, x_{i+1}, \dots, x_{i+k}] :=
 \frac{f[x_{i+1}, x_{i+2}, \dots , x_{i+k}] - f[x_i, x_{i+1}, \dots, 
 x_{i+k-1}]} {x_{i+k} - x_i},
\en 
%
$ i = 0, \dots, n, \;k = 0, \dots, n-i$
gegeben ist, hei{\ss}t k--te dividierte Differenz von $(x_i, f_i), \dots,
(x_{i+k}, f_{i+k}).$ Es gibt ein einfaches Schema zur Berechnung der
dividierten Differenzen.
\end{definition}
%
\begin{tbl}[Schema der dividierten Differenzen]\label{4.1.9}
%
\[
\begin{array}{c|ccccccc}
   &k = 0  &&  k = 1  &&  k = 2  && k=3\\ \hline
%
x_0&f_0=f[x_0]&{\phantom{\nearrow}\atop\searrow}&\\
   &          &                       &f[x_0,x_1]=\frac{f[x_1]-f[x_0]}{x_1-x_0}&{\phantom{\nearrow}\atop\searrow}& \\
x_1&f_1=f[x_1]&{\nearrow\atop\searrow}&                                        &                       &f[x_0,x_1,x_2] &{\phantom{\nearrow}\atop\searrow}\\
   &          &                       &f[x_1,x_2]=\frac{f[x_2]-f[x_1]}{x_2-x_1}&{\nearrow\atop\searrow}&                   &        &f[x_0,\dots, x_3]\\
x_2&f_2=f[x_2]&{\nearrow\atop\searrow}&                                        &                       &f[x_1,x_2,x_3]&{\nearrow\atop\searrow}&  \\
   &          &                       &f[x_2,x_3]=\frac{f[x_3]-f[x_2]}{x_3-x_2}&{\nearrow\atop{\searrow}}&  \vdots \\
x_3&f_3=f[x_3]&{\nearrow\atop\searrow}&  \vdots  & & \\
x_4&  \vdots  &  & & \\
 \vdots  & & & & 
\end{array}
\]
\end{tbl}
%
Einfach rekursiv zu berechnen.\\
$\longrightarrow$ \"Ubung \ref{numI/uebung055}\\
Bei der Newtoninterpolation verwendet man eine andere Basis: $N_0 (x) = 1$
%
\eq{4.1.10}
 N_i (x) = \prod^{i-1}_{j=0} (x-x_j) = (x-x_0) (x-x_1) \cdots
 (x-x_{i-1}) \quad i = 1, \dots, n
\en
%
Das Interpolationspolynom ist dann
%
\eq{4.1.11}
 P(x) = \sum\limits^n_{i=0} a_i N_i (x).
\en
%
Die Koeffizienten $a_i$ k\"onnen aus den Formeln
%
\eq{4.1.12}
\begin{array}{rclcl}
 f_0 & = & P(x_0) & = & a_0\\
 f_1 & = & P(x_1) & = & a_0 + a_1 (x_1 - x_0) \nonumber\\
 f_2 & = & P(x_2) & = & a_0 + a_1 (x_2 - x_0) + a_2(x_2 - x_0)(x_2 - x_1) \nonumber\\
 & \vdots & & & \nonumber
\end{array}
\en
bestimmt werden.\\
Es gilt sofort, da{\ss}
%
\eq{4.1.13}
 P_{0 \dots k} (x) = \sum\limits^k_{j=0} a_j N_j (x)
\en
%
die Interpolationsaufgabe f\"ur $(x_i, f_i) \quad i = 0, \dots, k$
erf\"ullt, f\"ur $k = 0, \dots, n$.\\
Sei $P_{i,i+1,\dots,i+k}$ das Polynom das die Interpolationsaufgabe f\"ur
$(x_j, f_j),\; j = i,i+1,\dots, i+k$ erf\"ullt.\\
Dann gilt
%
\begin{theorem}\label{4.1.14}
\[
\begin{array}{rcl}
 P_{i,i+1,\dots,i+k}(x) & = & f[x_i] + f[x_i, x_{i+1}] (x-x_i) + \cdots \\
 & & + f[x_i, x_{i+1}, \dots, x_{i+k}](x-x_i) \cdots (x-x_{i+k-1})
\end{array}
\]
%
\end{theorem}
%
\proof [Vollst\"andige Induktion]
Richtig f\"ur $k = 0.$ Induktionsvor.: Richtig f\"ur $k - 1 \ge 0.$\\
Nun gilt
%
\eq{4.1.15}
 P_{i,i+1,\dots,i+k}(x) = P_{i,i+1,\dots,i+k-1} (x) + a(x-x_i) \cdots (x-x_{i+k-1})
\en
%
per Konstruktion, wobei $a$ gerade der Koeffizient von $x^k$ in
$P_{i,i+1,\dots,i+k}(x)$ ist. Zu zeigen ist, da{\ss}
%
\eq{4.1.16}
 a = f[x_i, \dots, x_{i+k}]
\en
%
Nach IV sind die h\"ochsten Koeffizienten von $P_{i,\dots,i+k-1}$ und
$P_{i+1,\dots,i+k}$ gerade $f[x_i, \dots, x_{i+k-1}]$ und
$f[x_{i+1}, \dots, x_{i+k}]$, also 
%
\begin{eqnarray*}
 P_{i,\dots,i+k-1}(x) & = & \cdots + f[x_i, \dots, x_{i+k-1}]x^{k-1}\\
 P_{i+1,\dots,i+k}(x) & = & \cdots + f[x_{i+1}, \dots, x_{i+k}]x^{k-1}.
\end{eqnarray*}
%
Nun erf\"ullen die $P_{i, \dots, i+k}$ gerade die Rekursionsformel (Neville--Formel)
%
\eq{4.1.17}
 P_{i,\dots,i+k}(x) = 
 \frac{(x-x_{i+k}) P_{i,\dots, i+k-1}(x) - (x - x_{i}) P_{i+1, \dots, i+k} (x)}
 {x_{i+k} - x_i},
\en
wie man sofort durch Einsetzen und Satz \ref{4.1.1}
erh\"alt. Also folgt, da{\ss} der Koeffizient von $x^k$  
%
\eq{4.1.18}
 \frac{f[x_{i+1}, \dots, x_{i+k}] - f[x_i, \dots, x_{i+k-1}]}{x_{i+k} - x_i}
 = f[x_i, \dots, x_{i+k}]
\en
%
nach (\ref{4.1.8})
\eproof
%
Also sind die Werte in der ersten Zeile des Dividierten Differenzen Schemas 
gerade die Koeffizienten des Newton--Polynoms.
%
\begin{example}\label{4.1.19}
\begin{tabular}{c|c|c|c|}
 $x_i =$ & $0$ & $1$ & $3$\\ \hline
 $f_i =$ & $1$ & $3$ & $2$ 
\end{tabular}
%

Dividierte Differenzen Schema
%
\[
\begin{array}{c|ccccc}
 x_0=0&f[x_0]=1&
{\phantom{\nearrow}\atop\searrow}
                   &            &             &\\
       &       &   &f[x_0,x_1]=2           &
{\phantom{\nearrow}\atop\searrow}
                                              &\\
 x_1=1&f[x_1]=3&                           
{\nearrow\atop\searrow}
                   &                       &  &f[x_0,x_1,x_2]=-\frac{5}{6}\\
        &      &   &f[x_1,x_2]=-\frac{1}{2}&
{\nearrow\atop\phantom{\searrow}}
                                             &\\
 x_2=3&f[x_2]=2&
{\nearrow\atop\phantom{\searrow}}
                   &                       &  & 
\end{array}
\]
%
\[
 P_{0,1,2}(x) = 1 + 2 (x-0) - \frac{5}{6} (x-0) (x-1)
\]
%
\end{example}

Auswertung von $P_{0,\dots,n}(x)$ mit Hornerartigem Schema.\\
Vorteile der dividierten Differenzen und des Newton--Schemas.
\begin{itemize}
\item Weitere St\"utzstellen m\"oglich.
\item Man erh\"alt Interpolationspolynom, welches
 mit Hornerartigem Schema leicht zu berechnen ist.
\item $f[x_0, \dots, x_k]$ symmetrisch in $x_i$, d.h. auf Anordnung
kommt es nicht an. Siehe {\it Numerische Mathematik}, Stoer.
\item Rundungsfehlereinflu{\ss} l\"a{\ss}t sich durch Umordnung reduzieren.\\
\item 
   $f[x_0, \dots, x_n] = \frac{f^{(n)}(\xi)}{n!}$, f\"ur ein $\xi \in {\cal C}[x_0,\dots,x_n].$
\end{itemize}
$\longrightarrow$ \"Ubung \ref{numI/uebung055}, \ref{numI/uebung056}: einfache Interpolationsaufgabe, 
mehr zu Dividierten Differenzen.

%
Dividierte Differenzen lassen sich auf zusammenfallende St\"utzstellen erweitern
falls $f(x_j)=f(x_i)$.
%
\begin{eqnarray*}
 f[x_k, x_k] & := & \lim\limits_{h \to 0} \frac{f[x_k + h] - f[x_k]}
 {x_k + h - x_k} = f' (x_k)\\
 f[x_k, x_k, x_k] & := & \lim\limits_{h \to 0} 
 \frac{f[x_k + h, x_k + 2h]-f[x_k, x_k + h]}{x_k -2h - x_k} \\
 & = & \lim\limits_{h \to 0} \frac{f[x_k + 2h] - 2f[x_k + h] + f[x_k]}{2h^2}\\
 & = & \frac{1}{2} f'' (x_k)\\
 f[\underbrace{x_k, \dots, x_k}_{m+1~{\rm mal}}] & := & \frac{1}{m!} f^{(m)} (x_k).
\end{eqnarray*}
%
Damit kann man dann allgemeine \underline{Hermite Interpolation} durchf\"uhren,
bei der f\"ur mehrfache St\"utzstellen jeweils die entsprechenden Ableitungen
mit interpoliert werden.
%
%
\begin{example}\label{4.1.20}
{\scriptsize
\[
\begin{array}{c|ccccccccccc}
%0
\multicolumn{1}{c}{}    & c_0  &&&&&&&&&&\\
%1
 x_0&f[x_0]&{\phantom
             {\nearrow}
             \atop
             \searrow}&   c_1    &          &           &          &&&&&\\
%2
    &      &          &f'(x_0)   &{\phantom
                                  {\nearrow}
                                   \atop
                                   \searrow}& c_2       &          &&&&&\\
%3
 x_0&f[x_0]&{\nearrow
             \atop
             \searrow}&           &         &\frac{1}{2}
                                             f''(x_0)   &{\phantom
                                                          {\nearrow}
                                                          \atop
                                                          \searrow}&c_3&&&& \\
%4
    &          &          &f'(x_0)    &{\nearrow
                                        \atop
                                        \searrow}&            &          &f[x_0,x_0,x_0,x_1]&{\phantom
              {\nearrow}
                                                                                                  \atop
                                                                                                  \searrow}&c_4&&\\
%5
  x_0&f[x_0]   &{\nearrow
                 \atop
                 \searrow}&           &          &f[x_0,x_0,x_1]&{\nearrow
                                                                \atop
                                                                \searrow}&                     &&f[x_0,x_0,x_0,x_1,x_1]&{\phantom
 												      {\nearrow}
                                                          					      \atop
					                                                              \searrow}& c_5\\
%6
     &         &          &f[x_0,x_1] &{\nearrow
                                        \atop
                                        \searrow}&              &        &f[x_0,x_0,x_1,x_1]                  &{\nearrow
 		  \atop
                  \searrow}&          &          &f[x_0,x_0,x_0,x_1,x_1,x_1]\\
%7
  x_1&f[x_1]   &{\nearrow
                 \atop
                 \searrow}&           &          &f[x_0,x_1,x_1]&{\nearrow
                               				        \atop
			                                        \searrow}&                     &          &f[x_0,x_0,x_1,x_1,x_1]&{\nearrow
     \atop
     \phantom
     {\searrow}}&\\
%8
     &          &         &f'(x_1)    &{\nearrow
                                        \atop
                                        \searrow}&              &        &f[x_0,x_1,x_1,x_1]                 &{\nearrow
											        \atop
											        \phantom
                                                                                               {\searrow}}&&&\\
%9
  x_1&f[x_1]    &{\nearrow
                 \atop
                 \searrow}&           &          &\frac{1}{2} 
                                                  f''(x_1)      &{\nearrow
								  \atop
								  \phantom
                                                             {\searrow}}&                    &            &&&\\
%10
     &          &         &  f'(x_1)  &{\nearrow
					\atop
					\phantom
                                      {\searrow}}&              &       &                    &            &&&\\
%11
  x_1&f[x_1]&{\nearrow
	      \atop
	      \phantom
              {\searrow}} &           &          &              &       &                    &            &&&
\end{array}
\]
}
%
Das Interpolationspolynom ist damit
%
\begin{eqnarray*}
 P_{000111} (x) & = & c_0 + c_1 (x-x_0) + c_2 (x-x_0)^2 + c_3 (x-x_0)^3\\
 & & + c_4 (x-x_0)^3 (x-x_1) + c_5(x-x_0)^3 (x-x_0)^2.
\end{eqnarray*}
%
$\longrightarrow$ \"Ubung
\end{example}
%
\begin{example}\label{4.1.21}
 $x_0, x_0, x_1, x_1, \dots \quad$ Schema ergibt
%
\begin{eqnarray*}
 P_{00 11 22 \dots kk} (x) & = & [c_0 + c_1 (x-x_0)] +
 [c_2 + c_3 (x-x_1)](x-x_0)^2\\
 & & + [c_4 + c_5 (x-x_2)](x-x_0)^2 (x-x_1)^2 + \cdots \\
 & & + [c_{2k} + c_{2k-1} (x-x_k)] (x-x_0)^2 \cdots (x-x_{k-1})^2
\end{eqnarray*}
%
Es gilt die Bedingung
%
\[
\left. \begin{array}{lcl}
 P_{00 \dots kk}(x_i) & = & f(x_i) \\
 P'_{00 \dots kk} (x_i) & = & f' (x_i) \end{array}\right\} i = 0, \dots, k
\]
%
$\longrightarrow$ \"Ubung

\underline{Fehlerabsch\"atzung}:
Angenommen $f_i = f(x_i) \quad i = 0, \dots, n.$\\
Wie gut ist die Approximation?
\end{example}
%
\begin{theorem}\label{4.1.22}
Es sei $f \quad n + 1$--mal differenzierbar, so gibt es zu jedem $\hat{x}$ eine Zahl $\xi$
aus dem kleinsten Intervall $I$, da{\ss} alle $x_i$ und $\hat{x}$ enth\"alt
(konvexe H\"ulle ${\cal C}[x_i, \hat{x}]$), so da{\ss}
%
\eq{4.1.23}
 f(\hat{x}) - P_{0 1 \dots n}(\hat{x}) = w(\hat{x}) \frac{f^{(n+1)} (\xi)}
 {(n+1)!}
\en
wobei $w(x) = \prod^n_{i=0} (x-x_i).$
\end{theorem}
%
\proof
Sei f\"ur $\hat{x} \neq x_i$
\[
 F(x) : = f(x) - P(x) - kw (x).
\]
%
Bestimme $k$ derart, da{\ss} $F(\hat{x}) = 0.$ Dann hat $F(x)$ in
${\cal C}[x_0, \dots, x_n, \hat{x}] \quad n+2$ Nullstellen $x_0, \dots, x_n, \hat{x}.$\\
Nach dem Satz von Rolle hat dann $F'(x)$ mindestens $n+1$ Nullstellen, ...,
$F^{(n+1)} (x)$ mindestens eine Nullstelle  
$\xi \in {\cal C} [x_0, \dots, x_n \hat{x}].$
%
\begin{eqnarray*}
 P^{(n+1)} (x) \equiv 0 & \Longrightarrow & F^{(n+1)} ( \xi ) =
 f^{(n+1)} (\xi) - k(n+1) ! = 0\\
 & \Longrightarrow & k = \frac{f^{(n+1)} (\xi)}{(n+1)!}.
\end{eqnarray*}
%
\eproof
%
Wie sieht $w(x)$ aus?

\unitlength 1cm
\begin{picture}(16,8)
% \put(0,0){\epsfig{file=includeps/w1.ps,width=8cm,clip=}}
% \put(8,0){\epsfig{file=includeps/w2.ps,width=8cm,clip=}}
\put(0,0){\includegraphics[width=0.50\linewidth,height=0.50\linewidth]{includeps/w1}}
\put(8,0){\includegraphics[width=0.50\linewidth,height=0.50\linewidth]{includeps/w2}}
\end{picture}

W\"achst au{\ss}erhalb von ${\cal C} [x_0, \dots, x_n]$ stark an $\Longrightarrow$
Verwendung des Interpolationspolynoms au{\ss}erhalb von ${\cal C} [x_0, \dots, x_n]$
vermeiden.

Sei nun $f:[a,b] \to \R$ gegeben, $f$ gen\"ugend glatt. Dann kann ich $f$ beliebig
genau durch Polynome interpolieren. Man k\"onnte nun vermuten, da{\ss} die
Interpolationspolynome gegen $f$ konvergieren, 
falls ich die Intervallunterteilung
feiner und feiner mache.

Betrachte Folge von Unterteilungen
%
\begin{eqnarray*}
 \bigtriangleup_m & = & \{ a = x^{(m)}_0 < x_1^{(m)} < \cdots < x^{(m)}_{n_m}=b \} \\
 \| \bigtriangleup_m \| & = & \max\limits_i |x^{(m)}_{i+1} - x^{(m)}_i |
\end{eqnarray*}
%
%
\begin{theorem}\label{4.1.24}[Satz von Faber]
Zu jeder Folge von Intervalleinteilungen $\bigtriangleup_m$ von $[a,b]$ kann
man eine auf $[a,b]$ stetige Funktion $f$ finden, so da{\ss} die Polynome 
$P_{\bigtriangleup_m}$ die auf $(x^{(m)}_i, f(x^{(m)}_i)), i = 0, \dots, n_m$
interpolieren f\"ur $m \to \infty$ NICHT gleichm\"a{\ss}ig gegen $f(x)$ konvergieren.
\end{theorem}

Nur f\"ur ganze Funktionen gilt f\"ur alle $\|\bigtriangleup_m \| \to 0 \,\,,
P_m \to f$ gleichm\"a{\ss}ig.

F\"ur beliebige stetige Funktionen gibt es spezielle  $\bigtriangleup_m$, i.a. nicht
\"aquidistant.
 
 $\longrightarrow$ \"Ubung \ref{numI/uebung062}:  Tschebyschowknoten f\"ur $f(x) = \frac{1}{1+25x^2}$.\\
$\longrightarrow$ \"Ubung:  Orthogonale Polynome f\"ur Approximation.\\
Rationale Interpolation, hier nicht, \"Ubung?
%


