[Artikel] Schnelle Fourier Transformation (FFT) |
17.11.2008, 13:21 | tigerbine | Auf diesen Beitrag antworten » | |||||
[Artikel] Schnelle Fourier Transformation (FFT) Wer den Artikel um eigene Beispiele ergänzen möchte, schreibt diese bitte im Numerik-Forum und informiert mich per PN, diese hier anzuhängen.
|
|||||||
17.11.2008, 14:12 | tigerbine | Auf diesen Beitrag antworten » | |||||
1. Multiplikation von Polynomen Gegeben seien die beiden Polynome . Gesucht ist das Produkt : Beispiel (n=4): Es ist hierbei nicht nötig, dass beide den Polynome den gleichen Maximalgrad haben, solange sie in liegen (man würde mit Nullen als Koeffizient auffüllen). Mit dem Distributivgesetzt und einem Aufwand von 4² Rechenoperationen könnte man nun die Lösung berechnen und erhält: Wir wollen uns nun überlegen, wie man mit weniger Aufwand das gleiche Ziel erreichen kann. r ist nun ein Polynom vom Maximalgrad 6, also Element eines 7-dimensionalen VR. Wir stocken nun (mit Nullen) die Dimension soweit auf, dass wir eine Zweierpotenz erhalten. Bzgl. der Monom Basis des haben die Polynome p und q die Koordinatenvektoren (aufsteigende Potenz von x): |
|||||||
17.11.2008, 15:24 | tigerbine | Auf diesen Beitrag antworten » | |||||
1a. Die Diskrete Fourier Transformation -Teil 1
|
|||||||
17.11.2008, 16:56 | tigerbine | Auf diesen Beitrag antworten » | |||||
1b. Die Diskrete Fourier Transformation -Teil 2
Analyse
|
|||||||
17.11.2008, 17:55 | tigerbine | Auf diesen Beitrag antworten » | |||||
1c. Schnelle Fourier Transformation In Bezug auf [Workshop - Trigonometrische Interpolation] sind uns hier also die Koeffizienten d bereits gegeben und anstelle des Matrix-Vektorprodukts kann wie im Workshop die FFT durchgeführt werden. Für die ersten beiden Umrechnung ergibt sich also ein Aufwand in der Größenordnung von Um nun wieder den gleichen Vektor wie nach der diskreten Fourier Transformation zu erhalten, müssen wir die ursprüngliche Reihenfolge der Einträge wieder herstellen. Dazu verwendet man die Bitumkehr. |
|||||||
19.11.2008, 16:59 | tigerbine | Auf diesen Beitrag antworten » | |||||
1d. Inverse Schnelle Fourier Transformation FFT: Berechnung der Funktionswerte zu gegebenen Koeffizienten d. IFFT: Berechnung der Koeffizienten zu gegebenen Funktionswerten. Für gerades k = 2l Für ungerades k=2l+1 Am Ende der IFFT muss noch mit multipliziert werden. |
|||||||
Anzeige | |||||||
|
|||||||
20.11.2008, 23:11 | tigerbine | Auf diesen Beitrag antworten » | |||||
1e. Das Kleingedruckte Je nach Literatur werden unterschiedlich motivierte Zugänge zu dem Verfahren gewählt. So kann es sein, dass bei manchen das Polynom betrachtet wird. Zum Beispiel in matlab. Achtung, es kann auch mal j für den Imaginäreteil verwendet werden!
|
|||||||
20.11.2008, 23:44 | tigerbine | Auf diesen Beitrag antworten » | |||||
2. Auswerten von trig. Polynomen Wie das geht kann man im [Workshop - Trigonometrische Interpolation] nachlesen, wo auch die Formel der FFT erläutert wird. In Bezug auf Teil 1 dieses Artikels ist wieder ein Vektor mit der Fouriermatrix zu multiplizieren. Nur stehen dessen Einträge nun für die Koeffizienten d des Polynoms |
|||||||
20.11.2008, 23:47 | tigerbine | Auf diesen Beitrag antworten » | |||||
3. Trigonometrische Interpolations Aufgabe Hier sind nun die Funktionswerte an den äquidistanten Stützstellen gegeben und gesucht sind die Koeffizienten d. Mit Punkt 1 wissen wir, dass eine Möglichkeit zur Berechnung die folgende wäre. Dabei bezeichne y die Funktionswerte. Oder eben im Falle einer Zweierpotenz die Inverse Schnelle Fourier Transformation. Da haben wir auch schon eine Formel notiert: Die Koeffizienten können auch hier mit der FFT berechnet werden, es sind lediglich negative Einheitswurzeln zu verwenden und am Ende durch 1/N zu dividieren. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|