Изменения
→Применение ДПФ
{{Определение
|definition=
'''Дискретное преобразование Фурье''' (англ. ''Discrete Fourier Transform (, DFT)'') {{---}} многочлена <tex>A(x)</tex> называют вектор значений этого многочлена в точках <tex>x = \omega_{n,k}</tex>:
<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}))
</tex>
<tex>
{{Определение
|definition=
'''Обратное дискретное преобразование Фурье''' (англ. ''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>:
<center>
<tex>
\mathrm{InvDFT}(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}).
</tex>
</center>
<center>
<tex>
A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times DTF\mathrm{DFT}(B)).
</tex>
</center>
Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(n \log n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]]. ДПФ также применяют для быстрого умножения двух длинных чисел, которые в свою очередь могут быть представлены в виде полиномов.
== ДПФ в модульной арифметике ==
В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют [[Группа | группу]], то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый [[Первообразные корни | примитивным]].
Однако, то же верно и в случае корней <tex>n</tex>-ой степени из единицы в модульной арифметике. Не для любого модуля <tex>p</tex> найдется <tex>n</tex> различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:
== Следствия ==
{{Утверждение
|statement= <tex>\mathrm{DFT}(\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1})) = \dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1) </tex>|proof= '''Доказательство:'''
Применим к обеим частям обратное ДПФ и получим:
<center>
<tex>
\mathrm{DFT}(a_0, a_1, a_{n-1}) = \mathrm{InvDFT}\left(\dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1)\right)
</tex>
</center>
<center>
<tex>
y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}
</tex>
</center>
<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>
y_k ' = a_0 + \sum\limits_{j=1}^{n} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n} 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>
== См. также ==
*[[Быстрое преобразование Фурье]]
== Источники информации ==
*[https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Википедия {{---}} Дискретное преобразование Фурье]
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]
[[Категория: Дискретная математика Алгоритмы и структуры данных]][[Категория: Алгоритмы алгебры и теории чисел]][[Категория: Основные элементы теории чисел]][[Категория: Основные алгоритмытеории чисел]]
