[WS] Trigonometrische Interpolation

Neue Frage »

25.02.2007, 19:19

tigerbine

Auf diesen Beitrag antworten »

[WS] Trigonometrische Interpolation

Gliederung

Bezug zur Analysis

1a. Definition trigonometrisches Polynom
1b. Cosinus-Sinus-Darstellung
1c. Vektorraum der trigonometrischen Polynome
Approximation von Funktionen durch Fourierpolynome

2a. Fourierreihe und Konvergenz
2b. Fourierreihen von ungeraden Funktionen - reine Sinusreihe
2c. Fourierreihen von geraden Funktionen - reine Cosinusreihe
2d. Periodische Funktionen selbst gemacht
Trigonometrische-Interpolations-Aufgabe (TIPA)

3a. Darstellung 1
3b. Darstellung 2
3c. Existenz und Eindeutigkeit
3d. Hilfsresultate
3e. Berechnung der gesuchten Koeffizienten d
Diskrete Fourier Analyse (DFA)

4a. Eigenschaften der Koeffizienten d
4b. Zerlegung des in 2 Polynome
4c. Eigenschaften der beiden Polynome an den Knoten
4d. Berechnung der Koeffizienten d
4e. Berechnung der Koeffizienten a,b
4f. Das gesuchte Polynom
Unterschiede zwischen Approximation und Interpolation

5a. Approximationspolynom
5b. Lösung TIPA
5c. Lösung DFA
5d. Bemerkung
Fast-Fourier-Transformation (FFT) - Auswertung von trig. Polynomen

6a. Berechnung der Koeffizienten d
6b. Gerades N=2M
6c. N ist eine Zweierpotenz
6d. Beispielschema
Umsetzung am PC
7a. Koeffizienten-Näherungen
7b. "alte Bekannte"
7c. Effiziente Berechnung
Eine einfache Erklärung der Fouriertransformation
8a. Filterung der Sinusanteile
8b. Filterung der Cosinusanteile
8c. Filterung eines phasenverschobenen Sinus
8d. Filterung des Mittelwertes

25.02.2007, 23:34

tigerbine

Auf diesen Beitrag antworten »

1a. Definition trigonometrisches Polynom
Unter einem trig. Polynom vom Grad N versteht man die Abbildung $\begin{eqnarray*} T_N: \mathbb R \rightarrow \mathbb C \end{eqnarray*}$ mit folgender Definition:

$\begin{eqnarray*} \fbox{$\displaystyle T_N(x) = \sum_{j=-N}^{N}~c_j\cdot \exp(i\cdot jx)$} \quad x\in \mathbb R,~ c_j \in \mathbb C,\quad \text{für } j=-N,...,0,...,N \end{eqnarray*}$

26.02.2007, 00:31

tigerbine

Auf diesen Beitrag antworten »

1b. Cosinus-Sinus-Darstellung
Diese Darstellung kann man mittels der Substitution $\begin{eqnarray*} \exp(i\cdot jx)=\cos(jx)+i\cdot \sin(jx) \end{eqnarray*}$ durch geschicktes Zusammenfassung wie folgt umrechnen:

$\begin{eqnarray*} T_N(x) &&= \sum_{j=-N}^{N}~c_j\cdot \exp(i\cdot jx) =\\&&= \sum_{j=-N}^{-1}~c_j\cdot \exp(i\cdot jx) +c_0 + \sum_{j=1}^{N}~c_j\cdot \exp(i\cdot jx) = \\&&= \sum_{j=1}^{N}~c_{-j}\cdot \exp\bigl(i\cdot (-jx)\bigr) +c_0 + \sum_{j=1}^{N}~c_j\cdot \exp(i\cdot jx) =\\&&= c_0 + \sum_{j=1}^{N}~\Bigl( c_j\cdot \exp(i\cdot jx) +c_{-j}\cdot \exp \bigl(i\cdot (-jx)\bigr) \Bigr)=\\ && c_0 + \sum_{j=1}^{N}~\Bigl( c_j\cdot \bigl(\cos(jx)+i\cdot\sin(jx)\bigr) +c_{-j}\cdot \bigl(\cos(-jx)+i\cdot \sin(-jx)\bigr)\Bigr)=\\&& = c_0 + \sum_{j=1}^{N}~\Bigl( c_j\cdot \bigl(\cos(jx)+i\cdot\sin(jx)\bigr) +c_{-j}\cdot \bigl(\cos(jx)-i\cdot \sin(jx)\bigr)\Bigr)=\\&&=c_0 + \sum_{j=1}^{N}~\Bigl((c_j\ +c_{-j}) \cdot \cos(jx)+ (c_j-c_{-j})\cdot i\cdot\sin(jx) \Bigr)= \\&&= \fbox{$\displaystyle\frac{a_0}{2}+\sum_{j=1}^{N} \Bigl( a_j\cdot \cos(jx) + b_j\cdot \sin(jx) \Bigr)$} \end{eqnarray*}$

______________________________________________________________

Dabei gilt für die Umrechnung:

$\begin{eqnarray*} a_j=c_j+c_{-j},\qquad b_j=i\cdot(c_j-c_{-j}),\qquad a_j,b_j \in \mathbb C \end{eqnarray*}$

$\begin{eqnarray*} c_j=\frac{a_j-i\cdot b_j}{2},\qquad c_{-j}=\frac{a_j+i\cdot b_j}{2},\qquad c_j,c_{-j} \in \mathbb C \end{eqnarray*}$

26.02.2007, 02:13

tigerbine

Auf diesen Beitrag antworten »

1c. Vektorraum der trigonometrischen Polynome
$\begin{eqnarray*} \text{Die Polynome aus (1a, 1b) bilden den} \end{eqnarray*}$ $\begin{eqnarray*} \mathbb C-\text{Vektorraums } \Gamma_N. \end{eqnarray*}$ $\begin{eqnarray*} \text{Dieser besitzt die Dimension } 2N+1 \text{ und die Basis } \end{eqnarray*}$ $\begin{eqnarray*} \{e_{-n},...,e_0,...,e_n\}, \end{eqnarray*}$ $\begin{eqnarray*} \text{wobei gilt } \end{eqnarray*}$ $\begin{eqnarray*} e_j:=\exp(i\cdot jx). \end{eqnarray*}$

Beweis:

Der Nachweis der Vektorraumaxiome erfolgt intuitiv, da die Summe zweier trig. Polynome mit Grad $\begin{eqnarray*} \leq N \end{eqnarray*}$ wieder ein trig. Polynom mit Grad $\begin{eqnarray*} \leq N \end{eqnarray*}$ ist.
Ebenso verifiziert man die abelsche Gruppe mit neutralem Element 0(-Funktion)
Weiter ist durch die Definition ersichtlich, dass $\begin{eqnarray*} \{e_{-N},...,e_0,...,e_N\} \end{eqnarray*}$ ein Erzeugendensystem von $\begin{eqnarray*} \Gamma_N \end{eqnarray*}$ bilden
Somit bleibt die Lineare Unabhängigkeit zu zeigen. Dies macht man dadurch, dass man zeigt, dass die Basisfunktionen paarweise orthogonal sind.

Man verwendet das Skalarpodukt:

$\begin{eqnarray*} <f,g>=\frac{1}{2\pi}\int_0^{2\pi}~\overline{f(x)}\cdot g(x)~dx \end{eqnarray*}$

Desweiteren gilt:

$\begin{eqnarray*} \int e^{cx}~dx = \frac{1}{c}\cdot e^{cx} +C\text{ für } c \neq 0 \end{eqnarray*}$

Damit folgt:

$\begin{eqnarray*} <e_r,e_p> = \begin{cases} 1 & \text{für } r =p \\ 0 & \text{für } r \neq p \end{cases} \end{eqnarray*}$

Denn:

$\begin{eqnarray*} \frac{1}{2\pi}\int_0^{2\pi}~e^{-px}\cdot e^{px}~dx &&= \frac{1}{2\pi}\int_0^{2\pi}1~dx =\\&&= 1 \end{eqnarray*}$

$\begin{eqnarray*} \frac{1}{2\pi}\int_0^{2\pi}~e^{-rx}\cdot e^{px}~dx &&= \frac{1}{2\pi}\int_0^{2\pi}~e^{(p-r)x}~dx =\\&&=\frac{1}{2\pi} \cdot [\frac{1}{p-r} \cdot e^{(p-r)x}]_0^{2\pi} =\\&&= \frac{1}{2\pi} \cdot\frac{1}{p-r}\cdot [1-1]= \\&&=0 \end{eqnarray*}$

26.02.2007, 02:46

tigerbine

Auf diesen Beitrag antworten »

2. Approximation von Funktionen durch Fourierpolynome
Trigonometrische Polynome kann man nun z.B. zur Approximation von 2 $\begin{eqnarray*} \pi \end{eqnarray*}$ -periodischen Funktionen f verwenden. Es soll hier die Cosinus-Sinus-Darstellung verwendet werden. Gilt für die Koeffizienten a,b:

$\begin{eqnarray*} a_j=\frac{1}{\pi}~\int_{0}^{2\pi}~f(x)\cos(jx)~dx \end{eqnarray*}$
$\begin{eqnarray*} b_j=\frac{1}{\pi}~\int_{0}^{2\pi}~f(x)\sin(jx)~dx \end{eqnarray*}$

so nennt man das trig. Polynom N-tes Fourierpolynom von f:

$\begin{eqnarray*} T_N^f(x) = \frac{a_0}{2}+\sum_{j=1}^{N}~\Bigl( a_j\cdot \cos(jx) + b_j\cdot \sin(jx) \Bigr) \end{eqnarray*}$

Wie man auch nicht periodische Funktionen approximieren kann wird in 2.d gezeigt.
________________________________________________________________
Lehrer

Trigonometrische Polynome werde oft auch allgemein als Fourier-Polynome bezeichnet. Dabei müssen die Koeffizienten a,b aber nicht obige Gestalt haben.

26.02.2007, 13:49

tigerbine

Auf diesen Beitrag antworten »

2a. Fourierreihe und Konvergenz
Unter der Fourierreihe $\begin{eqnarray*} T_{\infty}^f \end{eqnarray*}$ einer 2 $\begin{eqnarray*} \pi \end{eqnarray*}$ -periodischen Funktion f versteht man die Folge der Fourierpolyme von f und im Konvergenzfall auch den Grenzwert.

$\begin{eqnarray*} T_{\infty}^f(x)=\frac{a_0}{2}+\sum_{j=1}^{\infty}~\Bigl( a_j\cdot \cos(jx) + b_j\cdot \sin(jx) \Bigr) =\lim_{N\to\infty}~T_{N}^f(x) \end{eqnarray*}$

Was läßt sich nun über das Konvergenzverhalten aussagen?

Satz von Carleson, (1964)

Die Fourrierriehe jeder stetigen 2 $\begin{eqnarray*} \pi \end{eqnarray*}$ -periodischen Funktion f konvergiert fast überall gegen f.

Fast überall bedeutet hier: Es gibt eine Ausnahmemenge A vom Lebesgue-Maß 0, so dass $\begin{eqnarray*} T_{\infty}^f(x)=f(x)~\forall x \notin A \end{eqnarray*}$ gilt.

Satz von Dirichlet

Sei f eine 2 $\begin{eqnarray*} \pi \end{eqnarray*}$ periodische Regelfunktion und besitze im Punkt sowohl eine linksseitige als auch rechtsseitige Ableitung. Dann konvergiert die Fourrierreihe in x gegen das arithmetische Mittel der linksseitigen und rechtsseitigen Grenzwertes von f in x:

$\begin{eqnarray*} T_{\infty}^f(x) =\frac{f(x-)+f(x+)}{2} \end{eqnarray*}$

Ist f stetig in x, so gilt:

$\begin{eqnarray*} T_{\infty}^f(x) =f(x) \end{eqnarray*}$

Darstellungssatz

Falls die Fourierreihe einer 2 $\begin{eqnarray*} \pi \end{eqnarray*}$ -periodischen Regelfunktion f in einem Punkt x konvergiert, gilt:

$\begin{eqnarray*} T_{\infty}^f(x) =\frac{f(x-)+f(x+)}{2} \end{eqnarray*}$

____________________________________________________________

Definition (Regelfunktion)
Sei I ein Intervall mit Anfangspunkt a und Endpunkt b. Eine Funktion $\begin{eqnarray*} f:~I \to \mathbb C \end{eqnarray*}$ heiß Regelfunktion auf I, wenn sie

in jedem Punkt $\begin{eqnarray*} x \in (a, b) \end{eqnarray*}$ sowohl einen linksseitigen als auch einen rechtsseitigen Grenzwert hat,
im Fall $\begin{eqnarray*} a\in I \end{eqnarray*}$ in A einen rechtsseitigen und im Fall $\begin{eqnarray*} b\in I \end{eqnarray*}$ in b einen linksseitigen Grenzwert hat.

Die Regelfunktionen auf I bilden einen $\begin{eqnarray*} \mathbb C \end{eqnarray*}$ -Vektorraum.
_____________________________________________________________

Lehrer

Dass die Stetigkeit alleine nicht reicht, zeigt z.B. das Beispiel von Fejér (vgl. Königsberger Analysis I, 5. Auflage S. 332)

26.02.2007, 14:04

tigerbine

Auf diesen Beitrag antworten »

2b. Fourierreihen von ungeraden Funktionen - reine Sinusreihe
Sei nun f eine ungerade $\begin{eqnarray*} 2\pi \end{eqnarray*}$ -periodische Funktion, d.h. es gilt

$\begin{eqnarray*} f(-x) = -f(x) \end{eqnarray*}$
$\begin{eqnarray*} f(2\pi-x) = -f(x) \end{eqnarray*}$

Dann gilt für die Koeffizienten des N-ten Fourierpolynoms $\begin{eqnarray*} T_N^f \end{eqnarray*}$ von f:

$\begin{eqnarray*} a_j = 0,~\forall ~k = 0,...,N \end{eqnarray*}$

Und es ist:

$\begin{eqnarray*} \fbox{$\displaystyle T_N^f(x) = \sum_{j=1}^{N}b_j\cdot \sin(jx) $} \end{eqnarray*}$

Beweis:

Wichtige Umformung $\begin{eqnarray*} \fbox{$\displaystyle\int_{-a}^{-b}~f(x)~dx = -\int_{a}^{b}~f(-x)~dx$} \end{eqnarray*}$ (*)

k=0:

$\begin{eqnarray*} a_0 &&= \frac{1}{\pi} \int_{0}^{2\pi}~f(x)\cos(0)~dx = \frac{1}{\pi} \int_{0}^{2\pi}~f(x) \cdot 1~dx = \\&&= \frac{1}{\pi}\Bigl( \int_{0}^{\pi}~f(x) ~dx + \int_{\pi}^{2\pi}~f(x) ~dx\Bigr) \stackrel{\mathrm{2\pi-periodisch}}=\\&&=\frac{1}{\pi}\Bigl( \int_{0}^{\pi}~f(x) ~dx + \int_{-\pi}^{0}~f(x) ~dx\Bigr) \stackrel{\mathrm{(*)}}=\\&&=\frac{1}{\pi}\Bigl( \int_{0}^{\pi}~f(x) ~dx - \int_{\pi}^{0}~f(-x) ~dx\Bigr) \stackrel{\mathrm{ungerade}}=\\&&=\frac{1}{\pi}\Bigl( \int_{0}^{\pi}~f(x) ~dx - \int_{\pi}^{0}~-f(x) ~dx\Bigr) =\\&&=\frac{1}{\pi}\Bigl( \int_{0}^{\pi}~f(x) ~dx - \int_{0}^{\pi}~f(x) ~dx\Bigr) = \\&&=0 \end{eqnarray*}$

k > 0:

Für k > 0 ist $\begin{eqnarray*} \cos(kx) \end{eqnarray*}$ eine $\begin{eqnarray*} \frac{2\pi}{k} \end{eqnarray*}$ - periodische gerade Funktion und es gilt $\begin{eqnarray*} \cos(kx) = \cos(-kx) \end{eqnarray*}$ . Somit ist $\begin{eqnarray*} \cos(kx) \end{eqnarray*}$ auch eine $\begin{eqnarray*} 2\pi \end{eqnarray*}$ - periodische gerade Funktion.

$\begin{eqnarray*} a_k &&= \frac{1}{\pi} \int_{0}^{2\pi}~f(x)\cos(kx)~dx = \\&&=\frac{1}{\pi} \Bigl( \int_{0}^{\pi}~f(x)\cos(kx) ~dx + \int_{\pi}^{2 \pi}~f(x)\cos(kx) ~dx\Bigr) \stackrel{\mathrm{2\pi-periodisch}}=\\&&=\frac{1}{\pi} \Bigl( \int_{0}^{\pi}~f(x)\cos(kx) ~dx + \int_{-\pi}^{0}~f(x)\cos(kx) ~dx\Bigr) =\\&&=\frac{1}{\pi} \Bigl( \int_{0}^{\pi}~f(x)\cos(kx) ~dx - \int_{\pi}^{0}~f(-x)\cos(-kx) ~dx\Bigr) \stackrel{gerade/ungerade}=\\&&=\frac{1}{\pi} \Bigl( \int_{0}^{\pi}~f(x)\cos(kx) ~dx - \int_{0}^{\pi}~f(x)\cos(kx) ~dx\Bigr) =\\&&=0 \end{eqnarray*}$

26.02.2007, 14:31

tigerbine

Auf diesen Beitrag antworten »

2c. Fourierreihen von geraden Funktionen - reine Cosinusreihe
Sei nun f eine gerade $\begin{eqnarray*} 2\pi \end{eqnarray*}$ -periodische Funktion, d.h. es gilt

$\begin{eqnarray*} f(-x) = f(x) \end{eqnarray*}$
$\begin{eqnarray*} f(2\pi+x) = f(x) \end{eqnarray*}$

Dann gilt für die Koeffizienten des N-ten Fourierpolynoms $\begin{eqnarray*} T_N^f \end{eqnarray*}$ von f:

$\begin{eqnarray*} b_j = 0,~\forall ~k = 0,...,N \end{eqnarray*}$

Und es ist:

$\begin{eqnarray*} \fbox{$\displaystyle T_N^f(x) = \frac{a_0}{2}+\sum_{j=1}^{N}a_j\cdot \cos(jx) $} \end{eqnarray*}$

26.02.2007, 16:02

tigerbine

Auf diesen Beitrag antworten »

2d. Periodische Funktionen selbst gemacht

Nichtperiodische Funktion

Sei $\begin{eqnarray*} f:~\mathbb R \to \mathbb R \end{eqnarray*}$ eine stetige Funktion, so kann man sie wie folgt zu einer 2 $\begin{eqnarray*} \pi \end{eqnarray*}$ -periodischen Funktion machen:

$\begin{eqnarray*} \hat f(x): = \begin{cases} f(x) & x \in (0,2\pi) \\ \frac{f(0)+f(2\pi)}{2}&x=0 \end{cases} \end{eqnarray*}$

Die Motivation für den Funktionswert am Intervallrand x=0 ist der Darstellungssatz, welcher sich aus dem Satz von Fejér ergibt.
Nur auf definierte Funktion

Wie sollte man diese auf das Intervall fortsetzen? Für die Intervallränder gilt wieder das Vorgehen gemäß Darstellungssatz. Für das Intervallinnere gibt es die Möglichkeit eine gerade oder ungerade Funktion zu kreieren. Beispiele:
- ungerade Fortsetzung von $\begin{eqnarray*} f \end{eqnarray*}$ auf $\begin{eqnarray*} [0,2\pi] \end{eqnarray*}$ mit $\begin{eqnarray*} f(0)=f(\pi)=0 \end{eqnarray*}$
  
  $\begin{eqnarray*} \hat {f}(x):=\begin{cases}f(x) & \text{für } x \in [0,\pi] \\ -f(2\pi-x) & \text{für } x \in [\pi,2\pi] \end{cases} \end{eqnarray*}$
  
  Falls $\begin{eqnarray*} f \end{eqnarray*}$ in $\begin{eqnarray*} x=\pi \end{eqnarray*}$ einseitig diff'bar war, dann ist $\begin{eqnarray*} \hat f \end{eqnarray*}$ stetig diff'bar.
  
  $\begin{eqnarray*} \lim_{h\to +}~\frac{\hat{f}(\pi+h)-\hat{f}(\pi)}{h}=\lim_{h\to 0+}~\frac{-f(\pi-h)+f(\pi)}{h}=f'(\pi) \end{eqnarray*}$
  
  $\begin{eqnarray*} \lim_{h\to +}~\frac{\hat{f}(\pi)-\hat{f}(\pi-h)}{h}=\lim_{h\to 0+}~\frac{f(\pi)-f(\pi-h)}{h}=f'(\pi) \end{eqnarray*}$
- gerade Fortsetzung von $\begin{eqnarray*} f \end{eqnarray*}$ auf $\begin{eqnarray*} [0,2\pi] \end{eqnarray*}$ mit $\begin{eqnarray*} f(0)=f(\pi)=0 \end{eqnarray*}$
  
  $\begin{eqnarray*} \hat {f}(x):=\begin{cases}f(x) & \text{für } x \in [0,\pi] \\ f(2\pi-x) & \text{für } x \in [\pi,2\pi] \end{cases} \end{eqnarray*}$

27.02.2007, 12:33

tigerbine

Auf diesen Beitrag antworten »

3. Trigonometrische-Interpolations-Aufgabe
Gesucht ist ein trig. Polynom kleinstes Grades, das die Interpolationsbedingung für die N äquidistanten Knoten $\begin{eqnarray*} x_k:=\frac{2\pi}{N}\cdot k \end{eqnarray*}$ und komplexe Funktionswerte $\begin{eqnarray*} y_k \in \mathbb C, \forall k = 0,...,N-1 \end{eqnarray*}$ erfüllt. Somit lautet die Interpolationsbedingung:

$\begin{eqnarray*} T_N^*(x_k) = y_k,\quad \forall k = 0,...,N-1 \end{eqnarray*}$

Die Lösung der TIPA soll mit $\begin{eqnarray*} T_N^* \end{eqnarray*}$ bezeichnet werden.

27.02.2007, 12:44

tigerbine

Auf diesen Beitrag antworten »

3a. Darstellung 1
Mit der Definition eines trig. Polynoms von Grad N aus (1a) erhalten wir folgende Darstellung :

$\begin{eqnarray*} T_N(x) =\sum_{j=-N}^{N}c_j\cdot \exp(i\cdot jx) \end{eqnarray*}$

Dieses Polynom hat jedoch (2N+1) Koeffizienten und mit nur N Interpolationsbedingungen sind diese nicht eindeutig bestimmbar.

27.02.2007, 12:51

tigerbine

Auf diesen Beitrag antworten »

3b. Darstellung 2
Um nun ein Trig. Polynom vom Grad N zu finden, dessen Koeffizienten eindeutig bestimmbar sind, bedient man sich folgender Rechnung. Setzt man für x die Knoten $\begin{eqnarray*} x_k \end{eqnarray*}$ ein, so erhält man:

$\begin{eqnarray*} T_N(x_k) =\sum_{j=-N}^{N}c_j\cdot \exp(i\cdot j x_k) = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \qquad \sum_{j=-N}^{N}c_j\cdot \exp(i\cdot \frac{2\pi}{N}jk) = \sum_{j=-N}^{N}c_j\cdot \exp(i\cdot \frac{2\pi}{N})^{jk} = \sum_{j=-N}^{N}c_j\cdot (w_N)^{jk}= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \qquad \sum_{j=-N}^{-1}~c_j\cdot (w_N)^{jk}+c_0\cdot 1 + \sum_{j=1}^{N}~c_j\cdot (w_N)^{jk}= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \qquad\sum_{j=1}^{N}~c_{-j}\cdot (w_N)^{-jk}+c_0 + \sum_{j=1}^{N}~c_j\cdot (w_N)^{jk}= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \qquad\sum_{j=1}^{N}~c_{-j}\cdot (w_N)^{(N-j)k}+c_0 + \sum_{j=1}^{N}~c_j\cdot c_N\cdot (w_N)^{jk}= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \qquad c_0+\sum_{j=1}^{N-1}~c_{-j}\cdot (w_N)^{(N-j)k} + c_{-N}\cdot(w_N)^{0k} + \sum_{j=1}^{N-1}~c_j\cdot (w_N)^{jk}+c_N\cdot (w_N)^{NK}= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \qquad c_0+(c_N-c_{-N})+\sum_{j=1}^{N-1}~(c_j+c_{-(N-j)})\cdot (w_N)^{jk}= \end{eqnarray*}$

$\begin{eqnarray*} = \qquad \qquad \sum_{j=0}^{N-1}~d_j\cdot (w_n)^{jk} = \sum_{j=0}^{N-1}~d_j\cdot (w_n^k)^{j} =\sum_{j=0}^{N-1}~d_j\cdot \exp(i\cdot x_k)^j = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \qquad \sum_{j=0}^{N-1}d_j\cdot \exp(i\cdot jx_k)=:T_N^*(x_k) \end{eqnarray*}$

D.h. die beiden trig. Polynome vom Grad N, $\begin{eqnarray*} T_N \end{eqnarray*}$ und $\begin{eqnarray*} T_N^* \end{eqnarray*}$ nehmen an den N Knoten dieselben Funktionswerte an.

Dennoch handelt es sich i.A. um verschiedene Polynome!

27.02.2007, 13:36

tigerbine

Auf diesen Beitrag antworten »

3c. Existenz und Eindeutigkeit
Bei dem in 3b gewonnenen trig. Polynom $\begin{eqnarray*} T_N^* \end{eqnarray*}$ sind jetzt nur N Koeffizienten zu bestimmen. (Dennoch ist es vom Grad N, es gilt eben $\begin{eqnarray*} d_{-N} = ... = d_{-1}=d_N =0 \end{eqnarray*}$ ). Es gilt also die Koeffizienten $\begin{eqnarray*} d_0,...,d_{N-1} \end{eqnarray*}$ so zu bestimmen, dass gilt:

$\begin{eqnarray*} y_k=\sum_{j=0}^{N-1}d_j\cdot \exp(i\cdot jx_k) \end{eqnarray*}$

Das gesuchte trig. Polynom hat nach (3b) also die Gestalt:

$\begin{eqnarray*} T_N^*(x)=\sum_{j=0}^{N-1}~d_j\cdot \exp(i\cdot x)^j = \sum_{j=0}^{N-1}~d_j\cdot z^j \end{eqnarray*}$

Da die N-Knoten paarweise verschieden sind, folgt aus dieser Darstellung, dass das trig. Interpolationsprobelm:

$\begin{eqnarray*} T_N^*(x_k)=y_k,~k = 0,...,N-1 \end{eqnarray*}$

immer (komplexe oder reelle $\begin{eqnarray*} y_k \end{eqnarray*}$ ) eindeutig lösbar ist. Nun benötigt man aber noch einen Weg, die gesuchten Koeffizienten zu bestimmen.

Aus der Darstellung

$\begin{eqnarray*} T_N^*(x)=\sum_{j=0}^{N-1}~d_j\cdot \Bigl( \cos(jx) + i\cdot \sin(jx) \Bigr) \end{eqnarray*}$

erkennt man, dass es sich um eine Abbildung von $\begin{eqnarray*} \mathbb R \rightarrow \mathbb C \end{eqnarray*}$ handelt, selbst wenn die $\begin{eqnarray*} y_k \end{eqnarray*}$ alle reell sind. Zur endgültigen Lösung des Problems sind die folgenden Hilfsresultate nötig.

_____________________________________________________________
Legende zu 3a,b,c:

$\begin{eqnarray*} w_N: \text{ n-te Einheitswurzel},~(w_N)^{-j} = 1\cdot (w_N)^{-j} = (w_N)^N\cdot (w_N)^{-j} = (w_N)^{(N-j)} \end{eqnarray*}$

$\begin{eqnarray*} d_0:=c_0 + (c_N + c_{-N}) = \frac{a_0}{2}+a_N \end{eqnarray*}$

$\begin{eqnarray*} d_j:=(c_j+c_{-(N-j)}) \end{eqnarray*}$

27.02.2007, 13:37

tigerbine

Auf diesen Beitrag antworten »

3d. Hilfsresultate
Hilfsresultat 1

$\begin{eqnarray*} S:=\sum_{k=0}^{N-1}~(w_N)^{kl} = \begin{cases} N & \text{für } l = vN \\ 0 & \text{für } l \neq vN \end{cases} \end{eqnarray*}$

Beweis:

Es gilt für $\begin{eqnarray*} z:=(w_N)^l: \end{eqnarray*}$

$\begin{eqnarray*} zS = (w_N)^l\cdot \sum_{k=0}^{N-1}(w_N)^{kl} =\sum_{k=1}^{N}(w_N)^{kl} \stackrel{\mathrm{(w_N)^0=(w_N)^{Nl}}}= \sum_{k=0}^{N-1}(w_N)^{kl} = S \end{eqnarray*}$ (*)

Für diese Gleichheit gibt es 2 Möglichkeiten:

Für $\begin{eqnarray*} S \neq 0 \end{eqnarray*}$ muss gelten $\begin{eqnarray*} z = 1 \end{eqnarray*}$ , also $\begin{eqnarray*} l =vN \end{eqnarray*}$ . Daraus folgt:

$\begin{eqnarray*} \sum_{k=0}^{N-1}(w_N)^{kl}=\sum_{k=0}^{N-1}(w_N^{vN})^{k}=\sum_{k=0}^{N-1}1 = N \end{eqnarray*}$
Sei nun $\begin{eqnarray*} S = 0 \end{eqnarray*}$ , dann gilt wegen (1) offensichtlich $\begin{eqnarray*} l \neq vN \end{eqnarray*}$ .
Da jedoch die Gleichung (*) für alle l gilt, muss für alle $\begin{eqnarray*} l \neq vN \end{eqnarray*}$ gelten $\begin{eqnarray*} S = 0 \end{eqnarray*}$

Hilfsresultat 2:

Um die Koeffizienten $\begin{eqnarray*} d_j \end{eqnarray*}$ bestimmen zu können, multipliziert man die Interpolationsbedingung:

$\begin{eqnarray*} y_k = T_N^*(x_k) = \sum_{j=0}^{N-1}~d_j\cdot (w_N)^{jk} \end{eqnarray*}$

für l =0,1,...,N-1 mit $\begin{eqnarray*} (w_N)^{(-lk)} \end{eqnarray*}$ und summiert über k:

$\begin{eqnarray*} \sum_{k=0}^{N-1}~(w_N^{(-lk)}\cdot y_k) = \sum_{k=0}^{N-1}(w_N^{(-lk)}\cdot \sum_{j=0}^{N-1}d_j\cdot (w_N)^{jk}) = \end{eqnarray*}$

$\begin{eqnarray*} =\sum_{k=0}^{N-1} \sum_{j=0}^{N-1} d_j \cdot (w_N)^{k(j-l)} = \sum_{j=0}^{N-1} d_j \sum_{k=0}^{N-1} (w_N)^{k(j-l)} \end{eqnarray*}$

Für j=l gilt (j-l) = 0 und es folgt mit HR 1:

$\begin{eqnarray*} \sum_{k=0}^{N-1}(w_N)^{k(j-l)} = N \end{eqnarray*}$

Für $\begin{eqnarray*} j \neq l \end{eqnarray*}$ gilt $\begin{eqnarray*} (j-l) \neq vN \end{eqnarray*}$ und es folgt:

$\begin{eqnarray*} \sum_{k=0}^{N-1}(w_N)^{k(j-l)} = 0 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \sum_{k=0}^{N-1} (w_N^{(-lk)}\cdot y_k) = d_l \cdot N \end{eqnarray*}$

27.02.2007, 13:38

tigerbine

Auf diesen Beitrag antworten »

3e. Berechnung der Koeffizienten d
Somit kann man (durch ersetzen von l durch j) wie folgt umstellen:

$\begin{eqnarray*} d_j=\frac{1}{N}\cdot \sum_{k=0}^{N-1}~y_k(w_N)^{(-jk)}, \quad j=0,1,...,N-1 \end{eqnarray*}$

27.02.2007, 13:59

tigerbine

Auf diesen Beitrag antworten »

4. Diskrete Fourier Analyse / Transformation
Sind nun die Funktionswerte an den Knoten reell, also $\begin{eqnarray*} y_k \in \mathbb R \end{eqnarray*}$ , so sucht man anstatt dem soeben bestimmenten interpolierenden trig.Polynom

$\begin{eqnarray*} T_N^*:~\mathbb R \rightarrow \mathbb C \end{eqnarray*}$

ein trignomotrisches Polynom mit dem folgenden Abbildungsverhalten:

$\begin{eqnarray*} t_N^{\mathbb R}:~\mathbb R \rightarrow \mathbb R \end{eqnarray*}$

Dieses soll dann in der Darstellung

$\begin{eqnarray*} t_N^{\mathbb R}(x) = \frac{a_0}{2} +\sum_{j=1}^? \Big(a_j\cdot \cos(jx)+b_j\cdot \sin(jx) \Bigr), \qquad a_j,b_j \in \mathbb R \end{eqnarray*}$

vorliegen. Da zu seiner Berechnung nur N Knoten voliegen, kann $\begin{eqnarray*} t_N^{\mathbb R} \end{eqnarray*}$ kein trig. Polynom vom Grad N sein, sondern nur den Grad

$\begin{eqnarray*} [M] :=\Bigl[\frac{N+1}{2} \Bigr] = \begin{cases} \frac{N+1}{2} & \text{für N ungerade} \\ \frac{N}{2} & \text{für N gerade} \end{cases} \end{eqnarray*}$

(Gausklammer) haben. Wir schreiben also:

$\begin{eqnarray*} t_N^{\mathbb R}(x) = \frac{a_0}{2} +\sum_{j=1}^M \Big(a_j\cdot \cos(jx)+b_j\cdot \sin(jx) \Bigr), \qquad a_j,b_j \in \mathbb R \end{eqnarray*}$

Dennoch soll dieses Polynom in Bezug zu $\begin{eqnarray*} T_N^* \end{eqnarray*}$ gestellt werden, um die Existenz und Eindeutigkeitsaussage übernehmen zu können.

27.02.2007, 17:31

tigerbine

Auf diesen Beitrag antworten »

4a. Eigenschaften Koeffizienten d
Da die $\begin{eqnarray*} y_k \end{eqnarray*}$ alle reell sind, folgt für die Koeffizienten $\begin{eqnarray*} d_j \end{eqnarray*}$ von $\begin{eqnarray*} T_N^* \end{eqnarray*}$ :

$\begin{eqnarray*} d_0=\frac{1}{N}\cdot \sum_{k=0}^{N-1}y_k \Rightarrow d_0 \in \mathbb R \end{eqnarray*}$
$\begin{eqnarray*} d_{N-j}=\frac{1}{N}\cdot \sum_{k=0}^{N-1}y_k \cdot(w_N)^{-(N-j)k}=\frac{1}{N}\cdot \sum_{k=0}^{N-1}y_k \cdot(w_N)^{-Nk+jk}= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \frac{1}{N}\cdot \sum_{k=0}^{N-1} y-k\cdot (w_N)^{jk} = \frac{1}{N} \cdot \sum_{k=0}^{N-1} y_k\cdot \overline{(w_N)^{-jk}}= \overline{d_j} \end{eqnarray*}$
für gerades N gilt:

$\begin{eqnarray*} d_{\frac{N}{2}}=\overline{d_{\frac{N}{2}}} \qquad \Rightarrow d_{\frac{N}{2}} \in \mathbb R \end{eqnarray*}$

27.02.2007, 18:19

tigerbine

Auf diesen Beitrag antworten »

4b. Zerlegung in 2 Polynome
Auf grund des gewünschten Grades von $\begin{eqnarray*} t_N^{\mathbb R} \end{eqnarray*}$ zerlegen wir $\begin{eqnarray*} T_N^* \end{eqnarray*}$ in die Summe zweier Polynome:

$\begin{eqnarray*} T_N^*(x)=:t_N^{\mathbb R}+t_N^{\mathbb C} \end{eqnarray*}$

Wobei folgende Definitionen verwendet werden:

$\begin{eqnarray*} h_j(x):=\exp(i\cdot(N-j)x)-\exp(i\cdot(-jx)) \end{eqnarray*}$
$\begin{eqnarray*} t_N^{\mathbb R}(x):=d_0~+~\sum_{j=1}^{M-1}2\cdot Re(d_j\cdot \exp(i\cdot jx))~+~ d_M\cdot \cos(M\cdot x) \end{eqnarray*}$
$\begin{eqnarray*} t_N^{\mathbb C}(x):=\sum_{j=1}^{M-1}\overline{d_j} h_j(x)~+~i\cdot d_M\sin(M\cdot x) \end{eqnarray*}$
$\begin{eqnarray*} d_M=0 \qquad \text{falls N ungerade ist} \end{eqnarray*}$

27.02.2007, 18:47

tigerbine

Auf diesen Beitrag antworten »

4c-1. Eigenschaften der beiden Polynome an den Knoten
Die in (4b) behauptete Zerlegung von $\begin{eqnarray*} T_N^* \end{eqnarray*}$ bzgl. der Definition muss natürlich noch nachgewiesen werden. Des weiteren sollen noch 2 wichtige Eigenschaften der beiden Zerlegungspolynome nachgewiesen werden. Aus Übersichtsgründen finden sich die Beweise dazu im nächsten Abschnitt (4c-2).

Behauptung 1:

$\begin{eqnarray*} t_N^{\mathbb C}(x_k)=0 \end{eqnarray*}$

Behauptung 2:

$\begin{eqnarray*} T_N^*(x)=t_N^{\mathbb R}(x)+ t_N^{\mathbb C}(x) \end{eqnarray*}$

Behauptung 3:

$\begin{eqnarray*} t_N^{\mathbb R}(x_k)=y_k \end{eqnarray*}$

27.02.2007, 19:23

tigerbine

Auf diesen Beitrag antworten »

4c-2. Beweise
Beweis 1:

$\begin{eqnarray*} t_N^{\mathbb C}(x_k)=\sum_{j=1}^{M-1}\overline{d_j} h_j(x_k)~+~i\cdot d_M\sin(M\cdot x_k) \end{eqnarray*}$

Dabei gilt:

$\begin{eqnarray*} h_j(x_k)&&=\exp\Bigl(i \cdot (N-j)x_k \Bigr)-\exp\Bigl(i \cdot (-j)x_k \Bigr)=\\ &&= \exp\Bigl(i \cdot (N-j)\frac{2\pi}{N}\cdot k \Bigr)-\exp\Bigl(i \cdot (-j)\frac{2\pi}{N}\cdot k \Bigr) =\\ &&= \exp\Bigl(i \cdot 2\pi k \Bigr) \cdot \exp\Bigl( i\cdot (-j)\frac{2\pi}{N}k \Bigr)-\exp\Bigl(i \cdot (-j)\frac{2\pi}{N}\cdot k \Bigr) = \\&&= 1\cdot \exp\Bigl( i\cdot (-j)\frac{2\pi}{N}k \Bigr)-\exp\Bigl(i \cdot (-j)\frac{2\pi}{N}\cdot k \Bigr) =\\&&= 0 \quad \forall ~k=0,...,N-1 \end{eqnarray*}$

$\begin{eqnarray*} d_M\sin(M\cdot x_k) = \begin{cases} 0 & \text{N ungerade} \\ d_M\cdot \sin(\pi k) & \text{N gerade} \end{cases} \end{eqnarray*}$

Somit gilt wie behauptet:

$\begin{eqnarray*} t_N^{\mathbb C}(x_k)=0 \quad \forall~k =0,...,N-1 \end{eqnarray*}$

Beweis 2:

$\begin{eqnarray*} T_N^*(x)&&=\sum_{j=0}^{N-1}~d_j\cdot \Bigl( \cos(jx) + i\cdot \sin(jx) \Bigr) =\\&&=\sum_{j=0}^{N-1}~d_j\cdot \Bigl(\exp(i \cdot jx)\Bigr) =\\&&= d_0 +\sum_{j=0}^{M-1}~d_j\cdot \Bigl(\exp(i \cdot jx)\Bigr) + d_M \cdot \Bigl(\exp(i \cdot Mx)\Bigr) + \sum_{j=M+1}^{N-1}~\Bigl(\exp(i \cdot jx)\Bigr) =\\&& = d_0 +\sum_{j=0}^{M-1}~d_j\cdot \Bigl(\exp(i \cdot jx)\Bigr) + d_M \cdot \Bigl(\exp(i \cdot Mx)\Bigr) + \sum_{j=1}^{M-1}~d_{N-j}\cdot \Bigl(\exp(i \cdot (N-j)x)\Bigr)=\\&&\stackrel{(4a)}{=} d_0 + \sum_{j=1}^{M-1} \Bigl\{d_j\cdot \Bigl(\exp(i \cdot jx)\Bigr) + \overline{d_j}\cdot \Bigl(\exp(i \cdot (N-j)x)\Bigr) \Bigr\} + d_M \cdot \Bigl(\exp(i \cdot Mx)\Bigr) = \\&&\text{Nun schiebt man einen Term ein und zieiht in wieder ab} \\&&= d_0 + \sum_{j=1}^{M-1} \Bigl\{d_j\cdot \Bigl(\exp(i \cdot jx)\Bigr) + \overline{d_j\cdot \bigl(\exp(i\cdot jx)\Bigr)}-\overline{d_j\cdot \bigl(\exp(i\cdot jx)\Bigr)}+\overline{d_j}\cdot \Bigl(\exp(i \cdot (N-j)x)\Bigr) \Bigr\} + d_M \cdot \Bigl(\exp(i \cdot Mx)\Bigr) =\\&& \text{Für eine komplexe Zahl z gilt: } z + \overline{z}=2 \cdot \text{Im}(z) \\&&=d_0 + \sum_{j=0}^{M-1}~2\cdot \text{Re}(d_j \cdot \Bigl(\exp(i\cdot jx)\Bigr) + d_M \cdot \cos(Mx) + \sum_{j=1}^{M-1}~\overline{d_j} \cdot \Bigl( \exp(i\cdot (N-j)x-\exp(i\cdot (-j)x)\Bigr)+i\cdot d_M\cdot \sin(Mx) =\\&&=t_N^{\mathbb R}(x) + t_N^{\mathbb C}(x) \end{eqnarray*}$

Aufgrund der Summenaufteilung ist nun auch klar, warum $\begin{eqnarray*} d_M=0 \end{eqnarray*}$ für ungerades N gilt.

Beweis 3:

Folgt direkt mit den zwei vorherigen Beweisen. Denn damit gilt:

$\begin{eqnarray*} y_k=T_N^{*}(x_k)=t_N^{\mathbb R}(x_k)+t_N^{\mathbb C}(x_k) =t_N^{\mathbb R}(x_k) + 0=t_N^{\mathbb R}(x_k) \end{eqnarray*}$

27.02.2007, 19:34

tigerbine

Auf diesen Beitrag antworten »

4d. Berechnung der Koeffizienten d
Somit erfüllen sowohl $\begin{eqnarray*} T_N^* \end{eqnarray*}$ als auch $\begin{eqnarray*} t_N^{\mathbb R} \end{eqnarray*}$ die Interpolationsbedingung. Da aber ein reelles trig. Polynom von möglichst kleinem Grad gesucht ist, lautet die Lösung der diskreten Fourier Analyse:

$\begin{eqnarray*} t_N^{\mathbb R}(x):=d_0~+~\sum_{j=1}^{M-1}2\cdot Re(d_j\cdot \exp(i\cdot jx))~+~ d_M\cdot \cos(M\cdot x) \end{eqnarray*}$

mit

$\begin{eqnarray*} d_j=\frac{1}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot(w_N)^{-jk},\qquad \forall j=0,...,M \end{eqnarray*}$

$\begin{eqnarray*} d_M = 0\qquad \text{ für N ungerade} \end{eqnarray*}$

27.02.2007, 20:05

tigerbine

Auf diesen Beitrag antworten »

4e. Berechnung der Koeffizienten a,b
Um das Polynom auf eine Cosinus/Sinus Darstellung zu bringen, ersetzt man wie in (1b):

$\begin{eqnarray*} \exp(i\cdot jx)=\cos(jx)+i\cdot \sin(jx) \end{eqnarray*}$

Damit ergibt sich:

$\begin{eqnarray*} d_j=\frac{1}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \exp(i \cdot \frac{2\pi}{N})^{-jk} =\frac{1}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \exp(i \cdot (-k) \frac{2\pi}{N}\cdot j) = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \frac{1}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \exp(i \cdot (-k)x_j) = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \frac{1}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \Bigl(\cos(-kx_j)+i\sin(-kx_j )\Bigr)= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \frac{1}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \Bigl(\cos(kx_j)-i\sin(kx_j )\Bigr)= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \frac{1}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \cos(kx_j)-i \cdot \frac{1}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \sin(kx_j ) \end{eqnarray*}$

In Analogie zu (1b) erhält man aus:

$\begin{eqnarray*} d_j:=\frac{a_j-i\cdot b_j}{2} \end{eqnarray*}$

die gesuchten Koeffizienten:

$\begin{eqnarray*} a_j = \frac{2}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \cos(kx_j) \end{eqnarray*}$

$\begin{eqnarray*} b_j = \frac{2}{N} \cdot \sum_{k=0}^{N-1}y_k \cdot \sin(kx_j) \end{eqnarray*}$

27.02.2007, 22:18

tigerbine

Auf diesen Beitrag antworten »

4f. Das gesuchte Polynom
Es gelten die Folgerungen:

$\begin{eqnarray*} \sin(0) =0~\Rightarrow b_0=0 \end{eqnarray*}$
$\begin{eqnarray*} \sin(k\pi) =0~\Rightarrow b_M=0 \end{eqnarray*}$

Damit ergibt sich (verlgeiche auch 4a!):

$\begin{eqnarray*} t_N^{\mathbb R}=d_0~+~\sum_{j=1}^{M-1}2\cdot Re(d_j\cdot \exp(i\cdot jx))~+~ d_M\cdot \cos(M\cdot x) = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \frac{a_0}{2}+\sum_{j=1}^{M-1}2\cdot Re \Bigl((\frac{a_j-i\cdot b_j}{2})\cdot \exp(i\cdot jx)\Bigr)~+\frac{a_M}{2}= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \frac{a_0}{2}+\sum_{j=1}^{M-1}2\cdot Re \Bigl[\Bigl( \frac{a_j}{2}\cos(jx) + \frac{b_j}{2}\sin(jx) \Bigr) +i \cdot \Bigl( \frac{a_j}{2}\sin(jx) - \frac{b_j}{2}\cos(jx) \Bigr)\Bigr]~+\frac{a_M}{2}\cos(M\cdot x)= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \frac{a_0}{2}+\sum_{j=1}^{M-1}\Bigl( a_j\cos(jx) + b_j\sin(jx) \Bigr) +\frac{a_M}{2}\cos(M\cdot x) \end{eqnarray*}$

28.02.2007, 00:31

tigerbine

Auf diesen Beitrag antworten »

5. Unterschiede zwischen Approximation und Interpolation
Nach all diesen Rechnungen und Polynomen mit einen "T" oder "t" im Namen, sollen diese anhand eines Beispiels dargestellt werden. Es soll die Funktion

$\begin{eqnarray*} f(x)=\begin{cases} 0 & \text{für } x = 0 \\ -1 & \text{für } 0<x<\pi \\ 0 & \text{für } x = \pi \\ 1 & \text{für } \pi < x <2\pi \end{cases} \end{eqnarray*}$

approximiert werden, oder der Datensatz $\begin{eqnarray*} (x_k,f(x_k)) \end{eqnarray*}$ interpoliert werden.

Es gelte N = 4

$\begin{eqnarray*} x_0=0,\quad x_1=\frac{1}{2}\pi,\quad x_2=\pi,\quad x_3=\frac{3}{2}\pi \end{eqnarray*}$

$\begin{eqnarray*} y_0=0,\quad y_1=-1,\quad y_2=0,\quad y_3=\-1 \end{eqnarray*}$

28.02.2007, 00:59

tigerbine

Auf diesen Beitrag antworten »

5a. Approximationspolynom
$\begin{eqnarray*} T_4^f(x) = \frac{a_0}{2}+\sum_{j=1}^{4}~\Bigl( a_j\cdot \cos(jx) + b_j\cdot \sin(jx) \Bigr) \end{eqnarray*}$

Da es sich um eine ungerade Funktion handelt, gilt nach 2d:

$\begin{eqnarray*} a_0=...=a_4 = 0 \end{eqnarray*}$

Für die Koeffizienten b gilt:

$\begin{eqnarray*} b_j=\frac{1}{\pi}~\int_{0}^{2\pi}~f(x)\sin(jx)~dx =\frac{1}{\pi}(\int_{0}^{\pi}-\sin(jx)~dx+\int_{\pi}^{2\pi}\sin(jx)~dx ) \end{eqnarray*}$

$\begin{eqnarray*} b_j=-\frac{2}{\pi}\int_{0}^{\pi}\sin(jx)~dx =\begin{cases} -\frac{4}{j\pi} & \text{für j ungerade} \\ 0 & \text{für j gerade} \end{cases} \end{eqnarray*}$

Somit lautet das gesuchte Polynom:

$\begin{eqnarray*} T_4^f(x)=-\frac{4}{\pi}\Bigl(\sin(x)+\frac{1}{3}\cdot \sin(3x)\Bigr) \end{eqnarray*}$

Die zu erkennende Überschwingung an den Sprungstellen wird als Gibbsches Phänomen bezeichnet.

28.02.2007, 02:23

tigerbine

Auf diesen Beitrag antworten »

5b. Lösung der trig. Interpolationsaufgabe
$\begin{eqnarray*} T_4^*(x)=\sum_{j=0}^{3}~d_j\cdot \Bigl( \cos(jx) + i\cdot \sin(jx) \Bigr) \end{eqnarray*}$

$\begin{eqnarray*} d_j=\frac{1}{4}\cdot \sum_{k=0}^{3}~y_k(w_4)^{(-jk)}, \quad j=0,1,...,3 \end{eqnarray*}$

$\begin{eqnarray*} w_4 = i \end{eqnarray*}$

Damit erhalten wir für die Koeffizienten:

$\begin{eqnarray*} d_0 = \frac{1}{4}\cdot \sum_{k=0}^{3}~y_k = 0 \end{eqnarray*}$

$\begin{eqnarray*} d_1=\frac{1}{4}\cdot ( -1\cdot w_4^{-1} +1\cdot w_4^{-3}) =\frac{1}{4}\cdot (i+i) = \frac{1}{2}i \end{eqnarray*}$

$\begin{eqnarray*} d_2=\frac{1}{4}\cdot ( -1\cdot w_4^{-2} +1\cdot w_4^{-6}) =\frac{1}{4}\cdot (+1-1) = 0 \end{eqnarray*}$

$\begin{eqnarray*} d_3 =\frac{1}{4}\cdot ( -1\cdot w_4^{-3} +1\cdot w_4^{-9})= \frac{1}{4}\cdot (-i-i)= -\frac{1}{2}i \end{eqnarray*}$

Somit lautet die Lösung der trig. Interpolationsaufgabe:

$\begin{eqnarray*} T_4^*(x)=\frac{1}{2}i\cdot \Bigl( \cos(x) + i\cdot \sin(x) \Bigr) -\frac{1}{2}i\cdot \Bigl( \cos(3x) + i\cdot \sin(3x) \Bigr) = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad -\frac{1}{2}\cdot \sin(x) + \frac{1}{2}\cdot \sin(3x) + i\cdot \frac{1}{2}\cdot \cos(x) - i\cdot \frac{1}{2}\cdot \cos(3x) \end{eqnarray*}$

$\begin{eqnarray*} Re\Bigl(T_4^*(x) \Bigr) =\frac{1}{2}\cdot (-\sin(x) + \sin(3x) ) \end{eqnarray*}$

$\begin{eqnarray*} Im\Bigl(T_4^*(x) \Bigr) = \frac{1}{2}(\cos(x) - \cos(3x)) \end{eqnarray*}$

$\begin{eqnarray*} T_4^*(x)=\frac{1}{2}i\cdot \Bigl( \cos(x) + i\cdot \sin(x) \Bigr) -\frac{1}{2}i\cdot \Bigl( \cos(3x) + i\cdot \sin(3x) \Bigr) \end{eqnarray*}$

28.02.2007, 05:38

tigerbine

Auf diesen Beitrag antworten »

5c. Lösung der diskreten Fourier-Analyse
$\begin{eqnarray*} t_4^{\mathbb R}(x)= \frac{a_0}{2}+\sum_{j=1}^{1}\Bigl( a_j\cos(jx) + b_j\sin(jx) \Bigr) +\frac{a_2}{2}\cos(2\cdot x) \end{eqnarray*}$

$\begin{eqnarray*} a_j = \frac{2}{4} \cdot \sum_{k=0}^{3}y_k \cdot \cos(kx_j) \end{eqnarray*}$

$\begin{eqnarray*} b_j = \frac{2}{4} \cdot \sum_{k=0}^{3}y_k \cdot \sin(kx_j) \end{eqnarray*}$

Damit erhält man für die Koeffizienten:

$\begin{eqnarray*} a_0= \frac{1}{2}\cdot (0-1+0+1) = 0 \end{eqnarray*}$

$\begin{eqnarray*} a_1= \frac{1}{2}\cdot (0-1\cdot \cos(\frac{\pi}{2})+0+1\cdot \cos(\frac{3\pi}{2})) = 0 \end{eqnarray*}$

$\begin{eqnarray*} a_2= \frac{1}{2}\cdot (0-1\cdot \cos(\pi)+0+1\cdot \cos(3\pi)) = 0 \end{eqnarray*}$

$\begin{eqnarray*} b_1=\frac{1}{2}\cdot (0-1 \cdot \sin(\frac{\pi}{2})+0+1 \cdot \sin(\frac{3\pi}{2}))=-1 \end{eqnarray*}$

Somit lautet die Lösung der diskreten Fourier-Analyse:

$\begin{eqnarray*} t_4^{\mathbb R}(x)=-\sin(x) \end{eqnarray*}$

28.02.2007, 05:46

tigerbine

Auf diesen Beitrag antworten »

5d. Bemerkung
Wie in 3b. erwähnt, sind der Realteil des trig. Interpolationspolynoms und die Lösung der diskreten Fourier-Analyse verschieden:

$\begin{eqnarray*} Re\Bigl(T_4^*(x) \Bigr) =\frac{1}{2}\cdot (-\sin(x) + \sin(3x) ) \end{eqnarray*}$

$\begin{eqnarray*} t_4^{\mathbb R}(x)=-\sin(x) \end{eqnarray*}$

01.03.2007, 02:12

tigerbine

Auf diesen Beitrag antworten »

6. Fast Fourier Transformation
Sei $\begin{eqnarray*} T_N(x) = \sum_{j=-N}^{N}~c_j\cdot \exp(i\cdot jx) \end{eqnarray*}$ ein Fourierpolynom vom Grad N. Dieses soll an den N Stellen $\begin{eqnarray*} x_k=\frac{2\pi k}{N} \quad k=0,1,...,N-1 \end{eqnarray*}$ ausgewertet werden. Aus (3b) wissen wir, dass $\begin{eqnarray*} T_N \end{eqnarray*}$ dort dieselben Funktionswerte annimmt wie $\begin{eqnarray*} T_N^* \end{eqnarray*}$ , es gilt also: $\begin{eqnarray*} T_N(x_k)=T_N^{*}(x_k) \end{eqnarray*}$

03.07.2007, 01:57

tigerbine

Auf diesen Beitrag antworten »

6a. Berechnung der Koeffizieten d
$\begin{eqnarray*} T_N(x) = \sum_{j=-N}^{N}~c_j\cdot \exp(i\cdot jx) \end{eqnarray*}$

$\begin{eqnarray*} T_N^*(x)= \sum_{j=0}^{N-1}d_j\cdot \exp(i\cdot jx) \end{eqnarray*}$

Für die Umrechnung der Koeffizienten gilt:

$\begin{eqnarray*} d_0:=c_0 + (c_N + c_{-N}) = \frac{a_0}{2}+a_N \end{eqnarray*}$

$\begin{eqnarray*} d_j:=(c_j+c_{-(N-j)}) \end{eqnarray*}$

Es gilt:

$\begin{eqnarray*} T_N(x_k)=T_N^{*}(x_k) \end{eqnarray*}$

Man benötigt also für jedes x, neben den trig. Funktionen, genau 2N Multiplikationen. Für alle auszuwertenden Stellen also 2N².

03.07.2007, 02:06

tigerbine

Auf diesen Beitrag antworten »

6b. Gerades N = 2M
Mit dem Wissen über Einheitswurzel verifiziere man:

$\begin{eqnarray*} w_N^r = w_N^s \Leftrightarrow (r-s) = l\cdot N,~l \in \mathbb Z \end{eqnarray*}$

Sei nun $\begin{eqnarray*} N \end{eqnarray*}$ gerade. So kann man $\begin{eqnarray*} M:=\frac{1}{2}N \end{eqnarray*}$ definieren. Die Auszuwertenden Stellen $\begin{eqnarray*} x_k \end{eqnarray*}$ werden nun in gerade und ungerade unterteit.

Für gerades k = 2l

$\begin{eqnarray*} T_N^*(x_{2l}) = \sum_{j=0}^{N-1}d_j \cdot w_N^{j\cdot 2l} = \sum_{j=0}^{N-1}d_j \cdot w_M^{j\cdot l} =\sum_{j=0}^{M-1}d_j \cdot w_M^{j\cdot l}+\sum_{j=0}^{M-1}d_{M+j} \cdot w_M^{(M+j) \cdot l} = \end{eqnarray*}$

$\begin{eqnarray*} = \qquad \quad \sum_{j=0}^{M-1}d_j \cdot w_M^{j\cdot l} + \sum_{j=0}^{M-1}d_{M+j} \cdot w_M^{Ml+jl} = \sum_{j=0}^{M-1}d_j \cdot w_M^{j\cdot l} + \sum_{j=0}^{M-1}d_{M+j} \cdot w_M^{jl}= \end{eqnarray*}$
$\begin{eqnarray*} =\qquad \quad \sum_{j=0}^{M-1}(d_j+d_{M+j}) \cdot w_M^{j\cdot l} \end{eqnarray*}$

Für ungerades k=2l+1

$\begin{eqnarray*} T_N^*(x_{2l+1}) = \sum_{j=0}^{N-1}d_j \cdot w_N^{j\cdot(2l+1)} = \sum_{j=0}^{N-1}d_j \cdot w_N^{j\cdot 2l+j}=\sum_{j=0}^{N-1}d_j \cdot w_N^{j} \cdot w_N^{j\cdot 2l}= \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \quad \sum_{j=0}^{N-1}d_j \cdot w_N^{j} \cdot w_M^{j\cdot l}= \sum_{j=0}^{M-1}d_j \cdot w_N^{j} \cdot w_M^{j\cdot l}+\sum_{j=0}^{M-1}d_j \cdot w_N^{M+j} \cdot w_M^{(M+j)\cdot l} = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \quad = \sum_{j=0}^{M-1}d_j \cdot w_N^{j} \cdot w_M^{j\cdot l}+\sum_{j=0}^{M-1}d_j \cdot w_N^M\cdot w_N^j \cdot w_M^{Ml} \cdot w_M^{jl} = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \quad = \sum_{j=0}^{M-1}d_j \cdot w_N^{j} \cdot w_M^{j\cdot l}+\sum_{j=0}^{M-1}d_j \cdot (-1) \cdot w_N^j \cdot 1 \cdot w_M^{jl} = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \quad \sum_{j=0}^{M-1}d_j \cdot w_N^{j} \cdot w_M^{j\cdot l}-\sum_{j=0}^{M-1}d_j \cdot w_N^j \cdot w_M^{jl} = \end{eqnarray*}$

$\begin{eqnarray*} =\qquad \quad \sum_{j=0}^{M-1} \Bigl( (d_j-d_{M+j}) \cdot w_N^{j}\Bigr) \cdot w_M^{j\cdot l} \end{eqnarray*}$

Somit erhält man die neuen Koeffizienten:

$\begin{eqnarray*} d_j^{(1)}:=d_j+d_{M+j},\qquad j=0,...,M-1 \end{eqnarray*}$

$\begin{eqnarray*} d_{M+j}^{(1)}:=(d_j-d_{M+j})\cdot w_N^j,\qquad j=0,...,M-1 \end{eqnarray*}$

03.07.2007, 02:45

tigerbine

Auf diesen Beitrag antworten »

6c. N ist eine Zweierpotenz
Gilt nun $\begin{eqnarray*} N=2^n \end{eqnarray*}$ so läßt sich das Schema von 7b n-mal durchführen und man erhält am Ende die gesuchten Funktionswerte. Der Berechnungsaufwand liegt nun nur noch bei

$\begin{eqnarray*} M(3n-2)+1=\frac{1}{2}N[3\cdot \log_2(N) -2] +1 \end{eqnarray*}$

Rechenoperationen nötig.

03.07.2007, 02:46

tigerbine

Auf diesen Beitrag antworten »

6d. Beispielschema für n=8
An welcher Stelle dann die Funktionswerte stehen, soll am Beispiel von $\begin{eqnarray*} N=8=2³ \end{eqnarray*}$ verdeutlicht werden. Ist $\begin{eqnarray*} T_N \end{eqnarray*}$ mit den Koeffizeienten c gegeben, so berechnet man sich zunächst einmal $\begin{eqnarray*} T_N^{*} \end{eqnarray*}$ mit den Koeffizienten d. Dann schreibt man die $\begin{eqnarray*} d_j \end{eqnarray*}$ in eine Tabelle.

$\begin{eqnarray*} \begin{array} {|c||c|c|c|c||c|} \hline \text{j} & d_j & d_j^{(1)} & d_j^{(2)} &d_j^{(3)} & \text{k}\\ \hline \hline 0&d_0&d_0+d_4&d_0^{(1)}+d_2^{(1)}& d_0^{(2)} + d_1^{(2)}&0 \\ \hline 1&d_1&d_1+d_5&d_1^{(1)}+d_3^{(1)}& (d_0^{(2)} - d_1^{(2)})\cdot \omega_2^0&4\\ \hline 2&d_2&d_2+d_6&(d_0^{(1)}-d_2^{(1)}) \cdot \omega_4^0& d_2^{(2)} + d_3^{(2)}&2\\ \hline 3&d_3&d_3+d_7&(d_1^{(1)}-d_3^{(1)}) \cdot \omega_4^1& (d_2^{(2)} - d_3^{(2)})\cdot \omega_2^0&6 \\ \hline 4&d_4&(d_0-d_4)\cdot w_8^0&d_4^{(1)}+d_6^{(1)}&d_4^{(2)}+d_5^{(2)}&1 \\ \hline 5&d_5&(d_1-d_5)\cdot w_8^1&d_5^{(1)}+d_7^{(1)}&(d_4^{(1)}-d_5^{(1)})\cdot \omega_2^0& 5\\ \hline 6&d_6&(d_2-d_6)\cdot w_8^2&(d_4^{(1)}-d_6^{(1)})\cdot \omega_4^0&d_6^{(2)}+d_7^{(2)}&3 \\ \hline 7&d_7&(d_3-d_7)\cdot w_8^3&(d_5^{(1)}-d_7^{(1)})\cdot \omega_4^{1}&(d_6^{(2)}-d_7^{(2)})\cdot \omega_2^0&7\\ \hline \end{array} \end{eqnarray*}$

Wie kommt man von j nach k?

08.11.2008, 00:34

tigerbine

Auf diesen Beitrag antworten »

7. Umsetzungen im PC
Hier soll noch einmal auf die 3 Varianten (Approximation, trig. Interpolation, Diskrete Fourier Analyse) zurückgekommen werden. Die letzten beiden lassen sich ja noch recht einfach implementieren. Bei ersterem benötigt man zur Berechnung ger Koeffizienten Integrale. Dies wirft sogleich die Frage auf "Wie wird numerisch integriert"

[WS] Numerische Integration -Theorie
[WS] Extrapolation

Folgendes gilt es zu berechnen:

$\begin{eqnarray*} a_0=\frac{1}{\pi}~\int_{0}^{2\pi}~f(x)~dx \end{eqnarray*}$

$\begin{eqnarray*} a_j=\frac{1}{\pi}~\int_{0}^{2\pi}~f(x)\cos(jx)~dx \end{eqnarray*}$

$\begin{eqnarray*} b_j=\frac{1}{\pi}~\int_{0}^{2\pi}~f(x)\sin(jx)~dx \end{eqnarray*}$

Diese wollen wir nun nicht exakt berechnen, sondern Näherungen verwendet. Dabei kommt auch die in Punkt 6 kennengelernte FFT ins Spiel.

08.11.2008, 01:35

tigerbine

Auf diesen Beitrag antworten »

7a. Koeffizienten-Näherungen
Wir wollen die Koeffizienten durch die N-fach wiederholte Trapezregel approximieren.

Zitat:

$\begin{eqnarray*} I^T(g)=\frac{h}{2} \Bigl\{g(a) +2\cdot \sum_{k=1}^{N-1}~g(a+k\cdot h)+g(b) \Bigr\} \end{eqnarray*}$

Dabei gilt für die Koeffizienten $\begin{eqnarray*} \hat{a}_j \end{eqnarray*}$ :

$\begin{eqnarray*} a=0,~b=2\pi \end{eqnarray*}$
$\begin{eqnarray*} g(x)=f(x)\cos(jx) \end{eqnarray*}$
$\begin{eqnarray*} g(0)=g(2\pi) \end{eqnarray*}$
$\begin{eqnarray*} h=\frac{2\pi}{N} \end{eqnarray*}$

Somit folgt

$\begin{eqnarray*} I^T(g) &&=\frac{\frac{2\pi}{N}}{2} \Bigl\{g(0) +2\cdot \sum_{k=1}^{N-1}~g(0+k \cdot \frac{2\pi}{N})+g(2\pi) \Bigr\} \\&&=\frac{2\pi}{N} \cdot \sum_{k=0}^{N-1}~g(k \cdot \frac{2\pi}{N}) \\&& = \pi \cdot \frac{2}{N}\cdot \sum_{k=0}^{N-1}~f(k \cdot \frac{2\pi}{N})\cos(j\cdot k \cdot \frac{2\pi}{N}) \end{eqnarray*}$

Und für die Koeffizienten folgt:

$\begin{eqnarray*} \hat{a}_j= \frac{2}{N}\cdot \sum_{k=0}^{N-1}~f(k \cdot \frac{2\pi}{N})\cos(j \cdot k \cdot \frac{2\pi}{N}) \end{eqnarray*}$

Analog zeigt man

$\begin{eqnarray*} \hat{b}_j= \frac{2}{N}\cdot \sum_{k=0}^{N-1}~f(k \cdot \frac{2\pi}{N})\sin(j \cdot k \cdot \frac{2\pi}{N}) \end{eqnarray*}$

08.11.2008, 01:36

tigerbine

Auf diesen Beitrag antworten »

7b. "Alte Bekannte"
Schauen wir uns die Näherungen noch einmal an. Dann sollte man erkennen, dass dies gerade die Koeffizienten der reellen trig. Interpolationsaufgabe (Diskrete Fourier Analyse) sind.

Für unsere Vergleichsaufgabe ergibt sich dann mit N=4:

$\begin{eqnarray*} \hat{a}_0= \hat{a}_1 =\hat{a}_2 =\hat{a}_3 = 0 \end{eqnarray*}$

$\begin{eqnarray*} \hat{b}_0 &&= \frac{1}{2}\cdot \sum_{k=0}^{3}~f(k \cdot \frac{2\pi}{4})\sin(0 \cdot k \cdot \frac{2\pi}{4}) \\ && = \frac{1}{2}\cdot (0 \cdot \sin(0) - 1 \cdot \sin(0) + 0 \cdot \sin(0) + 1 \cdot \sin(0)) \\ && = 0 ~[\triangle = 0] \end{eqnarray*}$

$\begin{eqnarray*} \hat{b}_1 &&= \frac{1}{2}\cdot \sum_{k=0}^{3}~f(k \cdot \frac{2\pi}{4})\sin(1 \cdot k \cdot \frac{2\pi}{4}) \\ && = \frac{1}{2}\cdot (0 \cdot \sin(0) - 1 \cdot \sin(0.5\pi) + 0\cdot \sin(\pi) + 1 \cdot \sin(1.5\pi)) \\ && = -1 ~[\triangle \approx 0.27] \end{eqnarray*}$

$\begin{eqnarray*} \hat{b}_2 &&= \frac{1}{2}\cdot \sum_{k=0}^{3}~f(k \cdot \frac{2\pi}{4})\sin(2 \cdot k \cdot \frac{2\pi}{4}) \\ && = \frac{1}{2}\cdot (0 \cdot \sin(0) - 1 \cdot \sin(\pi) + 0 \cdot \sin(2\pi) + 1 \cdot \sin(3\pi)) \\ && =0 ~ [\triangle = 0] \end{eqnarray*}$

$\begin{eqnarray*} \hat{b}_3 &&= \frac{1}{2}\cdot \sum_{k=0}^{3}~f(k \cdot \frac{2\pi}{4})\sin(3 \cdot k \cdot \frac{2\pi}{4}) \\ && = \frac{1}{2}\cdot (0 \cdot \sin(0) - 1 \cdot \sin(1.5\pi) + 0\cdot \sin(3\pi) + 1 \cdot \sin(4.5\pi)) \\ && = 1 ~[\triangle \approx 1.42] \end{eqnarray*}$

Das ist noch nicht gerade eine berauschende Genauigkeit. Ist der Ansatz daher falsch? Nein, denn würde man die Aufgabe aus dem Blickwinkel der num. Integration sehen, wäre es schon eher "verwunderlich", wenn man bei so kleinem N (2²) schon "dicht" dran liegen würde. Werfen wir einen Blick in die Fehlerabschätzung der summierten Trapezregel und das umformulierte Integral, so dass wir direkt die Ableitung der zu integrierenden Funktion bilden können':

Zitat:

$\begin{eqnarray*} |I(f)-I^T(f)|\leq \frac{(b-a)}{12}\cdot h^2 \cdot \max_{x \in[a,b]}~|f^{(2)}(x)| \end{eqnarray*}$

$\begin{eqnarray*} b_j=-\frac{2}{\pi}\int_{0}^{\pi}\sin(jx)~dx =\begin{cases} -\frac{4}{j\pi} & \text{für j ungerade} \\ 0 & \text{für j gerade} \end{cases} \end{eqnarray*}$

Damit ergibt sich dann für N:

$\begin{eqnarray*} |I(f_j)-I^T(f_j)| && \leq \frac{2\pi-0}{12}\cdot (\frac{2\pi}{N})^2 \cdot \max_{x \in[0,\pi]}~|j^2\cdot \sin(jx)| \end{eqnarray*}$

Die Periodenlänge des Sinus verkleinert sich, daher folgt:

$\begin{eqnarray*} |I(f_j)-I^T(f_j)| && \leq \frac{8\pi^3}{12}\cdot \frac{1}{N^2} \cdot j^2 \end{eqnarray*}$

Welche maximale Genauigkeit können wir so erreichen?

$\begin{eqnarray*} \frac{8\pi^3}{12}\cdot \frac{1}{N^2} \cdot j^2< \varepsilon \end{eqnarray*}$

Das größte j ist j=N-1, daher:

$\begin{eqnarray*} \frac{8\pi^3}{12}\cdot \frac{1}{N^2} \cdot (N-1)^2< \varepsilon \end{eqnarray*}$

$\begin{eqnarray*} \frac{2\pi^3}{3}\cdot (\frac{N-1}{N})^2< \varepsilon \end{eqnarray*}$

Unabhängig von N erhalten wir damit die Abschätzung:

$\begin{eqnarray*} \frac{2\pi^3}{3}\cdot (1)^2< \varepsilon \end{eqnarray*}$

$\begin{eqnarray*} \frac{2\pi^3}{3}< \varepsilon \end{eqnarray*}$

$\begin{eqnarray*} 20.67< \varepsilon \end{eqnarray*}$

Nun wählen wir die Knoten unabhängig vom Grad des FourierPolyoms.

$\begin{eqnarray*} \frac{2\pi^3}{3}\cdot \frac{1}{\hat{N}^2} \cdot (N-1)^2< \varepsilon \end{eqnarray*}$

Ist nun eine gewünschte Genauigkeit vorgegeben, so erhlät man:

$\begin{eqnarray*} \frac{2\pi^3}{3}\cdot \frac{1}{\varepsilon} \cdot (N-1)^2< \hat{N}^2 \end{eqnarray*}$

Beispiel für N=4:

$\begin{eqnarray*} \frac{2\pi^3}{3}\cdot \frac{1}{0.01} \cdot 3^2< \hat{N}^2 \end{eqnarray*}$

$\begin{eqnarray*} 136< \hat{N} \end{eqnarray*}$

Die tatsächlich benötige Zahl N wird wohl darunter liegen, da wir den Fehler nur abgeschätzt haben. Dies liegt daran, dass man das $\begin{eqnarray*} \xi \end{eqnarray*}$ in der exakten Fehlerdarstellung (vgl. einfache Trapezregel) im Allgemeinen nicht kennen.

08.11.2008, 02:31

tigerbine

Auf diesen Beitrag antworten »

7c. Effiziente Berechnung
Wählt wir nun N als Zweierpotenz, so kann man die FFT zur Berechnung der approximierten Koeffizienten verwenden.

[Artikel] Schnelle Fourier Transformation (FFT)

17.03.2014, 16:29

Steffen Bühler

Auf diesen Beitrag antworten »

8. Eine einfache Erklärung der Fouriertransformation

Man kann sich die Fouriertransformation wie ein Filter vorstellen, das nur eine einzige Frequenz aus einem Gemisch rausholt.

Nehmen wir mal so ein wirres Signalgemisch:

8a. Filterung der Sinusanteile

Jetzt lassen wir Fourier drauf los. Der sagt ja: "multipliziere das Signal erst einmal mit einem Sinus der Frequenz, an der Du interessiert bist".

Zuerst mal mit sin(x), also Frequenz 1:

Dann mit sin(2x):

Jetzt mit sin(3x):

Bei der Frequenz 3 ist der Mittelwert hochgegangen, bei den anderen beiden Frequenzen unten geblieben. Den genauen Mittelwert kann man ausrechnen, indem man die Flächen über und unter der x-Achse zusammenzählt (über der x-Achse positiv, sonst negativ) und durch die Länge der x-Achse dividiert. Wenn man das tut, ergibt sich bei den beiden ersten Frequenzen exakt Null (die Flächen gleichen sich aus), bei der Frequenz 3 dagegen der Wert 0,5. Fourier sagt nun, dass dieser Wert, wenn man ihn verdoppelt, genau die Amplitude des Sinus der Frequenz 3 ist, der in dem Gemisch versteckt ist.

25.06.2014, 08:21

Steffen Bühler

Auf diesen Beitrag antworten »

8b. Filterung der Cosinusanteile

So kann man nun für jeden Sinus, der in dem Gemisch enthalten ist, die Amplitude herausfinden. Ein Cosinus dagegen wird auf diese Weise nicht gefunden! Wenn wir die sin(3x)-Komponente des Gemischs durch eine cos(3x)-Komponente ersetzen, sieht das Signal zwar ähnlich aus:

Multipliziert man das nun mit sin(3x), bleibt der Mittelwert unten!

Erst wenn man mit cos(3x) multipliziert, ergibt sich ein positiver Mittelwert:

Das ist der Grund, warum man Sinus- und Cosinusglieder getrennt voneinander untersuchen muss.

25.06.2014, 08:26

Steffen Bühler

Auf diesen Beitrag antworten »

8c. Filterung eines phasenverschobenen Sinus

So eine Zerlegung in Sinus- und Cosinusanteile bedeutet aber auch, dass Sinusfunktionen mit beliebiger Phasenverschiebung untersucht werden können! Denn nach den Additionstheoremen gilt $\begin{eqnarray*} \sin (a+b)=\sin a \cos b + \cos a \sin b \end{eqnarray*}$ .

Nehmen wir also zum Beispiel einen um 18° verschobenen Sinus:

$\begin{eqnarray*} f(x)= \sin (x + 18 ^{\circ}) = \sin\left (x + \frac {\pi} {10} \right) \end{eqnarray*}$

Den kann man nach obiger Formel in einen reinen Sinus- und einen reinen Cosinusanteil zerlegen:

$\begin{eqnarray*} \sin\left (x + \frac {\pi} {10} \right) = \sin (x) \cos \left (\frac {\pi} {10} \right) + \cos (x) \sin \left (\frac {\pi} {10} \right) \approx 0,951 \cdot \sin(x) + 0,309 \cdot \cos (x) \end{eqnarray*}$

Bei der Fouriertransformation sollte also für diesen phasenverschobenen Sinus ein Sinusanteil mit Amplitude 0,951 und ein Cosinusanteil Amplitude 0,309 herauskommen, wobei die Amplitude des Sinusanteil etwa dreimal so hoch sein sollte. Probieren wir's aus:

Mulitplikation mit sin(x):

Mulitplikation mit cos(x):

In der Tat ist der Mittelwert (der Wert, um den die Schwingungen "pendeln") der Sinusmultiplikation bei etwas weniger als 0,5 und die der Cosinusmultiplikation bei ungefähr 0,15. Und das entspricht ja der jeweiligen erwarteten halben Amplitude.

12 nächste Seite »

Neue Frage »

Antworten »

[WS] Trigonometrische Interpolation

Verwandte Themen