«ФУРЬЕ ПРЕОБРАЗОВАНИЕ ДИСКРЕТНОЕ»

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

Если на множестве точек функция задана своими значениями Т> 0 - период функции, то Ф. п. д. вектора х= (х ₀, x₁,..., x_N-1) есть вектор где F- матрица с элементами i - мнимая единица, Компоненты вектора аналогичны коэффициентам Фурье в обычных тригонометрич. разложениях. Ф. п. д. используется для приближенного вычисления этих коэффициентов, спектров, авто- и взаимно корреляционных функций и т. п. Прямое вычисление Ф. п. д. требует выполнения около N² арифметич. операций и большой затраты машинного времени. Метод быстрого преобразования Фурье (см. [1]) позволил существенно сократить число операций. При N=n₁ n₂... п _т этот метод выполняет Ф. п. д. приблизительно за N(п ₁+п₂+...+п _т )операций, повышая точность вычислений. Особенно удобные для реализации алгоритмы получаются при N=2^m. Имеется значительное число программ, реализующих или использующих быстрое преобразование Фурье для решения прикладных задач. Метод быстрого преобразования Фурье включает в себя широко известные экономичные способы вычисления Ф. п. д., напр. метод Рунге (см. [2]).

Лит.:[1] Сoolеу J., Тukеу J., лMath. Comput.