Быстрое преобразование Фурье(самостоятельно)

(1.50)

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

Дата добавления: 2015-10-21