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

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

Обратимся, для определенности, к формуле (15.9). Предположим, что число является составным, т.е. при натуральных . Разделим с остатком число на и число (индекс суммирования) на ; получим: . Заметим, что в образовавшихся обозначениях суммирование по эквивалентное повторному суммированию по схеме:

;

преобразуем теперь суммируемое выражение:

 

 

введем обозначения:

;

тогда выражение (15.10) представляется в виде:

.

Совершенно аналогично можно провести рассуждения с коэффициентом , в результате чего снова возникнут те же ; в итоге получится:

 

 

отсюда возникает соотношение:

 

Отсюда возникает иная возможность вычисления дискретного преобразования Фурье, отличная от прямого вычисления: надо сначала найти выражения , а затем уже сами числа ; потребуется, как нетрудно заметить, меньше арифметических операций. Отсюда и название - «Быстрое преобразование Фурье».