---
# System prepended metadata

title: Zettel 8

---

> Sirma
> Wrana
> Pratscher

| **1** | **2** | **3** | **4** | $\Sigma$ |
| :---: | :---: | :---: | :---: | :---: |
|</br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ |

---

## 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 &nbsp;**procedure** fft (x: Vector in $\mathbb{C}^N$)
2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; X: Vector in $\mathbb{C}^N$
3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** N=1 **then**
4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_0=x_0$
5&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **else**
6&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_{0,\dots,\frac{N}{2}-1}=fft((x_i)_{i\in\{0,\dots,N-1\}\text{even}})$
7&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_{\frac{N}{2},\dots,N-1}=fft((x_i)_{i\in\{0,\dots,N-1\}\text{odd}})$
8&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $k=0$ **to** $\frac{N}{2}-1$ **do**
9&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $a=X_k$
10&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $b=e^{-\frac{2\pi ik}{N}}X_{k+\frac{N}{2}}$
11&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_k=a+b$
12&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_{k+\frac{N}{2}}=a-b$
13&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end for**
14&nbsp;&nbsp;&nbsp;&nbsp; **end if**
15&nbsp;&nbsp;&nbsp;&nbsp; **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 &nbsp;**procedure** ifft (x: Vector in $\mathbb{C}^N$)
2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **def** recursion (x: Vector in $\mathbb{C}^N$)
3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; X: Vector in $\mathbb{C}'$
4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $N=1$ **then**
5&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_0=x_0$
6&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **else**
7&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_{0,\dots,\frac{N}{2}-1}=\text{recursion}((x_i)_{i\in\{0,\dots,N-1\}\text{even}})$
8&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_{\frac{N}{2},\dots,N-1}=\text{recursion}((x_i)_{i\in\{0,\dots,N-1\}\text{odd}})$
9&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $k=0$ **to** $\frac{N}{2}-1$ **do**
10&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $a=X_k$
11&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $b=e^{\frac{2\pi ik}{N}}X_{k+\frac{N}{2}}$
12&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_k=a+b$
13&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $X_{k+\frac{N}{2}}=a-b$
14&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end for**
15&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end if**
16&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **return** $X$
17&nbsp;&nbsp;&nbsp;&nbsp; **end def**
18&nbsp;&nbsp;&nbsp;&nbsp; **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}$$