§ 11.12. Понятие о дискретном преобразовании Фурье и тригонометрической интерполяции

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

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

Здесь — мнимая единица. Коэффициенты разложения вычисляются по формулам 1

Однако во многих случаях функция бывает задана лишь в конечном числе точек этом случае аналогом формулы (11.83) является разложение вида

Заметим, что это разложение имеет место тогда и только тогда, когда тригонометрический многочлен

интерполирует функцию по ее значениям в точках Выше (см. пример 11.2) было доказано, что система функций ортогональна на множестве точек причем Следовательно, разложение (11.85) действительно имеет место, причем в силу равенства (11.19) коэффициенты определяются по формуле

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

Для удобства изложения введем обозначение и перепишем формулы (11.85), (11.87) в следующем виде:

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

Если вычисления проводить непосредственно по формулам (11.88) и (11.89), то на выполнение каждого из преобразований потребуется примерно № арифметических операций. (Здесь под арифметической операцией понимается умножение двух комплексных чисел с последующим сложением. Величины считаются вычисленными заранее.)

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

Пусть где целые числа. Представим индекс в виде где Положим

, где Пользуясь тем, что и имеем Заменяя в формуле (11.88) суммирование по индексу к операцией повторного суммирования по индексам и получим

где

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

Указанная выше идея развита в алгоритмах быстрою дискретною преобразования Фурье. В случае, когда (где с помощью быстрого дискретного преобразования Фурье можно выполнить дискретное преобразование Фурье за арифметических операций. Особенно эффективным является этот алгоритм, когда число является степенью числа 2 (т. е. ). В этом случае вместо операций требуется выполнить лишь операций. Например, для этот алгоритм позволяет ускорить вычисления в и 50 раз.

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

Замечание 1. Часто разложение (11.85) записывают в эквивалентном виде:

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

Здесь коэффициенты а по-прежнему задаются формулой (11.87). Замечание 2. Хотя интерполяционные тригометрические многочлены (11.86), (11.92) и совпадают в точках они принимают существенно разные значения в точках х, отличных от узловых.

3. Тригонометрическая интерполяция.

Рассмотрим кратко задачу интерполяции функции заданной в точках тригонометрическим многочленом (11.92). К ней приводит, например, типичная радиотехническая задача о тригонометрической интерполяции периодического сигнала.

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

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

аналогичная оценке (11.61) для алгебраических многочленов. Здесь постоянная, являющаяся аналогом константы Лебега

Примечательно то, что в отличие от задачи интерполяции алгебраическими многочленами (см. § 11.10) оптимальным (т. е. дающим минимальное значение является равномерное распределение узлов, которому отвечает значение

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