Die Fast-Fourier-Transformation FFT
Trigonometrische Interpolation

• Die Fast-Fourier-Transformation ist eine spezielle Form der trigonometrischen Interpolation. Im allgemeinen Fall beliebig verteilter Stützstellen läuft diese Aufgabe auf die Lösung eines linearen Gleichungssystems hinaus. Bei gleichabständigen Stützstellen kann man dies vermeiden und benötigt nur noch O(n²) Rechenoperationen, wobei wie üblich n+1 die Stützstellenanzahl ist. Für weiter eingeschränktes n kann dieser Aufwand auf O(n*ln(n)) reduziert werden, was die Anwendung der Methode etwa in der Signalanalyse überhaupt erst möglich macht, wo n oft im Bereich 10⁵ liegt. Hier benutzen wir eine Software, die von n+1 eine Primfaktordarstellung mit den Faktoren 2,3 und 5 erfordert. Die Rechnung läuft über den Zusammenhang
  cos(phi)+I*sin(phi)= exp(I*phi)
  mit der komplexen Einheit I. Das trigonometrische Polynom
  p(x) = a₀ + summe(i=1,m) { a_i cos(i*x) + b_isin(i*x) } {+a_m+1cos((m+1)*x)}
  wird in ein komplexes Polynom umgewandelt.
• Mit diesem komplexen Polynom ist die Berechnung von Koeffizienten a_i und b_i des interpolierenden trigonometrischen Polynoms zu den gegebenen Datenpunkten sehr vereinfacht, man rechnet zum Schluß von der komplexen auf die reelle Form zurück.
• Dabei richtet sich die Anzahl der verwendeten Koeffizienten nach der Menge der Datenpunkte, also n+1=2m+1 oder n+1=2m+2.
• Hier ist ein numerisches Experiment vorbereitet: Ein trigonometrisches Polynom mit m<=7 wird von Ihnen vorgegeben und an n+1 gleichabständigen Stützstellen ausgewertet. Die errechneten Werte werden dann mit Zufallszahlen überlagert und diese geänderten Werte werden trigonometrisch interpoliert. Man erhält dann die ursprünglich eingesetzten Koeffizienten gestört zurück und zusätzlich viele höher frequente Anteile mit kleinen Amplituden, ein gestörtes Signal. Um das ungestörte Signal zu rekonstruieren benutzen wir einen Filter: hier eine Abschneidefunktion, die sich an den Amplituden (also den Beträgen der Koeffizienten) orientiert. Das Endresultat ist dann eine bei richtiger Einstellung des Filters das Originalsignal, geringfügig phasen- und amplitudenverschoben.
• Alternativ haben Sie die Möglichkeit, einen eigenen Datensatz einzugeben und durch ein trigonometrisches Polynom interpolieren zu lassen, das Ihnen dann graphisch und als Formeltext angezeigt wird.

Die Eingaben für das Filterexperiment

• Angegeben wird der "Grad" m des Originalpolynoms. Wichtig : 1 <= m <= 7 !
• Die Anzahl n+1 der Abtastpunkte des Originalpolynoms. Wichtig : 2m+1 <= n+1 <= 2000, n+1=(2^i)*(3^j)*(5^k) !
• Die Koeffizienten des Originalpolynoms, einzugeben in der Reihenfolge a₀,a₁,b₁,a₂,b₂,...a_m,b_m.
• Der Fehlerlevel in Prozent, bezogen auf den betragsmässig größten wahren Funktionswert und
• Der Filterwert "droplevel" in Prozent. Es werden dann alle berechneten Koeffizienten mit einem Betrag unterhalb von max*droplevel/100 gleich 0 gesetzt. Dabei ist max der maximale Betrag der Eingabekoeffizienten.

Die Ausgaben

• Ausgegeben wird ein Ergebnisprotokoll, das die berechneten Koeffizienten zu den Originaldaten, den verrauschten Daten und die Koeffizienten zu den verrauschten Daten nach dem Filtern angibt.
• Die ausgegebene Grafik zeigt:
  1. Die erzeugten Auswertungen der Originalfunktion.
  2. Die kontinuierliche Originalfunktion.
  3. Die gestörten Daten.
  4. Die berechnete kontinuierliche Funktion zu den gestörten Daten.
  5. Die kontinuierliche Funktion zu den gefilterten Daten.

Fragen ?!

• Wie ist "Droplevel" zu wählen, um die Originalfunktion möglichst gut wiederherzustellen aus den gestörten Daten ?

Zum Filterexperiment

Die Eingaben für die Interpolation

• Die Anzahl n+1 Ihrer Datenpunkte. Achtung: das Verfahren 'denkt sich' einen weiteren Wert (für die periodische Fortsetzung bei x+(n+1)*dx) hinzu, diesen geben Sie nicht selbst ein.
• Den Anfangswert für x und die Schrittweite dx. Diese benötigt man nur für die Korrektheit der Auswertungsformel.
• Den Datensatz (nur die y-Werte).

Die Ausgaben für die Interpolation

• Eine Grafik mit dem Datensatz und der Interpolierenden.
• Eine Formeldarstellung der Interpolierenden

Zum Interpolieren eigener Daten

Zurück: Interpolation