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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм построения БПФ)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=

Версия 09:34, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

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


Определение:
Быстрое преобразование Фурье (англ. 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].

См. также

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