5.3. Метод матричной триангуляризации субрезультантных PRS

Мы видели, что метод Сильвестра-Габихта псевдоделения субрезультантных PRS включает в себя два алгоритма: алгоритм Сильвестра редуцированных (субрезультантных) PRS (основанный на статье Сильвестра 1853 г.), очень хорошо работающий для полных PRS, и алгоритм Габихта субрезультантных PRS (основанный на статье Габихта 1948 г.), более предпочтительный для неполных PRS. Заметим, что алгоритм Габихта субрезультантных PRS может быть использован для полных PRS, но за счет дополнительных затрат. Более того, мы не можем a priori сказать, будет получающаяся PRS полной или неполной.

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

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

помощью теоремы 5.3.6. Следует заметить, что результант в форме Сильвестра впервые используется в современной литературе. (См. также историческое замечание 2.)

5.3.1. Гауссово исключение и полиномиальное деление

Рассмотрим полиномы над целыми числами . Из евклидовости мы знаем, что существуют единственные полиномы с целыми коэффициентами такие, что (в этом месте читателю следует посмотреть еще раз алгоритм PDF). Пусть

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

Чтобы убедиться в этом, рассмотрим упомянутые выше полиномы и сформируем -матрицу М:

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

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

Пример. Рассмотрим полиномы Тогда

и, приведя ее к верхней треугольной форме, получаем

откуда заключаем, что псевдоостаток от деления на равен (Читателю следует заметить, что коэффициенты здесь меньше, чем полученные непосредственным псевдоделением.)

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

То есть при i к строки не меняются, а при мы получаем в соответствующих строках 0 в нижнем треугольнике. [См. также (Малашонок, 1983, 1986).]

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

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

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

После первого преобразования, мы получаем матрицу

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

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