Polynommultiplikation mit FFT < Analysis < Hochschule < Mathe < Vorhilfe
|
So, hi leute
ich habe ein paar verständnissfragen zur polynommultiplikation mittels fft
betrachte auch folgende links:
http://www.iti.fh-flensburg.de/lang/algorithmen/fft/fft.htm
http://www.iti.fh-flensburg.de/lang/algorithmen/fft/polyausw.htm
Die Arbeitsweise :
1. Umwandeln des Polynoms von Koeffizentendarstellung in Stützstellendarstellung
2. Multiplizieren der einzelnen stützstellen
3. Umwandeln der neuen stützstellendarstellung in Koeffizentendarstellung
so, das hauptproblem ist bei mir in schritt 1. !
Hier mal eine kleine situationsbeschreibung ...
I Die DiskreteFourierMatrix stellt ja den hauptvorteil dar, aber genau dazu habe ich ein paar fragen, das die DFM eine länge und breite von [mm] 2^n [/mm] haben muss ist mir bewusst, aber darum geht es nicht, viel mehr interressiert mich die sache mit den k-ten einheitswurzeln, die k-ten einheitswurzeln haben ja die eigenschaft das [mm] x^k [/mm] = 1 ergibt,
FRAGE 1 : Wirkt sich diese eigenschaft schon vorteilhaft auf die Polynommultiplikation aus ?
FRAGE 2: Die multiplikation der Koeffizenten der koeffizentendarstellung des polynoms mit der DFM ergibt die y werte an den komplexen einheitswurzel stützstellen ?!??!?!
FRAGE 3: Diese Stützstellen, wenn ich den richtig vermute das sie es sind, liegen alle auf dem einheitskreis der komplexen zahlenebene ?
so, das sollte es erst einmal gewesen sein, es geht mir nicht um die gesamte polynommultiplikation, sondern vielmehr um das verständniss der Diskreten Fourier Transformation, kann mir jemand beschreiben wieso selbige genau so gebildet wird wie sie wird, und noch einmal kurz nen wink geben wieso bei multiplikation mit den koeffizenten gerade der funktionswert an diesen stellen herauskommt ?
DANKE für ihre mühe !
p.s.: ich habe diese frage nirjendzwo anders jestellt
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:58 Mi 07.09.2005 | | Autor: | Toellner |
Hallo Ehrlich,
mich intressiert das Thema, ich müsste mich aber noch ein bisschen reinfuchsen. Hast Du noch ne Woche ca. Zeit für die Antwort?
Schneller gehts bei mir leider nicht...
Grüße Richard
|
|
|
| |
|
jau, kein problem, ich benoetige das fuer ne pruefung ende september ... ;)
|
|
|
| |
|
Hallo Ehrlich, da bin ich wieder...
Das Verfahren ist wirklich genial!
> Die Arbeitsweise :
>
> 1. Umwandeln des Polynoms von Koeffizentendarstellung in
> Stützstellendarstellung
> 2. Multiplizieren der einzelnen stützstellen
> 3. Umwandeln der neuen stützstellendarstellung in
> Koeffizentendarstellung
>
> so, das hauptproblem ist bei mir in schritt 1. !
>
>
> Hier mal eine kleine situationsbeschreibung ...
(der wurde Text von mir leicht verändert, bitte beachten!)
> I Die DiskreteFourierMatrix stellt ja den hauptvorteil dar,
> aber genau dazu habe ich ein paar fragen, das die DFM eine
> länge und breite von [mm]n=2^m[/mm] haben muss ist mir bewusst, aber
> darum geht es nicht, viel mehr interressiert mich die sache
> mit den k-ten einheitswurzeln, die k-ten einheitswurzeln
> haben ja die eigenschaft das [mm]w^k[/mm] = 1 ergibt,
> FRAGE 1 : Wirkt sich diese eigenschaft schon vorteilhaft
> auf die Polynommultiplikation aus ?
Ja, das ist der Schlüssel:
Du brauchst n Stützstellen [mm] x_{1}, x_{2}, [/mm] ... [mm] x_{n} [/mm] aus [mm] \IR [/mm] oder [mm] \IC [/mm] als Argumente für Dein Polynom und bastelst daraus die Transformationsmatrix T mit den Spalten [mm] \vektor{x_{i}^{0}\\x_{i}^{1}\\...\\x_{i}^{n-1}} [/mm] für i = 1 bis n, d.h., Du brauchst dazu schon n² Multiplikationen und gewinnst keine Rechenzeit.
Wenn Du aber als Stützstellen die n Einheitswurzeln [mm] w^{0}, w^{1}, [/mm] ... [mm] w^{n-1} [/mm] nimmst, dann hast Du eine geschlossene multiplikative Gruppe, jede Spalte von T entsteht durch eine Permutation der Wurzeln, das sind max. n Multiplikationen (und da kann man noch sparen), und T heißt jetzt DFM und ist symmetrisch (gut für die Berechnung von [mm] DFM^{-1}).
[/mm]
> FRAGE 2: Die multiplikation der Koeffizenten der koeffizentendarstellung
> des polynoms mit der DFM ergibt die y werte an den komplexen einheitswurzel
> stützstellen ?!??!?!
Genau. Du machst aus den Koeffizienten [mm] a_{i} [/mm] einen Zeilenvektor und wenn Du ihn von links mit T (bzw. mit DFT) multiplizierst (Matritzenmultipl.: in den Spalten stehen die zugehörigen Potenzen von [mm] x_{i}) [/mm] dann erhältst Du wieder einen Zeilenvektor, bei dem an der i. Stelle der Funktionswert des Polynoms [mm] p(a_{i}) [/mm] steht.
> FRAGE 3: Diese Stützstellen, wenn ich den richtig vermute das sie es sind,
> liegen alle auf dem einheitskreis der komplexen zahlenebene ?
Genau: das ist geometrisch gesprochen die Gruppe der Drehungen um 2pi/n.
> so, das sollte es erst einmal gewesen sein, es geht mir
> nicht um die gesamte polynommultiplikation, sondern
> vielmehr um das verständniss der Diskreten Fourier
> Transformation, kann mir jemand beschreiben wieso selbige
> genau so gebildet wird wie sie wird,
Du ersetzt die Potenzen der allgem. Stützstellen durch die Potenzen der Einheitswurzeln.
> und noch einmal kurz nen wink geben wieso bei multiplikation mit den
> koeffizenten gerade der funktionswert an diesen stellen herauskommt ?
Matritzenmultiplikation, wie oben erklärt.
Grüße Richard
|
|
|
|
