Zettel 8 - HackMD

> Sirma > Wrana > Pratscher | **1** | **2** | **3** | **4** | $\Sigma$ | | :---: | :---: | :---: | :---: | :---: | |__ __ __ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | --- ## Aufgabe 8.1 Fast Fourier Transform nach Cooley-Tukey Die DFT eines Vektors $x=(x_i)_{i=0,\dots,N-1}\in\mathbb{C}^N$ ist gegeben durch $$x_k=\sum\limits_{j=0}^{N-1}e^{-\frac{2\pi ijk}{N}}x_j~~~\forall k\in 0,\dots,N-1$$ ### (8.1a) **Pseudocode: fft** 1  **procedure** fft (x: Vector in $\mathbb{C}^N$) 2      X: Vector in $\mathbb{C}^N$ 3      **if** N=1 **then** 4          $X_0=x_0$ 5      **else** 6          $X_{0,\dots,\frac{N}{2}-1}=fft((x_i)_{i\in\{0,\dots,N-1\}\text{even}})$ 7          $X_{\frac{N}{2},\dots,N-1}=fft((x_i)_{i\in\{0,\dots,N-1\}\text{odd}})$ 8          **for** $k=0$ **to** $\frac{N}{2}-1$ **do** 9               $a=X_k$ 10             $b=e^{-\frac{2\pi ik}{N}}X_{k+\frac{N}{2}}$ 11             $X_k=a+b$ 12             $X_{k+\frac{N}{2}}=a-b$ 13         **end for** 14     **end if** 15     **return** $X$ 16 **end procedure** ### (8.1b) zz: FFT-Algorithmus von Cooley und Tukey Komplexität $O(N\log_2 N)$ Kritische Stelle sind die rekursiven Aufrufe und der for-loop 1. **for-loop** (9-14) Da der Loop für $\frac{N}{2}$ Schritte läuft, ist dort die Laufzeit $O(\frac{N}{2})$, bzw $O(n)$, da $O(\frac{N}{2})\subseteq O(n)$. 2. **Rekursiver Aufruf** (7+8) Der rekursive Teil läuft in $O(n\log_2n)$, da rekursive Funktionen in $O(\log_2n)$ laufen und wir die Funktion $n$-mal aufrufen. Da die for-loops mit $O(n)$ in der Laufzeit $O(n\log_2n)$ liegen, folgt also die Laufzeit $O(n\log_2n)$ für den Algorithmus. ### (8.1c) **Pseudocode: ifft** 1  **procedure** ifft (x: Vector in $\mathbb{C}^N$) 2      **def** recursion (x: Vector in $\mathbb{C}^N$) 3          X: Vector in $\mathbb{C}'$ 4          **if** $N=1$ **then** 5              $X_0=x_0$ 6          **else** 7              $X_{0,\dots,\frac{N}{2}-1}=\text{recursion}((x_i)_{i\in\{0,\dots,N-1\}\text{even}})$ 8              $X_{\frac{N}{2},\dots,N-1}=\text{recursion}((x_i)_{i\in\{0,\dots,N-1\}\text{odd}})$ 9              **for** $k=0$ **to** $\frac{N}{2}-1$ **do** 10                 $a=X_k$ 11                 $b=e^{\frac{2\pi ik}{N}}X_{k+\frac{N}{2}}$ 12                 $X_k=a+b$ 13                 $X_{k+\frac{N}{2}}=a-b$ 14             **end for** 15         **end if** 16         **return** $X$ 17     **end def** 18     **return** $\text{recursion}(x)/N$ 19 **end procedure** Die Laufzeitkomplexität $O(n\log_2n)$ folgt aus (8.1b) ## Aufgabe 8.3 Kompression von Rastergrafiken mit FFT in 2D ### (8.3a) Nach (8.1c) ist die 1-dimensionale inverse DFT gegeben durch $$x_k=\frac{1}{N}\sum\limits_{j=0}^{N-1}e^{\frac{2\pi ijk}{N}}X_j~~~~\forall k\in 0,\dots,N-1$$ $$\begin{split} \implies x_{k_1,k_2}&=\frac{1}{N_1}e^{\frac{2\pi ijk}{N_1}}(\frac{1}{N_2}\sum\limits_{j_2=0}^{N_2-1}e^{\frac{2\pi ijk}{N_2}}X_{j_1,j_2}) \\ &=\frac{1}{N_1}\sum^{N_1-1}_{j_1=0}\frac{1}{N_2}\sum\limits_{j_2=0}^{N_2-1}e^{\frac{2\pi ij_1k_1}{N_1}}e^\frac{2\pi ij_2k_2}{N_2}X_{j_1,j_2}~~\forall k_1\in 0,\dots,N-1,~k_2\in 0,\dots,N_2-1 \end{split}$$ ## Aufgabe 8.4 Kondition der numerischen Quadratur Sei $I_{[a,b]}[f]$ das Integral von $f\in C^0([a,b])$ auf $[a,b]$ und $Q^{(n)}[f]$ eine Quadratur mit Gewichten $\alpha_i$ an den Punkten $x_i\in[a,b]$, $i=0,\dots,n$ d.h. $$I_{[a,b]}[f]:=\int\limits_a^bf(x)dx~~\text{und}~~Q^{(n)}[f]:=\sum\limits_{i=0}^n\alpha_if(x_i)$$ ### (8.4a) $$\begin{split} ||I_{[a,b]}||&:=\sup\limits_{f\in C^0([a,b])\backslash\{0\}}\frac{|I_{[a,b]}[f]|}{||f||_{C^0([a,b])}} \\ &\overset{||f||=\sup\limits_{||x||=1}||fx||}{\leq}\sup\limits_{f\in C^0([a,b])\backslash\{0\}}\frac{|\int\limits^b||f||dx|}{||f||_{C^0([a,b])}} \\ &=\sup\limits_{f\in C^0([a,b])\backslash\{0\}}\frac{|~||f||\int\limits_a^bdx|}{||f||_{C^0([a,b])}} \\ &=\sup\limits_{f\in C^0([a,b])\backslash\{0\}}\frac{|~||f||(b-a)|}{||f||_{C^0([a,b])}} \\ &=b-a \end{split}$$ $$\begin{split} |I_{[a,b]}[f]-I_{[a,b]}[g]|&\leq L||f-g||_{C^0([a,b])} \\ |I_{[a,b]}[f-g]|&\leq L\sup\limits_{||x||=1}||(f-g)(x)|| ~~~~~~L=b-a\\ &\leq L\sup\limits_{||x||=1}||f(x)-g(x)|| \end{split}$$ ### (8.4b) $$\begin{split} K_{abs}(I_{[a,b]})(f)&=\limsup\limits_{g\to f}\frac{|I_{[a,b]}[f]-I_{[a,b]}[g]|}{||f-g||_{C^0([a,b])}} \\ &\leq \limsup\limits_{g\to f}\frac{L||f-g||_{C^0([a,b])}}{||f-g||_{C^0([a,b])}} \\ &=L \end{split}$$ ### (8.4c) $Q^{(n)}$ ist für kleine $\alpha_i$ gut konditioniert, für große Gewichte allerdings schlecht konditioniert. $$\begin{split} K_{abs}(Q^{(n)})(f)&=\limsup\limits_{s\to f}\frac{|Q^{(n)}[f]-Q^{(n)}[g]|}{||f-g||_{C^0([a,b])}} \\ &=\limsup\limits_{g\to f}\frac{|\sum\limits_{i=0}^n\alpha_i(f(x_i)-g(x_i))|}{||f-g||_{C^0([a,b])}} \\ &=\sum\limits_{i=0}^n\alpha_iL \end{split}$$ ### (8.4d) $$\begin{split} K_{abs}(I_{w,[a,b]})(f)&=\limsup\limits_{g\to f}\frac{|I_{w,[a,b]}[f]-I_{w,[a,b]}[g]|}{||f-g||_{C^0([a,b])}} \\ &=\limsup\limits_{g\to f}\frac{|\int\limits_a^bw(x)dx(I_{[a,b]}[f]-I_{[a,b]}[g])|}{||f-g||_{C^0([a,b])}} \\ &\leq\limsup\limits_{g\to f}|\int\limits_a^bw(x)dx|\frac{L||f-g||_{C^0([a,b])}}{||f-g||_{C^0([a,b])}} \\ &=|\int\limits_a^bw(x)dx|L \end{split}$$