11.2.3. МЕТОД КУЛИ — ТЬЮКИ

Описанный в 1965 г. в работе [11.6] метод Кули — Тьюки представляет собой вариант алгоритма (11.60); этот метод особенно удобен для реализации на ЭВМ с двоичной системой счисления. В частности, он применим в случаях, когда число анализируемых ординат равно

Чтобы удовлетворить этому требованию, можно при необходимости

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

Желательно теперь отдельно выписать уравнения для этого весьма важного частного случая. Это делается просто подстановкой нужных величин в предыдущие формулы. Формула (11.47) принимает вид

где величины могут иметь только значения . Для всех уравнение (11.54) переписывается в виде

причем эта экспонента может быть равна только 1 или — 1. Вместо формулы (11.56) имеем

Итерационное преобразование Фурье (11.57) можно записать для этого частного случая следующим образом:

где

Согласно уравнению (11.58), первая итерация дает

На шаге уравнение (11.60) запишется следующим образом:

Это и есть алгоритм быстрого преобразования Фурье по Кули — Тьюки. Последняя итерация (уравнение (11.61)), принимающая вид

завершает последовательность действий для этого частного случая. Более подробное обсуждение метода содержится в работах [11.2-11.6].