§ 3. Тригонометрическая интерполяция. Дискретное преобразование Фурье

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

Пусть -периодическая функция с периодом 1 — разложена в ряд Фурье

причем

Здесь i - мнимая единица.

Рассмотрим значения этой функции на сетке из точек , где , N целые, N фиксировано, и обозначим . Если , где целое, то , где целое. Следовательно,

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

Лемма. При , определяемых (5), соотношение (4) остается в силе, если пределы суммирования [0, N—1] заменить на , где — любое целое.

Доказательство. В самом деле, если , то

Принимая за новую переменную суммирования , получим

Поскольку в узлах сетки согласно (3), то в совокупности имеем

Таким образом, при определяемом соотношением (5), функция является периодической по q с периодом N и, следовательно, сумма

не зависит от и совпадает с . Лемма доказана.

Если с самого начала была задана функция, определенная только на сетке, то на этой сетке ее можно также представить в форме (1). Действительно, такую функцию можно продолжить на всю прямую, доопределив ее между узлами сетки путем линейной интерполяции. Для непрерывной кусочно-дифференцируемой функции выполняется (2), поэтому в точках сетки после приведения подобных членов получим (4).

Определим скалярное произведение для функций на сетке следующим образом:

(Множитель введен для согласованности получаемых соотношений с непрерывным случаем: если и - непрерывные функции на отрезке [0, 1], то вследствие интегрируемости по Риману

при ). Функции при образуют ортонормированную систему относительно введенного таким образом скалярного произведения. Действительно,

При , суммируя геометрическую прогрессию, имеем

(при знаменатель отличен от 0). Поскольку , то в итоге имеем

Умножая (4) скалярно на , получим равенство

Выражение в правой части образует квадратурную сумму для интеграла

поэтому

при и фиксированном j.

Покажем, что соотношение

в общем случае не имеет места. Пусть . Из (4) получаем , остальные . Таким образом, правая часть (8) есть . Она совпадает с в точках , но, как правило, далека от нее вне этих точек.

Воспользовавшись утверждением леммы, перепишем (4) в виде

Если - достаточно гладкая функция, то величины с ростом j убывают быстро, поэтому и при малых q. Кроме того, при гладкой величины и малы при больших .

Задача 1. Пусть непрерывно дифференцируема. Доказать, что

при .

Напомним, что это приближенное равенство обращается в точное равенство в точках сетки. Способ аппроксимации функции

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

Игнорирование установленного нами факта о равенстве функций и в узлах сетки при часто является источником получения неверных соотношений.

При решении одной инженерной задачи потребовалось определить первую собственную частоту колебаний конструкции. Было принято решение написать нестационарное уравнение, описывающее процесс колебаний, вывести на печать график и из рассмотрения графика определить частоту. Соответствующее уравнение, которое мы условно будем обозначать , решалось методом конечных разностей. Для контроля над надежностью результата производился повторный расчет с вдвое меньшим шагом. Графики кривых, полученных в результате расчетов, совпали с точностью до 10%. Однако из сравнения с экспериментом оказалось, что полученная частота отличается от истинной в десятки раз. Причина недоразумения заключалась в том, что график решения строился с шагом , существенно большим периода колебаний решения задачи. Решение было близко к функции , где близко к четному числу . Поэтому как на сетке с шагом , так и на вдвое более мелкой с шагом получался график одной и той же функции .

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

Рис. 4.3.1.

Существует соответствие между задачей приближения функций линейными комбинациями многочленов Чебышева и тригонометрическими многочленами. Пусть на отрезке функция приближается линейными комбинациями . Замена переменных сводит исходную задачу к задаче приближения функции линейной комбинацией .

Справедливо равенство

Следовательно, задача наилучшего приближения в норме, соответствующей скалярному произведению , эквивалентна задаче приближения в норме, соответствующей скалярному произведению . Точно так же существует соответствие в случае задач интерполяции и наилучшего приближения в равномерной метрике. Задача интерполирования функции многочленом по узлам - пулям многочлена Чебышева — после такой замены сводится к задаче интерполирования функции при помощи тригонометрического многочлена по узлам , образующим равномерную сетку.