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

Вычисление преобразования Фурье по формуле (1.50) предполагает выполнение $N^2$ операций сложения и умножения. Большая трудоемкость вычислений сдерживала  широкое применение  преобразования Фурье до середины 60-х годов, когда был предложен алгоритм быстрого преобразования Фурье (БПФ). На сегодняшний день БПФ -- это название не одного, а ряда различных алгоритмов, предназначенных для быстрого вычисления дискретно-временного ряда Фурье (1.50). Алгоритмы БПФ имеются в наличии практически во всех пакетах прикладных программ, предназначенных для научных исследований.

Основная идея БПФ состоит в разбиении исходного преобразования (1.50) на несколько частей, каждую из которых можно вычислить отдельно, затем линейно просуммировать с остальными, чтобы получить исходное преобразование. Эти части меньшего размера можно, в свою очередь, разбить на еще меньшие. Пусть длина временного ряда равна $N$.Если использовать деление исходного преобразования (1.50) на каждом шаге на две части, то исходный временной ряд будет состоять из $k$ частей так, что $2^k=N$, тогда для выполнения вычислений потребуется $\log_2 N$ операций сложения и $N/2$ операций умножения на каждом шаге, что составляет примерно $4 N \log_2 N$ операций. Это значительно меньше тех $N^2$ операций, которые необходимы при вычислениях по формуле (1.50). Эффективность алгоритма БПФ линейно возрастает с ростом длины реализации.