Метод базисов гребнера и его приложения

Информация о документе

Цена	12000UZS
Размер	540.6KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Педагогика

Метод базисов гребнера и его приложения

Купить

2СОДЕРЖАНИЕ
… ВВЕДЕНИЕ........................................................................................................ 3
ГЛАВА 1. ИДЕАЛЫ И АФФИННЫЕ МНОГООБРАЗИЯ
...................... 8
§1. Полиномы
и аффинные многообразия ....................................................... 8
§2.
Идеалы ............................................................................................................ 13
§3. Полиномы от одной переменной
............................................................. 17
Заключение
по главе I ................................................................................ 21
ГЛАВА 2. БАЗИСЫ … ГРЁБНЕРА
............................................................... 22
§1. Упорядочение
мономов в k[x 1 , x 2
,…,x n ] .................................................. 22
§2. Алгоритм
деления в k[x 1 , x 2
,…,x n ] ........................................................... 28
§3. Мономиальные
идеалы и лемма Диксона ............................................... 39
§4. Теорема
Гильберта о базисе и базисы Грёбнера .................................... 44
§5. Свойства базисов Гребнера
........................................................................ 49
§6. Алгоритм
Бухбергера ................................................................................... 55
Заключение
по главе II ............................................................................... 58
ГЛАВА 3. ПРИЛОЖЕНИЯ БАЗИСОВ … ГРЁБНЕРА
............................ 59
§1. Задача
о принадлежности идеалу ............................................................. 59
§2. Решение
полиномиальных уравнений .................................................... 64
Заключение
по главе III ........................................................................... 77
… ЗАКЛЮЧЕНИЕ
.............................................................................................. 78
… ЛИТЕРАТУРА
................................................................................................ 79

3ВведениеПодготовка
высококвалифицированных кадров играет
важную роль
. в развитии экономики и общества Позитивные
,
преобразования в сфере среднего и высшего образования как
. . [11],
отметил Президент Узбекистана И А Каримов являются

практическим воплощением политики реализации
.
целенаправленных реформ В этом отношении необходимо

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

Данная диссертационная работа посвящена изложению
,
некоторых результатов бурно развивающийся области
,
связанной с алгоритмами превращающими базисные понятия

коммутативной алгебры и алгебраической геометрии из
- .
абстрактно теоритических в конкретно вычислимые Изучение

алгоритмов основывается на обобщении алгоритма деления для
,
полиномов от одной переменной найденном лишь в
шестидесятых годах 20 .
века
Базисы Грёбнера идеалов в полиномиальных кольцах были
. открыты Б Бухбергером в 1965 .г и названы им честь .В Грёбнера (1899-
1980)- научного
. руководителя Бухбергера Родственное понятие
« »
стандартного базиса идеала в кольце степенных рядов было
. независимо введено Х Хиронакой в
1964 . г Как мы увидим , далее
Бухбергер также разработал алгоритмы
для работы с базисами
. « »
Грёбнера Термин базис Грёбнера используется в английском
«Groebner base»
написании в качестве команды в некоторых
. системах компьютерной алгебры
Актуальность .
работы Диссертационная работа на тему
« »
Метод базисов Грёбнера и его приложения посвящена

изучению связей между алгебраическими свойствами
k[
полиномиальных колец
, ……. ] и геометрическими свойствами
. аффинных многообразий В работе изучены
, базисы Грёбнера

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

4Цели и задачи :исследования Исследовать алгебраические

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

5 : Степень изученности проблемы В последние годы бурно
, , развивается область связанная с алгоритмами превращающими
базисные
понятия коммутативной алгебры и алгебраической

геометрии из - абстрактно теоретических в конкретно . вычислимые
Речь идёт о способах
явного нахождения , объектов существование
которых устанавливается .
в ключевых утверждениях теории
,
Ответы на возникающие вопросы удаётся получить за счет
,
объединения классических методов в последние десятилетия
,
ушедшие в тень и современных идей основанных на
относительно
новой теории базисов . Грёбнера
Научная
: новизна Основные результаты , являются новыми
важными
и состоят в : следующем

 Показана связь между алгебраическими свойствами
k[
полиномиальных колец
, ……. ] и геометрическими
свойствами
аффинных . многообразий
 k[
Описан алгоритм деления в кольце
, ……. ] в

зависимости от упорядочения . мономов
 Описан
алгоритм решения задачи о принадлежности
. идеалу
,
 Найдены решения некоторых систем полиномиального уравнений основанные на вычислении базисов Грёбнера по отношению к различным типам . упорядочений
Объект и предмет :
исследования Объектом исследования

являются базисы Грёбнера и их . приложения Предметом
исследования являются
k[ полиномы в кольце
, …….
], а также

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

6 .Работа носит теоретический и практический характер

Результаты диссертации могут быть использованы в различных

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

на семинаре « Методы степенной геометрии и компьютерной

алгебры в исследовании алгебраических и дифференциальных
»
уравнений под . руководством профессоров А Солеева и
. ( И Икрамова СамГУ
2013-2015 .) гг
« » - ,
 Амалий математика ва ахборот хавфсизлиги илмий техник конференция 2014
 Магистрантларнинг
XIV илмий , конференцияси 2014

- , Замонавий ахборот коммуникация технологиялари ТАТУ
Самарканд
- филиали профессор укитувчиларининг Х
-
илмий амалий , конференцияси 2015
Опубликованность :
результатов Основные
результаты диссертации
опубликованы
в
работах
1.
Сеттарова . .,Э С Каримова . ., М А Задача о принадлежности
; идеалу
2.
Каримова . ., М А Задача о принадлежности ; идеалу
3. Нарзуллаев . .,
У Х Каримова . ., М А Грёбнер базислари ; хакида
:
Структура и объем диссертации Диссертация состоит из
,
введения трех глав и списка . литературы П о л ь н ы й объем
диссертации 70 ,
страниц библиография включает 34
. наименований
Во введении ,
отражена история вопросов рассмотренных в
, ,
диссертации и приведен обзор результатов связанных с темой
.
исследования Кратко излагается содержание работы и

формулируются основные . результаты
П е р в а я глава «
Идеалы и аффинные » многообразия

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

7 аффинных многообразий требует знания теории идеалов в
кольцах полиномов k[
, …….
].
А также мы рассматриваем
,
полиномы от одной переменной чтобы проиллюстрировать роль
. алгоритмов

8Во второй главе «Базисы » Грёбнера изучается упорядочение
мономов вполиномиальном кольце от n , переменных алгоритм
деления в k[
, …….
],
, , мономиальные идеалы лемма Диксона
, , теорема Гильберта о базисе базисы Грёбнера свойства базисов
, Грёбнера алгоритм Бухбергера для вычисления
. базисов Грёбнера
k[x]
Рассмотрение алгоритма деления в и алгоритма приведения
( )
системы или матрицы к ступенчатому виду методом
исключения Гаусса , показывает что понятие упорядочение членов
полинома
является ключевым в обоих . алгоритмах П о э т о м у
обобщение
алгоритмов деления и приведения к ступенчатому

виду на случай произвольных полиномов от нескольких
переменных должно базироваться на упорядочении
членов
k[
полиномов из
, …….
].
В главе 1 было ,
объяснено как алгоритм деления для
полиномов
от одной переменной может быть применен для
.
решения задачи о принадлежности идеалу Для решения этой

задачи в случае нескольких переменных необходимо было
k[x] обобщить алгоритм деления в на общий случай
k[ полиномиального кольца
, …….
]. Научившись делить полином
∈ k[
, ……. ] на полиномы
, …… k[
∈
, ……. ], мы смогли
представить в виде
где « »
частные
,
…,
= + + ⋯ + , и
остаток принадлежат k[ , ……. ].
Самое
трудное в этом вопросе – это корректно определить . остаток Остаток
не был
, определен однозначно как это было в кольце полиномов

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

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

же задача в общем случае решается с помощью переопределения
, . базисов образующих идеал Для этого нам будет необходимо
« » ( определить базисы с хорошими по отношению к
алгоритму

9) . деления свойствами Используя базисы Грёбнера удалось
доказать конечную порожденность любого полиномиального идеала
( теорема
). Гильберта о базисе В следующем параграфе
,
рассматриваются свойства базисов Грёбнера и особенно тот факт

что нежелательные свойства алгоритма деления в k[
, …….
] не
, проявляются
если делители образуют

10 ( . . базис Грёбнера т е в этом случае остаток от деления определен
). однозначно , , Также используя алгоритм Бухбергера научились
строить базис Грёбнера любого заданного идеала ⊂ [
, …….
] .
В третьей главе «
П р и л о ж е н и я базисов » Грёбнера решаются

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

техника базисов Грёбнера была применена для решения систем
. , полиномиальных уравнений Практика показывает что
lex- вычисление базиса Грёбнера по отношению к упорядочению
существенно упрощает форму
. , уравнений В частности мы

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

Автор выражает глубокую благодарность кандидату
- , . .
физико математических наук доценту У Х Нарзуллаеву за

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

11ГЛАВА 1
ИДЕАЛЫ И АФФИННЫЕ МНОГООБРАЗИЯ§1. Полиномы и аффинные многообразия
Определение 1.1. Мономом от
переменных
, ,…,
,
называется произведение вида

…
,
где показатели степеней , ,…, ,-
неотрицательные целые
. 1.1. 2
числа Пример полная степень равна 6.
Для упрощения мономов будем пользоваться записью
= ( ,
, …,

) - n
набор неотрицательных . чисел Положим = … .
,
Отметим что если =(0,0,…,0), то
=1.
Через | |= + +…+ мы будем обозначать полную степень монома
.
Определение 1.2. П о л и н о м f от переменных
,

, …, с
коэффициентами из произвольного поля
k
называется
конечная линейная ( комбинация мономов с
k). коэффициентами из
Полином
f будет записываться в виде
= , ∈ ,
где
суммирование производится по конечному множеству наборов
= ( , , …, ).
Множество
всех полиномов от
переменных ,
из k обозначается k[
, , …, ].
, …, с
коэффициентами
Когда
мы будем работать с полиномами от малого количества
, . , переменных то обычно будем обходиться без индексов Так
, полиномы от одной двух или
трех переменных
принадлежат множествам k[ ] , k[ , ], k[
, , ]
. соответственно Например

12f =2
z+3/2 ------- 3 +
является полиномом из Q[ , ,
.] Как , правило будем
использовать
для обозначения полиномов буквы f ,g, h, p, q ,r.

13 1.3.Определение П у с т ь f = ∑
, ∈ полином из [
, , …,
1)
называется коэффициентом монома .
2) Если
≠ 0, то называется членом полинома f.
]:
3)
Полной степенью полинома f , обозначаемой deg(f),
| называется максимум степеней | по всем мономам с ненулевыми
. коэффициентами
, Например
полином
f =2
z+3/2 ------- 3
+
, рассмотренный выше содержит четыре члена и имеет полную степень
. шесть , Отметим что f
содержит два члена максимальной , степени
что невозможно .в случае полинома от одной переменной
. Сумма и произведение двух полиномов являются полиномами Мы
, говорим
что полином f делит полином g, если g=fh для
некоторого полинома
h
∊ [ ,
, …, ].
Операции сложения и умножения на множестве [
,
, …, ]
, удовлетворяют всем аксиомам поля за исключением аксиомы
(1/g, существования обратного элемента по умножению например не
). являются полиномами Такая
структура называется коммутативным
кольцом
,и по этой , причине мы
будем называть [
,
, …,
.
кольцом
] кольцом полиномов или
полиномиальным
1.4. k Определение Пусть дано поле
и n; n- натуральное число тогда
мерным
аффинным пространством над k называется
множество
= { ( , , …, ): , , …, ∊ }.
,
П у с т ь , например =R. П р о с т р а н с т в о R - , объект знакомый из

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

- аффинной . плоскостью

14Связь между полиномами и аффинными .пространствами
П о л и н о м f=∑
∊ [ ,
, …, ] задает функцию f: → .
П у с т ь (
,
, …,
)
∊ . В , формуле определяющей f, заменим каждое
на

. Так как коэффициенты из , то эта операция дает
элемент f (

,
, …, )
∊ .

Двойная природа полинома приводит к некоторым
. , « , f=0?»
неожиданным следствиям Например вопрос верно ли что
:
допускает два истолкования « является ли f нулевым
?»
полиномом . . т е верно , ли что все коэффициенты f равны , нулю
или «
является ли f нулевой ?», функцией . . , т е верно ли что f (
,
,
…,
)
=0 для всех (
,
, …, )
∊
.
,
Удивительно но эти два утверждения в общем случае не
!
эквивалентны , , Рассмотрим например множество из двух
0 1. элементов и Это множество
можно сделать , полем в котором
1+1=0.
Это поле обычно обозначается . Теперь рассмотрим
полином
− = ( −1) ∊ . Так как этот полином обращается в нуль в
точках 0 и 1, то он дает пример ненулевого ,
полинома
являющегося нулевой функцией на аффинном пространстве
.
Однако если , бесконечно то никаких проблем не . возникает
П р е д л о ж е н и е 1.1. [
15 ]
П у с т ь - бесконечное поле и f ∊ [
,
,
…, ] .
f=0 ,
Тогда в том и только в том случае когда f: → является нулевой
.
функцией
. Доказательство В одну сторону : доказательство очевидно нулевой
. полином определяет нулевую функцию
,
Обратно надо , доказать что если f (
,
, …, )
=0 для

всех (
,
, …, )
∊ , f - . то нулевой полином Доказательство по

индукции по числу n. переменных
П у с т ь n=1. Ненулевой полином из
[ с]тепени m имеет более m
.
различных корней П у с т ь ∊ [ ] f(a)=0 и для всех a ∊ . Так как -
,
бесконечно то ; , имеет бесконечно много корней следовательно f -
. нулевой полином
Пусть предложение справедливо для n-1 и пусть
f ∊ [ ,
,

15…, ] -
, полином
обращающийся в нуль во всех точках из .
Объединяя
члены
по степеням переменной
, запишем f в : виде
= ∑ ( , , …, ) ,

16где ∊ [ ,
, …, ] . П о к а ж е м что - нулевой полином
от
(n- 1)-
, переменных
откуда будет , следовать что f нулевой полином из

[ ,
, …, ].
Если мы
зафиксируем (
, , …, ) ∊ , то получим полином
f(
,
,
…, ,
) ∊ [
] от одной . переменной П о
предложению f
обращается в нуль в каждой точке ∊ ,
,
следовательно
f(
,
, …,
,
) является нулевым полиномом из [
] . , Значит
его
коэффициенты равны ,
нулю . . т е (
,
, …,
) для любого i. Так
как
(
точка
,
, …,

∊ [ , , …, ) выбрана в ,
произвольно то каждый

] является нулевой функцией на .
Тогда по
предложению
индукции каждый является нулевым полиномом в

[ , , …,

[ , , …,
] . Отсюда , следует что f является нулевым
полиномом
в

]. Что и требовалось . доказать ■
, Отметим
что в формулировке предложения утверждение «f=0 в

[ ,
, …, ]» , означает что f является нулевым , полиномом . .т е все
его
коэффициенты
равны . нулю Таким , образом символ 0 обозначает и
нулевой
элемент в k , и нулевой полином в [
,
, …, ].
Следствие 1.1. П у с т ь k - бесконечное поле и f, ∊ [
,
,
…, ]. Тогда
f=g в том и
только в том , случае когда функции f: → и g: →
.
равны
. . f
Доказательство В одну сторону утверждение тривиально Пусть
g
и задают одну и ту же функцию на
. Тогда полином f-g

обращается в нуль во всех точках из ,
. .т е по предложению
полином f-g
является . нулевым
,
Значит f=g в [ ,
, …, ]. ■
Теорема 1.1. Каждый постоянный полином f C
∊ [ x ] имеет
корень в C
( ).основная теорема алгебры
Поле
k называется алгебраически , замкнутым если любой
непостоянный
полином из [x] имеет корень в k.
Определение 1.5. П у с т ь k - некоторое ,
поле а ,
, … - полиномы в

17 [ ,
, …, ]. П о л о ж и м
V( , , … ) ={ ( , , …,
) ∊
: (
,
, …, ) =0 для всех 1 ≤ ≤ } .
V(
,
, …
) называется аффинным ,
многообразием
определенным
полиномами ,
, …
.
Другими ,
словами аффинное многообразие ------------------------------- V(
,
,
…
) ⊂ это
множество
решений системы уравнений
(
,
, …,
) = =⋯ ( , , …, ) = 0 .

18,Например многообразие V( + −1) на
плоскости -
окружность радиуса 1 с центром в
начале
( координат графики полиномов являются аффинными
, многообразиями
y=f(x) есть аффинное многообразие V(y-f(x)).
Графики рациональных функций
также
являются
аффинными многообразиями
−1
= ⟹ ( − +1)
Лемма 1.1. Если V, W- аффинные ,
многообразия то V W ∪ и V ∩ W

также являются аффинными . многообразиями
.
Доказательство П у с т ь V=V( ,
, … ) и W=V( ,
, … ).

Мы , утверждаем что
V W= V (⋂ , , … , , , … )
V W=∪ V( : 1 ≤ ≤ , 1 ≤ ≤ .)
Первое
утверждение : тривиально если точка принадлежит V ⋂ W, то
как
функции
,
, …, , так и функции
, , …, обращаются в этой
точке в
. нуль Это то же , самое что обращение в нуль набора функций
, , …, , , , …, .
Докажем
второе : утверждение если (
, , …, ) V, ∈ то все
обращаются
в нуль в этой ; точке значит и все функции обращаются
в нуль в
(
,
, …, ) .
Таким образом V ⊂ (
) и аналогично W ⊂ V (
) .
,
Следовательно V W ∪ V( ⊂
). С другой , стороны пусть
(
,
, …, ) ∈ ( ). Если эта точка принадлежит V, то все
,
доказано
если же ,
нет то ( ,
, …, ) ≠ 0 для некоторого . Так как
функции
обращаются в нуль в (
,
, …, )
при всех j , то все равны
нулю в
этой . точке
, Значит (
, , …, ) ∈ и V ⊂ ∪ W. ■

19§2.Идеалы
Определение
1.6. П о д м н о ж е с т в о I ⊂ [ ,

, …,
если
выполнены следующие : условия
1) 0 I
∊
2) если f,g
∊ , то f+g ∊
] называется , идеалом
3) если f ∊ и h
∊ [ ,
, …, ], то ℎ ∊ .
Определение 1.7. П у с т ь
, , …, - полиномы в [
,
, …, ]. П о л о ж и м

< , , …, >= ℎ : ℎ ,
…,

.

ℎ∊ [ , …, ]
,
Оказывается что множество <
,
, …, > - . идеал
Лемма
1.2. П у с т ь
, , …, принадлежат кольцу [
, ,
…,
множество <
,
, …, > является
идеалом в [
,
, …,
] ; тогда
] . Оно
называется ,
идеалом порожденным полиномами ,
, …, , а
полиномы
,
,
…,
- образующими этого , идеала или его
порождающими
.
элементами
Идеал <
,
, …, > имеет изящную интерпретацию на
языке
полиномиальных .
уравнений П у с т ь
,
, …, ∊ [
, ,
…,
систему
уравнений
]. Рассмотрим
=0
………
= 0
Из
этих уравнений мы можем вывести , другие используя
обычные алгебраические
. преобразования , Так , например если мы
умножим
первое
уравнение на ℎ ∊ [
,
, …,
], второе – на ℎ ∊ [
, , …, ] и . ., т д а
затем
сложим , произведения то получим уравнение

20ℎ +ℎ + +⋯ ℎ = 0 ,
которое является следствием уравнений первоначальной . системы
, Отметим
что левая часть уравнения принадлежит идеалу <
,
,
…, >, . .
т е идеал
<
,
, …, > можно рассматривать как множество всех
«
полиномиальных » следствий системы = = =⋯ = 0 .

21Идеал I называется конечно , порожденным если существуют
полиномы
,
,
…, ∊ [ ,
, …, ] , , такие что I=< ,
, …, > ; при этом
множество
полиномов
, , …, , называется базисом идеала I.
, .
Отметим что идеал может иметь много различных базисов
,
Далее мы покажем что можно определить особенно удобный
, .
базис называемый базисом Грёбнера

Следует обратить внимание на аналогию с линейной
.
алгеброй Определение идеала похоже на определение
: подпространства ,и то и другое множества замкнуты относительно
операций сложения и , умножения только
в случае
подпространства идет речь об умножении на ,
скаляры а в случае
. идеала мы умножаем на полиномы
,
О роли идеалов говорит и следующее предложение в
,
котором доказывается что многообразие зависит лишь от
,
идеала порожденного . определяющими уравнениями
П р е д л о ж е н и е 1.2. П у с т ь
, , …, и
,
, …, - базисы одного и того
же
идеала в [
,
, …,
] , так что < , , …, >=< ,
,
…, > . Тогда
( , , …, ) = ( , , …, ).
Таким
, образом изменяя базис , идеала мы упрощаем процедуру
описания
. многообразия
, , Возможность изменять базис не меняя многообразия очень важна и
. полезна
Рассмотрим в качестве примера
многообразие (
2 +3
−
11, 2− 2−3. Легко , показать что <2 2+3 2−11, 2−
2−3>=< 2−4,

−1 > , так что в силу предложение 1.2.
(2 +3 −11, − −3 ) = ( −4, −1) ={( ±2, ±1) }.
Теперь
мы , обсудим как аффинные многообразия связаны с
интересным
классом . идеалов П у с т ь V=V (
, , …, ) ⊂ -
аффинное
, многообразие
определенное полиномами
, , …, ∊ [
,
, …, ] . Мы ,
знаем что
,
, …, обращаются в нуль на V, но только ли ?
они Есть ли
,
другие полиномы равные нулю на V?
Определение 1.8. П у с т ь ⊂
- аффинное . многообразие П о л о ж и м
I(V)={f ∊ [

, , …,
]
: (
,
, …, ) =
0 для всех (
,
, …, ) ∊ V} .

22, Оказывается что I(V) – .идеал
Лемма 1.3. П у с т ь ⊂
- аффинное . многообразие Тогда I(V) –
,
идеал который мы будем называть идеалом V. многообразия
. Пример
Рассмотрим многообразие {(0,0)}, состоящее только из одной
точки
- начала координат в . Элементами его
идеала I({(0,0)})
являются , полиномы равные
(0,0). , нулю в точке Мы утверждаем что
I({(0,0)})=<x,y>.

23Водну сторону доказательство тривиально –
любой полином
вида A(x,y)x+B(x,y)y обращается
в нуль в начале . координат Пусть теперь
полином ∑ ,
равен
нулю в точке
(0,0).
Тогда , следовательно
= (0, 0) = 0 , и
= + ∑ , = 0 + ∑ ,
+ ∑ 〈 , 〉
. Доказательство окончено ■
П у с т ь
,
, …, ∊
[
,
, …, ]
. Имеем полиномы
, , …,
→
многообраз
ие (
V
,
, …, )
→ идеал ( V (
, , …, )
).
Возникает естественный :
вопрос верно , ли что
( V( , , …, ))=< , , …, >?
К ,
сожалению ответ здесь не всегда оказывается
. положительным , – Наилучший ответ который мы можем дать это
: следующее утверждение
Лемма 1.4. П у с т ь
, , …, ∊ [
,
, …, ]
. Тогда < , , …, > ⊂
( V (
,
, …,
)
), но эти два идеала не всегда . совпадают
, (
Теперь нам нужно привести пример когда идеал V (
,
, …, )
)
<
строго больше идеала
,
, …, >.
Мы
, докажем что включение
< , >⊂ ( V ( , ))
. (
не является равенством Сначала опишем идеал V (
,
)
) . Система
уравнений
= =0 определяет , многообразие состоящее из одной
V
точки (
,
) = {
( 0, 0 }
). , Но мы видели раньше что идеал
{(0,0)} <x,y>, . . V(
многообразия есть т е
,
) = <x,y>. Для того чтобы
,
убедиться что этот идеал строго больше идеала < , >,
достаточно ,
заметить что x ∉ < , >, так как все члены
полинома ℎ
(
, )
+ℎ (
, )
имеют степень . не меньше двух
Хотя в общем случае ( V (
,
, …, )
) не равен <
, , …, >,
идеал
многообразия
всегда определяет многообразие . однозначно
П р е д л о ж е н и е 1.3. П у с т ь V и W – аффинные многообразия в
. Тогда
(i) V W
⊂ в том и только в том , случае когда ( V) ⊃ ( W )
(ii) V=W в том и только в том ,
случае когда (
V ) =
( W )
Связь между аффинными многообразиями
и идеалами сложна
и . разнообразна Здесь
мы затронули только верхушку
. айсберга А теперь
сформулируем три , проблемы касающиеся идеалов в
[
, , …,

24 (Описание ) идеала Каждый ли
идеал I ⊂ [

, , …,
]:

]
является
конечно
, порожденным . .т е всегда ли I=<
, , …, > для
некоторых
,
,
…, ∊ [
,
, …, ]
?

25 (П р и н а д л е ж н о с т ь ) идеалу П у с т ь
, , …, ∊ [
,
, …, ]
.
Существует ли ,
алгоритм позволяющий решить вопрос

о принадлежности полинома
f
∊ [
,
, …, ]
идеалу < , , …, > ?

( Решение полиномиальных ) уравнений Описать множество
решений в
системы полиномиальных . уравнений , Конечно
это то же ,
самое что описать V( аффинное многообразие
,
,
…, ).

26§3. Полиномы от одной переменной
Определение 1.9. П у с т ь f ∊ [ ]- ненулевой , полином
f = + + +⋯ ,
где
∊ и ≠ 0 ( . . deg(f)=m). т е Тогда называется старшим членом
f LT(f)=
полинома и обозначается («LT» - первые буквы

английского термина «leading term»). ,Например если f=2 −4 +3
,
то LT(f)=2 .
Следует
, отметить что если f и g - ненулевые , полиномы то
deg(f)≤deg(g) LT(f) ⟺ делит
LT(g). Теперь
мы можем дать описание
алгоритма
. деления
Предложения
1.4. (алгоритм ). деления Пусть g ∊ [ ]- ненулевой
. полином
Тогда любой полином f ∊ [
] может быть записан в виде
f=qg+r,
где g,r ∊
[ ] и либо r=0, либо deg(r)<deg(g). Более , того g и r

определены однозначно и имеется алгоритм для их . вычисления
Вот
алгоритм вычисления g и r , записанный на
: псевдокоде
: Вход g, f
Выход : q,r
q:0; r:=f
WHILE r ≠ 0 AND LT(g) делит LT(r) DO
g:=q+LT(r)/LT(g)
r:=r-( LT(r)/LT(g))g
, Операции
подчиненные оператору цикла WHILE… DO,
, выполняются
пока выполняется , условие записанное между
WHILE и DO; q:=… и r:=… -
это операторы определения или
переопределения
значений q и r. И q и r
являются
переменными в этом алгоритме – на каждом шаге их
. значения меняются
Следствием существование алгоритма
деления
является такое утверждение о количестве корней
полинома
от одной : переменной Следствием 1.2. П у с т ь f ∊ [ ]-
ненулевой .
полином Тогда он имеет в k не более чем deg(f)
.
корней
Предложение 1.4. позволяет также описать все идеалы в [ ].
1.3. k – .
Следствием Пусть поле Тогда каждый идеал в [ ] м ожет
<f> f
быть представлен в виде для некоторого полинома ∊ [ ].
, f
Более того определен однозначно с точностью до умножения на

27 ненулевую константуиз k.
, Идеал порожденный одним , элементом называется главным
. идеалом Таким
, 1.3. , образом ввиду следствия мы говорим что [ ]

является областью . главных идеалов или сокращенно ОГИ

28Определение 1.10. Наибольшим общим делителем полиномов f,g ∊
[ ]
называется
полином h, , такой что
(i) h делит и f, и g;
(ii)
если p- , некоторый полином который делит и f и g, то p

делит h.
Наибольший общий делитель будет обозначаться через GCD(f, g)
( GCD
начальные буквы английского термина greatest common divisor).
Основные
свойства наибольших общих делителей
сформулированы
.в следующем предложении
П р е д л о ж е н и е 1.5. П у с т ь f,g ∊ [ ]. Тогда
(i) GCD(f, g) существует и единственен с
точностью
до k; умножения на ненулевую константу из
(ii)
GCD(f, g) является образующим идеала <f, g>;
(iii)
существует алгоритм для вычисления GCD(f, g).
Дадим сначала необходимые .
определения П у с т ь f,g ∊ [ ], g≠ 0 .
Запишем f f=qg+r, q
в виде где и r определены как в предложении
1.4. r
Тогда называется остатком от деления f на g ( мы будем
писать r= остаток (f, g)).
Теперь мы можем дать описание алгоритма
: Евклида
: f,g
Вход
: Выход
h
h:=f
s:=g
WHILE s ≠0 DO
rem:= остаток (h,s)
h:=s
s:=rem
Как
пример работы алгоритма Евклида рассмотрим процесс
вычисления
GCD( −1, −1 ). Сначала мы применяем алгоритм
:
деления
−1 = 0 ( −1 ) + −1 ,
−1 = ( −1 ) + −1 ,
−1 = ( +1 ) ( −1 ) +0 .
Тепер мы имеем
GCD( −1, −1 )=GCD( −1, −1 )=GCD( −1 , −1 )=
GCD( −1, 0)
, GCD
Следует отметить что вычисление дает ответ и на вопрос об

29 <определении порождающего элемента идеала −1, −1 >, а именно

из предложения и того , факта что GCD( −1, −1 ) = −1 ,
,
следует что
< −1, −1 >=< −1 >.

30Однако здесь можно задать естественный :вопрос а как
,
быть когда идеал порожден тремя или большим количеством
?
полиномов Для этого необходимо определить наибольший общий
. делитель нескольких полиномов 1.11. Определение Наибольшим
общим делителем полиномов
,
, …, ∊ [ ]
называется полином h, , такой что
(i) h делит
, , …, ;
(ii)
если p - некоторый , полином который делит
,
, …, , то p
делит
h. h GCD(
Такой полином обозначается через
,
, …, ) . Основные
свойства наибольшего общего делителя сформулированы в
следующем
. предложении
П р е д л о ж е н и е 1.6. П у с т ь
,
,
…, [ ]
, ≥2 . Тогда
(i) GCD(
,
, …, ) существует и определен
однозначно
с точностью до
умножения на ненулевую константу из k;
(ii) GCD(
,
,
…, ) порождает идеал <
,
, …, > ;
(iii) если s≥3 , то GCD( , , …, )=GCD( ,GCD( ,…… ));
(iv) существует алгоритм для вычисления GCD(
,
, …,
).
, Пусть
, например мы хотим найти наибольший общий делитель
четырех
полиномов
,
, , . Имеем
GCD( , , ,
) = GCD(( ,GCD( ,
, )) = GCD( ,GCD( ,GCD( , ))).
Таким ,
образом для вычисления наибольшего
общего делителя
полиномов ,
, , нам нужно применить алгоритм Евклида три . раза
GCD
П р о ц е д у р а в ы ч и с л е н и я в б о л ь ш и н с т в е с и с т е м

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

полиномов необходимо использовать метод 1.6. предложения
, , Рассмотрим например идеал
< −3 +2, −1, −1 >⊂ [ ] .
Мы
,знаем что GCD( −3 +2, −1, −1 ) порождает этот . идеал
,
Далее легко , проверить что
GCD( −3 +2, −1, −1 ) =GCD( −3 +2 ,GCD( −1, −1 )) =
= GCD( −3 +2, −1 ) = −1,
. .
т е
< −3 +2, −1, −1 > = < −1 > .
,
Теперь понятно как должен быть построен алгоритм

31 <вычисления порождающего элемента идеала
,
, …, >,
,
, …,
[
]
.
В качестве следующего приложения алгоритмов деления и
вычисления GCD : рассмотрим задачу о принадлежности идеалу
, существует ли алгоритм
позволяющий определить для

произвольного полинома [
]
и заданных полиномов ,
, …, [
]
,
лежит в идеале <
,
, …,
> или . нет Ответ

32, . утвердительный и такой алгоритм несложно описать Первый
– GCD(
шаг это вычисление
,
, …, ), . . т е определение порождающего
h <
элемента идеала ,
, …, >. Так как включение < ,
, …, >

эквивалентно включению < ℎ > , то нам осталось только
поделить :
на ℎ с остатком f=qh+r, deg(r)<deg(h) . , Таким образом f
принадлежит идеалу в том и только
, в том случае когда = 0 .

33Заключение по главе I
В первой главе изучены основные понятия алгебраической
.
геометрии Под геометрией понимается геометрия аффинных
.
многообразий задаваемых полиномами Понимание теории

аффинных многообразий требует знания теории идеалов в
кольцах
полиномов
[
, …….
] .
А также были рассмотрены полиномы от одной
.
переменной
Основные
результаты по главе I:

 Изучена связь между алгебраическими свойствами
полиномиальных колец и геометрическими свойствами
аффинных
. многообразий

Изучены идеалы и их связь с полиномиалными . уравнениями

Сформулированны три проблемы касающиеся идеалов
в
[
, …….
]
, . .
т е задача описания , идеала задача о
,
принадлежности идеалу нахождение решения

полиномиальных . уравнений

Дано описание алгоритма деления в кольце [ ].

 Полностью решены задачи описания идеала и о принадлежности идеалу в случае [ ].

34
2 ГЛАВА
Б АЗИСЫ ГРЁБНЕРА§1.
Упорядочение мономов в [
,
, …,
]
Алгоритм
деления полиномов от одной переменной имеет дело

со следующим упорядочением : мономов
… > > >…> > >1
,
Результативность алгоритма связана именно с тем что мы

работаем последовательно со старшими членами полиномов f и
g,
а не « » случайным образом убираем члены из f, используя

произвольные члены из g. Обобщение алгоритмов деления и
приведения к ступенчатому виду на случай произвольных
полиномов
от
нескольких переменных должно базироваться
на упорядочении членов из [
,
, …, ]
.
Отметим
, сначала что существует взаимно однозначное
соответствие между
мономами = … и n- наборами (n-
) векторами
показателей
степеней
= (
, …
)
∈ . , Упорядочение которое мы определим
на
,
определит и упорядочение на множестве : мономов если > в ,

то
мы будем , говорить что > .

Упорядочение на . можно задать многими способами Так

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

35быть .линейным Это , означает что для любой пары мономов и

должно выполняться ровно одно из следующих : соотношений

36
> , = , < .
Еще мы , потребуем чтобы упорядочение мономов обладало
следующим дополнительным
. свойством Если > , а -
произвольный ,
моном то
> .
B терминах векторов - показателей степеней это , означает
что
если > в , то для любого , + > +
Теперь
мы можем дать следующее . определение
Определение 2.1. Мономиальным
упорядочением на
[
,
, …,
]
называется
любое бинарное отношение > на , обладающее
следующими
:
свойствами
(i)
> является линейным упорядочением на .
(ii) если > и , то + > + ;
(iii)
> вполне упорядочивает , . . т е любое непустое

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

вполне упорядоченности (iii).
2.1.
Лемма [
15 ]
Упорядочение > на вполне упорядочивает это
,
множество тогда и только тогда когда каждая строго убывающая
последовательность элементов из

(1) > (2) > (3) >...
.
обрывается
Нашим первым примером упорядочивания n-
векторов

37 будет лексикографическое упорядочение (или
сокращенно lex - ). упорядочение
Определение
2.2. (лексикографическое ). упорядочение Пусть

38
= ( , … ), = ( , … ) . Мы , говорим что > , если
самая
левая ненулевая координата вектора − . положительна Мы
будем
писать > , если > .
Вот
несколько : примеров
(a) (1,2,0) > (0,3,4), так как − =( 1, −1, 4)
(b) (3,2,4) >
(3,2,1), так как − = ( 0, 0, 3)
(c) Обычный порядок > > >⋯
переменных , , …,
является
lex- . упорядочением Так как
(1,0,…,0) > (0,1,…,0) > …> (0,0,…1) то
> > … > .
,
Работая с полиномами от двух или трех переменных мы

обозначаем переменные через x,y,z, а не
,
,
. В дальнейшем мы
, , ,
будем также как правило предполагать что алфавитный
порядок
> > переменных и определяет упорядочение . мономов
Предложение
2.1. [15 ] Лексикографическое
упорядочение на
является
мономиальным
. упорядочением
,
Необходимо отметить что существует много
:
лексикографических упорядочений каждому упорядочению
переменных отвечает .
свое До сих пор мы рассматривали
лексикографическое ,
упорядочение порожденное
упорядочением
> > >⋯ . , Но задав произвольный
порядок
переменных
,
, …,
, мы получим соответствующее ему
. , ,
лексикографическое упорядочение Пусть например

39 , , x y. переменных две скажем и Тогда мы можем определить два
:
лексикографических упорядочения одно порождается
порядком
> , а другое – порядком

> . В общем случае n переменных имеется n!
лексикографических . упорядочений В дальнейшем термин
« » лексикографическое упорядочение будет , означать что имеется
в виду порядок > > >⋯ .

40
В случае лексикографического упорядочения переменная
,
больше любого монома который содержит только меньшие
,
переменные вне зависимости от его . степени , Так при
упорядочении
> > мы имеем

> . В ряде случаев нам будет необходимо учитывать также
.
степени мономов и сравнивать сначала именно степени Это

можно сделать с помощью градуированного лексикографического
( упорядочения сокращенно
grlex- ). упорядочения
Определение
2.3. (градуированное лексикографическое ). упорядочение
Пусть
, . Мы , говорим что > , если
| | = ∑ > | | = ∑
или | | = | |
и >
Таким ,
образом grlex сначала упорядочивает по , степени а если
, степени равны то использует лексикографическое . упорядочение
Вот
несколько : примеров
(a) (1,2,3) > ( 3, 2, 0)т а к как |( 1, 2, )3| = 6 > |( 3, 2, )0| =5
(b) (1,2,4) > ( 1, 2, 4), так как |( 1, 2, )4| = |( 1, 1, )5|,

но (1,2,4) > ( 1, 1, 5)
(c)
Переменные упорядочиваются в соответствии с
лексикографическим
, порядком . .т е > > … > .
Следующее (
интуитивно несколько менее
)
естественное упорядочение является для
некоторых операций
наиболее эффективным при . вычислениях
Определение 2.4. (
градуированное обратное
лексикографическое
упорядочение grevlex). П у с т ь ,
. Тогда мы ,
говорим что
> , если

42или |
| = | | и
самая правая ненулевая координата вектора
−
. отрицательна
Как и
grlex, grevlex сначала сравнивает степени , мономов но
упорядочивает мономы
- . по другому в случае равенства их степеней
: Например
(a) (4,7,1) > (4, 2, )3, так как (4, 7, )1= 12 > |( 4, 2, )3| = 9.
(b) (1,5,2) > ( 4, 1, 3)т а к как |( 1, 5, )2| = |( 4, 1, )3| , и
− =( −3, 4, −1)

Для того чтобы объяснить связь между grlex grevlex, и

отметим , сначала что оба эти упорядочения одинаково оценивают
. степень монома В
случае равенства степеней grlex использует lex
- , . .
упорядочение т е обращает внимание на самую левую
( )
большую переменную и
« »
предпочитает . , grevlex большую степень Напротив в случае

равенства степеней обращает внимание на самую правую
( )меньшую
переменную и
« »предпочитает меньшую . степень
Мы
обсудим , то как мономиальные упорядочения могут помочь
при
работе с .
полиномами П у с т ь = ∑ [
,
, …, ]
и пусть
выбрано
мономиальное
упорядочение >. Тогда мы можем однозначно
упорядочить
члены полинома f в соответствии с >. , П у с т ь
,
например
= 4 +4 −5 +7 [ , , ] . : Тогда
(a) при lex-
упорядочении мы записываем полином f
в порядке
убывания членов : так
= −5 +7 +4 +4 ;

43(b) приgrlex -упорядочении запись : такова
= 7 +4 −5 +4 ;
(c)
при grevlex -упорядочении запись : такова
=4 +7 −5 +4 .

44
Далее мы будем пользоваться следующими . понятиями
Определение 2.5. П у с т ь
= ∑
- ненулевой полином в [
,

, …,
и
пусть > - мономиальное . упорядочение
(i)
Мультистепень полинома f определяется так :
]
( ) = ( : ≠ 0 )
(максимум
берется по отношению к >).
(ii)
Старший коэффициент полинома f - это
LC(f) = ( )
(iii)
Старший моном полинома f - это
LM(f) = ( )
(с
коэффициентом 1).
(iv)
Старший член полинома f - это
LT(f)=LC(f)*LM(f).
, Пусть , например = 4 +4 −5 +7 , как и , выше и пусть
>
обозначает
lex- . упорядочение Тогда
( ) =( 3, 0, 0, )
LC ( ) = −5 ,
LM ( ) = ,
LT ( ) =−5
Лемма 2.2. П у с т ь ,
[
, , …, ]
- . ненулевые полиномы Тогда
(i) ( ) = ( ) + ( ).
(ii)
Eсли + ≠ 0, то

46, Если кроме , того ( ) ≠ ( ) , то
указанное . неравенство становится равенством
§2.
Алгоритм деления в k[x
1 , x
2 ,…,x
n ]
В главе 1 было ,
объяснено как алгоритм деления для полиномов
от
одной переменной может быть применен для решения задачи о
принадлежности
. идеалу Для решения этой же задачи в случае

нескольких переменных необходимо обобщить алгоритм
деления в
[
]
на общий случай
полиномиального кольца [
,
, …, ]
. Наша цель – научиться
делить

полином
[
,
,
…, ]
на полиномы , …, [
,
,
…, ]
. Как мы
, увидим
это означает научиться представлять f в
виде
= + + + ⋯ + ,
где « »
частные
,
…, и остаток r принадлежат [
, ,
…, ] . Самое
– . трудное в этом вопросе это корректно определить остаток Именно
здесь . будут использованы мономиальные упорядочения После этого
мы применим этот алгоритм для решения задачи о принадлежности
. идеалу
Основная идея алгоритма та ,
же что и в случае одной
:
переменной мы должны уничтожать старший член полинома f
( ),
определенный заданным мономиальным упорядочением

умножая некоторый . на подходящий моном и вычитая Этот

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

47несколько делителей и .частных Будем записывать делители ,
,
…,
и частные
,
,
…, в столбец , слева . .т е мы имеем следующую : схему

48
:
:
:
:
Причем
остаток должен обладать : свойством ни один член остатка
нельзя поделить на старший член хотя бы одного . делителя
Теорема 2.1. [
15 ]
(
алгоритм деления в [
,
, …, ]
).
Зафиксируем
некоторое
мономиальное упорядочение > на , и пусть
=
(
, …, )
-
упорядоченный s
-набор полиномов из [
, ,
…, ]
. Тогда любой полином
[
,
,

…, ]
может быть записан в виде
= + + + ⋯ + ,
где
, [
,
, …, ]
и или = 0 , или r есть линейная
комбинация
мономов (
с коэффициентами из k ), ни один из которых не
делится ни LT(
на один из старших членов
),…,LT(
). Мы называем
r остатком
от деления полинома f на F. Более , того если ≠
0, то
( ) ≥
( )
Вот
формальное описание : алгоритма
: Вход f1,, f s , f
: Выход a1,, as , r
a1
: 0;...; as
: 0; r : 0

50:= естьделение false
WHILE
i  s AND = естьделение false DO
IF LT ( f
i ) делит LT(p) THEN
a
i :
 a
i  LT(p)/LT( f
i )
p:=
p-( LT(p)/LT( fi
)) fi
:= естьделение
true
ELSE
i:= i+1
IF
:=false естьделение
THEN
r: =r+LT(p)
p: =p-LT(p)
Алгебраическая ,
техника использованная в , алгоритме
очень . ,
проста Тем более удивительно что этот алгоритм был

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

любую упорядоченную . совокупность полиномов Алгоритм был
реализован в системе компьютерной
Maple 12. алгебры
>restart;with(Groebner):
>s: =2 plx:='plex(x,y,z)':
>fs:=[x*y^2-x, x- y^3];
fs:=[ − , − ]

$51>f:=x^7*y^2+x^3*y^2-y+1; f:= + − +1 >a:=array(1..s): >for j from1 to s do a[j]:=0: od: >r:=0; r:=0 >p:=f: >while p<>0 do >i:=1: isdiv:=0: >while (i<=s) and (isdiv=0) do >if divide(leadterm(p, plx), leadterm(fs[i], plx), 'rt')=true then >a[i]:=a[i]+(leadcoeff(p, plx)*leadterm(p, plx))/(leadcoeff(fs[i], plx)*leadterm(fs[i], plx)): a[i]:=normal(a[i], expanded): printf("a[%d]:=%a\n", i, a[i]): >p:=p-((leadcoeff(p, plx)*leadterm(p, plx))/(leadcoeff(fs[i], plx)*leadterm(fs[i], plx)))*fs[i]: p:=normal(p, expanded): prinrf("p:=%a\n", p): >isdiv:=1: >else i:=i+1: end if: >end do: >if isdiv=0 then$ $52>r:= r+leadcoeff(p,plx)*leadterm(p,plx): r:=normal(r, expanded): printf("r:=%a\n", r): >p:=p-leadcoeff(p,plx)*leadterm(p,plx): p:=normal(p, expanded): printf("p:=%a\n", p): >end if: >end do; i:=1 a[1]:=x^6 p:=x^3*y^2+1+x^7 a[2]:=x^6 p:=x^3*y^2- y+1+x^6*y^3 a[1]:=x^6+y*x^5 p:=x^3*y^2-y+1+y*x^6 a[2]:=x^6+y*x^5 p:=x^3*y^2-y+1+y^4*x^5 a[1]:=x^6+y*x^5+y^2*x^4 p:=x^3*y^2-y+1+y^2*x^5$