§ 4. Быстрое преобразование Фурье

Осуществление прямого и обратного дискретных преобразований Фурье

является составной частью решения многих задач. Непосредственное осуществление этих преобразований по формулам (3.4), (3.7) требует арифметических операций. Рассмотрим вопрос о возможности сокращения этого числа. Для определенности речь пойдет о вычислении коэффициентов по заданным значениям функции. Идея построения алгоритмов быстрого преобразования Фурье опирается на то, что при составном N в слагаемых правой части (3.7) можно выделить группы, которые входят в выражения различных коэффициентов . Вычисляя каждую группу только один раз, можно значительно сократить число операций.

Рассмотрим сначала случай . Представим , лежащие в пределах , в виде , где . Имеем цепочку соотношений

Из равенства

и предыдущего соотношения получим

где

Непосредственное вычисление всех требует арифметических операций, а последующее вычисление еще операций. Поэтому при общее число операций составит . Точно так же при строится алгоритм вычисления совокупности значений для которого общее число операций не превосходит , здесь С — постоянная, не зависящая от N. Выпишем соответствующие расчетные формулы для наиболее употребительного случая . Представим числа q, j в виде

где . Величину представим в виде

где s — целое, равное сумме всех слагаемых вида , у которых . Очевидно, что , поэтому

После перегруппировки слагаемых имеем

Это соотношение можно записать в виде последовательности рекуррентных соотношений

где

Переход от каждой совокупности к совокупности требует арифметических и логических операций; всего таких шагов , поэтому общее число операций имеет порядок .

Вычисление при помощи совокупностей дает меньшее накопление вычислительной погрешности по сравнению с формулами (3.7). Определенные удобства имеются также при вычислении экспонент, входящих в расчетные формулы. При вычислении величин используются значения . В частности, при величина принимает значения или —1. Для вычисления значений потребуются еще значения при нечетных j, удовлетворяющих неравенству . Их можно вычислить через уже вычисленные до этого величины, в частности, при помощи соотношений

где, в свою очередь,

при .

В ряде случаев удается еще уменьшить число операций. Один из таких случаев упоминался выше: дана вещественная функция , известная в точках требуется найти коэффициенты интерполяционного многочлена

Другой случай: при четном N заданы значения функции

в точках : нужно определить коэффициенты . Задача 1. Найти коэффициенты произведения двух многочленов

Показать, что для их нахождения достаточно операций.