А. А. Самарский, А. В. Гулин

§ 5. Быстрое дискретное преобразование Фурье
Наибольшее число действий в методе Фурье требуется для вы­
числения сумм (3), (4). Эти суммы имеют вид
S,- —
N-i
2 2*sin
ft=l
n k j _
.
.
2
N • 
1
’ ’
N -
1,
0)
где 
z
h— заданные числа.
Для непосредственного вычисления всех Sj, /'= 1, 2, . . . ,
N—
1, 
требуется, как уже отмечалось, 
(N
—I ) 2 умножений. Сейчас мы, 
следуя [21], изложим метод вычисления сумм вида (1), требую­
щий 
0 ( N \ n N )
действий умножения. Такое ускоренное вычисление
Tiki
сумм основано на том, что среди чисел s in -^ - > 
k =
1 , 2 , . . . ,
N
—1,
/ = 1 , 2, . . . ,
N
— 1, есть много одинаковых. Поэтому можно пере­
группировать слагаемые и уменьшить тем самым число умножений. 
Для дальнейшего удобно преобразовать сумму (1) к виду
N - 1
Sj
= 2 г*sin
а
=1
2 л 
kj
2 
N
27V — 1
= 2 ZfeSin
k=o
Inkj
2 
N
’
где полагаем 
za = zN= z N+l =
. . . =
2
2N_, = 0. Обозначим 
M = 2N
и 
рассмотрим более общую задачу о вычислении суммы
М-1 . 2
п
4/ 
М-1
V j —
2
2kel 
м
= 2
ZkW>!' '
ft=0 
k=Q
где
. 2Л
w — е м
(2)
и 
i
— мнимая единица. Итак, будем вычислять суммы
М-1
Vj
= 2
ZkWki
’ 
/ = о, l , . . . , м — l. 
(3)
ft—
о
Ясно, что Inm 3 = Sj для действительных 
zk.
Для дальнейшего суще­
ственным является условие Л1 = 2т, т > 0, означающее, что число 
точек сетки 
N — 2m~l
является степенью двойки.
Представим число 
k
в формуле (3) в двоичной системе 
k =
= ka + 2ki + 22k2 + . . . + 2
где 
ki
либо нуль, либо единица.
334

---

Обозначим
k
(&т—
1, 
km—
2t • ■
• t 
k
$) t 2* jj 
Z{Ji
o, 
kiy
. . . , 
km—
l) •
Тогда сумму (3) можно записать в виде
И/ =
2
2 (fe0l Alf . . . , fem_x) до(,г° ^ ‘+' • 
=
*0 А. • • • 
tkfti—
i
= 2 ^ 0/" 2 ^ 2fei/ • •. 
2
ДО'
*m- lk>n-l!'Z(k0, ku . . . , km-,)
*o=o 
L*.=l 
l!m-i
Преобразуем внутреннюю сумму
2
до2™
(£0, /гь . . . , 
k,n-l).
i—0
(4)
(5 )
Представим число 
j
в двоичной системе 
j= jo + 2ji + - ■
. + 2m_1/m_1. 
Тогда получим
(KJ2m-1Am_1/o) 
_ _ _ (ш*№'1*т-1/т-1). 
(6)
В этом произведении все сомножители начиная со второго рав- 
ны единице. Действительно, 
w 
m~x t=w
m_1 =
w
и, вспо-
миная выражение (2) для до, получим дом= 1, до2'" lfe'n_l2/‘= 1, по­
скольку 
равно либо нулю, либо единице.
Точно так же равны единице и последующие сомножители в