TU Wien:Mathematik 3 VO (Panholzer)/Mitschrift WS06/11.VO LaTeX

 %-------------------------------------------------  % Created by Markus Diem, Markus Nemetz  %------------------------------------------------- \documentclass[12pt,a4paper]{article} \usepackage[latin1]{inputenc} %umlaute \usepackage[german]{babel} \usepackage{amsmath} \usepackage{amssymb} \usepackage[dvips]{graphicx} \usepackage[bf]{caption} \usepackage[pdfborder= 0]{hyperref} %links zu refs ohne rahmen \usepackage{dsfont} \usepackage{listings} %codelistings \usepackage{color} %fuer angabe der rationalen zahlen etc. \renewcommand{\captionfont}{\footnotesize} \setlength{\belowcaptionskip}{3pt} \renewcommand{\arraystretch}{1.3} %abstand beim brechen der formeln \definecolor{Gray}{gray}{0.9} \lstset{basicstyle=\ttfamily\scriptsize, backgroundcolor=\color{Gray}, numbers=left, numberstyle=\tiny, stepnumber=1, numbersep=5pt}  %**************************************************  % spezifische Makros  %************************************************** \newcommand{\real}{\mathds{R}} \newcommand{\definition} {\textbf{Definition: }} \newcommand{\bsp} {\textbf{Beispiel: }} \title{\textbf{Mathematik III} \linebreak \large{Vorlesung 11, 12.01.2007}} \author{Markus Nemetz} \date{Jänner 2007} \DeclareGraphicsExtensions{.eps} \setcounter{MaxMatrixCols}{11} \begin{document} \maketitle \section{Vorbemerkung} Prof. Panholzer hat die illustrierenden Beispiele aus der zur VO empfohlenen Lektüre gebracht - sie sind hier nicht angeführt. Die z.T. gerafften Zusammenstellungen sind z.T. auch die jeweiligen theoretischen Grundlagen zu den Übungsbeispielen, die in ausgearbeiteter Form jeweils nach der Übungsrunde auf \emph{http://wikiserver.fsinf.at/mathe3/} zu finden sind. \begin{flushright} Markus Nemetz 15.01.2007 \end{flushright} \section{Rechenregeln für DFT} $\operatorname{DFT}(\vec{y}=\vec{c}=(c_0,\dots,c_{N-1})^T$; für $\vec{y}=(y_0,\dots,y_{N-1})^T$. Periodische Funktion $(y_k)$, wobei $y_k=y_{k+N}$ für alle $k \in \mathbb{Z}$. \begin{itemize} \item Linearität \begin{gather*} \alpha\vec{y} + \beta\vec{z} \overbrace{\longrightarrow}^{\operatorname{DFT}} \alpha\vec{c}+ \beta \vec{d}, \qquad \vec{c}=\operatorname{DFT}(\vec{y}), \vec{f}=\operatorname{DFT}(\vec{z}) \end{gather*} \item Verschiebung im Zeitbereich \begin{gather*} (y_{k+N})_{k \in \mathbb{Z}} \overbrace{\longrightarrow}^{\operatorname{DFT}}(\omega^{k\cdot n} \cdot c_k)_{k \in \mathbb{Z}}, \qquad \omega = e^{\frac{2\cdot\pi\cdot i}{N}} \end{gather*} \item Verschiebung im Frequenzbereich \begin{gather*} (y_{k} \cdot \omega^{k\cdot n} )_{k \in \mathbb{Z}} \overbrace{\longrightarrow}^{\operatorname{DFT}}(c_{k-n})_{k \in \mathbb{Z}} \end{gather*} \item Periodisches Faltunsprodukt \begin{gather*} \vec{y} \ast \vec{z} = (\frac{1}{N} \cdot \sum_{j=0}^{N-1} y_j \cdot z_{k-j})_{k \in \mathbb{Z}}\\ \vec{y} \ast \vec{z} \overbrace{\longrightarrow}^{\operatorname{DFT}} (c_k \cdot d_k)_{k \in \mathbb{Z}} \end{gather*} Algorithmus mit $\mathcal{O}(N \log N)$, danach $\mathcal{O}(N)$. \end{itemize} \section{FFT-Algorithmus} Betrachten nur $\operatorname{IDFT}: \,\, \vec{c} \overbrace{\longrightarrow}^{\operatorname{IDFT}} \vec{y}, \,\, y_j=\sum_{k=0}^{N-1} c_k \cdot \omega^{k\cdot j}$, mit $0 \leq j \leq N-1$. Idee: 'Die Kosten', um alle Werte $(y_0, \dots, y_{N-1})$ zu berechnen ist i.A. viel geringer als das $N$-fache einer Berechnung von z.B. $y_j$. Betrachten den wichtigsten Fall, daß $N=2^r$, $r \in \mathbb{N}$. Idee ($k=2\cdot m$, gerade): \begin{gather*} y_j = \sum_{k=0}^{2^r-1} c_k \cdot e^{\frac{2\cdot \pi \cdot i}{2^r}\cdot k \cdot j} = \sum_{m=0}^{2^(r-1)-1} c_{2\cdot m} \cdot e^{\frac{2\cdot \pi \cdot i}{2^{r}}\cdot 2\cdot m \cdot j} + \sum_{m=0}^{2^(r-1)-1} c_{2\cdot m + 1} \cdot e^{\frac{2\cdot \pi \cdot i}{2^{r}}\cdot (2\cdot m + 1) \cdot j} =\\ \underbrace{\sum_{m=0}^{2^(r-1)-1} c_{2\cdot m} \cdot e^{\frac{2\cdot \pi \cdot i}{2^{r-1}}\cdot m \cdot j}}_{u(j)} + \underbrace{e^{\frac{2\cdot \pi \cdot i}{2^r}} \cdot j \cdot \sum_{m=0}^{2^(r-1)-1} c_{2\cdot m + 1} \cdot e^{\frac{2\cdot \pi \cdot i}{2^{r-1}}\cdot m \cdot j}}_{v(j)} \end{gather*} \begin{itemize} \item $u(j)$ ist Element der $\operatorname{IDFT}$ von den geraden Koeffizienten ($[c_0, c_2, \dots,c_{N-2}]$) \item $v(j)$ ist Element der $\operatorname{IDFT}$ von den ungeraden Koeffizienten ($[c_1, c_3, \dots,c_{N-1}]$) \end{itemize} Einziges Problem: $\operatorname{IDFT} [c_0, c_2, \dots,c_{N-2}]$ liefert nur $\frac{N}{2}$ Werte, analog $\operatorname{IDFT} [c_1, c_3, \dots,c_{N-1}]$; d.h. erhalte $y_j$ zunächst für Werte $0 \leq j \leq 2^{r-1} - 1$. Problem ist leicht zu lösen, weil $u(j)$ und $v(j)$ periodisch mit der Periode $\frac{N}{2}=2^{r-1}$ sind, d.h. (bitte nachrechnen!): \begin{itemize} \item $u(j + 2^{r-1}) = u(j)$ \item $v(j + 2^{r-1}) = v(j)$ \end{itemize} \section{Allgemeine FFT} Um die diskrete Fouriertransformation durchzuführen, genügt es, den Vektor $ f$ mit der $ N \times N$ -Matrix $ F_N$ zu multiplizieren. Dies erfordert (neben den Additionen) $ N^2$ Multiplikationen, für große $ N$ ein zu hoher Aufwand. Die schnelle Fouriertransformation beruht darauf, dass man im Fall $ N = 2^d$ für ein $ d \in \mathbb{N}$ nur $ d \cdot N = N \cdot \log_2(N)$ Multiplikationen benötigt, wenn man gewisse Symmetrien ausnutzt. Dies machen wir uns am Beispiel $ d = 2$ klar. Dann ist $\displaystyle \omega = \exp ( \frac{2 \pi i}{4} ) = \exp ( \frac{\pi}{2} i ) = i.$ Es ergibt sich für $ k = 0, \ldots, 3 $ $\displaystyle \hat{f}_k$ $\displaystyle =$ $\displaystyle f_0 + f_1 i^k + f_2 i^{2 k} + f_3 i^{3 k}$ $\displaystyle =$ $\displaystyle f_0 + f_2 (i^2)^k + i^k ( f_1 + f_3 (i^2)^k ).$ Wir setzen $ g = ( f_0 , f_2 )^t$ und $ u = ( f_1 , f_3 )^t$ . Dann lässt sich die Gleichung für $ \hat{f}_k$ umformen. Für $ k \leq 1 = N/2 - 1$ gilt $\displaystyle \hat{f}_{k, N} = \hat{g}_{k, N/2} + i^k \hat{u}_{k, N/2} .$ (Wir haben dabei durch den zusätzlichen Index $ N$ bzw. $ N/2$ angedeutet, dass es sich um eine diskrete Fouriertransformation im $ \mathbb{C}^N$ bzw. $ \mathbb{C}^{N/2}$ handelt.) Für $ k = 2$ bzw. $ 3$ sei $ k' = k$ mod $ N/2$ . Dann ist $ \hat{f}_{k, N} \, = \, \hat{g}_{k', N/2} + i^k \hat{u}_{k', N/2}$ . Wir haben also Fouriertransformationen in $ \mathbb{C}^{N/2}$ und eine anschließende ``Zusammensetzung'' erhalten. Allgemein ergibt sich das folgende rekursive Schema: $\displaystyle g (f)$ $\displaystyle =$ $\displaystyle ( f_0 , f_2, f_4, \ldots, f_{N-2} ), u (f) = ( f_1, f_3 , \ldots, f_{N-1} )$ $\displaystyle \hat{f}_{k, N}$ $\displaystyle =$ $\displaystyle \widehat{g(f)}_{k \mbox{ \rm mod }N/2 , N/2} + \overline{\omega}^k \widehat{u(f)}_{k \mbox{ \rm mod }N/2, N/2} \quad \quad k = 0, \ldots , N-1.$ Die Rekursion kann man $ d = \log_2(N)$ mal aufrufen. Pseudocode: \begin{center} \includegraphics[scale=0.6]{FFT-Pseudo.eps} \end{center} \textbf{Komplexitätsanalyse}: $M(r)$ sei die Anzahl der komplexen Muötiplikationen im FFT eines Vektors der Länge $N=2^r$: \begin{gather*} M(r) = 2^r + 2\cdot M(r-1), \qquad r > 1\\ M(0) = 0, \qquad \frac{M(r)}{2^r} = M(\frac{r-1}{2^{r-1}}) + 1 = r - \underbrace{M(0)}{=0}\\ M(r) = r \cdot 2^r = N \cdot \log_2 N = \mathcal{O}(N \cdot \log N) \end{gather*} \newpage \section{Beispiele für Anwendung der DFT} \subsection{Approximation der Fourier-Koeffizienten einer Fourier-Reihe} Betrachten $2r$-periodische Funktion $f(t)$. Auswerten an den Stützstellen $f(\frac{2r}{N}, j)$, $0 \leq j \leq N-1$: \begin{gather*} \Rightarrow \,\,\, (y_0, y_1, \dots, \underbrace{y_j}_{\frac{2r}{N}}, \dots, y_{N-1})=y \end{gather*} Betrachte $\vec{c} = (c_0, \dots, c_{N-1}) = \operatorname{DFT}(y)$. Betrachte $N$-periodische Fortsetzung ($c_k$). Es gilt: $c_k$ für $-\frac{N}{2} \leq l \leq \frac{N}{2}$ sind eine gute Approximation für Fourier-Koeffizienten der Fourier-Reihe von $f(t)$. \subsection{Trigonometrische Interpolation} 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ützstellen $\frac{2r}{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ü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ß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{Fourier-Transformation} \begin{gather*} \mathbf{F(s)=\mathcal{F}\{f(t)\} = \operatorname{(CHW)}\int_{-\infty}^{+\infty} f(t) \cdot e^{-i \cdot \omega \cdot t} \operatorname{d}t} \end{gather*} Beispiel Rechteckfunktion: \begin{gather*} \sqcap (t)=\begin{cases}0, & |t| < 1\\0, & |t|>1 \\ 1, & \text{sonst.}\end{cases}\\ \mathcal{F} \{ \sqcap (t) \} = \int_{-\infty}^{+\infty} \sqcap (t) \cdot e^{-i \cdot \omega \cdot t} \operatorname{d}t= \int_{-1}^{1} 1 \cdot e^{-i \cdot \omega \cdot t} = \frac{e^{-i \cdot \omega \cdot t}}{-i \cdot \omega}= \frac{1}{-i\cdot\omega}(e^{-i\omega} - e^{i\omega})=\\ \frac{1}{-i\cdot\omega}(\cos(-i\omega) + i\sin(-i\omega)-\cos(i\omega) - i\sin(i\omega) = \frac{2\sin \omega}{\omega}\\ \omega \neq 0, \, (\omega = 0 \, \Rightarrow \, F(0)=2) \end{gather*} Beispiel Spaltfunktion: \begin{gather*} \mathrm{sinc}(x) = \mathrm{si}(x) := \begin{cases} \frac{\sin (x)}{x} & \mbox{falls } x \ne 0 \\ 1 & \mbox{falls } x = 0 \end{cases} \end{gather*} Die Spaltfunktion ist die Fouriertransformierte der Rechteckfunktion \begin{gather*} \mathrm{rect} \left(\frac{t}{\tau} \right) =\chi_{[-\tau/2,\tau/2]}(t) := \begin{cases}1 & |t|\le\tau/2 \\ 0 & \mathrm{sonst} \end{cases}, \end{gather*} denn es gilt \begin{gather*} \mathcal F(\chi_{[-\tau/2,\tau/2]})(\omega) = \frac1{\sqrt{2\pi}}\int \limits_{-\tau/2}^{\tau/2} e^{-\mathrm{i} \omega t}\, dt = \frac1{\sqrt{2\pi}}\,\tau \,\mathrm{sinc} \left( \frac{\omega \tau}{2} \right) \end{gather*} Wichtige Frage: Wann existiert die $\mathcal{F}$-Transformation der Funktion $f(t)$? Definition: Eine Funktion $f(t)$ heisst \textbf{absolut integrierbar}, wenn sie in jedem endlichen Intervall stückweise stetig ist und wenn gilt: \begin{gather*} \int_{-\infty}^\infty |f(t)| \operatorname{d}t < \infty \end{gather*} Satz: Falls eine Funktion $f(t)$ absolut integrierbar ist, dann existiert die $\mathcal{F}$-transformierte $F(\omega)$ für alle $\omega \in \mathbb{R}$; $F(\omega)$ ist stetig und beschränkt. Weiters gilt die Plancherel-leichung (Energiegleichung). Der parsevalschen Gleichung für die Fourierreihe entspricht eine Identität der Fouriertransformation, die gemeinhin als Satz von Plancherel bezeichnet wird: \begin{gather*} \frac{1}{2\pi}\int_{-\infty}^{\infty} |F(\omega)|^2 \operatorname{d}\omega = \int_{-\infty}^{\infty} |f(t))|^2 \operatorname{d}t \end{gather*} Satz: \textbf{Fourier-Integraltheorem}: Ist die Funktion $f(t)$ absolut integrierbar und ist $f(t)$ auf jedem endlichen Intervall stückweise stetig differenzierbar, dann gilt: \begin{gather*} \frac{f(t)^+f(t)^-}{2} = \frac{1}{2\pi}\int_{-\infty}^{\infty} F(\omega)e^{i\omega t} \operatorname{d}\omega \end{gather*} Anmerkung: Falls $f(t)$ stetig ist gilt: \begin{gather*} f(t)=\frac{1}{2\pi}\int_{-\infty}^{\infty} F(\omega)e^{i\omega t} \operatorname{d}\omega=\mathcal{F}^{-1}(F(\omega)) = \frac{1}{2\pi}\mathcal{F}\{F(-\omega)\} \end{gather*} \end{document}