\documentclass[12pt,a4paper]{report}
\usepackage{latexsym,amssymb,german,a4wide,verbatim,xr}
\usepackage{fancyhdr} 
%\usepackage{pgffor}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{mathtools}
\usepackage{listings}
\usepackage{tikz}
\usetikzlibrary{calc}



\lstset{
 %frame=tb,
  language=Matlab,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  %columns=flexible,
  basicstyle={\small\ttfamily},
  %numbers=none,
  %numberstyle=\tiny\color{gray},
  %keywordstyle=\color{blue},
  %commentstyle=\color{dkgreen},
  %stringstyle=\color{mauve},
  %breaklines=true,
  %breakatwhitespace=true,
  tabsize=3
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Layout
%\addtolength{\topmargin}{-15ex}
%\addtolength{\textheight}{20ex}
\pagestyle{fancy}
\setlength{\headheight}{28pt}
\lhead{Technische Universität Berlin\\Numerische Mathematik I - WS 2019/2020}
\rhead{Prof.~V.~Mehrmann\\M.~Froidevaux}
\cfoot{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\vcenteredinclude}[1]{\begingroup
\setbox0=\hbox{\includegraphics[height=3cm]{#1}}%
\parbox{\wd0}{\box0}\endgroup}


\newcommand{\CurrentWeekNb}{11}
\newcommand{\vertiii}[1]{{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert #1 
    \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}}
\newcounter{taskNb}
\stepcounter{taskNb}

\begin{document}
\begin{center}
%{\LARGE Numerische Mathematik}\\[1.5ex]
%%{\large \CurrentWeekNb. \"Ubungsblatt}\\ 
{\Large \CurrentWeekNb. \"Ubungsblatt}\\ 
{Diskrete Fourier-Transformation}\\
%\\{Diese Aufgaben müßen spätestens am 24.10.19 in der Vorlesung abgegeben werden.}
%{Abgabe:} Spätestens am 24.10.19 in der Vorlesung\\[0.5cm]
\end{center}
%\begin{center}
\hfill{Abgabe: Spätestens am 16.1.20 am Anfang der Vorlesung}\\[0.5cm]
%\end{center}
%
%%\def\exerciseList{001, 002, 003}
%\begin{enumerate}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% Aufgabe 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Gegeben sei die Funktion $f\colon \mathbb{R}\to \mathbb{R}$ durch
\[
f|_{[0, 2\pi]}(x)\coloneqq \begin{cases}
1, \text{falls } 0<x<\pi, \\
0, \text{falls } x=0,\pi, 2\pi,\\
-1,\text{falls } \pi<x<2\pi.
\end{cases}
\]
\textbf{Theorieaufgabe \arabic{taskNb} (4 Punkte):} \stepcounter{taskNb} 
\begin{itemize}
\item Bestimmen Sie die 7 ersten Koeffizienten 
\[
\begin{aligned}
a_k &= \frac{1}{\pi} \int\limits_{0}^{2\pi} f(x) \cos(kx)\text{d}x,\ k=0,1,2,3,\\
b_k &= \frac{1}{\pi} \int\limits_{0}^{2\pi} f(x) \sin(kx)\text{d}x,\ k=1,2,3
\end{aligned}
\]
der zu $f$ gehörigen Fourier-Reihe
\[
F(x)=\frac{1}{2}a_0 +\sum\limits_{k=1}^{K=\infty} a_k \cos(kx) + b_k \sin(kx).
\]
\item Skizzieren Sie die ersten vier Partialsummen von $F$ (d.h. $K = 0,1,2,3$ anstatt $\infty$) und vergleichen Sie sie mit $f$.
\end{itemize}
%
\textbf{Theorieaufgabe \arabic{taskNb} (4 Punkte):} \stepcounter{taskNb} 
Sei $n=8$ und $s=\frac{n}{2}-1$. Bestimmen Sie (per Hand) mit Hilfe des FFT-Algorithmus aus der Vorlesung die zu $f$ gehörige diskrete Fourier-Transformation
\[
\hat{f}_{s,s}(x) = \frac{1}{2} \tilde{a}_0 + \sum\limits_{k=1}^s (\tilde{a}_k \cos(kx) + \tilde{b}_k \sin(kx)),
\]
\[
\tilde{a}_k= \frac{2}{n}\sum\limits_{l=0}^{n-1} f(x_l) \cos(k x_l), \qquad \tilde{b}_k = \frac{2}{n}\sum\limits_{l=0}^{n-1} f(x_l) \sin(k x_l),
\]
wobei $x_l=l \frac{2\pi}{n}$.
\\[0.3cm]
%
\textbf{Theorieaufgabe \arabic{taskNb} (3 Punkte):}\stepcounter{taskNb} 
%
Sei ein Vektor $f=[f_0, f_1, \ldots, f_{n-1}]$, wobei $n$ eine Zweierpotenz ist. Für $j=0,\ldots, n-1$ ist die $j$-te Komponente der diskreten Kosinustransformation von $f$ durch
\[
(DCT(f))_j:=\sum\limits_{l=0}^{n-1}f_l \cos\big(\frac{\pi}{n}(l+\frac{1}{2})j\big)
\]
definiert. Zeigen Sie, dass die DCT mit Hilfe des FFT-Algorithmus aus der Vorlesung durch
\[(DCT(f))_j= \frac{1}{2}(FFT(g))_j
\]
komponentenweise berechnet werden kann, wobei
\[g=[0,f_0,0,f_1,0,f_2,0,\ldots,f_{n-1},0,f_{n-1},0,f_{n-2},\ldots,0,f_1,0,f_0].\]
%
\textbf{Programmieraufgabe (4 Punkte):} Das Bild \texttt{PA11\_waves.jpg} ist eine Interferenz zwischen zwei sinusförmigen Wellen. Wir wollen diese von einander trennen, indem wir die Amplitude der Fourier-Transformation ausnutzen. 
\begin{center}
\vcenteredinclude{matlab/PA11_sine1} $\longrightarrow$ \vcenteredinclude{pics/welle1.png} \vcenteredinclude{pics/welle2.png} 
\end{center}
Implementieren Sie dafür den Algorithmus \textit{Fast Fourier Transform} der Vorlesung in einer Matlab-/Python-Funktion \texttt{PA11\_FFT}.
Implementieren Sie anschließend eine Funktion \texttt{PA11\_FFT2}, die die schnelle Fourier-Transformation eines zweidimensionalen Bildes berechnet. Wenden Sie dafür die Funktion \texttt{PA11\_FFT} auf alle Spalten des Bildes und anschließend auf alle Zeilen an. Achtung, die Reihenfolge ist hier wichtig!
Hinweis: Das Bild ist in der Variable \texttt{imageB1} als Matrix gespeichert. Jeder Eintrag der Matrix bezeichnet die Intensität eines Pixels. 
%
\end{document}

