5.2.3. Алгоритм Габихта субрезультантных PRS

Как мы видели, Сильвестр указал отношение делимости, существующее между некоторыми членами полной последовательности полиномиальных остатков, и это явилось основанием для алгоритма редуцированных (субрезультантных) PRS. Однако, для того чтобы иметь дело с неполными PRS, нам требуется отношение делимости, существующее между любыми членами PRS. Это новое отношение делимости было сформулировано Габихтом в 1948 г. и составляет предмет данного раздела. [Удивительно простое доказательство см. в (Gonzalez et al., 1990).]

Чтобы доказать теорему Габихта, рассмотрим два полинома в

степеней соответственно и последовательность полиномиальных остатков , где индекс указывает степень соответствующего полинома. Отметим, что Габихт интересовался в первую очередь последовательностями Штурма, и

это объясняет выбор степеней первых двух полиномов. Многие из представленных ниже результатов справедливы при произвольных степенях двух первых полиномов (читатель легко может определить, когда это имеет место), но мы придерживаемся подхода Габихта.

Как мы напоминали, для полных PRS Сильвестр доказал, что член PRS делится на квадрат i-го главного субрезультантного коэффициента:

Другими словами, квадрат старшего коэффициента полинома делит без остатка полином был определен в теореме 5.2.5]. Для неполных PRS, когда некоторые члены PRS отсутствуют, Габихт доказал, что

где полиномы получены из коэффициентов полиномов таким же образом (объясненным ниже), как полиномы (определенные ниже в теореме 5.2.11) получены из коэффициентов полиномов

Замечание. Читатель должен хорошо разобраться в различии между двумя парами полиномов с верхними индексами, т.е. роль индекса i в них совершенно разная. Для согласованности последняя пара может также обозначаться но мы пользуемся более простым обозначением.

В полном объеме смысл и значение соотношения (НО) будет разбираться позже. Заметим, что для неполных PRS с помощью мы приходим к новым свойствам делимости, сформулированным в конце раздела, которые приводят к алгоритму Габихта субрезультантных PRS, упоминавшемуся в разд. 5.1.1.

Вначале будет доказана

Теорема 5.2.11. Рассмотрим последовательность полиномиальных остатков над целыми числами, в которой индекс обозначает степень соответствующего

полинома; тогда для любого члена этой мы можем найти в два полинома

степеней и — соответственно, таких, что

Доказательство. Локазательство является конструктивным и аналогично расширенному алгоритму Евклида для целых чисел или полиномов над полем, т.е. мы требуем соблюдения соотношения для любого

Очевидно, что при при . Как мы уже видели, чтобы вычислить для мы изменяем их таким же образом, как изменяем значения , а именно, если

где — частное от деления на , то

Теорема 5.2.11 показывает, что расширенный алгоритм Евклида работает также с полиномами над целыми числами. [Если мы сравним выражения в теореме 5.2.11 с выражениями вида

полученными в доказательстве теоремы 5.2.5, мы увидим, что старший коэффициент полинома (где ) — произвольный член PRS), является субрезультантом и поэтому он называется главным субрезультантным коэффициентом.]

Мы видели, что произвольный член может быть вычислен из соответствующего главного субрезультантного коэффициента, как описано в теореме 5.2.9; подобным образом

мы видим, что полиномы в выражении также могут быть получены из главного субрезультантного коэффициента следующим образом:

Определитель для в точности совпадает с определителем для кроме последнего столбца, который равен (начиная сверху).

Определитель для в точности совпадает с определителем для кроме последнего столбца, который равен (начиная сверху).

[Итак, если нам нужны последовательности Штурма и мы пользуемся формой Брюно для определителя, то во всех определителях присутствует сомножитель в этом состоит различие между формами Брюно и Труди для результанта. Ниже мы этот сомножитель будем игнорировать.]

Таким образом, полиномы могут быть непосредственно получены из следующих определителей порядка где мы меняем местами строки и столбцы:

Мы можем также представить соотношения (HI) в виде

где рассматриваются как операторы, действующие на любой паре полиномов степеней .

Пример. Рассмотрим полиномы , т. е. и вычислим так что

Заметим, что в этом случае и, следовательно, определители имеют порядок так что

и

что нам уже известно. [Читателю следует проверить, что мы получим те же полиномы , используя расширенный алгоритм Евклида для полиномов, описанный в теореме 5.2.11.] Затем для вычисления , таких, что нам нужно вычислить два определителя порядка 5:

и

следовательно,

Заметим, что в приведенном примере выполняются удивительные соотношения:

Как мы уже говорили, старший коэффициент члена PRS равен и отличается знаком от игнорируя различие в знаках, мы обозначаем оба результанта Поэтому в общем случае

Эти формулы проверяются несложными вычислениями, если рассмотреть определители вместе с тем фактом, что порядок первого из них равен , а двух последних см. также предыдущий пример.

Таким образом, для каждого индекса мы создали множество из трех полиномов сейчас мы свяжем их попарно следующим образом.

Теорема 5.2.12 (Габихт). В предположениях теоремы 5.2.11 для

Доказательство. Мы имеем

Умножая первое соотношение на , а второе — на мы получаем

Левая часть соотношения — это полином степени , поскольку степень полинома равна , а степень полинома — только . Однако, поскольку степень полинома равна , определитель в правой части соотношения является целой константой; в действительности эта константа равна — частному от деления старших коэффициентов полиномов которое по первой из формул равно (проверьте это для последнего примера). Таким образом, мы доказали два первых соотношения (НЗ). Последнее легко получается после умножения соотношений из на соответственно.

[Формулы (НЗ) можно расширить, чтобы включить полагая . В этом случае формулы остаются справедливыми; более того, если мы воспользуемся разницей в знаках, которую до сих пор игнорировали, и положим (посмотрите, как это получилось в последнем примере), то (R3) справедливо для , а для положим

Выведем сейчас соотношение между и более общее соотношение между для

Из двух последних соотношений (НЗ) мы получаем для

Умножая первое из этих соотношений на а второе — на получаем

что в соответствии с (НЗ) равно

где — полином степени 1, который мажет быть выражен через коэффициенты полиномов (например, коэффициент при равен ). С использованием введенных ранее операторов можно переписать в виде

Основываясь на этом уравнении, рассмотрим теперь более общий случай.

Теорема 5.2.13 (Habicht, 1948). В предположениях теоремы 5.2.11, если положить то

Доказательство. Пользуясь обозначениями этой теоремы, полиномы определенные в теореме 5.2.11, можно записать как соответственно. Поэтому полиномы и могут быть вычислены исходя из определителя, элементами которого являются коэффициенты полиномов таким же образом, как полиномы могут быть вычислены исходя из определителя, элементами которого являются коэффициенты полиномов

Фиксировав t, образуем полиномы

Заметим, что полиномы выражаются через а полиномы — через (теорема 5.2.11); поэтому коэффициенты первых полиномов больше, чем коэффициенты вторых, и мы хотим доказать, что

Для простоты обозначений положим также {напомним, что и образуем полиномы с рациональными коэффициентами

Обозначим старшие коэффициенты полиномов через соответственно. Покажем, что выполняется для любых и этим закончим доказательство теоремы.

Очевидно, что а по (HG) мы имеем поэтому мы можем последовательно заключить, что также Однако по определению операторов повторным применением использованных выше рассуждений мы устанавливаем, что выполняется для значений т. е.

Следовательно, разделив для каждого индекса j соответствующее соотношение на

получаем

Эта теорема показывает, что (без вычисления наибольших общих делителей) наименьшие коэффициенты членов PRS получаются как субрезультанты результанта т.е. мы получаем наименьшие коэффициенты для членов PRS только при использовании коэффициентов полиномов Однако вычисление определителей является трудоемким процессом, и члены PRS вычисляются путем псевдоделения; коэффициенты членов PRS тогда получаются большими, но мы уже знаем, на что их нужно делить.

Пример. Рассмотрим снова полиномы из последнего примера для которых мы уже знаем, что Очевидно, что в этом случае и, таким образом, мы можем вычислить Мы имеем и

Поэтому и по теореме старший коэффициент полинома , возведенный в квадрат, делит —441, т.е.

В дальнейшем мы полагаем и рассмотрим, что случится, если один или несколько главных субрезультантных коэффициентов равны нулю, т.е. мы выведем формулы, составляющие основу алгоритма Габихта субрезультантных PRS [формула (Н) разд. 5.1.1]. Наши исследования основаны на соотношениях

Рассмотрим последовательность полиномиальных остатков где для всех

и пусть — член этой последовательности, такой, что

т. е. степень полинома равна . Тогда следующие соотношения легко выводятся из и вида полинома [напомним, что определители получаются таким же образом, как и определители и , т.е. из , где заменено на на j и коэффициенты полиномов — коэффициентами полиномов равны нулю.

Формулы пунктов составляют основу алгоритма Габихта субрезультантных

Пример. Рассмотрим неполную последовательность полиномиальных остатков Мы видим, что здесь но т.е. во введенных выше обозначениях и Тогда, чтобы вычислить мы применяем случай и получаем

где и коэффициенты полиномов заменены коэффициентами полиномов . Поэтому из , получаем

и

т. е. — это полином, пропорциональный полиному Читателю предлагается в качестве упражнения вычислить используя случай

Рис. 5.2.1. Лакунарная структура PRS; отрезок длины представляет полином степени к (Габихт).

Представляет интерес рис. 5.2.1.

Используя (Н) из разд. 5.1.1, получаем следующий алгоритм.

HSPRS. Субрезультантные PRS Габихта

Вход: Два ненулевых полинома

Выход: Субрезультантная PRS полиномов

1. [Инициализация]

2. [Готово?] Если то выход из алгоритма.

3. [Вычисление псевдоостатка] где вычислено из соотношения (Н) разд. 5.1.1 (см. также ниже упр. 3 к этому разделу); положить и перейти к шагу 2.

Анализ времени работы алгоритма HSPRS. Пусть Тогда в худшем случае имеется полиномиальных псевдоделений над целыми числами, которые выполняются (см. также разд. 3.1.1) за время где а — наибольший коэффициент, появляющийся в ходе вычислений [аналогично времени, требуемому для вычисления произведения . Множитель соответствует имеющему место умножению целых чисел (коэффициентов). Наибольший коэффициент, появляющийся в ходе вычислений, , что в свою очередь ограничено по неравенству Адамара

где обозначают элементы результанта. Если положить , то и время всех полиномиальных псевдоделений равно