Составители:
Рубрика:
Нетрудно видеть, что для каждого корня ω
j
, для которого x−ω
j
входит в q
1
(x), вычисление остатка P (x) при делении на x −ω
j
эк-
вивалентно вычислению остатка r
1
(x) при делении на тот же бином
x −ω
j
. Рекурсивное применение этого соображения (как видно да-
лее) приводит к значительной экономии.
Заметим также, что при перемножении пар одночленов вида x−
ω
j
, а также при перемножении пар полученных произведений и т.д.
на каждом шаге можно иметь дело лишь с одночленами вида x
j
−c
при подходящем упорядочивании исходных точек ω
0
, ω
1
, . . . , ω
n−1
.
8. Более точное описание алгоритма БПФ
Пусть
0
,
1
, . . . ,
n−1
(8.1)
– некоторая перестановка элементов ω
0
, ω
1
, . . . , ω
n−1
, которая будет
указана впоследствии.
Определим многочлены q
l,m
(степени 2
m
) формулой
q
l,m
=
l+2
m
−1
Y
j=l
(x −c
j
) (8.2)
для индексов l и m, удовлетворяющих условиям
0 ≤ m ≤ k, 0 ≤ l ≤ 2
k
− 1, l = σ · 2
m
, σ = 0, 1, . . . (8.3)
l + 2
m
− 1 ≤ 2
k
− 1. (8.4)
Тем самым
6
q
0,k
(x) = (x −c
0
)(x − c
1
) . . . (x − c
n−1
), (8.5)
q
l,0
(x) = (x − c
l
). (8.6)
Ввиду определения (8.2)
q
l,m
(x) = q
l,m−1
(x)q
l+2
m−1
,m−1
(x). (8.7)
Нетрудно видеть, что
7
существует ровно 2
k−m
различных мно-
гочленов q
l,m
со вторым индексом, равным числу m. При этом каж-
дый бином x − c
l
делит ровно один из этих многочленов.
8
6
Проверить формулы (8.4), (8.5), (8.6).
7
Доказать существование указанного числа многочленов q
l,m
8
Доказать последнее утверждение.
17
Страницы
- « первая
- ‹ предыдущая
- …
- 14
- 15
- 16
- 17
- 18
- …
- следующая ›
- последняя »
