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

2019-12-01T19:50:05Z

Amsilevich: /* Алгоритм построения БПФ */

{{Определение
|definition=
'''Быстрое преобразование Фурье''' (англ. ''Fast Fourier Transform, FFT'') {{---}} метод, позволяющий вычислять [[Дискретное преобразование Фурье | дискретное преобразование Фурье]] за время <tex>O(n \log n)</tex>.
}}

== Описание задачи ==
{{Задача
|definition=
Необходимо научиться вычислять прямое и обратное дискретное преобразование Фурье многочлена <tex>A(x)</tex> степени <tex>n</tex> за время <tex>O(n \log n)</tex>.
}}

Метод основывается на том, что степени одних комплексных корней единицы в степени <tex>n</tex> дают другие.

Cначала мы разделяем вектор коэффициентов на два вектора, рекурсивно вычисляем значение ДПФ для них, и объединяем их в одно ДПФ.

== Алгоритм построения БПФ ==
Пусть имеется многочлен <tex>A(x)</tex> порядка <tex>n</tex>, где <tex>n > 1, n = 2^t</tex>. Если <tex>n</tex> не является степенью двойки, добавим недостающие члены и положим коэффициенты равными нулю.

<center><tex> A(x) = a_0 x^0 + a_1 x^1 + \ldots + a_{n-1} x^{n-1} </tex></center>

Разделим <tex>A(x)</tex> на два многочлена, где один будет с четными, а другой с нечетными коэффициентами:

<center>
<tex> A_0(x) = a_0 x^0 + a_2 x^1 + \ldots + a_{n-2} x^{\frac{n}{2} - 1} </tex>

<tex> A_1(x) = a_1 x^0 + a_3 x^1 + \ldots + a_{n-1} x^{\frac{n}{2} - 1} </tex>
</center>

Многочлен <tex>A(x)</tex> получается из <tex>A_0(x)</tex> и <tex>A_1(x)</tex> следующим образом:

<center><tex>A(x) = A_0(x^2) + xA_1(x^2) \ \ \ \ \ (1)</tex></center>

Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным <tex>\mathrm{DFT}(A_0)</tex> и <tex>\mathrm{DFT}(A_1)</tex> за линейное время вычислить <tex>\mathrm{DFT}(A)</tex>. Так как здесь используется идея ''разделяй и властвуй'', то асимптотическая оценка будет <tex>O(n \log n)</tex>.

Пусть <tex>\mathrm{DFT}(A_0) = \{y_k^0\}^{\frac{n}{2}-1}_{k=0}</tex> и <tex>\mathrm{DFT}(A_1) = \{y_k^1\}^{\frac{n}{2} - 1}_{k=0}</tex>. Найдем вектор значений <tex>\mathrm{DFT}(A) = \{y_k\}^{n-1}_{k=0}</tex>.
* Из <tex>(1)</tex> получаем значения для первой половины коэффициентов:
<center><tex>y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex></center>
* Для второй половины получаем:
<center><tex>y_{k+\frac{n}{2}}= A(\omega_n^{k+\frac{n}{2}})= A_0(\omega_n^{2k+n})+ \omega_n^{k+\frac{n}{2}} A_1(\omega_n^{2k+n})= </tex> <tex>A_0(\omega_n^{2k} \omega_n^{n})+ \omega_n^k \omega_n^{\frac{n}{2}} A_1(\omega_n^{2k} \omega_n^n) </tex>
</center>

Заметим, что <tex> \omega_n^n = 1, \omega_n^{\frac{n}{2}} = -1</tex>, тогда:

<center><tex>y_{k+\frac{n}{2}}= A_0(\omega_n^{2k})- \omega_n^k A_1(\omega_n^{2k})= y_k^0- \omega_n^k y_k^1</tex>.</center>

Таким образом, мы получили:

<center><tex>y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex></center>

<center><tex>y_{k+\frac{n}{2}}= y_k^0- \omega_n^k y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex>. </center>

== Алгоритм построения обратного БПФ ==
Пусть вектор <tex>(y_0, y_1, \ldots , y_{n-1})</tex> {{---}} значения многочлена <tex>A</tex> степени <tex>n</tex> в точках <tex>n = \omega_n^k</tex>. Необходимо, по данному вектору восстановить коэффициенты <tex>(a_0, a_1, \ldots , a_{n-1})</tex> многочлена.

Рассмотрим ДПФ в матричном виде:

<center>
<tex>
\begin{pmatrix}
\omega_n^0 & \omega_n^0 & \omega_n^0 & \ldots & \omega_n^0\\
\omega_n^0 & \omega_n^1 & \omega_n^2 & \ldots & \omega_n^{n-1} \\
\omega_n^0 & \omega_n^2 & \omega_n^4 & \ldots & \omega_n^{2(n-1)} \\
\vdots& \vdots & \vdots &\ddots & \vdots\\
\omega_n^0 & \omega_n^{n-1} & \omega_n^{2(n-1)} &\ldots & \omega_n^{(n-1)(n-1)}
\end{pmatrix}
\begin{pmatrix}
a_0 \\
a_1 \\
a_2 \\
\vdots \\
a_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
y_0 \\
y_1 \\
y_2 \\
\vdots \\
y_{n-1}
\end{pmatrix}
</tex></center>

Отсюда можно найти вектор <tex>(a_0, a_1, \ldots ,a_{n-1})</tex>, умножив вектор <tex>(y_0, y_1, \ldots ,y_{n-1})</tex> на матрицу обратную матрице Вандермонда (матрица слева).

<center><tex>
\begin{pmatrix}
a_0 \\
a_1 \\
a_2 \\
\vdots \\
a_{n-1}
\end{pmatrix}
=
{\begin{pmatrix}
\omega_n^0 & \omega_n^0 & \omega_n^0 & \ldots & \omega_n^0\\
\omega_n^0 & \omega_n^1 & \omega_n^2 & \ldots & \omega_n^{n-1} \\
\omega_n^0 & \omega_n^2 & \omega_n^4 & \ldots & \omega_n^{2(n-1)} \\
\vdots& \vdots & \vdots &\ddots & \vdots\\
\omega_n^0 & \omega_n^{n-1} & \omega_n^{2(n-1)} &\ldots & \omega_n^{(n-1)(n-1)}
\end{pmatrix}}^{-1}
\begin{pmatrix}
y_0 \\
y_1 \\
y_2 \\
\vdots \\
y_{n-1}
\end{pmatrix}
</tex></center>

Непосредственной проверкой можно убедиться, что обратная матрица имеет вид:

<center><tex>
\dfrac{1}{n}
\begin{pmatrix}
\omega_n^0 & \omega_n^0 & \omega_n^0 & \ldots & \omega_n^0\\
\omega_n^0 & \omega_n^{-1} & \omega_n^{-2} & \ldots & \omega_n^{-(n-1)} \\
\omega_n^0 & \omega_n^{-2} & \omega_n^{-4} & \ldots & \omega_n^{-2(n-1)} \\
\vdots& \vdots & \vdots &\ddots & \vdots\\
\omega_n^0 & \omega_n^{-(n-1)} & \omega_n^{-2(n-1)} &\ldots & \omega_n^{-(n-1)(n-1)}
\end{pmatrix}
</tex></center>

Получаем формулу для <tex>a_k</tex>:

<center><tex>a_k = \dfrac{1}{n}\sum \limits_{j=0}^{n-1} {y_j \omega_n^{-kj}} </tex></center>

Аналогично прямому ДПФ, по принципу ''разделяй и властвуй'' посчитаем <tex>\mathrm{InvDFT}</tex>.

== См. также ==
*[[Дискретное преобразование Фурье]]

== Источники информации ==
*[https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%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)]

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

Викиконспекты - Вклад участника [ru]

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