5.2.2. Результант двух полиномов

Результанты и субрезультанты существенны для глубокого понимания PRS-алгоритм Габихта, и в этом разделе мы изучаем их свойства. (Сильвестр неявно использовал их.) Великолепной работой является (Netto, 1896); см. также (Bocher, 1907) и (Lipson, 1981).

Рассмотрим два полинома в

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

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

это и есть то условие, которое мы ищем. [Читателю следует отметить, что между и переменной использованной в разд. 2.4 и 3.1.4, нет никакой связи; эта переменная обозначена сокращением слова result (результат).] Группируя строк и столбцов и принимал во внимание, что

имеем

Таким образом, мы видим, что множитель необходим, чтобы сделать целой функцией коэффициентов Очевидно, что

и это выражение мы называем результантом полиномов Поэтому нами доказана следующая

Теорема 5.2.2. Обращение в нуль результанта это необходимое и достаточное условие для того, чтобы уравнения имели общий корень.

Некоторые свойства результантов.

Если , где , то из соотношения (R) вытекает

То

Более того, если с — константа, то из (R) получаем

а поскольку

Наконец, если то все значения - равны нулю, и мы получаем специальный вид

Представление результанта.

Мы не будем вычислять результанты по формуле (R), поскольку тогда нам потребовалось бы прежде вычислить корни полинома . Вместо этого мы представим результант как определитель, который нетрудно посчитать. Чтобы сделать это, рассмотрим следующую систему ( уравнений [мы все еще имеем дело с данными выше двумя полиномами степеней пит соответственно]:

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

и корни этого уравнения определяют величины Воспользовавшись тем, что если мы имеем уравнение

то произведение всех его корней равно мы видим, что если мы разделим наше уравнение степени от v на коэффициент при то свободный член будет равен Поскольку в нашем случае коэффициент при равен (проверьте!), получаем следующее соотношение (заметим, что мы положили и следовательно, определитель — это свободный член уравнения степени ):

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

Субрезультанты — получение коэффициентов членов PRS.

Введем определение субрезультантов, играющих важную роль в наших исследованиях PRS-алгоритмов. Рассмотрим полную последовательность полиномиальных остатков где

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

где первый определитель — это старший коэффициент полинома второй определитель — это коэффициент при и т.д. По причинам, которые объясняются ниже, эти определители называются субрезультантами. [Мы знаем, что для последовательных членов каждый определитель делится на Сравнивая эти определители с результантом полиномов представленным в виде определителя порядка мы легко видим, что коэффициенты полинома получаются следующим образом. Поскольку степень полинома равна удалим из матрицы соответствующей последние (из строк значений с, последние (из ) строк значений d и последние столбца. Таким образом, у нас осталась -матрица т.е. имеет 3 строки и столбцов п. Последовательно вычисляем коэффициентов полинома из определителя (субрезультанта) порядка 3, первые два столбца которого всегда совпадают с а третий последовательно равен при получаем старший коэффициент полинома [Это в точности то, что Сильвестр делал в теореме 5.2.1, чтобы вычислить коэффициенты только полинома

Этот процесс мондао обобщить для вычисления коэффициентов любого члена степени Мы просто должны удалить из матрицы соответствующей последние строк значений с, последние строк значений d и последние столбцов, оставив имеет строк элементов строк элементов Тогда коэффициентов полинома последовательно вычисляются из определителя (субрезультанта) порядка первые столбцов которого всегда равны последний последовательно равен Этот общий способ вычисления коэффициентов любого члена полной PRS был открыт в 1859 г. Ди Брюно [см. (Muir, 1920, р. 327-328)], т.е. Ди Брюно обнаружил, что для полиномов член PRS, равен

где — «распределенный» множитель, для любого значения k.

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

строк элементов с и d и последние столбцов. Однако, удаляя из последовательно последние строк элементов с и d и последние столбцов, получаем пулевые полиномы. Эти факты доказаны в разд.

В нашем обсуждении теоремы 5.2.1 мы уже упоминали, что Сильвестр интересовался вычислением противоположных к полиномиальным остаткам (последовательностью Штурма). Так, для полиномов (ВТ) он вычислял коэффициенты полинома как

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

Индекс Т стоит в честь итальянского математика прошлого века Н. Труди, давшего первое систематическое изложение биградиентов [см. (Muir, 1902, р. 329)]; термином биградиент обозначаем форму результанта, обозначенную нами

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

Отметим, что

Представим теперь теорему Труди в ее первоначальном виде и обозначениях.

Теорема 5.2.3 (Trudi, 1862). Коэффициенты остатка возникающие в ходе выполнения процесса деления Штурма для полиномов

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

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

Доказательство. Локазательство можно найти в книге (Householder, 1970).

Пример. Для полиномов мы имеем две следующие матрицы для соответствующих результантов:

Коэффициенты полинома степени 1 получаются следующим образом.

Используя

и, таким образом,

Используя

и

Что касается полинома являющегося константой, то мы просто вычисляем результант и получаем Читатель может сравнить эти результаты с результатами, полученными в примере разд. 5.2.1. (Заметим, что в этом случае, чтобы получить значение ±49, определитель не нужно ни на что делить.)

Дополнительное свойство результантов.

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

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

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

Эта теорема напоминает нам о соотношении, существующем между двумя полиномами и их наибольшим общим делителем. более подробного исследования снова рассмотрим два полинома в

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

где

Из теорем 5.2.2 и 5.2.4 легко следует, что

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

Пусть теперь

и заменим в (CR) все полиномы соответствующими их выражениями. Тогда, группируя все коэффициенты при равных степенях и полагая все их равными 0, мы получаем систему уравнений, выписанную на стр. 321 (где мы предполагаем ).

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

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

(см. скан)

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

Существование наибольшего общего делителя заданной степени.

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

Теорема 5.2.5. Степень наибольшего общего делителя двух полиномов из кольца равна индексу первого ненулевого определителя среди

где — субрезультант, получающийся из результанта если мы удалим последние i строк коэффициентов так и и последние столбцов, т.е. — это определитель порядка и называется (как мы убедимся, по очевидным причинам) главным субрезулътантным коэффициентом.

Локазательство. Выведем сначала условия, необходимые для того, чтобы полиномы имели наибольший общий делитель степени 1. Пусть

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

с неизвестными коэффициентами Тогда из уравнения

получаем следующую систему уравнений:

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

В этом случае

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

суть необходимые и достаточные условия, чтобы степень наибольшего общего делителя полиномов равнялась 1.

Если, однако, , то

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

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

Поэтому если то мы полагаем

с неизвестными коэффициентами и снова из уравнения

мы получаем следующую систему уравнений:

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

не равен нулю, то мы можем определить неизвестные так, чтобы

В этом случае

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

суть необходимые и достаточные условия, чтобы степень наибольшего общего делителя полиномов равнялась 2. Продолжая таким же образом, мы закончим доказательство теоремы.

В качестве следствия теоремы 5.2.5 мы получаем

Следствие 5.2.6. Необходимым и достаточным условием взаимной простоты двух полиномов от одной переменной является необращение в нуль их результанта.

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

Результаты, аналогичные полученным выше, могут быть получены для где используются те же обозначения (причем различие знаков игнорируется), а именно имеет место

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

Пример. Для полиномов мы получаем следующие субрезультанты

Теорема 5.2.8. Степень наибольшего общего делителя двух полиномов от одной переменной равна индексу первого ненулевого главного субрезультантного коэффициента

Локазательство аналогично доказательству теоремы

В последнем примере мы находим, что откуда заключаем, что степень наибольшего общего делителя полиномов равна 0, т.е.

Имеет место также следующая

Теорема 5.2.9. Если главный субрезультантный коэффициент полиномов является первым ненулевым , то наибольший общий делитель полиномов может быть получен из если мы заменим (а) на последний элемент в последней строке коэффициентов полинома на — элемент, находящийся непосредственно над ним, на — элемент над этим и т.д., — последний элемент в первой строке коэффициентов полинома на — элемент под ним, на — элемент под этим и т. д.

Локазательство. Доказательство основано на теореме 5.2.4, и мы оставляем его читателю в качестве упражнения.

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

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

Пример. Мы уже знаем, что для полиномов следовательно, наибольший общий делитель получается из вычислением определителя

Подобным же образом мы видим, что третий член PRS, получается из

(Сравните это с результатами, полученными в примере, предшествующем теореме 5.2.4.)

В заключение этого раздела дадим следующее

Определение 5.2.10. Дискриминант полинома определяется следующей формулой:

Отметим, что дискриминант дает меру близости корней полинома. Это будет использоваться в методе изоляции корней. Более того, можно доказать, что для нормированного полинома степени

где — производная полинома Дополнительные свойства дискриминанта можно найти в литературе (Berlecamp, 1968).