\section{Trigonometrische Interpolation}
Interpolation durch trigonometrische Polynome\\
Betrachte Intervall $[0, 2\pi]$, St\"utzpunkte $(x_k, f_k),\; k = 0,\dots, n-1$.
%
\begin{eqnarray*}
 x_k & = & k \frac{2\pi}{n} \quad f_k \in \C, n \mbox { fest }.\\
 P(x) & = & \beta_0 + \beta_1 e^{ix} + \beta_2 e^{2ix} +
 \cdots + \beta_{n-1} e^{(n-1)xi}
\end{eqnarray*}
%
soll die Interpolationsbedingungen
%
\eq{4.2.1}
  p(x_k) = f(x_k),\; k = 0, \dots, n-1
\en
erf\"ullen. Periodizit\"at $\Longrightarrow$
%
\eq{4.2.2}
 p(x_k) = f(x_k), \; k = \dots, -2, -1, \dots .
\en
%
Setze 
\eq{4.2.3}
 w = e^{ix}, \;  w_k = e^{ix_k}
\en
%
Dann ist die Interpolationsaufgabe identisch
 mit der komplexen Interpolationsaufgabe
%
\eq{4.2.4}
 p (w_k) = f_k
\en
mit 
\[
 p = \beta_0 + \beta_1 w + \cdots + \beta_{n-1} w^{n-1}
\]
%
Also folgt aus Satz \ref{4.1.1} sofort
%
\begin{theorem}\label{4.2.5}
Sei $x_k = \frac{2\pi k}{n}, f_k$ beliebig f\"ur $k = 0,\dots, n-1, n \in \N.$ Dann 
gibt es ein eindeutiges trigonometrisches Polynom $p(w) = \beta_0 + \beta_1 w + \cdots + \beta_{n-1} 
w^{n-1}$ mit $p(w_k) = f_k,$ f\"ur $w_k = e^{ix_k},\; k = 0,\dots,n-1$.\\
Zus\"atzlich gilt
%
\[
\begin{array}{l}
 i) \quad w^j_k = w^k_j \quad \forall j,k \in \Z\\
 ii) \quad \sum\limits^{n-1}_{k=0} w^j_k w^{-l}_k = \left\{ \begin{array}{cl}
      n & \mbox { f\"ur } j = l\\
      0 & \mbox { f\"ur } j \neq l, 0 \le j, l \le n-1.
      \end{array}\right. 
\end{array}
\]
%
\end{theorem}
%
\proof
i) trivial, ii) f\"ur alle $k = \Z$ ist $w_k$ eine Wurzel von
\[
 w^n - 1 = (w-1)(w^{n-1} + w^{n-2} + \cdots + 1) = 0
\]
%
f\"ur $k \neq 0, \pm n, \pm 2n,$ ist $w_k \neq 1$, also folgt
\[
 \sum\limits^{n-1}_{l=0} w^l_k = \left\{ \begin{array}{cl}
  n & k = 0, \pm n, \pm 2n, \dots \\
  0 & \mbox { sonst. } \end{array}\right.
\]
%
Die $n$--Vektoren $\Phi_j = (w^j_0, \dots, w^j_{n-1}), \; j = 0,\dots, n-1$
bilden eine Orthonormalbasis von $\C^n$ unter dem Skalarprodukt
%
\eq{4.2.7}
  [f,g] := \frac{1}{n} \sum\limits^{n-1}_{j=0} f_j \bar{g}_j
\en
%
(diskrete Version von $(f,g)= \frac{1}{\pi} \int\limits^\pi_{-\pi}
f(x) \bar{g(x)} dx)$. Denn es gilt wegen (\ref{4.2.2})
%
\[
 [\Phi_j, \Phi_l] = \left\{ \begin{array}{cl}
                    1 & j = l\\
                    0 & j \neq l \quad 0 \le j,l, \le n-1.
                   \end{array}\right. 
\]
%
Damit erh\"alt man eine explizite Formel f\"ur die Koeffizienten $\beta_i$.
\eproof
%
\begin{theorem}\label{4.2.8}
Sei $p(x) = \sum\limits^{n-1}_{k = 0} \beta_k e^{ikx}$
das interpolierende trigonometische Polynom f\"ur 
$p(x_k) = f_k, \; k = 0, \dots, n-1$, so gilt
%
\eq{4.2.9}
 \beta_j = \frac{1}{n} \sum\limits^{n-1}_{k=0} f_k w_k^{-j} =
 \frac{1}{n} \sum\limits^{n-1}_{k=0} f_k \exp \left\{ \frac{-2\pi ikj}{n} \right\}, \;
 j = 0, \dots, n-1.
\en
\end{theorem}
%
\proof
Aus dem Skalarprodukt $[\bullet,\bullet]$ folgt
\[
 \frac{1}{n} \sum\limits^{n-1}_{k=0} f_k w_k^{-j} =
 [f, \Phi_j] = [\beta_0 \Phi_0 + \cdots + \beta_{n-1} \Phi_{n-1}, \Phi_j]=\beta_j.
\]
%
Es gilt die folgende Minimaleigenschaft der trigonometrischen Interpolation.
\eproof
%
\begin{theorem}\label{4.2.10}
Unter allen trigonometrischen Polynomen $q_s$ der Form 
$q_s (x) = \gamma_0 + \gamma_1 e^{ix} + \cdots + \gamma_s e^{isx},\;s \le n-1$,
minimiert das $s$--te Abschnittspolynom
$p_s{(x)} = \beta_0 + \beta_1 e^{xi} + \cdots + \beta_s e^{sxi}$ f\"ur 
$s=0, \dots, n-1$ die Fehlerquadratsumme
%
\eq{4.2.11}
 S(q_s) = \sum\limits^{n-1}_{k=0} |f_k - q_s (x_k) |^2
\en
\end{theorem}
%
\proof
Ordne $p_s, q_s$ die $n$--Tupel
%
\begin{eqnarray*}
 \underline{p_s} & = & (p_s (x_0), \dots, p_s (x_{n-1}))\\
 \underline{q_s} & = & (q_s (x_0), \dots, q_s (x_{n-1}))
\end{eqnarray*}
%
zu, die $p_s, q_s$ eindeutig festlegen. Dann gilt\\
 $\frac{1}{n} S(q_s) = [f - \underline{q_s}, f-\underline{q_s}].$ Da aber\\
$\beta_k = [f,\Phi_k]$ f\"ur $k = 0,\dots, n-1$ folgt f\"ur $f \in \C^n$\\
$[f-\underline{p_s}, \Phi_j] = [f-\sum\limits^s_{k=0} \beta_k \Phi_k, \Phi_j]
= \beta_j - \beta_j = 0, j = 0, \dots, s$ und
%
\[
\begin{array}{l}
 [f-\underline{p_s}, \underline{p_s} - \underline{q_s}] =
 \sum\limits^s_{j=0} [f - \underline{p_s},(\beta_j - \gamma_j) \Phi_j] = 0,\\
%
 \frac{1}{n} S({q_s}) = [f-\underline{q_s}, f-\underline{q_s}] =
 [(f-\underline{p_s} + \underline{p_s} - \underline{q_s}), 
 (f-\underline{p_s}+\underline{p_s}-\underline{q_s})\\
%
 = [f-\underline{p_s},f-\underline{p_s}] + [\underline{p_s}-\underline{q_s},
 \underline{p_s}-\underline{q_s}]\\
%
 \ge [f-\underline{p_s}, f-\underline{p_s}] = \frac{1}{n}S({p_s})
\end{array}
\]
und Gleichheit nur f\"ur $\underline{p_s} = \underline{q_s}$ da $[\bullet,\bullet]$ eine Norm definiert.
\eproof


Reelle Version: Beachte $e^{ix} = \cos x + i \sin x$. Setze
%
\eq{4.2.12}
\begin{array}{rcl}
 A_j & = & \displaystyle\frac{2}{n} \sum\limits^{n-1}_{k=0} f_k \cos \frac{2\pi jk}{n}\\
  B_j & = & \displaystyle\frac{2}{n} \sum\limits^{n-1}_{k=0} f_k \sin \frac{2\pi jk}{n}
\end{array}
\en
%
f\"ur reelle $f_k$ sind $A_j, B_j$ reell und es gilt\\
$\longrightarrow$ \"Ubung
%
\eq{4.2.13}
 \beta_{n-j} = \frac{1}{n} \sum\limits^{n-1}_{k=0} f_k w^{j-n}w_k =
 \frac{1}{n} \sum\limits^{n-1}_{k=0} f_k w^j_k
\en
%
\eq{4.2.14}
 \beta_j = \frac{1}{2} [A_j - iB_j], \beta_{n-j} = \frac{1}{2} [A_j + iB_j]
\en
%
\eq{4.2.15}
 \beta_j w_k^j + \beta_{n-j} w^{n-j}_k = A_j \cos j x_k + B_j \sin j x_k
\en
%
Damit erh\"alt man die reelle diskrete Fouriertransformation. $A_j, B_j$
sind diskrete Approximationen an die Fourierkoeffizienten
%
\[
\begin{array}{ll}
  a_k = \frac{1}{\pi} \int\limits^\pi_{-\pi} f(x) \cos (kx)\, dx, & k = 0,\dots, n-1\\
   b_k = \frac{1}{\pi} \int\limits^\pi_{-\pi} f(x) \sin (kx)\, dx, & k = 1,\dots, n-1.
\end{array}
\]
%
$\longrightarrow$ \"Ubung bei Quadratur

%
\begin{theorem}\label{4.2.16}
Gegeben $(x_k, f_k), \; k = 0,\dots, N-1$
mit $x_k = \frac{2\pi k }{N}$. Man setze f\"ur $j \in \Z$
%
\eq{4.2.17}
\left. \begin{array}{rcl}
 A_j & := & \frac{2}{N} \sum\limits^{N-1}_{ k=0} f_k \cos (kx_j)\\
 B_j & := &  \frac{2}{N} \sum\limits^{N-1}_{ k=0} f_k \sin (kx_j) 
\end{array} \right\}
\en
%
Definiere f\"ur ungerades $N = 2M+1$
%
\eq{4.2.18}
 \Psi (x) = \frac{A_0}{2} + \sum\limits^M_{k=1} (A_k \cos kx + B_k \sin kx)
\en
%
und f\"ur gerades $N=2M$
%
\eq{4.2.19}
 \Psi (x) = \frac{A_0}{2} + \sum\limits^{M-1}_{k=1} (A_k \cos kx + B_k \sin kx)
 + \frac{A_M}{2} \cos Mx
\en
%
so gilt
%
\[
 \Psi (x_k) = f_k,\; k = 0, \dots, N-1.
\]
\end{theorem}
%
\proof
$N = 2M \Longrightarrow$
\[
 f_k = \sum\limits^{N-1}_{j=0} \beta_j w^j_k = \beta_0 + \sum\limits^{M-1}_{j=1}
 (\beta_j w^j_k + \beta_{N-j} w^{(N-j)}_k) + \beta_M w^M_k
\]
%
mit (\ref{4.2.14}), (\ref{4.2.15}) folgt
%
\[
\begin{array}{ll}
 B_0 = \frac{2}{N} & \sum\limits^{N-1}_{k=0} f_k \sin \frac{2\pi k \cdot 0}{N} = 0,\\
 B_M = \frac{2}{N} & \sum\limits^{N-1}_{k=0} \sin \frac{2\pi k\cdot 1}{N} = 0.
\end{array}
\]
%
Analog f\"ur ungerades $N$.
\eproof
%
\underline{Berechnung von Fouriertransformation}\\
\underline{Fast Fourier Transformation (FFT)} f\"ur $N = 2^n \quad n > 0$. Was ist zu berechnen?
%
\begin{eqnarray*}
 \beta_j & = & \frac{1}{N} \sum\limits^{N-1}_{k=0} f_k e^{\frac{-2\pi ikj}{N}}\\
         & = & \frac{1}{N} \sum\limits^{N-1}_{k=0} f_k \epsilon^{kj}_N
\end{eqnarray*}
%
mit $\epsilon_N = e^{\frac{-2\pi i}{N}}$.\\
Der Trick ist die Tasache auszunutzen, da{\ss} die $e^{\frac{-2\pi i}{N}}$
eine $N$--te Einheitswurzel ist, d.h. alle Potenzen liegen auch auf dem
Einheitskreis und die Exponenten lassen sich nach $N$ reduzieren. Betrachte
als Beispiel $N=4$
%
\[
\begin{array}{l}
 \left[ \begin{array}{c}
 \beta_0\\ \beta_1\\ \beta_2\\ \beta_3 \end{array}\right] = \frac{1}{N}
%
 \left[ \begin{array}{cccc}
  \epsilon^0_N & \epsilon^0_N & \epsilon^0_N & \epsilon^0_N\\
  \epsilon^0_N & \epsilon^1_N & \epsilon^2_N & \epsilon^3_N\\
  \epsilon^0_N & \epsilon^2_N & \epsilon^4_N & \epsilon^6_N\\
  \epsilon^0_N & \epsilon^3_N & \epsilon^6_N & \epsilon^9_N \end{array}\right]
%
 \left[ \begin{array}{c}
 f_0\\f_1\\f_2\\f_3 \end{array}\right] = \frac{1}{N}
%
 \left[ \begin{array}{cccc}
 1 & 1 & 1 & 1 \\
 1 & \epsilon^1_N & \epsilon^2_N & \epsilon^3_N\\
 1 & \epsilon^2_N & 1 & \epsilon^2_N\\
 1 & \epsilon^3_N & \epsilon^2_N & \epsilon^1_N \end{array}\right]
%
 \left[ \begin{array}{l}
  f_0\\f_1\\f_2\\f_3 \end{array}\right] \\
%%
\left[ \begin{array}{c}
 \beta_0\\ \beta_2\\ \beta_1\\ \beta_3 \end{array}\right] = \frac{1}{N}
%
 \left[ \begin{array}{cccc}
 1 & 1 & 1 & 1 \\
 1 & \epsilon^2_N & 1 & \epsilon^2_N\\
 1 & \epsilon_N & \epsilon^2_N & \epsilon^3_N\\
 1 & \epsilon^3_N & \epsilon^2_N & \epsilon_N \end{array}\right] = \frac{1}{N}
%
 \left[ \begin{array}{cc|cc}
  1 & 1 & 0 & 0\\
  1 & \epsilon^2_N & 0 & 0\\ \hline
  0 & 0 & 1 & 1\\
  0 & 0 & 1 & \epsilon^2_N \end{array}\right]
%
 \left[ \begin{array}{cc|cc}  
   1 & 0 & 1 & 0\\
   0 & 1 & 0 & 1\\ \hline
   1 & 0 & \epsilon^2_N & 0\\
  0 & \epsilon_N  & 0 & \epsilon^3_N \end{array}\right]
% 
 \left[ \begin{array}{c}
  f_0\\f_1\\f_2\\f_3 \end{array}\right]
%
\end{array}
\]
%
Bilde Teilschritte: erst
\[
 \left[ \begin{array}{c}
 z_0\\z_1\\z_2\\z_3 \end{array}\right] = \left[ \begin{array}{cccc}
 1 & 0 & 1 & 0\\
 0 & 1 & 0 & 1\\
 1 & 0 & \epsilon^2_N & 0\\
 0 & \epsilon_N & 0 & \epsilon^3_N \end{array}\right] \left[ \begin{array}{c}
 f_0\\f_1\\f_2\\f_3 \end{array}\right]
\]
Verwende $\epsilon^2_N = -1, \epsilon^3_N = - \epsilon_N$
%
\[
\begin{array}{ll}
 z_0 = f_0 + f_2 & z_2 = f_0 - f_2\\
 z_1 = f_1 + f_3 & z_3 = \epsilon_N (f_1-f_3)
\end{array}
\]
%
\[
 \left[ \begin{array}{c}
  \beta_0\\ \beta_2\\ \beta_1\\ \beta_3 \end{array}\right] =
  \frac{1}{N} 
%
\underbrace{\left[ \begin{array}{cccc}
  1 & 1 & 0 & 0\\
  1 & \epsilon^2_N & 0 & 0\\
  0 & 0 & 1 & 1\\
  0 & 0 & 1 & \epsilon^2_N \end{array} 
  \right]}_{2 {\rm ~komplexe~FT~der~Ordnung~2~mit~} \epsilon^2_N}
%
\left[ \begin{array}{c}
  z_0\\z_1\\ z_2\\ z_3 \end{array}\right] = \frac{1}{N} 
%
\left[ \begin{array}{cccc}
  1 & 1 & & \\
  1 & -1 & &  \\
  & & 1 & 1\\
  & & 1 & -1 \end{array}\right]
%
\left[ \begin{array}{c}
  z_0\\z_1\\ z_2\\ z_3 \end{array}\right]
\]
\[
 \Longrightarrow \begin{array}{ll}
 N \beta_0 = z_0 + 1z_1, & N \beta_1 = z_2 + z_3 \\
 N \beta_2 = z_0 - z_1, & N \beta_3 = z_2 - z_3
\end{array}
\]
%
Es findet jeweils eine R\"uckf\"uhrung einer FFT der Ordnung $N = 2^2$
auf 2 FFT der Ordnung $\frac{N}{2} = 2^{n-1}$
statt $ + {\cal O} (N)$ Arbeit. Anstatt $N^2$ f\"ur Matrixmultiplikation
erh\"alt man dann $\frac{1}{2} N \log_2 N = 2^{n-1}\times (n-1)$ Operationen.

Da die FFT halber Dimension unabh\"angig laufen k\"onnen lassen sie sich gut auf 
Parallelrechner implementieren. \\
$\longrightarrow$ \"Ubung

Allgemeine Formeln:
\[
 \mbox { Sei } M = \frac{N}{2}, \mbox { Setze } j = 2l
\]
%
\eqa\label{4.2.20}
 \beta_{2l} & = & \sum\limits^{2M-1}_{k=0} f_k \epsilon^{2lk}_{N} =
 \sum\limits^{M-1}_{k=0} (f_k + f_{M+k}) \epsilon^{2lk}_N\\
 & = & \sum\limits^{M-1}_{k=0} (f_k + f_{M+k}) (\epsilon^2_N)^{lk}, \nonumber
\ena
%
wobei wir benutzen
\[
 \epsilon_N^{2l (M+k)} = \epsilon_N^{2lk} \epsilon_N^{2lM} =
 \epsilon_N^{2lk}.
\]
%
Mit Hilfswerten
%
\eq{4.2.21}
 z_{{k}} = f_{{k}} + f_{M+k}, \; k = 0,\dots,M-1
\en
%
und mit $\epsilon^2_N = \epsilon_M$ folgt
%
\eq{4.2.22}
 \beta_{2l} = \sum\limits^{M-1}_{k=0} z_{{k}} \epsilon^{kl}_M
 \quad (l=0,\dots, M-1).
\en
%
F\"ur die ungeraden Indizes gilt analog 
%
\eq{4.2.23 }
 \beta_{2l+1} = \sum\limits^{M-1}_{{k}=0} z_{M+k} \epsilon^{kl}_M \quad
 l = 0, \dots, m-1
\en
%
mit Hilfswerten
%
\eq{4.2.24} 
 z_{M+{k}} = (f_k - f_{M+{k}} \epsilon^{{k}}_N), \;
 {k}= 0, \dots, M-1
\en
%
Algorithmus von Cooley/Tukey (1965)\\
$\longrightarrow$ \"Ubung \ref{numI/uebung084}, \ref{numI/uebung085}\\
Weitere Tricks m\"oglich.
%
