\>Je asi vidìt, ¾e klíèové jsou kroky 2 a 4. Vybrání bodù jistì stihneme pohodlnì v~lineárním èase a vynásobení samotných hodnot té¾ (máme $2n+2$ bodù a $C(x_{k}) = A(x_{k}) \cdot B(x_{k}), k = 0,1,2, \ldots , 2n+1$, tak¾e na to nepotøebujeme více ne¾ $2n+2$ násobení).
-Celý trik spoèívá v~chytrém vybrání onìch bodù, ve kterých budeme polynomy vyhodnocovat. Je na to potøeba vìdìt pár zajímavostí o~komplexních èíslech, na stránce Matrina Mar¹e jsou k dispozici slajdy, zde to bude zapsáno o~trochu struènìji.
+Celý trik spoèívá v~chytrém vybrání onìch bodù, ve kterých budeme polynomy vyhodnocovat. Je na to potøeba vìdìt pár zajímavostí o~komplexních èíslech, na stránce Matrina Mare¹e jsou k dispozici slajdy, zde to bude zapsáno o~trochu struènìji.
\ss{Vyhodnocení polynomu metodou rozdìl a panuj (algoritmus FFT):}
Mìjme polynom $P$ øádu $n$ a chceme jej vyhodnotit v $n$ bodech. Vybereme si body tak, aby byly spárované, èili $\pm x_{0}, \pm x_{1}, \ldots , \pm x_{n/2-1} $. To nám výpoèet urychlí, proto¾e pak se druhé mocniny $x_{i}$ shodují s~druhými mocninami $-x_{i}$.
Máme tedy algoritmus, který \uv{pøevede} koeficienty polynomu na hodnoty tohoto polynomu v~námi zadaných bodech. Ale potøebujeme také algoritmus, který doká¾e reprezentaci polynomu pomocí hodnot pøevést zpìt na koeficienty polynomu. Tedy nìjaký inverzní algoitmus.
-Definuje me si algoritmus DFT, která vyu¾ívá maticovou reprezentaci a s~jeho¾ pomocí získáme hledaný algoritmus.
+Definujeme si algoritmus DFT, která vyu¾ívá maticovou reprezentaci a s~jeho¾ pomocí získáme hledaný algoritmus.
\s{Definice:}
\>{\I Diskretní Fourierova transformace} $(DFT)$
je funkce $f: { {\bb C} ^n} \rightarrow { {\bb C} ^n}$, kde $y=f(x) \equiv \forall j \ y_{j} = \sum \limits ^{n-1}_{k=0} x_{k} . \omega ^{jk}$.
\s{Poznámka:}
-Vezmeme polynom, který má $x_{kj}$ jako koeficienty a vyhodnotíme ho v~bodì $\omega ^{j} [y_{j} = x(\omega^{j})] \Rightarrow {f}$ je linearní $\Rightarrow$ mù¾eme napsat $f(x) = \Omega_{x} ,\ \Omega _{jk} =\omega ^{jk}$, kde $\Omega$ je matice.
+Vezmeme polynom, který má $x_{kj}$ jako koeficienty a vyhodnotíme ho v~bodì $\omega ^{j} [y_{j} = x(\omega^{j})] \Rightarrow {f}$ je linearní $\Rightarrow$ mù¾eme napsat $f(x) = \Omega x ,\ \Omega _{jk} =\omega ^{jk}$, kde $\Omega$ je matice.
\s{Jak najít inverzní matici?} Víme, ¾e $\Omega =\Omega ^{T}$ proto¾e $\omega ^{jk} = \omega ^{kj}$.
projects / ads2.git / blobdiff