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

Если продолжать процесс, то можно попытаться уменьшить число умножений при вычислении сз> (х):

с(3) (х) = g(3) (X) (х) = {ах + ах f 1) {dx + dx f do). Выберем

b (x) =x(x + 1)(х + x + I);

тогда

c(3) (X) = (a3d2) b (X) f Rb (.) [сЗ) (x)].

Для вычислени,р аЫ необходимо только одно умножение. Вычеты даются равенствами

g(3) (3) (х = а

d<3) С) (X) = do,

d3) (2) (Х) = do + di + d„

d(3) (3) = + dj X + (do + d,).

Тогда

(0 (x) = d(3) (1) (x), (2) (x) = d<3) (2) (x), c(3) (3) (x) = ad<3) (3) (x).

Для вычисления c) (з) (л;) необходимо два умножения. Мы уже использовали одно умножение для вычисления аМа, так что всего для вычисления с-) (х) с помощью выписанной выше процедуры требуются три умножения. Так как непосредственное вычисление сз> (х) также включает три умножения, то предпочтение надо отдать ему.

11.3. БЫСТРЫЕ ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Дискретное преобразование Фурье (ДПФ) в той форме, как оно задается:

Vj = I o.4Vi, »=о

требует порядка умножений и сложений. Для составного п имеется несколько способов превратить такое преобразование

Vj = I] aVl

Число умножений

БПФ-алгоритм Кули-Тьюки [1965]

п = пп",

i = i+ni", г о, ...,п -\, /" = 0, ...,п"-1 j = n"j + r, j=.0.....n-l, r = 0, ...,n"-l.

/7"-1

i"=0

Число умножений » n (n Ч- n") -f n

БПФ-алгоритм Гуда-Томаса ([I960], [1963])

n = nn", n и n" взаимно просты Перестановка входных символов

i - iN"tr + i"Nn {mod п).

., ., , ,, , f I - iN"n +

\<-\ причем f(modn") J ,,, , , ,,„ „

Nn + N"n" - 1

Перестановка выходных символов / = /V"/ (mod n) y" = yV/(modn")

i = n"j -fn/"(modn)

rn"-1

1 ,/"= I P--

i-=0

i"=0

Число умножений л; n (n -f n")

Рис. 1J.3. Некоторые алгоритмы БПФ.

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

Уг.г = 1Г>

п"-1 ("=0

Хотя эта формула сложнее исходной, число сложений и умножений при вычислении по ней гораздо меньше, а именно требуется не более п {п -Ь п" + 1) умножений по сравнению с п, необходимых в исходном варианте. Заметим, что при каждом значении i внутренняя сумма представляет собой -точечное преобразование Фурье и при каждом значении i" внешняя сумма представляет собой п-точечное преобразование Фурье. Если соответствующая длина является составным числом, то каждое из этих преобразований в свою очередь можно упростить с помощью быстрого преобразования Фурье. Преобразование длины п с делителями щ таким образом представляется в форме, требующей около niUt умножений.

БПФ-алгоритм Кули-Тьюки можно наглядно представить в виде отображения двумерной таблицы в двумерную таблицу, пример которого для п = 15 и п = 21 приведен на рис. 11.4. Преобразование Фурье сначала применяется к каждой строке, а затем к каждому столбцу. Перед применением преобразования Фурье к столбцам производится поэлементное умножение. Отметим, что компоненты спектра упорядочены иначе, чем компоненты

Начнем с БПФ-алгоритма Кули-Тьюки. Предположим, что п = пп". В выражении для преобразования Фурье сделаем следующую перестановку входных и выходных символов:

1 = i + пЧ", i = О, п - 1, Г = 0, п"-и

j = п"Г + /", / = о, /г - 1, /•" = 0, п"-\.

Тогда

Уп-г+г = "l асч-"-") ("Г+Г)г;,. „,,„.

Раскроем скобки в показателе степени и положим а" = у и а"" = р. Так как порядок элемента а равен пп", то член а""""-" = = 1 можно опустить. Определим теперь двумерные переменные, которые также обозначим через v и V, задавая их равенствами

Vi, i" = Viini", i" = О,.. ., n - 1,

i" = 0.....

Vj-. Г=Уп"Г+Г /=0,..., -1,

i" = Q,...,n"-\.

Это задает отображение входного и выходного векторов данных в двумерные таблицы, причем