3.7. О вычислении коэффициентов Фурье

Пусть ортонормальная система элементов в пространстве со скалярным произведением и Точная нижняя грань

при фиксированном достигается в случае, когда (см. п. 3.3.)

— коэффициенты Фурье элемента х. Известны (см., напр., [8], [44], [49]) приемы, позволяющие ускорить процесс вычисления коэффициентов Фурье, сократить число вычислительных операций.

Приведем такой прием для вычисления коэффициентов Фурье по тригонометрической системе полиномов. Выражая по формулам Эйлера, запишем ряд Фурье -периодической функции в комплексной форме

Для вычисления коэффициентов Фурье требуется найти интеграл

Зададим на [0,1] равномерную сетку пользуясь формулой прямоугольников, сведем задачу вычисления каждого коэффициента Фурье к вычислению суммы

Назовем "операцией" процедуру вычисления экспоненты для одного а. Как видно из (3.14), для приближенного вычисления коэффициентов Фурье придется произвести операций, перебирая от до В случае, когда число составное, число операций можно сократить. Пусть, к примеру, Представим в виде

Для перебора всех и I достаточно перебрать от до номера от до Имеем

В силу -периодичности функции будет

и, значит, обозначив

получим

Для вычисления величины требуется операций, всех величин операций, поскольку Для вычисления всех сомножителей требуется операций. Общее число требуемых операций равно которое при меньше, чем