ПРИЛОЖЕНИЕ П7.3. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Недавним новшеством в спектральном анализе является алгоритм быстрого преобразования Фурье (БПФ). С помощью этого алгоритма дискретное преобразование Фурье вычисляется гораздо быстрее, чем с помощью прямого метода, приведенного в разд. 2.1.2, и с той же самой точностью. Так, используя прямой метод для вычисления дискретного преобразования Фурье ряда из членов, потребовалось бы приблизительно операций, в то время как БПФ требует лишь операций. Экономия времени вычислений может быть очень велика, если нужно проводить анализ Фурье длинных рядов. Например, для вычисления с помощью БПФ коэффициентов Фурье ряда из членов [1] требовалось около 5 сек на вычислительной машине в то время как для прямого метода нужно было около 30 мин.

Важность БПФ для спектрального анализа заключается в том,

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

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

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

а) необходимо ли брать разности или нет,

б) где выбрать подходящие точки отсечения,

в) какая требуется величина выравнивания при анализе взаимной корреляции двух рядов.

Описание алгоритма быстрого преобразования Фурье. Полное описание БПФ приведено в [2], а история его открытия и повторного открытия изложена в [3]. Эти статьи входят в специальный выпуск журнала [4], где помещены также статьи об использовании БПФ при вычислении некоторых других преобразований [5, 6]. Мы будем следовать изложению [2].

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

Каждый из рядов содержит членов, и преобразования Фурье этих рядов имеют вид

где верхний индекс преобразованных величин указывает число членов ряда, которое совпадает с числом членов преобразования.

Величины связаны следующими соотношениями:

Кроме того,

так что

Следовательно, окончательный результат равенств имеет вид

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

вести соответствующий вариант формулы (П7.3.5), который выразит преобразования через преобразования рядов длиной

Для рядов длины эту процедуру можно продолжать до тех пор, пока расщепление не приведет к рядам, состоящим из одного члена; в этом случае преобразование Фурье этого члена совпадает с ним самим. В случае если не равно степени двойки, расщепление на два ряда продолжается до тех пор, пока либо легко взять преобразование Фурье вспомогательного ряда, либо пока не встретится новый множитель скажем 3. Процедура при этом остается той же самой, что и выше, с той лишь разницей, что очередной вспомогательный ряд расщепляется на три ряда. Подробности приведены в [2]. Ниже разобран пример.

Пример. Рассмотрим ионосферные данные из гл. 2, где Данные таковы:

Расщепление на два дает следующие ряды:

Расщепление на два дает ряды

Преобразование Фурье рядов уже нетрудно вычислить. Каждое из них состоит из трех членов, как показано ниже.

Затем с помощью формулы (П7.3.5) вычисляются преобразования Фурье Например,

Преобразование получается аналогично, и, сводя вместе получаем таблицу.

Комбинируя эти значения по формуле получаем оконча тельное преобразование Например,

Полное преобразование имеет вид

С точностью до сдвига фазы, вызванного изменением начала отсчета времени, эти значения совпадают со значениями, приведенными в табл. 2.2, которые были вычислены с помощью метода разностного уравнения, описанного в Приложении или же с помощью прямого метода гл. 2.

ЛИТЕРАТУРА

(см. скан)