\documentclass[a4paper]{scrartcl}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{ngerman}
\usepackage[dvips]{graphicx}
\usepackage{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{booktabs}
\usepackage{listings}
\usepackage{color} % f{\"u}r den grauen Hintergrund

%\usepackage{endnotes}

\setlength{\parindent}{0 em}

\definecolor{Gray}{gray}{0.9}

\lstset{basicstyle=\ttfamily\scriptsize,
backgroundcolor=\color{Gray}, numbers=left, numberstyle=\tiny,
stepnumber=1, numbersep=5pt}

\DeclareGraphicsExtensions{.eps}

%\DeclareGraphicsRule{.gif}{eps}{}{`convert #1 'eps:-'}

  \setcounter{MaxMatrixCols}{11}

\begin{document}
\begin{center}
\textbf{\huge{Runde 10, Beispiel 66}}

\Large{LVA 118.181, {\"U}bungsrunde 10, 19.01.2007}

\large{Markus Nemetz, \emph{markus.nemetz@tuwien.ac.at}, TU Wien,
18.01.2007}
\end{center}

\section{Angabe}
Gesucht ist das trigonometrische Polynom
\begin{gather*}
    f(t)=\sum_{k=-n}^n c_ke^{ikt}
\end{gather*}
von minimalem Grad $n$, welches im Intervall $[0; 2\pi]$ an den
$3$ St{\"u}tzstellen $t_j=\frac{2\pi}{3}j, \, j=0,1,2$ die
vorgegebenen Funktionswerte $y(t_j)$ annimmt:
\begin{gather*}
    y(0)=0, \qquad y(\frac{2\pi}{3})=\frac{\sqrt{3}}{2},\qquad
    y(\frac{4\pi}{3})=-\frac{\sqrt{3}}{2}
\end{gather*}
Wie lautet das
trigonometrische Polynom in der Sinus-Cosinus-Form.

\section{Trigonometrische Interprolation durch die DFT}
Gegeben sind Werte $(y_0,y_1, \dots, y_{N-1})=\vec{y}$.

Gesucht ist ein trigonometrisches Polynom von kleinstem Grad
\begin{gather*}
    \sum_{k=-n}^n c_k \cdot e^{i\cdot k \cdot t},
\end{gather*}
sodass dieses an den St{\"u}tzstellen $\frac{2\pi}{N} \cdot j$
genau die Werte $y_j$ annimmt.

Falls $N$ ungerade ist, so ist das trigonometrische Polynom
eindeutig bestimmt und es gilt dann $N=2n+1$.

Einsetzen der Werte an den St{\"u}tzstellen liefert $N$
Gleichungen:
\begin{gather*}
    \mathbf{y_j = \sum_{k=-n}^n c_k \cdot \omega^{k \cdot j}, \qquad 0
    \leq j \leq 2n, \omega=e^{\frac{2\pi i}{N}}}\\
    y_j = \sum_{k=0}^{2n} c_{k-n} \cdot \omega^{(k-n) \cdot j} = \sum_{k=0}^{2n} c_{k-n} \cdot
    \omega^{kj}\cdot\omega^{-nj}\\
    \Rightarrow \omega^{nj} \cdot y_j = \sum_{k=0}^{2n} c_{k-n} \cdot
    \omega^{kj}, \qquad 0 \leq j \leq 2n = N - 2\\
    \Rightarrow (\omega^{nj} \cdot y_j)_{j \in \mathbb{Z}} =
    \operatorname{IDFT}(c_{k-n})\\
    \Rightarrow c_{k-n} = \operatorname{IDFT} ((\omega^{nj} \cdot y_j)_{j \in
    \mathbb{Z}})
\end{gather*}
Liefert schlie{\ss}lich $(c_0. c_1, \dots, c_{n-1}, c_n, c_{n+1},
\dots, c_{2n}) = \operatorname{DFT}(y_0, y_1, \dots, y_{2n})$.


\section{L{\"o}sung des Beispiels}
In unserem Fall ist $N = 3$, also ungerade. Es sind daher $2n +1$
Koeffizienten ($n=1$) zu bestimmen mit  $k = 0,1$.

Wir müssen für die Anwendung der Formel
\begin{gather*}
    f(t)=\frac{a_0}{2} + \sum_{k=1}^n(a_k \cdot \cos (kt) + b_k
    \cdot \sin(kt)
\end{gather*}
berechnen:
\begin{itemize}
    \item $a_0$,$k=0$:
\begin{gather*}
        a_0 := c_0 + c_{-0} = \frac{2}{N} \sum_{j=0}^{N-1} y_j \cos \frac{2\pi k
        j}{N}=0
\end{gather*}
    \item $a_1$,$k=1$:
\begin{gather*}
        a_1 := c_1 + c_{-1} = \frac{2}{N} \sum_{j=0}^{N-1} y_j \cos \frac{2\pi k
        j}{N}=0
\end{gather*}
    \item $b_0$,$k=0$:
\begin{gather*}
        b_0 := i(c_0 - c_{-0}) = \frac{2}{N} \sum_{j=0}^{N-1} y_j \sin \frac{2\pi k
        j}{N}=1
\end{gather*}
    \item $b_1$,$k=1$:
\begin{gather*}
        b_1 := i(c_1 - c_{-1}) = \frac{2}{N} \sum_{j=0}^{N-1} y_j \sin \frac{2\pi k
        j}{N}=0
\end{gather*}
\end{itemize}
Ergibt somit $\mathbf{f(t)=\sin(t)}$.


\end{document}
