Фурье преобразование дискретное

-преобразование, используемое для гармонич. анализа функций, заданных на дискретном множестве точек. Если на множестве точек [img: http://localhost:8080/file/052218-97.jpg] функция задана своими значениями [img: http://localhost:8080/file/052218-98.jpg] Т> 0 - период функции, то Ф. п. д. вектора х= (х 0, x1,..., xN-1) есть вектор [img: http://localhost:8080/file/052218-99.jpg] где F- матрица с элементами [img: http://localhost:8080/file/052218-100.jpg] i - мнимая единица, [img: http://localhost:8080/file/052218-101.jpg] [img: http://localhost:8080/file/052218-102.jpg] Компоненты вектора [img: http://localhost:8080/file/052218-103.jpg] аналогичны коэффициентам Фурье в обычных тригонометрич. разложениях. Ф. п. д. используется для приближенного вычисления этих коэффициентов, спектров, авто- и взаимно корреляционных функций и т. п. Прямое вычисление Ф. п. д. требует выполнения около N2 арифметич. операций и большой затраты машинного времени. Метод быстрого преобразования Фурье (см. [1]) позволил существенно сократить число операций. При N=n1 n2... п т этот метод выполняет Ф. п. д. приблизительно за N(п 1+п2+...+п т)операций, повышая точность вычислений. Особенно удобные для реализации алгоритмы получаются при N=2m. Имеется значительное число программ, реализующих или использующих быстрое преобразование Фурье для решения прикладных задач. Метод быстрого преобразования Фурье включает в себя широко известные экономичные способы вычисления Ф. п. д., напр. метод Рунге (см. [2]).