Анализ точности БПФ над полем комплексных чисел.

При реализации дискретного преобразования Фурье встает вопрос о погрешности метода. Особенно он актуален, если все величины, которые должны получить являются целочисленными. Например, при умножении многочленов с целочисленными коэффициентами в результате получится многочлен с целыми коэффициентами. Естественно, из-за ошибок округления, в результате получится многочлен не с целыми коэффициентами. Для того чтобы коэффициенты искомого многочлена восстанавливались однозначно необходимо, чтобы результирующая величина ошибок округления метода была менее 0,5. Это налагает требования на точность, с которой вычисляется , а значит и на разрядность промежуточных вычислений. Увеличение разрядности приводит к усложнению алгоритма и увеличению его трудоемкости.

Оценим ошибку округления при выполнении быстрого преобразования Фурье порядка (по формулам леммы 1). Для простоты проведения рассуждений будем считать, что величины вычисляются с погрешностью , а компоненты вектора x известны с точностью .

Из неравенств (под понимается наибольшая из абсолютных величин компонент вектора x ) и унитарности матрицы вытекает . Аналогично устанавливается неравенство . Величина погрешности вычисления по обычным формулам не превосходит . Следовательно, величина погрешности вычисления не превосходит . Теперь легко оценивается погрешность вычисления , где W – диагональная матрица, по диагонали которой расположены корни из 1, величиной . Далее рассуждения можно повторить с вектором y, компоненты которого вычислены с точностью и удовлетворяют неравенствам . Пусть выбрано так, чтобы выполнялось неравенство , тогда . Применим полученные оценки к формулам быстрого преобразования Фурье. В результате получим верхнюю оценку погрешности (при этом должно удовлетворять неравенству ).