Университет города Переславля "Алгоритмы непрерывной математики" осенний семестр 1998-99 учебного года С.В.Дужин Лекция 1 Алгоритм Бухбергера Всякую систему линейных уравнений можно решить путем приведения ее матрицы к ступенчатому виду по методу Гаусса. Аналогом метода Гаусса для произвольных систем полиномиальных уравнений является алгоритм Бухбергера. При этом имеют место такие соответствия: линейные системы нелинейные системы линейное многообразие алгебраическое многообразие пространство линейных функций алгебра многочленов подпространство идеал ступенчатая матрица базис Гребнера Основное действие в методе Гаусса -- это добавление к одному уравнению другого, умноженного на подходящий множитель, с тем, чтобы обратить в ноль коэффициент при первой по порядку переменной этого уравнения. Для нелинейных уравнений аналогом этого действия является редукция одного многочлена по модулю другого. Многочлен от нескольких переменных -- это сумма нескольких термов. Терм -- это моном с коэффициентом. Моном -- это произведение переменных в целых неотрицательных степенях (в частности, когда все степени равны 0, мы получаем моном 1 и, соответственно, свободный член многочлена). Для определения редукции мы должны предполагать, что все члены (или мономы) обоих многочленов определенным образом упорядочены, т.е. для любых двух мономов мы можем сказать, который из них старше, чтобы при упорядочении поставить его вперед. Наиболее употребительный порядок на множестве мономов -- лексикографический, т.е. два монома сравниваются сначала по степени переменной x_1, если у одного монома эта степень старше, то он объявляется старшим из двух, если равны, то сравниваем степени по переменной x_2, и т.д. Более подробно о различных способах задания порядка на множестве мономов будет рассказано в следующей лекции. Если фиксирован какой-то порядок на мономах, то самый старший моном многочлена f (первый, если многочлен записан по порядку) называется ведущим и обозначается lm(f). Определение. Пусть f и g --- два многочлена от одного и того же набора переменных, lm(f) и lm(g) --- их ведущие мономы. Редукция f по модулю g определена, если lm(f) делится нацело на lm(g), и задается правилом: g f --> f - (lm(f)/lm(g))g Пояснение. Делимость одно монома на другой нацело означает, что в частном получается моном. Это равносильно тому, что степень любой переменной в первом мономе больше или равна степени той же переменной во втором мономе. Определение. Редукция многочлена f по модулю семейства многочленов {g_1,...,g_k} -- это редукция f посредством какого-либо из многочленов g_i. Редукцию данного многочлена по модулю данного семейства (как, впрочем, и по модулю данного одно многочлена) можно итерировать. Поскольку после каждой отдельной редукции ведущий член многочлена становится меньше, рано или поздно всякая цепочка редукций закончится. Пример. Который показывает, что окончательный результат процесса редукции данного многочлена f по модулю данного набора {g_1,...,g_k} может зависеть от порядка, в котором проводятся действия. Определение. S-полином пары многочленов f и g в смысле данного порядка на мономах определяется формулой: S(f,g) = (lm(g)/gcd) f - (lm(f)/gcd) g, где gcd = gcd(lm(f),lm(g)) -- наибольший общий делитель двух мономов. Смысл этого определения заключается в том, что мы домножаем старшие мономы двух данных многочленов на такие наименьшие множители, чтобы они взаимно уничтожились. Алгоритм Бухбергера. Дан список многочленов {f_1,...,f_k} от n переменных x_1,...,x_n и зафиксирован некий порядок на множестве мономов, скажем, лексикографический. Алгоритм Бухбергера заключается в преобразовании данного списка путем попеременного выполнения следующих двух шагов до тех пор, пока в списке будет что-то меняться. Как только окажется, что после очередного выполнения двух шагов список не изменился, алгоритм заканчивает работу. Пусть L_0 -- исходный список. Алгоритм работает с переменным списком, которому в начальный момент присваивается значение L_0, после чего начинаются итерации. Шаг 1. Полная редукция каждого многочлена f_i по модулю всех остальных многочленов и замена в списке этого многочлена f_i на результат редукции. Если результат нулевой, то он отбрасывается. Шаг 2. Добавление к списку всевозможных S-полиномов, которые можно получить из элементов списка. Возврат к шагу 1. Определение. Базис Гребнера идеала -- это набор многочленов , который получается в результате применения алгоритма Бухбергера.