5.3.3. Гауссово исключение + результант в форме Сильвестра = метод матричной триангуляризации субрезультантных PRS

До сих пор нам встречались результанты в формах Брюно и Труди; в действительности в литературе обе эти формы обычно называются формами Сильвестра. Однако мы будем называть результантом в форме Сильвестра описываемый ниже результант; эта форма была «погребена» в статье Сильвестра 1853 г. и упоминалась только в статье Ван Влека (Van Vleck, 1899). Сильвестр указывает (с. 426 его статьи 1853 г.), что он получил эту форму в 1839 или 1840 г., а несколькими годами позже ее воспроизвел, не зная о ней, также Кэли. Именно результант в форме Сильвестра образует основу метода матричной триангуляризации субрезультантных PRS.

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

Сильвестр получил эту форму результанта (известную также как элиминант) из системы уравнений

и указал, что если мы возьмем к пар из выписанных выше уравнений, то наивысшая степень переменной появляющаяся в некотором из них, равна Поэтому мы смажем исключить такое количество степеней что будет наивысшей неисключенной степенью и будет степенью одного из членов последовательности (Штурма) полиномов, противоположных (со знаком «минус») к полиномиальным остаткам, порожденной полиномами это доказано в теореме 5.3.4. Более того, Сильвестр показал, что полиномиальные остатки, полученные таким образом, являются тем, что он назвал упрощенными вычетами, т.е. коэффициенты являются наименьшими из тех, что можно получить без вычисления наибольших общих делителей целых чисел и без введения рациональных чисел. Другими словами, полиномиальные остатки освобождены от соответствующих распределенных сомножителей (используя терминологию Сильвестра). (Этот факт очевиден после нашего обсуждения теоремы Габихта, поскольку единственные коэффициенты, входящие в этот результант, — это коэффициенты исходных полиномов, а не остатков.)

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

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

а второй коэффициент равен

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

В качестве упражнения читателю предлагается вычислить

В общем случае, если имеется последовательность полиномиальных остатков мы можем получить (противоположные) коэффициенты члена как миноры, образованные первыми строками матрицы с поочередным приписыванием к первым столбцам (-матрицы] каждого из оставшихся. Полиномы, образованные таким образом, пропорциональны полиномам, полученным с использованием соответствующих процедур для результантов в формах Брюно и Труди; более того, в случае неполных PRS полиномы следуют образцу, данному на рис. 5.2.1 (доказательство дано ниже).

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

Чтобы доказать, что члены PRS, полученные описанным выше способом, составляют последовательность Штурма, нам понадобится следующая

Лемма мультипликативные правила для вычисления произведения определителя на один из его миноров). Читателю следует посмотреть (Muir, 1882, р. 118, Art. 90). Произведение определителя на любой из его миноров М может быть выражено

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

Пример. Рассмотрим определитель

который мы обозначаем и его минор

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

Теорема 5.3.4 (Van Vleck, 1899). Рассмотрим в полиномы Тогда последовательность полиномов, образованных из первых строк матрицы является последовательностью Штурма.

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

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

Из приведенных выше рассуждений видно, что результант в форме Сильвестра мажет дать нам последовательность Штурма двух полиномов (последовательность их полиномальных остатков, домножаемых на —1), являющуюся в общем случае полной последовательностью полиномиальных остатков. Более того, и это наиболее существенно: для того чтобы найти коэффициенты, требуется вычислять определители. Это следует из того, что в исходном определителе элементы любых двух последовательных строк совпадают с элементами двух предыдущих строк.

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

Теорема 5.3.5 (Van Vleck, 1899). Если мы приведем , матрицу, соответствующую результанту в форме Сильвестра, к верхней треугольной форме , то четные строки матрицы дают коэффициенты последовательных полиномиальных остатков (Штурма). Коэффициенты, взятые из данной строки, умножаются на где k — число отрицательных «составляющих» на главной диагонали выше рассматриваемой строки.

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

Пример. Пусть тогда

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

Замечание. Если мы рассмотрим строки обеих матриц этого примера, то увидим, что каждая из них соответствует данному полиному, степень которого на единицу меньше числа элементов, заключенных между левыми и/или правыми нулями. Небольшая сложность, которая может возникнуть при такой реализации, состоит в том, что один или несколько коэффициентов при младших степенях могут быть нулевыми. В этом случае степень полинома легко определить, рассматривая все строки верхней треугольной матрицы. Однако эта проблема не возникает, если мы изменим представление, используя, например, связные списки.

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

Теорема 5.3.6 (Akritas, 1986). Пусть — два полинома степеней пит соответственно, . Пользуясь алгоритмом Доджсона, приведем матрицу соответствующую к верхней треугольной форме Пусть — степень полинома, соответствующего i-й строке матрицы и пусть член (полной или неполной) последовательности полиномиальных остатков для Тогда если находится в i-й строке матрицы то коэффициенты полинома получаются из строки матрицы где j — наименьшее целое, такое, что [Если то и ассоциируются с первой строкой матрицы

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

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

Заметим, что в качестве частного случая теоремы 5.3.6 мы получаем теорему 5.3.5 для полных PRS. Мы видим, таким образом, что на базе теоремы 5.3.6 мы имеем другой метод субрезультантных PRS для вычисления последовательности полиномиальных остатков и наибольшего общего делителя двух полиномов. Этот метод, в котором не выполняется явное деление, с единой позиции рассматривает как полные, так и неполные PRS и дает наименьшие коэффициенты, которые можно ожидать без вычисления наибольших общих делителей коэффициентов. Как мы уже указывали в разд. 5.1.1, в некоторых случаях коэффициенты меньше тех, которые получаются при использовании метода Сильвестра-Габихта псевдоделения субрезультантных

Мы имеем следующий алгоритм (примеры были даны в разд. 5.1.1).

ASPRS.

Матричная триангуляризация субрезультантных PRS (Matrix-Tbiangularization Subresultant PRS)

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

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

1. [Инициализация] Сформировать матрицу соответствующую результанту

2. [Основной шаг] Используя алгоритм Доджсона (D), описанный выше, привести к верхней треугольной форме Тогда члены PRS получаются из строк матрицы согласно теореме 5.3.6.

Анализ времени работы алгоритма ASPRS.

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

Пользуясь формулами

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

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

где Таким образом, время умножения на себя равно

а поскольку имеется таких умножений, мы получаем

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