approximation.tex

%\section{Approximation von Funktionen}
% hat er es nur umbenannt?, ja glaub schon
\section{Interpolation}
Aufgabenstellung: Aus einer festgelegten Menge von Funktionen $M_n$ 
bestimme man eine Funktion, die durch die gegebenen Punkte
$(x_0, f_0), (x_1, f_1), \cdots, (x_n, f_n) \in \mathbb{R}^2$ verläuft.

\missingfigure{Funktion mit Stützstellen}
Die Wahl von $M_n$ ist abhängig von der Problemstellung:
\begin{itemize}
  \item $\Pi_n$: Menge der Polynome mit Grad $\leq$ n
  \item stückweise polynomiale Funktion
  \item trigonometrische Funktion
	\item $\cdots$
\end{itemize}
Warum und weshalb:
\begin{itemize}
  \item Berechnung von Zwischenwerten einer Funktion, die nur an wenigen 
    Stellen bekannt ist
  \item Vereinfachung der Komplexität einer Funktion. (Beschreibung
    einer Funktion durch eine kleine Anzahl von Funktionen) $\Rightarrow$
    einfacheres Rechnen
  \item wichtige theoretische Grundlage für verschiedene andere numerische
    Aufgaben (Integration, Differenzialgleichungen)
\end{itemize}

\subsection{Polynominterpolation}
\underline{Gegeben}: Paarweise verschiedene Stützstellen $x_0, x_1, \cdots x_n$ und
Werte $f_0, f_1, \cdots f_n$.\\
\underline{Gesucht}:
\begin{equation*}
  \tag{2.1} p_n \in  \Pi_n \text{, so dass } p_n(x_i) = 
  f_i \text{ für } i = 0, 1, \cdots ,n
\end{equation*}
Grundlegende Fakten zu Polynomen:
\begin{enumerate}[(i)]
  \item $\Pi_n$ die Menge der Polynome mit Grad $\leq$ n ist ein Vektorraum
  \item Die Monome $1, x, x^2, \cdots, x^n$ bilden eine Basis von $\Pi_n$
  \item Polynom von Grad n $\geq$ 1 mit komplexen Koeffzienten besitzt genau n-Nullstellen
    in $\mathbb{C}$, wobei die Anzahl der Nullstellen entsprechend der Vielfachheit
    gezählt wird.
\end{enumerate}
\para{Satz} Die Polynominterpolationsaufgabe (2.1) ist eindeutig lösbar\\
Beweis:
\begin{enumerate}[(a)]
  \item Eindeutigkeit: Angenommen $p_n, q_n \in \Pi_n$ erfüllen (2.1), d.h. $p_n(x_i)=q_n(x_i)=f_i $für i=0,1,...n\\
    $r := p_n - q_n \in \Pi_n$ \\
    $r(x_i) = 0$ für $i = 0, \cdots, n \Rightarrow r$ hat $n + 1$ Nullstellen
    $\Rightarrow r \equiv 0 \Rightarrow p_n \equiv q_n$
  \item Existenz: Konstruiere Polynome $L_0(x), L_1(x), \cdots, L_n(x) \in \Pi_n$ mit\\
    $L_i(x_k)=\begin{cases} 1 & \mbox{für } \mbox{ $i = k$} \\ 
      0 & \mbox{sonst} \end{cases}$ \\
    $\Rightarrow L_i$ hat n Nullstellen: $x_0, x_1, \cdots, x_{i-1}, x_{i+1}, \cdots, x_n$
		\begin{align*}    
		L_i \in \Pi_n \Rightarrow L_i(x) = a(x-x_0)(x-x_1)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_n)\\
    L_i(x_i) \mustbe 1 \Rightarrow
      a = \frac{1}{(x_i-x_0)(x_i-x_1)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)}\\
    \end{align*}
		\begin{empheq}[innerbox=\fbox,right=\Leftarrow{\text{LAGRANGE-POLYNOME}}]{align*}
		\Rightarrow L_i(x) = \frac{(x - x_0)\cdots}{(x_i - x_0)\cdots} = 
      \prod\limits_{j = 0,\,j \neq i}^n \frac{x - x_j}{x_i - x_j} \\
		\end{empheq}
    \begin{equation*}
      \tag{2.2}
      p_n(x) = f_0 L_0(x) + f_1 L_1(x) + \cdots + f_n L_n(x) = 
      \sum\limits_{k = 0}^n f_k L_k(x)
    \end{equation*}
    $p_n(x_i) = 0 + 0 + \cdots + f_i\underbrace{L_i(x_i)}_{1} + 0 + \cdots = f_i$\\
\end{enumerate}

% 17.10.2012
Wh. Polynominterpolation

\begin{align*}
\text{geg.} \hspace{0.5cm} & (x_0,f_0),\cdots\,,(x_n,f_n) \\
\text{ges.} \hspace{0.5cm} & p_n \in \Pi_n:p_n(x_i)=f_i & \Rightarrow p_n(x) = f_0\,L_0+\cdots\,+f_n\,L_n(x) \hspace{1cm} (2.2)\\
& & L_i(x)=\prod\limits_{i=0,i\neq\,j}^n \frac{x-x_j}{x_i-x_j}
\end{align*}

\begin{equation*} 
  L_i(x_k)
	\left\{  
  \begin{aligned} 
   & i=k: 1 \\ 
   & i\neq\,k: 0\\
  \end{aligned} 
	\right.
\end{equation*} 

(2.2) nennt man Lagrange-Darstellung des Interpolationspolynoms [theoretisch von Interesse]

\subsubsection{Effiziente Berechnung und Auswertung des IPs (Newton-Darstellung)}
\underline{Nachteile der Lagrange-Darstellung:}

\begin{itemize}
	\item Hinzunahme neuer Daten ($x_{n+1},f_{n+1}) \Rightarrow$ komplett neue Berechnung notwendig
	\item Auswertung des IPs ist nicht effizient $L_i$
\end{itemize}

\para{Definition}
Zu $x_0,\cdots\,x_n$ sind die Newton-Basispolynome definiert durch:\\

\begin{align*}
&N_0 \equiv 1\\
&N_1(x) = (x-x_0)\\
&N_2(x) = (x-x_0)(x-x_1)=N_1(x)(x-x_1)\\
&\vdots \\
&N_n(x) = (x-x_0)(x-x_1)\cdots\,(x-x_{n-1})=N_{n-1}(x)(x-x_{n-1})
\end{align*}
$N_0,\cdots\,,N_n$ bilden eine Basis von $\Pi_n$ (lässt sich einfach zeigen).\\
Ansatz: für Polynominterpolation $(x_0,f_0)\cdots\,(x_n,f_n)$:\\
Suche: $a_0,\cdots\,,a_n$ so dass 

\begin{align*}
p_n(x)&=a_0\,N_0(x) + \cdots\, + a_n\,N_n(x) \quad \text{und} \\
p_n(x_i)&= f_i \quad \text{für} \quad i=0\cdots\,n \\
f_0 &\mustbe p_n(x_0) = a_0\,\underbrace{N_0(x_0)}_{1} + \underbrace{a_1\,\underbrace{N_1(x_0)}_{(x_0-x_0)} + \cdots + a_n\,N_n(x_0)}_{=0} \\
& \Rightarrow a_0 = f_0 \\
f_1 &\mustbe p_n(x_1) = a_0\cdot\,1 + a_1\,(x_1-x_0) + \underbrace{a_2\,(x_1-x_0)(x_1-x_1)}_{=0} + 0  \\
& a_1 = \frac{f_1-a_0}{x_1-x_0}\\
f_n &\mustbe p_n(x_n) = a_0\,N_0(x_n) + \cdots + a_n\,N_n(x_n) \\
& a_0,\cdots\,,a_n \quad \text{lassen sich durch Vorwärtseinsetzen bestimmen}
\end{align*}\\

\underline{Effizienter Algorithmus:} Dividierte Differenzen
\para{Definition}
Zu $(x_0,f_0),\cdots\,,(x_n,f_n)$ mit $x_i\neq\,x_j$ für $i\neq\,j$ sind die div. Differenzen definiert durch
\begin{align*}
f[x_i] &= f_i \quad i=0\cdots\,n\\
f[x_i,x_{i+1},\cdots\,,x_{i+m}] &:= \frac{f[x_{i+1},\cdots\,,x_{i+m}]-f[x_{i},\cdots\,,x_{i+m-1}]}{x_{i+m}-x_i}
\end{align*}

\para{Satz}
Sei $p_n\in\,\Pi_n$ das IP zu $(x_0,f_0)\cdots\,(x_n,f_n)$ dann gilt:
\begin{equation*}
p_n(x) = f[x_0]\,N_0(x)+f[x_0,x_1]\,N_1(x)+\cdots\,+f[x_0,x_n]\,N_n(x)
\end{equation*}
Beweis erfordert mehr als "`Einsetzen"'. \\
\underline{Schema zur Berechnung:}

\begin{tabular}{c|l}
$x_0$ & $f_0 = f[x_0] \searrow$ \\
$x_1$ & $f_1 = f[x_1] \rightarrow f[x_0,x_1]  \searrow$ \\
$x_2$ & $f_2 = f[x_2] \rightarrow f[x_1,x_2] \rightarrow f[x_0,x_1,x_2]$\\
$\vdots$ &  \\
$x_{n-1}$ & $f_{n-1} = f[x_{n-1}] \rightarrow \cdots \rightarrow f[x_0,\cdots\,,x_{n-1}] \searrow$\\
$x_n$ & $f_n = f[x_n] \rightarrow \cdots \rightarrow f[x_1,\cdots\,,x_n] \rightarrow f[x_0,\cdots\,,x_n]$ \\
\end{tabular}

\para{Einschub: Vollständige Induktion (Beweistechnik)}
Um zu beweisen, dass Aussage A für alle natürlichen Zahlen $n\geq\,n_0$ gilt, reicht es zu zeigen:

\begin{enumerate}
	\item A gilt für $n_0$ [Induktionsanfang, IA] 
	\item Aus der Gültigkeit von A für eine Zahl $n$, folgt eine Gültigkeit von A für $n+1$ [Induktionsschritt, $A(n)\Rightarrow A(n+1)$, IS]
\end{enumerate}

Beispiel: Gauß'sche Summenformel\\
$\sum\limits_{i=1}^{n}{i}=?$\\\\
a) Gauß Lösung\\
\begin{center}
\begin{tabular}{c|c|c|c|c}
	1 & 2 & 3 & $\cdots$ & n \\
	n & n-1 & n-2 & $\cdots$ & 1 \\\hline
  n+1 & n+1 & n+1 & $\cdots$ & n+1
\end{tabular}
$\Rightarrow\,\sum\limits_{i=1}^{n}{i}=\frac{n}{2}(n+1)$ (*)\\
\end{center}
b) Vollständige Induktion

\begin{enumerate}
	\item IA $n_0=1$ $\sum\limits_{i=1}^{n=1}{i}=1\mustbe\,\frac{1}{2}(1+1)=1 \Rightarrow ok$
	\item IS $n \mapsto n+1$ Annahme (*) gilt für n. Zu zeigen: (*) gilt für n+1, d.h. z.z.\\
	$\sum\limits_{i=1}^{n+1}{i}=\frac{1}{2}(n+1)(n+1+1)=\frac{n^2+3n+2}{2}$\\
	$\sum\limits_{i=1}^{n+1}{i}=\underbrace{\sum\limits_{i=1}^{n}{i}}_{Annahme} + n+1$ \\
	$=\frac{n}{2}(n+1) + \frac{2(n+1)}{2}= \frac{n^2+3n+2}{2} \Rightarrow ok$
\end{enumerate}

\para{Behauptung}
Die Berechnung von $f[x_0], f[x_0,x_1],\cdots\,f[x_0,\cdots\,,x_n]$ benötigt $\frac{3n(n+1)}{2}$ Flops. \\
Beweis: Vollständige Induktion\\

\begin{enumerate}
	\item IA, $n_0=1 \quad f[x_0],f[x_0,x_1]=\frac{f[x_1]-f[x_0]}{x_1-x_0} \Rightarrow 3 \mustbe \frac{3\cdot\,1(2)}{2}=3 \Rightarrow ok$
	\item IS $n \mapsto n+1 \quad$ Annahme: Aufwand für $f[x_0], \cdots\,f[x_0,\cdots\,,x_n]$ beträgt $\frac{3n(n+1)}{2}$ Flops. Z.z. für $\underbrace{f[x_0], \cdots\,,f[x_0,\cdots\,,x_n]}_{\text{wissen wir}},f[x_0,\cdots,x_{n+1}]$ sind $\frac{3(n+1)(n+1+1)}{2}$ Flops nötig. \\
Aufwand für $f[x_0,\cdots\,,x_{n+1}]$\\
\begin{tabular}{c|l}
\vdots \\
$x_{n}$ & $f_{n} = f[x_{n}] \searrow$\\
$x_{n+1}$ & $f_{n+1} = f[x_{n+1}] \rightarrow \underbrace{f[x_n,x_{n+1}] \rightarrow f[x_{n-1},x_n,x_{n+1}] \rightarrow f[x_0,\cdots\,,x_{n+1}]}_{\underbrace{\text{n+1 d.D. mit jeweils 3 Flops}}_{3(n+1)}}$ 
\end{tabular}

D.h. insgesamt $\underbrace{f[x_0],\cdots\,,f[x_0,\cdots\,,x_n]}_{\frac{3n(n+1)}{2}} + \underbrace{f[x_0,\cdots\,,x_{n+1}]}_{\frac{2\cdot\,3n(n+1)}{2}} = \frac{(n+2)3(n+1)}{2} \Rightarrow $ ok
\end{enumerate}

\para{2.1.1.1 Horner Schema (Auswertung von Polynomen)}
Naive Auswertung von $p_n(x) = a_0+a_1x+\cdots\,+a_nx^n$ erfordert 

\begin{itemize}
	\item $x^2, x^3,\cdots\,,x^n \rightarrow$ n-1 Multiplikationen
	\item $a_i\cdot\,x^i \quad i = 1\cdots\,n \rightarrow$ n Mulitplikationen
	\item n Additionen
\end{itemize}

\underline{Horner Schema}
$p_n(x) = a_0 + x\cdot\,(a_1 + x\cdot\,(a_2 + \cdots + x\cdot\,(\underbrace{a_{n-2} + x\cdot\,(\underbrace{a_{n-1} + x\cdot\,(a_n))}_{b_{n-1}}}_{b_{n-2}}\cdots\,)$
Auswertung von innen nach außen:

\begin{equation*}
\left.
\begin{aligned}
 b_n &:= a_n \\
 b_{n-1} &:= a_{n-1} + x\,b_n \\
 b_{n-2} &:= a_{n-2} + x\,b_{n-1} \\
 & \vdots \\
 b_{1} &:= a_{1} + x\,b_{2} \\
 b_{0} &:= a_{0} + x\,b_{1} 
\end{aligned}
\right\}
\text{Aufwand:} \\
\text{n Multiplikationen, n Additionen}
\end{equation*}
$\Rightarrow p_n(x) = b_0$\\

Horner Schema zur Auswertung von $p_n$ in Newtondarstellung.\\
\begin{align*}
 p_n(x) &= \underbrace{f[x_0]}_{a_0}\underbrace{N_0(x)}_{1} + \underbrace{f[x_0,x_1]}_{a_1}\underbrace{N_1(x)}_{(x-x_0)}
+ \underbrace{f[x_0,x_1,x_2]}_{a_2}\underbrace{N_2(x)}_{(x-x_0)(x-x_1)} + \cdots + \underbrace{f[x_0,\cdots\,,x_n]}_{a_n}\underbrace{N_n(x)}_{(x-x_0)\cdots(x-x_n)} \\
 &= a_0 + (x-x_0)(a_1 + (x-x_1)(a_2+ \cdots + (x-x_{n-2})(a_{n-1})+(x-x_{n-1})(a_n))\cdots)) \\
\end{align*}
\begin{equation*}
\left.
\begin{aligned}
 b_n &:= a_n \\
 b_{n-1} &:= a_{n-1} + (x-x_{n-1})b_n \\
 b_{n-2} &:= a_{n-2} + (x-x_{n-2})b_{n-1} \\
 \vdots \\
 b_0 &:= a_0 + (x-x_0)b_1
\end{aligned}
\right\}
\text{Aufwand: \\
2n Additionen, \\
n Multiplikationen}
\end{equation*}

\subsubsection{Absolute Kondition der Polynominterpolation}
Geg.: Exakte Daten $(x_0, f_0), \cdots, (x_n, f_n)$ wobei $x_0, \cdots, x_n \in [a, b]$ und
gestörte Daten $(x_0, f_0 + \Delta_0), \cdots, (x_n, f_n + \Delta_n)$ \\
Ges.: Maximale Abweichung der Interpolationspolynome $p_n(x) = \sumizn{f_i L_i(x)}$ und
$p^{\Delta}_n(x) = \sumizn{(f_i + \Delta_i) L_i(x)}$ im Intervall $[a, b]$ \\
WH:
\begin{align*}
  \maxxab |\alpha f(x) + \beta g(x)| &\leq
    \maxxab |\alpha| |f(x)| + \maxxab |\beta| |g(x)| \\
  &\leq max\{|\alpha|, |\beta|\}\, \maxxab\{|f(x)|, |g(x)|\}
\end{align*}

\begin{align*}
  \maxxab |p_n(x) - p^{\Delta}_n(x)| = \maxxab | \sumizn{|\Delta_i L_i(x)} | \leq
  \underset{0 \leq i \leq n}{max}\,|\Delta_i| \maxxab \sumizn{\underbrace{|L_i(x)|}_{\geq 1}}
\end{align*}
Maß für dier Verstärkung des Eingangsfehlers:
\begin{equation*}
  \maxxab \sumizn{|L_i(x)|} =: \Lambda_n(x_0, \dots, x_n) = \Lambda_n 
  \text{Lebesque Konstante}
\end{equation*}
Ändert sich nicht durch affin-lineare Transformation der Stützstellen.
\example{Bsp:} Interpolation von $f(x) =\sin(2\pi x)$ in $[-1, 1]$ mit 21
gleichverteilten Stützstellen. $p_{20}, p_{20}^\Delta$ mit Störung $\Delta_9 = -10^{-3}$
\missingfigure{Sinus interpoliert}

\subsubsection{Fehlerschätzung der Polynominterpolation}
\para{Satz}
Sei $f \in C^{n+1} [a, b]$ ($(n+1)$ mal stetig differenzierbar) und $p_n \in \Pi_n$
das Interpolationspolynom in den paarweise verschiedenen Stützstellen $x_0, \dots, x_n$
interpoliert, dann existiert für jedes $x \in [a, b]$ ein $\zeta \in [a, b]$ so, dass
\begin{align*}
  f(x) - p_n(x) = \frac{1}{(1 + n)!} f^{(n+1)}(\zeta(x))(x - x_0)\cdot \dots \cdot(x - x_n)
\end{align*}
Ist $f \in C^\infty [a, b]$ und gelte $\maxxab |f^{(n)}(x)| \leq M \, \forall n \in \mathbb{N}$ \\
\begin{align*}
  \Rightarrow \maxxab |f(x) - p_n(x)| \leq 
  \frac{1}{(1 + n)!}M(b - a)^{n + 1} \xrightarrow[x\to\,\infty]{} 0
\end{align*}

%TODO define a \subsubsubsction?
\para{Tschebyscheff Interpolation}
Maximale Fehler der Polynominterpolation einer Funktion f ist abhängi von f und ihren
Ableitungen sowie der Wahl der Stützstellen, d.h. vom Term
$(x - x_0)\cdot \ldots \cdot(x - x_n)$. \\
Idee: Wähle $x_0, \ldots, x_n$ so, dass $\maxxab |(x - x_0)\cdot \ldots \cdot(x - x_n)|$
minimal ist. $\Rightarrow$ Minmax-Aufgabe \\
Zunächst: Spezieller Fall $[a, b] = [-1, 1]$. Danach Übertragung auf allgemeins
Intervall. \\
Definition: Die Tschebyscheff-Polynome sind definiert durch
\begin{align*}
  T_o(x) &\equiv 1\\
  T_1(x) &= x\\
  T_n(x) &= 2xT_{n-1}(x) - T_{n-2}(x)\,\, n = 2, 3, \ldots
\end{align*}
Im Intervall $[-1, 1]: T_n(x) = \cos(n\arccos(x))$ (Beweis über Additionstheoreme)
\para{Satz} Für die Nullstellen des Tschebyscheff-Polynoms $T_{n+1}$, 
$\overline{x}_i^{(n+1)} = \cos(\frac{2i + 1}{2(n + 1)}\pi)\, i = 0, \ldots, n$ gilt:
\begin{align*}
  \underset{x_0, \ldots, x_n \in [a, b]}{min} \, \maxxab |(x - x_0)
    \cdot \ldots \cdot(x - x_n)| = 
    \maxxab |(x - \overline{x}_0^{(n + 1)})\cdot \ldots 
    \cdot(x - \overline{x}_n^{(n + 1)})| =\frac{1}{2^n}
\end{align*}
Fehlerabschätzung für 
$\overline{x}_0^{(n + 1)}\cdot \ldots \cdot\overline{x}_n^{(n + 1)}$: 
$\maxmpo|f(x) - p_n(x)| \leq \frac{1}{(n + 1)!} \maxmpo |f^{(n + 1)}| \frac{1}{2^n}$ \\
Allgemerin Fall $[a, b]$: Verwende affin-lineare Transformation für die Stützstellen
$\overline{x}_0^{(n + 1)}\cdot \ldots \cdot\overline{x}_n^{(n + 1)}$:
\begin{align*}
  \psi: [-1, 1] &\longrightarrow [a, b] \\
  x &\longmapsto \frac{1}{2}((b - a)x + a + b) \\
  \psi(-1) = a\,\,&\,\, \psi(1) = b
\end{align*}
Es gilt $\psi(\overline{x}_0^{(n + 1)}),\,\ldots,\,\psi(\overline{x}_n^{(n + 1)})$ ist
Lösung der Minmax-Aufgabe.
% TODO change all \dots to \ldots? add space?

% 2.1.3.2
\para{Indikator für die Güte der Wahl der Stützstellen}
Wie gut ist für eine Funktion f die Polynominterpolation für eine bestimmte Wahl
von $n + 1$ Stützstellen im Vergleich zur bestmöglichen Approximation der Funktion f
durch ein Polynom?
\para{Satz} Sei $f:[a, b] \longrightarrow \mathbb{R}$ stetig.
\begin{enumerate}[(a)]
  \item Es gibt eine Folge von Polynomen $(q_n)$ mit $q_n \in \Pi_n$, so dass
    \begin{equation*}
      \maxxab |q_n(x) - f(x)| \underset{n \to \infty}{\longrightarrow} 0
    \end{equation*}
  \item Es existiert genau eine Bestapproximation $q_n^* \in \Pi_n$ mit
    \begin{equation}
      \tag{2.3}
      \maxxab |q_n^*(x) - f(x)| \leq \maxxab |p(x) - f(x)| \; \forall p \in \Pi_n
    \end{equation}
\end{enumerate}
\para{Satz} Sei $f:[a, b] \longrightarrow \mathbb{R}$ stetig. $\xztoxn$
seien paarweise verschiedene Stützstellen in $[a, b]$. Für $q_n^* \in \Pi_n$ gelte
(2.3). Für das Interpolationspolynom $p_n \in \Pi_n$, das f in den Stützstellen
$\xztoxn$ interpoliert gilt:
\begin{equation*}
  \maxxab |p_n(x) - f(x)| \leq (1 + \Lambda_n(\xztoxn))\,\maxxab |q_n^*(x) - f(x)|
\end{equation*}
\para{Beweis}
\begin{align*}
  \maxxab |p_n(x) - f(x)| &= \maxxab |p_n(x) - q_n^*(x) + q_n^*(x) - f(x)|\\
  &\leq \maxxab |p_n(x) - q_n^*(x)| + \underbrace{\maxxab |q_n^*(x) - f(x)|}_{=:A}\\
  &= \maxxab |\sumizn[f(x_i) - q_n^*(x_i)]L_i(x)| + A\\
  &\leq \underbrace{\maxxab |f(x) - q_n^*(x)|}_A \: \underbrace{\maxxab \sumizn|L_i(x)| + A}_{\Lambda_n}\\
  &= (1 + \Lambda_n) \: \maxxab |f(x) - q_n^*(x)|
\end{align*}