Составители:
Рубрика:
Оказывается можно всегда работать с многочленами с целыми
коэффициентами, если домножать P (x) на некоторую степень стар-
шего коэффициента у Q(x) (а именно на степень deg P −deg Q+1).
Тогда мы получим следующую последовательность:
−15x
4
+ 3x
2
− 9, (7.7)
15795x
2
+ 30375x − 59535, (7.8)
1254542875143750x −1654608338437500, (7.9)
12593338755007431009331151992187500. (7.10)
Последовательность многочленов (7.7) - (7.10) называется после-
довательностью Евклида, длина коэффициентов такой последова-
тельности имеет экспоненциальный рост (относительно степеней
исходных многочленов). Однако (Коллинз, Браун) можно выби-
рать числовые множители перед делением многочленов так, что в
соответствующей последовательности (называемой последователь-
ностью субрезультантов) будет наблюдаться лишь линейный рост.
Опишем этот приём (без доказательства) более подробно.
Пусть даны два многочлена P
1
и P
2
с целыми коэффициентами,
а P
3
, P
4
, . . . – соответствующая последовательность для вычисления
НОД, δ
i
= degP
i
−degP
i
+ 1, A
i
– старший коэффициент многочле-
на P
i
. Тогда остаток от деления A
δ
i−1
+1
i
P
i−1
на P
i
всегда является
многочленом с целыми коэффициентами; его будем записывать в
виде β
i+1
P
i+1
, где β
i+1
подлежит определению. Алгоритм Евклида
соответствует выбору β
i+1
= 1. Если взять
β
3
= (−1)
δ
i+1
, (7.11)
β
i
= −A
i−2
ψ
δ
i−2
i
, (7.12)
где ψ
i
задаются формулами
ψ
3
= −1, ψ
i
= (−A
i−2
)
δ
i−3
ψ
1−δ
i−3
i−1
,
то (по теореме о субрезультантах) все P
i
окажутся многочленами с
целыми коэффициентами, а длина коэффициентов растёт не более,
чем линейным образом.
В нашем примере получаем последовательность
P
3
= 15x
4
− 3x
2
+ 9, (7.14)
48
Страницы
- « первая
- ‹ предыдущая
- …
- 45
- 46
- 47
- 48
- 49
- …
- следующая ›
- последняя »
