Составители:
Рубрика:
Теперь из (8.15) и (8.16) вытекает свойство (8.14).
Лемма 3. Положим
c
j
= ω
rev
k
(j)
. (8.17)
Тогда многочлены (8.2) могут быть представлены в виде
q
l,m
= x
2
m
ω
rev
k
(l/2
m
)
(8.18)
Д о к а з а т е л ь с т в о. Воспользуемся индукцией по m.
Случай m = 0 тривиален, ибо согласно формулам (8.6) и (8.14)
q
l,0
(x) = x − c
l
= x − ω
rev
k
(l)
= x
2
0
− ω
rev
k
(l/2
0
)
, что совпадает с
(8.18) при m = 0.
Для проведения шага индукции возьмём m > 0. Согласно пред-
положению индукции
q
l,m−1
(x) = x
2
m−1
− ω
rev
k
(l/2
m−1
)
q
l+2
m−1
,m−1
(x) = x
2
m−1
− ω
rev
k
(l/2
m−1
+1)
из формулы (8.7) имеем
q
l,m
(x) = q
l,m−1
(x)q
l+2
m−1
,m−1
(x) =
= (x
2
m−1
− ω
rev
k
(l/2
m−1
)
)(x
2
m−1
− ω
rev
k
(l/2
m−1
+1)
). (8.19)
Заметим, что l/2
m−1
– чётное число между 0 и 2
k−1
, ибо в соответ-
ствии с (8.3), (8.4)
l = σ · 2
m
, σ = 0, 1, . . . , 2
k−m
− 1,
и потому
ω
rev
k
(l/2
m−1
+1)
= ω
2
k−1
+rev
k
(l/2
m−1
)
=
= −ω
rev
k
(l/2
m−1
)
; (8.20)
в последнем равенстве использовано очевидное соотношение
ω
2
k−1
= ω
n/2
= −1.
Из (8.19), (8.20) и (8.14) следуют равенства
q
l,m
(x) = x
2
m−1
·2
− ω
2rev
k
(l/2
m−1
)
= x
2
m
·2
− ω
rev
k
(l/2
m
)
.
20
Страницы
- « первая
- ‹ предыдущая
- …
- 17
- 18
- 19
- 20
- 21
- …
- следующая ›
- последняя »
