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

Wie verläuft die Multiplikation der Polynome $p(x)=4-4x$ und $q(x)=6+2x$ mit Hilfe der Diskreten Fourier-Transformation? (Anleitung: Man repräsentiere $p(x)$ und $q(x)$ durch Vektoren in $\mathbb {C} ^{4}$ 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 ${\mathcal {O}}(N\log N)$ durchgeführt werden, anstatt ${\mathcal {O}}(n^{2})$. 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:

$F_{4}={\begin{pmatrix}1&1&1&1\\1&e^{-{\frac {\pi }{2}}i}&e^{-\pi i}&e^{-{\frac {3\pi }{2}}i}\\1&e^{-\pi i}&e^{-2\pi i}&e^{-3\pi i}\\1&e^{-{\frac {3\pi }{2}}i}&e^{-3\pi i}&e^{-{\frac {9\pi }{2}}i}\end{pmatrix}}={\begin{pmatrix}1&1&1&1\\1&-i&-1&i\\1&-1&1&-1\\1&i&-1&-i\\\end{pmatrix}},\quad F_{4}^{-1}={\tfrac {1}{4}}{\overline {F_{4}}}={\frac {1}{4}}{\begin{pmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\\\end{pmatrix}}$

Die Polynome als Vektoren ($a\cdot x^{0}+b\cdot x^{1}+c\cdot x^{2}+d\cdot x^{3}\rightarrow (a,b,c,d)^{T}$)

${\vec {p}}={\begin{pmatrix}4\\-4\\0\\0\end{pmatrix}},\quad {\vec {q}}={\begin{pmatrix}6\\2\\0\\0\end{pmatrix}}$

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

${\vec {c}}_{p}={\tfrac {1}{4}}{\overline {F_{4}}}{\vec {p}}={\begin{pmatrix}0\\1+i\\2\\1-i\end{pmatrix}},\quad {\vec {c}}_{q}={\tfrac {1}{4}}{\overline {F_{4}}}{\vec {q}}={\begin{pmatrix}2\\{\tfrac {3}{2}}-{\tfrac {1}{2}}i\\1\\{\tfrac {3}{2}}+{\tfrac {1}{2}}i\end{pmatrix}}$

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

${\vec {c_{pq}}}={\vec {c}}_{p}\cdot {\vec {c}}_{q}={\begin{pmatrix}0\cdot 2\\(1+i)\cdot ({\tfrac {3}{2}}-{\tfrac {1}{2}}i)\\2\cdot 1\\(1-i)\cdot ({\tfrac {3}{2}}+{\tfrac {1}{2}}i)\end{pmatrix}}={\begin{pmatrix}0\\2+i\\2\\2-i\end{pmatrix}}$

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

${\vec {y_{pq}}}=4\cdot F_{4}\cdot {\vec {c_{pq}}}=4\cdot {\begin{pmatrix}6\\-4\\-2\\0\end{pmatrix}}={\begin{pmatrix}24\\-16\\-8\\0\end{pmatrix}}$

Darstellung des Ergebnisvektors als Polynom

$pq=24-16x-8x^{2}$

Überprüfung: $p(x)q(x)=(4-4x)(6+2x)=24-24x+8x-8x^{2}=24-16x-8x^{2}$ 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

• Diskussion im Forum [1]