Быстрое преобразование Фурье — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм построения обратного БПФ)
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 4 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Быстрое преобразование Фурье''' (англ. ''Fast Fourier Transform (FFT)'') {{---}} это метод, позволяющий вычислять дискретное преобразование Фурье за время <tex>O(nlogn)</tex>.
+
'''Быстрое преобразование Фурье''' (англ. ''Fast Fourier Transform, FFT'') {{---}} метод, позволяющий вычислять [[Дискретное преобразование Фурье | дискретное преобразование Фурье]] за время <tex>O(n \log n)</tex>.
 
}}
 
}}
  
Строка 7: Строка 7:
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Необходимо научиться вычислять прямое и обратное дискретное преобразование Фурье многочлена <tex>A(x)</tex> степени <tex>n</tex> за время <tex>O(nlogn)</tex>.
+
Необходимо научиться вычислять прямое и обратное дискретное преобразование Фурье многочлена <tex>A(x)</tex> степени <tex>n</tex> за время <tex>O(n \log n)</tex>.
 
}}
 
}}
  
 
Метод основывается на том, что степени одних комплексных корней единицы в степени <tex>n</tex> дают другие.  
 
Метод основывается на том, что степени одних комплексных корней единицы в степени <tex>n</tex> дают другие.  
  
Идея заключается в том, что сначала мы разделяем вектор коэффициентов на два вектора, рекурсивно вычисляем значение ДПФ для них, и объединяем их в одно ДПФ.
+
Cначала мы разделяем вектор коэффициентов на два вектора, рекурсивно вычисляем значение ДПФ для них, и объединяем их в одно ДПФ.
  
 
== Алгоритм построения БПФ ==
 
== Алгоритм построения БПФ ==
Пусть имеется многочлен <tex>A(x)</tex> степени <tex>n</tex>, где <tex>n > 1, n = 2^t</tex>. Если <tex>n</tex> не является степенью двойки, добавим недостающие члены и положим коэффициенты равными нулю.
+
Пусть имеется многочлен <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>
 
<center><tex> A(x) = a_0 x^0 + a_1 x^1 + \ldots + a_{n-1} x^{n-1} </tex></center>
Строка 33: Строка 33:
  
  
Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным <tex>DFT(A_0)</tex> и <tex>DFT(A_1)</tex> за линейное время вычислить <tex>DFT(A)</tex>. Так как здесь используется идея "разделяй и властвуй", то асимптотическая оценка будет <tex>O(nlogn)</tex>.
+
Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным <tex>\mathrm{DFT}(A_0)</tex> и <tex>\mathrm{DFT}(A_1)</tex> за линейное время вычислить <tex>\mathrm{DFT}(A)</tex>. Так как здесь используется идея ''разделяй и властвуй'', то асимптотическая оценка будет <tex>O(n \log n)</tex>.
  
Пусть <tex>DFT(A_0) = \{y_k^0\}^{\frac{n}{2}-1}_{k=0}</tex> и <tex>DFT(A_1) = \{y_k^1\}^{\frac{n}{2} - 1}_{k=0}</tex>. Найдем вектор значений <tex>DFT(A) = \{y_k\}^{n-1}_{k=0}</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> получаем значения для первой половины коэффициентов:
 
* Из <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 = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex></center>
Строка 83: Строка 83:
 
</tex></center>
 
</tex></center>
  
Отсюда можно найти вектор <tex>(a_0, a_1, \ldots ,a_{n-1}</tex>, умножив вектор <tex>(y_0, y_1, \ldots ,y_{n-1})</tex> на матрицу обратную матрице Вандермонда (матрица слева).
+
Отсюда можно найти вектор <tex>(a_0, a_1, \ldots ,a_{n-1})</tex>, умножив вектор <tex>(y_0, y_1, \ldots ,y_{n-1})</tex> на матрицу обратную матрице Вандермонда (матрица слева).
  
 
<center><tex>
 
<center><tex>
Строка 125: Строка 125:
 
Получаем формулу для <tex>a_k</tex>:
 
Получаем формулу для <tex>a_k</tex>:
  
<center><tex>a_k = \dfrac{1}{n}\sum \limits_{j=0}^{n-1} {y_j \omega_n^{kj}} </tex></center>
+
<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 Википедия {{---}} Быстрое преобразование Фурье]
 
*[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)]
 
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Алгоритмы алгебры и теории чисел]]
 +
[[Категория: Основные элементы теории чисел]]
 +
[[Категория: Основные алгоритмы теории чисел]]

Текущая версия на 19:06, 4 сентября 2022

Определение:
Быстрое преобразование Фурье (англ. Fast Fourier Transform, FFT) — метод, позволяющий вычислять дискретное преобразование Фурье за время [math]O(n \log n)[/math].


Описание задачи

Задача:
Необходимо научиться вычислять прямое и обратное дискретное преобразование Фурье многочлена [math]A(x)[/math] степени [math]n[/math] за время [math]O(n \log n)[/math].


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

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

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

Пусть имеется многочлен [math]A(x)[/math] порядка [math]n[/math], где [math]n \gt 1, n = 2^t[/math]. Если [math]n[/math] не является степенью двойки, добавим недостающие члены и положим коэффициенты равными нулю.

[math] A(x) = a_0 x^0 + a_1 x^1 + \ldots + a_{n-1} x^{n-1} [/math]

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

[math] A_0(x) = a_0 x^0 + a_2 x^1 + \ldots + a_{n-2} x^{\frac{n}{2} - 1} [/math]

[math] A_1(x) = a_1 x^0 + a_3 x^1 + \ldots + a_{n-1} x^{\frac{n}{2} - 1} [/math]

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


[math]A(x) = A_0(x^2) + xA_1(x^2) \ \ \ \ \ (1)[/math]


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

Пусть [math]\mathrm{DFT}(A_0) = \{y_k^0\}^{\frac{n}{2}-1}_{k=0}[/math] и [math]\mathrm{DFT}(A_1) = \{y_k^1\}^{\frac{n}{2} - 1}_{k=0}[/math]. Найдем вектор значений [math]\mathrm{DFT}(A) = \{y_k\}^{n-1}_{k=0}[/math].

  • Из [math](1)[/math] получаем значения для первой половины коэффициентов:
[math]y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 [/math]
  • Для второй половины получаем:
[math]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})= [/math] [math]A_0(\omega_n^{2k} \omega_n^{n})+ \omega_n^k \omega_n^{\frac{n}{2}} A_1(\omega_n^{2k} \omega_n^n) [/math]

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

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

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

[math]y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 [/math]
[math]y_{k+\frac{n}{2}}= y_k^0- \omega_n^k y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 [/math].

Алгоритм построения обратного БПФ

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

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

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

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

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

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

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

Получаем формулу для [math]a_k[/math]:

[math]a_k = \dfrac{1}{n}\sum \limits_{j=0}^{n-1} {y_j \omega_n^{-kj}} [/math]

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

См. также

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