5.2. Метод Сильвестра-Габихта псевдоделения субрезультантных PRS

В этом разделе мы детально изучаем метод Сильвестра-Габихта псевдоделения субрезультантных PRS. По существу мы собираемся показать, почему значения указанные в разд. 5.1.1 в связи с алгоритмами Сильвестра и Габихта PRS, делят член PRS. В этом месте читателя просят вновь просмотреть свойства определителей в приложении в конце этой книги.

5.2.1. Алгоритм Сильвестра редуцированных (субрезультантных) PRS

В своей статье 1853 г. Сильвестр разработал мегод вычисления полной последовательности полиномиальных остатков над целыми числами; более того, он сохранял коэффициенты членов PRS насколько возможно малыми, удаляя их распределенные сомножители (используя терминологию Сильвестра), а не их содержание (операция, включающая вычисление наибольшего общего делителя целых чисел). Следует также отметить, что Сильвестр интересовался вычислением последовательностей Штурма (рассматриваемых в гл. 7), где вычисляется противоположный для каждого полиномиального остатка в т.е. Поэтому определители в его доказательстве в точности совпадают с определителями, используемыми ниже, за исключением того, что в них переставлены вторая и третьи строки (Akritas, 1987). (Результанты и субрезультанты определяются в следующем разделе.)

Теорема 5.2.1 (Сильвестр 1853). Пусть

— полная последовательность полиномиальных остатков, Тогда т.е. квадрат старшего коэффициента полинома является делителем полинома

Доказательство. Пусть — коэффициенты какого-либо делимого — делителя где Тогда, как легко видеть, коэффициенты остатка образующие второй делитель, равны

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

видим, что каждый коэффициент второго остатка будет иметь форму блочного определителя [заметим, что, присваивая значение переменной , нам не нужно делить определитель на (почему?)]:

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

Снова разлагая, мы видим, что для некоторых выражений А, В первый член имеет вид

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

Следовательно, после сокращения весь определитель имеет вид и мы видим, что будет входить в качестве сомножителя в этот и остальные коэффициенты полинома

Заметим, что в теореме 5.2.1 мы не можем редуцировать коэффициенты полинома предложение применяется к коэффициентам полиномов и т.д.

Сильвестр указывает, что «тот же самый явный метод может применяться, чтобы показать, что если степень первого делителя была бы на единиц, а не на одну, меньше степени первого делимого, то содержалось бы в каждом члене второго вычета; однако сложность доказательства этим методом возрастает с возрастанием (Sylvester, 1853, р. 419).

Пример. Рассмотрим снова полиномы Как уже говорилось, последовательность полиномиальных остатков, полученная с помощью евклидова алгоритма PRS — это

Пользуясь теоремой 5.2.1, вычислим коэффициенты полинома как определители, полученные из матрицы

Эти определители суть

(В действительности они являются субрезультантами и определяются в следующем разделе.) Заметим, что в этом месте мы не мажем выполнить какое-либо деление, поскольку — это первый остаток.

Подобным образом единственный коэффициент полинома получается из определителя

Легко видеть, что в этом случае мы можем разделить без остатка 441 на где и получить гораздо меньший коэффициент.

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

SRSPRS.

Редуцированные (субрезультантные) PRS Сильвестра (Sylvester’s reduced (subresultant) PRS)

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

Выход: Редуцированная (субрезультантная) PRS полиномов .

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

2. [Готово?] Если , то выход.

3. [Вычисление псевдоостатка] Вывести положить и перейти к шагу 2.

Анализ времени работы алгоритма SRSPRS. Время работы этого алгоритма равно

где . Доказательство этого факта использует результанты (обсуждаемые в следующем разделе) и опускается, поскольку оно совпадает с доказательством анализа времени вычислений алгоритма HSPRS, приведенном в разд. 5.2.3. (Кстати, оно совпадает со временем вычислений классического PRS-алгоритма.)

Теорема Сильвестра указывает отношение делимости, существующее между некоторыми членами полных PRS, в качестве результата которого мы можем легко получить существующие отношения делимости. Однако для того, чтобы увидеть, почему работает алгоритм Габихта субрезультантных PRS (который, напоминаем, используется в неполных случаях), нам понадобится более общее отношение делимости, т.е. нам требуется отношение делимости между любыми членами PRS. На это новое отношение делимости намекнул Сильвестр, но впервые оно было представлено Габихтомв 1948 г. Прежде, однако, нам потребуются некоторые дополнительные понятия, обсуждаемые в следующем разделе.