Основы вычислительной математики. Денисова Э.В - 150 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

1.2 Быстрое Преобразование Фурье
Быстрое преобразование Фурье (БПФ) — это быстрый алгоритм вычисления дискретного преобразования
Фурье. То есть алгоритм вычисления за количество действий, меньше чем N
2
, требуемых для прямого (по
формуле) вычисления ДПФ.
Наиболее популярным из алгоритмов ускоренного вычисления ДПФ является т.н. метод Cooley-Tukey,
позволяющий вычислить ДПФ для числа отсчетов N = 2k за время порядка N·log
2
N (отсюда и название -
быстрое преобразование Фурье, БПФ). Этот способ чем-то неуловимо напоминает быструю сортировку. В
ходе работы алгоритма также проводится рекурсивное разбиение массива чисел на два подмассива и сведение
вычисления ДПФ от целого массива к вычислению ДПФ от подмассивов в отдельности.
Изобретение БПФ привело к потрясающему всплеску популярности преобразования
Фурье. Целый ряд
важных задач раньше решался за время порядка N
2
, но после проведения преобразования Фурье над
исходными данными (за время порядка N·log
2
N) решается практически мгновенно. Преобразование Фурье
лежит в основе цифровых корелляторов и методов свертки, активно используется при спектральном анализе
(практически в чистом виде), применяется при работе с длинными числами.
§2. Алгоритм быстрого преобразования Фурье
2.1 Алгоритм
Покажем как выполнить дискретное преобразование Фурье за
))((
1 n
ppNO ++ …
действий при
n
pppN …
21
= . В частности, при N = 2n понадобится O(Nlog(N)) действий.
Дискретное преобразование Фурье преобразует набор чисел
в набор чисел
10
,,
−n
bb … ,
такой, что
ij
n
j
ji
ab
ε
∑
−
=
=
1
0
, где и при 0 < k < n. Алгоритм быстрого преобразования Фурье
применим к любым коммутативным ассоциативным кольцам с единицей. Чаще всего этот алгоритм
применяют к полю комплексных чисел (c
) и к кольцам вычетов.
Основной шаг алгоритма состоит в сведении задачи для N чисел к задаче для p = N / q числам, где q —
делитель N. Пусть мы уже умеем решать задачу для N / q чисел. Применим преобразование Фурье к наборам
для . Покажем теперь, как за O(Np) действий решить
исходную задачу. Заметим, что
kiq
p
k
jkq
ij
q
j
ji
aab
εε
∑∑
−
=
+
−
=
=
1
0
1
0
(
. Выражения в скобках нам уже известны — это
i(mod p)-тое число после преобразования Фурье j-той группы. Таким образом, для вычисления каждого bi
нужно O(q) действий, а для вычисления всех bi — O(Nq) действий, что и требовалось получить.
2.2 Обратное преобразование Фурье
Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно
лишь использовать
вместо (или применить операцию комплексного сопряжения в начале к входным
данным, а затем к результату полученному после прямого преобразования Фурье) и окончательный результат
поделить на N.
2.3 Общий случай
Общий случай может быть сведён к предыдущему. Пусть .
Заметим, что
∑
−
=
−+
−
=
1
0
2/2/)(
2/
22
2
N
j
jji
i
i
j
a
b
ε
εε
. Обозначим
2/)22(2/2/
222
,,
iN
ii
i
ii
i
i
cbbaa
−−−
===
εεε
.
Тогда
jiN
iN
j
ji
cab
−−−
−−
=
∑
=
22
22
0
, если положить при .
Таким образом, задача сведена к вычислению свёртки, но это можно сделать с помощью трёх преобразований
Фурье для 2k элементов. Выполняем прямое преобразование Фурье для
и ,
перемножаем поэлементно результаты и выполняем обратное преобразование Фурье.

Страницы