Изменения

'''Дискретное преобразование Фурье''' (англ. ''Discrete Fourier Transform (, DFT)'') {{---}} многочлена <tex>A(x)</tex> называют вектор значений этого многочлена в точках <tex>x = \omega_{n,k}</tex>:

\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = (y_0, y_1, \ldots , y_{n-1}) = (A(\omega_{n,0}), A(\omega_{n,1}), \ldots , A(\omega_{n,n-1}))

'''Обратное дискретное преобразование Фурье''' (англ. ''Inverse DFT'') для вектора значений многочлена <tex>A(\omega_n)</tex> <tex>(y_0, y_1, \ldots , y_{n-1})</tex> {{---}} это вектор коэффициентов этого многочлена <tex>(a_0, a_1, \ldots , a_{n-1})</tex>:

\mathrm{InvDFT}(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}).

A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times DTF\mathrm{DFT}(B)).

Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(n \log n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].  ДПФ также применяют для быстрого умножения двух длинных чисел, которые в свою очередь могут быть представлены в виде полиномов.

В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют [[Группа | группу]], то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый [[Первообразные корни | примитивным]].

== Утверждения Следствия =={{Утверждение|statement= <tex>\mathrm{DFT}(\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1})) = n (a_0, a_{n-1}, \ldots , a_1) </tex>|proof=Применим к обеим частям обратное ДПФ и получим: <center><tex>\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = \mathrm{InvDFT}\left(n (a_0, a_{n-1}, \ldots , a_1)\right)</tex></center> Заметим, что слева у нас находится вектор значений многочлена с коэффициентами <tex>(a_0, a_1, \ldots , a_{n-1})</tex> и обозначим его за <tex>(y_0, y_1, \ldots , y_{n-1})</tex>. Заметим, что: <center><tex>y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}</tex></center> Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями <tex>\left( n a_0, n a_{n-1}, \ldots , n a_1 \right)</tex> в точках <tex>x = \omega_n^k</tex>. Обозначим его как <tex>(y_0 ', y_1 ', \ldots , y_{n-1} ')</tex>, где: <center><tex>y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j},</tex></center> где <center><tex>\begin{pmatrix}z_0 \\z_1 \\z_2 \\\vdots \\z_{n-1}\end{pmatrix}=\begin{pmatrix}n{a_0}\\n{a_{n-1}}\\n{a_{n-2}}\\\vdots \\n{a_1}\end{pmatrix}</tex></center> Тогда, подставляя значения <tex>z_j</tex>, получаем: <center><tex>y_k ' = a_0 e^0 + \sum\limits_{j=1}^{n-1} a_j e^{-i\frac{2\pi k}{n} (n - j)} = a_0 + \sum\limits_{j=1}^{n-1} a_j e^{-i 2\pi k} e^{i\frac{2\pi k}{n} j}</tex></center> А так как <tex>e^{-i 2\pi k} = \left(\dfrac{1}{e^{i 2\pi}}\right)^k = 1</tex>, получаем: <center><tex>y_k ' = a_0 + \sum\limits_{j=1}^{n-1} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j} = y_k.</tex></center>}} == Пример == Посчитаем <tex>\mathrm{DFT}</tex> для полинома степени <tex>n = 4</tex>. <center><tex>A(x) = 5 + 2x + 4x^2 - x^3</tex></center> Тогда подставляя значения <tex>k</tex> в <tex>e^{2i\frac{\pi k}{4}}</tex> получаем:<center><tex>x_0 = \ \ 5 \\x_1 = \ \ 2 \\x_2 = \ \ 4 \\x_3 = -1</tex></center> Построим матрицу Вандермонда: <center><tex>\begin{pmatrix}1 & 1 & 1 & 1 \\1 & i & -1 & -i \\1 & -1 & 1 & -1 \\1 & -i & -1 & i\end{pmatrix}\begin{pmatrix}5 \\2 \\4 \\-1\end{pmatrix}=\begin{pmatrix}10 \\1 + 3i \\8 \\1 - 3i\end{pmatrix}</tex></center> Получаем вектор значений многочлена <tex>(y_0, y_1, y_2, y_3)</tex>: <center><tex>y_0 = 1 \cdot 5 \ + \ 1 \cdot 2 \ + \ 1 \cdot 4 \ -1 \ = \ 10 \\y_1 = 1 \cdot 5 \ + \ 2i \ - \ 4 \ + \ i \ = \ 1 \ + \ 3i \\y_2 = 1 \cdot 5 \ - \ 2 \ + \ 4 \ + 1 \ = \ 8 \\y_3 = 1 \cdot 5 \ - \ 2i \ - \ 4 \ - \ i = 1 \ - \ 3i </tex></center> В итоге получаем:  <center><tex>\mathrm{DFT}(A) = (10, 1 + 3i, 8, 1 - 3i)</tex></center> Аналогично, получаем обратное ДПФ. <center><tex>\begin{pmatrix}a_0 \\a_1 \\a_2 \\a_3\end{pmatrix}={\begin{pmatrix}1 & 1 & 1 & 1 \\1 & i & -1 & -i \\1 & -1 & 1 & -1 \\1 & -i & -1 & i\end{pmatrix}}^{-1}\begin{pmatrix}10 \\1 + 3i \\8 \\1 - 3i\end{pmatrix}</tex></center>  <center><tex>\begin{pmatrix}a_0 \\a_1 \\a_2 \\a_3\end{pmatrix}=\dfrac{1}{-16i}\begin{pmatrix}-4i & -4i & -4i & -4i \\-4i & -4 & 4i & 4 \\-4i & 4i & -4i & 4i \\-4i & 4 & 4i & -4\end{pmatrix}\begin{pmatrix}10 \\1 + 3i \\8 \\1 - 3i\end{pmatrix}</tex></center>  <center><tex>a_0 = \dfrac{1}{4} (10 + 1 + 3i + 8 + 1 - 3i) = 5 \\a_1 = \dfrac{1}{4} (10 + (1 + 3i)(-i) + (-1)8 + (1 - 3i)i) = 2 \\a_2 = \dfrac{1}{4} (10 + (1 + 3i)(-1) + 8 + (1 - 3i)(-1)) = 4 \\a_3 = \dfrac{1}{4} (10 + (1 + 3i)i + (-1)8 + (1 - 3i)(-i)) = -1</tex></center> 

== Источники информации ==

[[Категория: Дискретная математика Алгоритмы и структуры данных]][[Категория: Алгоритмы алгебры и теории чисел]][[Категория: Основные элементы теории чисел]][[Категория: Основные алгоритмытеории чисел]]