Изменения
Нет описания правки
'''Быстрое преобразование Фурье''' (англ. ''Fast Fourier Transform (FFT)'') {{---}} это метод, позволяющий вычислять дискретное преобразование Фурье за время <tex>O(nlogn)</tex>.
}}
== Алгоритм построения БПФ Описание задачи =={{Задача|definition=Необходимо научиться вычислять прямое и обратное дискретное преобразование Фурье многочлена <tex>A(x)</tex> степени <tex>n</tex> за время <tex>O(nlogn)</tex>.}}
Метод основывается на том, что степени одних комплексных корней единицы в степени <tex>n</tex> дают другие.
Идея заключается в том, что сначала мы разделяем вектор коэффициентов на два вектора, рекурсивно вычисляем значение ДПФ для них, и объединяем их в одно ДПФ.
== Алгоритм построения БПФ ==
Пусть имеется многочлен <tex>A(x)</tex> степени <tex>n</tex>, где <tex>n > 1, n = 2^t</tex>. Если <tex>n</tex> не является степенью двойки, добавим недостающие члены и положим коэффициенты равными нулю.
== Алгоритм построения обратного БПФ ==
Пусть вектор <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> многочлена. Рассмотрим ДПФ в матричном виде: <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> Отсюда можно найти вектор <tex>(a_0, a_1, \ldots ,a_{n-1}</tex>, умножив вектор <tex>(y_0, y_1, \ldots ,y_{n-1})</tex> на матрицу обратную матрице Вандермонда (матрица слева). <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> Непосредственной проверкой можно убедиться, что обратная матрица имеет вид: <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> Получаем формулу для <tex>a_k</tex>: <tex>a_k = \dfrac{1}{n}\sum \limits_{j=0}^{n-1} {y_j \omega_n^{kj}} </tex>
