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

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

коэффициенты находятся по следующим формулам

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

Разложение имеет место когда функцию можно приблизить тригонометрическим многочленом следующего вида в заданных нам точках

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

Далее для удобства записи будем использовать 

Часто используется следующий вид формул:

 и это соответствует интерполяции тригонометрическим многочленом

,

где коэффициенты считаются по тем же формулам.

Если вычисления проводить по вышеприведённым формулам, то на выполнения каждого из преобразований потребуется арифметических операций (считаем, что уже вычислены). Если N не является простым числом, то количество операций можно значительно сократить, используя быстрое преобразование Фурье.

Пример использования

Рассмотрим применение тригонометрической интерполяции. Будем использовать для приближения следующий тригонометрический полином:

Будем искать приближение функции f(x). Пусть известно значения при 

Тогда по формулам изложенным выше можно получить 

Если интерполировать тригонометические функции и выбирать правильное число узлов, то погрешность приближается к нулю. Интересно рассмотреть функции, не являющиеся тригонометрическими, но обладающие периодом. Рассмотрим ряд вычислений приближенных функций с помощью программы, использующей выше изложенный алгоритм апроксимации. На вход подается функция и количество точек на промежутке , точки по умолчанию расположены равномерно на промежутке. Как будет показано ниже, это соответсвует наилучшей аппроксимации.

Тригонометрическая функция с шумом

На вход подавалась функция , (пусть под 'rand()' понимается некоторая шумовая функция). Вычислияем значение функции в 5 точках. По графику ('Рис.1')видно, что аппроксимация произвендена достаточно точно.

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

Не тригонометрическая кусочно-заданная функция

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

На вход программе подавалась кусочно-заданная функция , функция подразумевается периодической с периодом . Для вычисления полинома бралось 25 точек. На Рис.2 приведен график функциии и график интерполирующего полинома. На Рис.4 приведен график ошибки интерполяции.

Как видно из графика функции ошибки она максимальна на а районе концлв промежутка.