2.2 Fouriertransformation (S. 13)

• Entspricht: Trigonometrische Interpolation (s.a. Stoer I, S.78)
• Verwendung: Interpolation periodischer Funktionen
• Idee: $\sin(x), \cos(x)$ spannen eine vollständige Orthonormalbasis für einen Vektorraum auf. Alle Funktionen sollten sich in dieser Basis entwickeln lassen. (Beweise für Basis etc. s. Stoer I) Man kann zeigen, daß es genau ein Interpolationspolynom gibt, das durch alle Stützstellen geht.
• Ansatz:
  • Gegeben seien N Stützpunkte $(x_k, f_k), k=0\cdots N-1$
  • o.B.d.A. nach Größe geordnet, d.h. $0 \leq x_0 < x_1 < \cdots < x_{N-1} < 2\pi$
  • Entwicklung in $\sin()$ und $\cos()$:
    

    $$\psi(x) = {A_0 \over 2} + \sum_{h=1}^M (A_h \cos(hx) + B_h \sin(hx))$$ (2.15)

    $$\mbox{f\uml {u}r $N=2M+1$\ ungerade}$$

    $$\psi(x) = {A_0 \over 2} + \sum_{h=1}^{M-1} (A_h \cos(hx) + B_h \sin(hx)) + {A_M \over 2} \cos(Mx)$$ (2.16)

    $$\mbox{f\uml {u}r $N=2M$\ gerade}$$

    $$\mbox{beide Formen sind \uml {a}quivalent zu}$$

    $$p(x) = \beta_0 + \beta_1 e^{ix} + \beta_2 e^{2ix}+ \cdots \beta_{N-1} e^{(N-1) ix}$$ (2.17)

    
    
    (übergang zwischen beiden Formen mit Moivrescher Formel)
  • Zu bestimmen ist p(x) so, daß $p(x_k) = f_k \forall k$
  • Koeffizienten des komplexen Polynoms:
    

    $$\beta_j = {1 \over N} \sum_{k=0}^{N-1} f_k \omega_k^{-j} = {1 \over N} \sum_{k=0}^{N-1} f_k e^{-2\pi i {j k \over N}}$$ (2.18)

    
    
    Beweis:

    Es sei: $\omega^j = e^{j i x}$, d.h. an den Stützstellen x_k ist $\omega_k^j = e^{j i x_k}$. Damit kann man das Interpolationspolynom schreiben als:
    

    $$p(\omega) = \beta_0 + \beta_1 \omega + \cdots + \beta_{N-1... ... \sum_{j=0}^{N-1} \beta_j \omega^j \equiv f_k \vert _{x=x_k}$$ (2.19)

    
    
    Damit ergibt sich:
    

    $$\sum_{k=0}^{N-1} f_k \omega_k^{-j} =$$

    $$= \beta_0 {(\omega_0)^0 \over (\omega_0)^0} + \beta_1 {(\omega_1)^1 ... ...cdots \beta_{N-1} {(\omega_{N-1})^{N-1} \over (\omega_{N-1})^{N-1}} = N \beta_j$$ (2.20)

    $$\folgt \beta_j = {1 \over N} \sum_{k=0}^{N-1} f_k e^{-2\pi i {j k \over N}}$$ (2.21)

    $$\Box$$

    
    
    Die Abbildung von f auf $\beta$ heißt diskrete Fouriertransformation
  • Minimaleigenschaft der Abschnittspolynome: Von allen möglichen trigonometrischen Polynomen $q(x) = \gamma_0 + \gamma_1 e^{ix} + \cdots + \gamma_s e^{i sx}, s \leq N-1$ minimiert das Fourierpolynom $p_s(x) = \beta_0 + \beta_1 e^{ix} + \cdots + \beta_s e^{i sx}$ die Fehlerquadratsumme:
    

    $$S(q) = \sum_{k=0}^{N-1} \left\vert f_k - q(x_k)\right\vert^2$$ (2.22)

    
    
    Insbesondere ist S(p) = 0. Dadurch sind die Abschnittspolynome eindeutig bestimmt. (Beweis: Stoer I, S.83)
  • Für die Koeffizienten der trigonometrischen Polynome gilt:
    

    $$A_h = \beta_h + \beta_{N-h}$$ (2.23)

    $$B_h = i(\beta_h - \beta_{N-h})$$ (2.24)

    
    
    Dies gilt allgemein im komplexen.

    Beachte: Für reelle Stützordinaten f_k sind die Koeffizienten reell.

• Beachte: Hohe Frequenzen ergeben oft eine schlechte Näherung. Aber man kann hohe Frequenzen in niedrige negative umwandeln, wenn man beachtet, daß $\beta_s = \beta_{s-N}$ ist.