11.2.2. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ

Преобразование Фурье действительной или комплексной функции заданной на бесконечном интервале, представляет собой комплексную величину

Если область интегрирования не ограничена, то, как уже отмечалось ранее, преобразование не существует, когда реализация обладает всеми свойствами стационарного случайного процесса. Ограничив интервал задания функции скажем приняв его равным можно построить финитное преобразование Фурье

Предположим теперь, что функция представлена эквидистантными наблюдениями с интервалом дискретности который выбран таким образом, что частота Найквиста достаточно высока. Поскольку моменты (в данном случае удобно начать с Формула (11.30) запишется в виде

Дискретная аппроксимация выражения (11.35) при произвольном значении есть

Для расчета функции обычно выбираются дискретные значения частоты

Преобразованная последовательность дает на этих частотах составляющие Фурье

причем интервал дискретности внесен в значение чтобы перед

знаком суммы не было множителя. Заметим, что преобразование однозначно только до значений поскольку этой точке соответствует частота Найквиста. Быстрое преобразование Фурье применяется для вычисления последовательности но может быть также использовано для нахождения коэффициентов Фурье из формул (11.33).

Упростим обозначения, положив

Заметим, что и при всех и и справедливо равенство

Положим также Формула (11.38) примет теперь вид

Следует внимательно рассмотреть равенства (11.38) и (11.40), представляющие собой не что иное, как преобразования Фурье последовательности содержащей конечное число членов. Для расчета всех значений по этим формулам необходимо выполнить примерно операций умножения и сложения комплексных чисел (одна такая комплексная операция эквивалентна четырем операциям умножения и сложения действительных чисел).

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

то, как доказано ниже, входящая в соотношение (11.40) последовательность может быть найдена итеративно путем расчета суммы слагаемых:

Таким образом, общее число операций над действительными числами

ставляет

В результате при использовании БПФ, а не стандартного метода получаем коэффициент ускорения вычислений

ПРИМЕР 11.2. КОЭФФИЦИЕНТ УСКОРЕНИЯ ВЫЧИСЛЕНИЙ ДЛЯ ГДЕ ЦЕЛОЕ ЧИСЛО. Если то

В этом случае, согласно формуле (11.44),

Однако скорость вычислений можно увеличить еще вдвое, используя следующее свойство: при все значения равны либо 1, либо —1, так что соответствующие операции умножения заменяются сложением и вычитанием. Таким образом,

В частности, при из формулы (11.45) получаем: Но и этот результат представляет собой лишь консервативную оценку; в действительности можно добиться нового двукратного увеличения скорости, разделив исходную реализацию пополам и производя расчет, как указано в разд. 11.24.

Построение метода. Для получения результата, постулированного в (11.42), представим индексы к и из формулы (11.40) в виде

Отметим, что теперь индексы кип заменены индексами к и Последние формулы можно переписать в виде

где

Фиксируя поочередно можно непосредственно убедиться в том, что величины кип принимают значения от 0 до где есть произведение всех значений (см. равенство (11.41)). Перепишем теперь формулу (11.40) в виде

где (11.48)

а величина к определена равенством (11.46).

Другой способ представления величины к заключается в следующем:

Следовательно, в формуле (11.49)

Далее величина для любого аргумента, кратного равна единице, поэтому при

Рассмотрим последнее равенство подробнее. При имеем

Мы получили экспоненциальное выражение для преобразования Фурье функции состоящей из а не из членов (см. формулы (11.36) и (11.40)). Заметим, что переменные принимают значения от 0 до и потому для расчета каждого значения нужно всего операций умножения и сложения. Имея в виду равенство Щи нетрудно показать, что при формула (11.51) принимает вид произведения

в котором только второй сомножитель содержит величину к Этот сомножитель представляет собой выражение

т. e. экспоненту, необходимую для преобразования Фурье функции состоящей из членов. Заметим, что переменные принимают значения от 0 до Следовательно, для вычисления каждого значения нужно всего операций умножения и сложения.

Алгоритм БПФ. С учетом преобразований (11.50)-(11.52) уравнение (11.49) можно записать в виле

Величины типа часто называют «ориентирующими коэффициентами». Подставив выражение (11.55) в формулу (11.48), получим

Таким образом, согласно формуле (11.57), искомое преобразование Фурье может быть построено за итераций. Теперь следует остановиться на этом итеративном методе более подробно.

Рассмотрим последнюю внутреннюю сумму в формуле (11.57). Пусть

Имея в виду все возможные значения, которые могут принимать величины найдем, что уравнение (11.58) дает преобразований Фурье функции каждое из которых требует операций. Рассмотрим теперь следующую внутреннюю сумму в формуле (11.57). Пусть

Тогда, имея в виду все возможные значения, которые могут принимать величины найдем, что уравнение (11.54) дает преобразований Фурье функции каждое из которых требует операций. Продолжая эти рассуждения шага, где положим

И вновь, имея в виду все возможные значения, которые могут принимать величины получим преобразований Фурье функции каждое из которых требует операций. На последнем шаге формула (11.57) дает

откуда, имея в виду все возможные значения величин получим преобразований Фурье функции х (и 0), каждое из которых требует операций. Последовательность действий, определенная равенствами (11.58) — (11.61), приводит к результату, постулированному в (11.42), причем комплексные числа теперь заменены действительными.

Выражение (11.60) и есть алгоритм быстрого преобразования Фурье; оно служит основой для многих применяемых сейчас численных методов расчета преобразования Фурье. Более детальное рассмотрение содержится в книге (11.5).