Программные продукты и системы

Системы полиномиальных уравнений в общем случае решаются построением базиса Грёбнера из базиса, составленного многочленами рассматриваемой системы, и решением системы уравнений, левые части которых являются многочленами, составляющими базис Грёбнера [1]. В числе самых широко распространенных методов для построения базиса Грёбнера – алгоритм Бухбергера и алгоритм Фужера [2–4]. Однако оба они при относительной простоте выполняемых преобразований имеют очень высокую операционную сложность, что затрудняет, а зачастую делает невозможным вычисление базиса.

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

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

Итак, пусть K – поле вещественных чисел, K[x, y] – кольцо многочленов от двух переменных с коэффициентами из K. Рассмотрим некоторый идеал I над кольцом многочленов, в который входят полиномы из системы. Множество H={g, h} является базисом идеала I. Зададим лексикографическое упорядочение мономов в многочленах:

             (1)

Используя операции сложения и умножения над многочленами, входящими в базис H, необходимо редуцировать его так, чтобы построить базис Грёбнера идеала I.

Введем понятие S-полинома [2]:

. (2)

Здесь LT(fi) представляет старший терм многочлена fi(x, y), а LCM(fi, fj) равен наименьшему моному, который делится на старшие мономы многочленов fi(x, y) и fj(x, y). Операцией редуцирования произвольного полинома f(x, y) из K[x, y] относительно H является нахождение такого минимального многочлена r(x, y), который выражается в виде

, (3)

где ai(x, y)ÎK[x, y] и fi(x, y)ÎH.

Базис H можно назвать базисом Грёбнера, если для любых двух полиномов fi(x, y) и fi(x, y) из H выполняется условие

.                                                    (4)

При заданном лексикографическом упорядочении (1) базис Грёбнера будет составлен парой многочленов, удовлетворяющих условию (4), вида

                    (5)

Множество решений системы, составленной из полиномов (5), будет соответствовать множеству решений системы.

Алгоритм нахождения базиса Грёбнера представлен в виде блок-схемы (см. рис.).

На вход алгоритма редукции подается базис H идеала I, составленный из множества полиномов исходной системы уравнений. Каждая итерация алгоритма редуцирования базиса начинается с того, что в базисе H ищется полином fi(x, y) с минимальным старшим мономом, который может быть редуцирован относительно множества полиномов, состоящего из всех полиномов базиса, кроме выбранного полинома. Дальнейшее выполнение алгоритма разбивается на две ветви.

Если такой полином найден, он исключается из базиса и находится остаток r(x, y) от редукции этого полинома. Произвольный полином является редуцируемым относительно некоторого множества полиномов, если в этом множестве есть многочлены, старшие мономы которых являются делителями старшего монома редуцируемого полинома. Редукция полинома – итеративный процесс. Если перед редукцией остаток r(x, y) принять равным исходному редуцируемому полиному fi(x, y), то на каждом шаге уменьшения остатка осуществляется поиск максимального полинома fj(x, y) в множестве H, который может редуцировать остаток r(x, y), и выполняется редукция

, (6)

где LC(r) – коэффициент перед старшим мономом многочлена r(x, y).

Редуцирование по формуле (6) следует продолжать до тех пор, пока остаток r(x, y) не станет нередуцируемым. Когда редуцирование завершено и остаток r(x, y) не является нулевым полиномом, он добавляется в базис H.

Перед добавлением остатка в базис следует провести корректировку коэффициентов для r(x, y). В кольце K[x, y] необходимо найти такие многочлены ag,i(x, y), ah,i(x, y), ag,r(x, y) и ah,r(x, y), чтобы можно было представить полиномы g(x, y) и h(x, y) в базисе H+{r}:

(7)

Если решение системы (7) не находится, значит, при вычислениях в коэффициентах остатка накопилась методическая погрешность из-за способа представления вещественных чисел в памяти ЭВМ. Так как уже имеющиеся в базисе полиномы имеют правильные значения коэффициентов, необходимо откорректировать коэффициенты остатка r(x, y) в соответствии со значениями погрешности для каждого из коэффициентов в системе (7). Эта задача решается подобно задаче редуцирования: сначала определяются значения коэффициентов для полиномов ag,i(x, y) и ah,i(x, y), затем вычисляются разности:

         (8)

Если разности представляют собой нулевые полиномы, то одну или несколько базисных функций fj(x, y) нужно исключить из суммы и повторить операцию. По оставшимся разностям вычисляются коэффициенты полиномов ag,r(x, y) и ah,r(x, y) и корректируются (при необходимости) коэффициенты r(x, y). После этого r(x, y) добавляется в базис H и алгоритм редуцирования базиса идет на очередную итерацию.

По второй ветви алгоритм редуцирования базиса развивается, если в базисе H не найден полином, который может быть редуцирован. В таком случае набор базисных функций должен быть расширен для продолжения редукции. Из всех возможных пар полиномов базиса fi(x, y) и fj(x, y), для которых не выполняется условие (4), нужно найти пару с минимальным LCM(fi, fj).

Если такая пара найдена, редуцированный остаток S-полинома этой пары включается в базис H, предварительно пройдя корректировку коэффициентов, как это было описано ранее. Если же такой пары многочленов в базисе H нет, значит, этот базис полностью редуцирован и является базисом Грёбнера.

Таким образом, в результате работы алгоритма получим базис, составленный из пары многочленов (5). Теперь для решения исходной системы нужно вычислить все корни  полиномиального уравнения одной переменной fy(x, y)=0, подставить по очереди эти значения в многочлен fx(x, y), превращая его в полином одной переменной, и рассчитать соответствующие корни  уравнения .

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

Литература

1.     Прасолов В.В. Многочлены. М.: МЦНМО, 2001.

2.     Buchberger B. Grobner Bases: an Algorithmic Method in Polynomial Ideal Theory / Recent trends in multidimensional system theory, U. Reidel Publishing Company, 1985.

3.     Buchberger's algorithm. URL: http://www.geocities.com/ famancin/buchberger.html (дата обращения: 01.06.12).

4.     Faugere J.C. A new efficient algorithm for computing Grobner bases (F4) // Journal of Pure and Applied Algebra, 1999, no. 139, pp. 61–88.