TU Wien:Analysis 2 UE (diverse)/Übungen SS23/Beispiel 199

Aus VoWi
Zur Navigation springen Zur Suche springen

Wie verläuft die Multiplikation der Polynome und mit Hilfe der Diskreten Fourier-Transformation? (Anleitung: Man repräsentiere und durch Vektoren in und berechne deren Faltung mittels Diskreter Fourier-Transformation mit N = 4.)

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:
{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}


Eine Polynommultiplikation entspricht einer Faltung. Eine Faltung wird im Spektralbereich durch komponentweises multiplizieren der Fourier-Koeffizienten durchgeführt.

Vorteil: Mittels Fast Fourier Transform (FFT) kann die Polynommultiplikation somit in durchgeführt werden, anstatt . Für uns in der händischen Durchführung ist natürlich nichts von einem Vorteil zu merken, im Gegenteil ;)

Fourier-Matrix für die IDFT, und Inverse für die DFT:

Die Polynome als Vektoren ()

Die Polynome im Frequenzraum durch DFT (Multiplikation mit inverser Fourier-Matrix)

Wir führen die Polynommultiplikation durch einfache Multiplikation der Fourierkoeffizienten durch

Rückführen in den Zeitbereich durch IDFT (Multiplikation mit Fourier-Matrix)

Darstellung des Ergebnisvektors als Polynom

Überprüfung: KORREKT

Wir haben also das selbe Ergebnis der Polynommultiplikation (Faltung) durch einfache Multiplikation der Fourierkoeffizienten erzielt. Wie oben erwähnt ist dies bei größeren Polynomen und bei automatischer Ausführung mittels FFT (anstatt händisch) unter Umständen effizienter!

Links[Bearbeiten | Quelltext bearbeiten]

  • Diskussion im Forum [1]