А.6. Быстрое преобразование Фурье

Дискретное преобразование Фурье (ДПФ) рассматривалось в п. 9.7 как линейное преобразование из в

а именно

Введем обозначение:

Тогда

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

Такая сложность вполне приемлема, пока N не велико. В противном случае, а также когда вычислять ДПФ нужно многократно, как это приходится делать при решении уравнений в частных производных, обработке изображений и в некоторых других областях, сложность порядка слишком велика. Одним из действительно важных достижений вычислительной математики было создание алгоритма быстрого преобразования Фурье (БПФ). Современный подход основан на алгоритме Кули-Тъюки, хотя основная идея была известна еще Гауссу.

Для работы алгоритма БПФ необходимо, чтобы число N раскладывалось на возможно большее число сомножителей. Это число максимально, когда N равно степени 2, то есть для некоторого . Ниже рассматривается именно этот случай.

В основе алгоритма БПФ лежит следующее наблюдение. Величины связаны соотношением (см. (А.12)):

Это позволяет расщепить задачу N х N на две подзадачи что приводит к уменьшению сложности с до Но можно продолжить процесс и далее. Каждая из подзадач расщепляется на две подзадачи а значит число умножений уменьшается еще вдвое, и так далее. Таким образом, число умножений можно сократить с до или Это значительная экономия машинного времени. Например, если то сложность уменьшается с 16 777216 умножений до 24576. В общем случае, число умножений уменьшается в раз.

Механизм расщепления -задачи заключается в группировании вместе составляющих с четными индексами и составляющих с нечетными индексами:

Теорема А.6.18. Вычисление ДПФ порядка можно свести к вычислению двух ДПФ порядка

причем

Доказательство. По формуле (9.18),

Сгруппируем слагаемые с четными (нечетными) индексами:

По формуле (А. 13):

При это немедленно приводит к формуле . Если запишем . Тогда

и

Подставляя эти выражения в (А.16), получаем (А.15).

Теорема А.6.19. Вычислительная сложность алгоритма БПФ в случае равна

Доказательство. Если обозначает вычислительную сложность БПФ порядка к к (к четное), то по теореме А.6.18:

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

Она безусловно верна при и если она верна при что означает , то при имеем

Таким образом, эта формула верна при всех N вида

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