Дискретное преобразование Фурье

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определение:

Дискретное преобразование Фурье (англ. Discrete Fourier Transform, DFT) многочлена [math]A(x)[/math] называют вектор значений этого многочлена в точках [math]x = \omega_{n,k}[/math]: [math] \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})) [/math] [math] = (A(\omega_n^0), A(\omega_n^1), \ldots , A(\omega_n^{n-1})), [/math] где [math]\omega_{n,k} = e^{i\frac{2\pi k}{n}}[/math] — [math] k-[/math]ый из [math]n[/math] комплексных корней из единицы. [math]\omega_n = \omega_{n,1} = e^{i\frac{2\pi}{n}}[/math] называется главным значением корня [math]n[/math]-ой степени из единицы, а все остальные корни являются его степенями: [math]\omega_{n,k} = (\omega_n)^k[/math].

Определение:

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

Применение ДПФ

Дискретное преобразование Фурье используют для быстрого перемножения двух полиномов [math]A[/math] и [math]B[/math].

Для того чтобы получить произведение двух многочленов за время, меньшее чем [math]O(n^2)[/math], необходимо сначала посчитать [math]DFT[/math] обоих многочленов. Так как при умножении двух многочленов их значения просто перемножаются в каждой точке. Следовательно, если [math]DFT[/math] — это вектор значений многочлена, то мы можем получить значение произведения двух многочленов, просто перемножив их ДПФ. Значит, чтобы получить коэффициенты полученного многочлена, применим обратное ДПФ.

[math] A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DFT}(B)). [/math]

Так как ДПФ многолчена — это вектор его значений, значит, перемножение двух ДПФ требует только [math]O(n)[/math] операций. Осталось только вычислять ДПФ и обратное ДПФ за время [math]O(n \log n)[/math]. Для этого используем быстрое преобразование Фурье.

ДПФ также применяют для быстрого умножения двух длинных чисел, которые в свою очередь могут быть представлены в виде полиномов.

ДПФ в модульной арифметике

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

Однако, то же верно и в случае корней [math]n[/math]-ой степени из единицы в модульной арифметике. Не для любого модуля [math]p[/math] найдется [math]n[/math] различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:

[math] (\omega_n)^n = 1 \ \mod p, [/math]

[math] (\omega_n)^k \ne 1 \ \mod p, 1 \leqslant k \lt n. [/math]

Как и с комплексными корнями, остальные [math]n-1[/math] корней [math]n[/math]-ой степени из единицы по модулю [math]p[/math] можно получить как степени примитивного корня [math]\omega_n[/math]

Следствия

Утверждение:

[math]\mathrm{DFT}(\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1})) = n (a_0, a_{n-1}, \ldots , a_1) [/math]

[math]\triangleright[/math]

Применим к обеим частям обратное ДПФ и получим: [math] \mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = \mathrm{InvDFT}\left(n (a_0, a_{n-1}, \ldots , a_1)\right) [/math] Заметим, что слева у нас находится вектор значений многочлена с коэффициентами [math](a_0, a_1, \ldots , a_{n-1})[/math] и обозначим его за [math](y_0, y_1, \ldots , y_{n-1})[/math]. Заметим, что: [math] y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j} [/math] Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями [math]\left( n a_0, n a_{n-1}, \ldots , n a_1 \right)[/math] в точках [math]x = \omega_n^k[/math]. Обозначим его как [math](y_0 ', y_1 ', \ldots , y_{n-1} ')[/math], где: [math] y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j}, [/math] где [math] \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} [/math] Тогда, подставляя значения [math]z_j[/math], получаем: [math] 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} [/math] А так как [math]e^{-i 2\pi k} = \left(\dfrac{1}{e^{i 2\pi}}\right)^k = 1[/math], получаем: [math] 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. [/math]

[math]\triangleleft[/math]

Пример

Посчитаем [math]\mathrm{DFT}[/math] для полинома степени [math]n = 4[/math].

[math] A(x) = 5 + 2x + 4x^2 - x^3 [/math]

Тогда подставляя значения [math]k[/math] в [math]e^{2i\frac{\pi k}{4}}[/math] получаем:

[math] x_0 = \ \ 5 \\ x_1 = \ \ 2 \\ x_2 = \ \ 4 \\ x_3 = -1 [/math]

Построим матрицу Вандермонда:

[math] \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} [/math]

Получаем вектор значений многочлена [math](y_0, y_1, y_2, y_3)[/math]:

[math] 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 [/math]

В итоге получаем:

[math] \mathrm{DFT}(A) = (10, 1 + 3i, 8, 1 - 3i) [/math]

Аналогично, получаем обратное ДПФ.

[math] \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} [/math]

[math] \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} [/math]

[math] 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 [/math]

См. также

• Быстрое преобразование Фурье

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

• Википедия — Дискретное преобразование Фурье
• MAXimal::algo::Быстрое преобразование Фурье за O (N log N)