Обратное преобразование Фурье

Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно лишь использовать ε ^{− 1} вместо ε (или применить операцию комплексного сопряжения в начале к входным данным, а затем к результату, полученному после прямого преобразования Фурье) и окончательный результат поделить на N.

Общий случай

Общий случай может быть сведён к предыдущему. Пусть  . Заметим, что  . Обозначим  . Тогда  , если положить   при  .

Таким образом задача сведена к вычислению свёртки, но это можно сделать с помощью трёх преобразований Фурье для 2^k элементов. Выполняем прямое преобразование Фурье для   и  , перемножаем поэлементно результаты и выполняем обратное преобразование Фурье.

Вычисления всех   и c_i требуют O(N) действий, три преобразования Фурье требуют O(Nlog(N)) действий, перемножение результатов преобразований Фурье требует O(N)действий, вычисление всех b_i зная значения свертки требует O(N) действий. Итого для дискретного преобразования Фурье требуется O(Nlog(N)) действий для любого N.

Этот алгоритм быстрого преобразования Фурье может работать над кольцом только когда известны первообразные корни из единицы степеней 2N и 2^k.

Вывод преобразования из дпф

Дискретное преобразование Фурье для вектора  , состоящего из N элементов, имеет вид:

элементы матрицы   имеют вид:  .

Пусть N четно, тогда ДПФ можно переписать следующим образом:

Коэффициенты   и   можно переписать следующим образом (M=N/2):

В результате получаем:

То есть дискретное преобразование Фурье от вектора, состоящего из N отсчетов, свелось к линейной композиции двух ДПФ от   отсчетов, и если для первоначальной задачи требовалось N² операций, то для полученной композиции —  . Если M является степенью двух, то это разделение можно продолжать рекурсивно до тех пор, пока не дойдем до двухточечного преобразования Фурье, которое вычисляется по следующим формулам: