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

Для построения интересующих нас статистик в этой книге применяется, главным образом, дискретное преобразование Фурье. Поэтому важно уметь быстро вычислять дискретное преобразование Фурье данного набора чисел .

Заметим, что если вычислять это преобразование по формуле

    (3.5.1)

т. е. по определению, то требуется произвести Т операций умножения комплексных чисел. В случае когда Т — составное число (произведение нескольких целых чисел), был предложен ряд простых процедур, сокращающих необходимое число умножений [Cooley и др. (1967)]. Недавно появились формальные алгоритмы, сокращающие число умножений почти до минимума [Good (1958), Cooley, Tukey (1965), Gentleman, Sande (1966), Cooley и др. (1967), Bergland (1967), Bingham и др. (1967), Brigham, Morrow (1967)]. О формулировках в терминах композиционных рядов конечной группы см. Posner (1968), Cairns (1971).

Укажем вначале вид алгоритма быстрого преобразования Фурье в двух элементарных случаях. "Идея этих алгоритмов — сократить число операций при преобразовании длинного ряда наблюдений, сводя задачу к последовательному вычислению преобразований Фурье более коротких наборов данных.

Теорема 3.5.1. Пусть , где — целые числа; тогда

    (3.5.2)

Заметим, что пробегает все целые значения при Заметим также,

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

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

Теорема 3.5.2. Пусть , где взаимна простые числа. Тогда для имеем

    (3.5.3)

Отметим, что необходимое число умножений комплексных чисел опять равно Здесь для каждого j мы должны определить фигурирующие выше, и подсчитать соответствующий коэффициент Фурье. При этом отсутствуют члены вида входящие в (3.5.2), и результирующее выражение симметрично по . Good (1971) сравнил эти два алгоритма быстрого преобразования Фурье.

Расширение теоремы 3.5.1 на случай, когда при некотором k и числа — целые, очевидно. В формуле теперь является составным числом и поэтому Енутреннее преобразование Фурье по аргументу само может быть записано в виде повторной процедуры (в виде . Продолжая таким образом, мы видим, что

может быть получено последовательным применением k дискретных преобразований Фурье порядков . Для этого понадобится произвести умножений комплексных чисел. Некоторые формулы, касающиеся этого случая, можно найти в работе Bingham и др. (1967).

Справедливо следующее обобщение теоремы 3.5.2.

Теорема 3.5.3. Пусть , где - взаимно простые числа. Пусть

Тогда

    (3.5.4)

Здесь означает периодическое продолжение с периодом Т.

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

Для вычисления результата по формуле теоремы 3.5.3 также необходимо произвести умножений. Отсюда видно, что наибольшая выгода получается, когда малы. Если , то в сущности необходимо выполнить умножений. В конце § 3.4 приводились дискретные преобразования Фурье для . Изучение этих примеров показывает, что может понадобиться даже меньшеечисло операций, чем указано выше. Случаи представляются особенно важными. Дополнительный выигрыш может быть достигнут при учете свойств или за счет преобразования нескольких рядов; см. Cooley и др. (1967), а также упр. 3.10.30.

Часто случается, что Т не разлагается на большое число множителей, и нас не интересуют значения на частотах вида . Если это так, то можно выбрать такое которое разлагается на большое число множителей, и добавить нулевых значений к набору X (t). Преобразование теперь получается при

Совершенно очевидно, что мы можем комбинировать технику, предоставляемую теоремой 3.5.3, когда Т разлагается на взаимно простые множители, с предыдущей процедурой, имеющей дело с произвольными множителями. Таким образом может быть сокращено число умножений на экспоненты. Подробности о случае Т —12 см. в книге Hamming (1962, стр. 74). Программу на языке Фортран для вычисления быстрого преобразования Фурье приводит Singleton (1969).

В заключение заметим, что быстрое преобразование Фурье— это прежде всего эффективный численный алгоритм. Используется такое преобразование или нет — на основных выводах статистического исследования это не скажется. Цель этого преобразования—радикальным образом сократить количество вычислений при эмпирическом анализе временных рядов.