Составители:
Рубрика:
g
3
= x
2
y
2
− z. (5.23)
g
4
= −x
2
yz + z
2
, (5.24)
g
5
= z
2
y − z
2
, (5.25)
g
6
= −x
2
z
2
+ z
3
. (5.26)
Нетрудно проверить, что S-полиномы
S(g
3
, g
5
), S(g
2
, g
6
), S(g
3
, g
6
), S(g
4
, g
6
), S(g
5
, g
6
)
редуцируется в g к нулю. Таким образом базис (5.22) – (5.26) яв-
ляется стандартным базисом рассматриваемого идеала.
Замечание 4. Этот пример показывает, что отыскание стандарт-
ного базиса может быть весьма трудоёмким делом и полезны бы-
ли бы те или иные методы оптимизации. Можно исключить неко-
торые S-полиномы из рассмотрения, используя следующий факт
(критерий Бухбергера): если S(f, h) и S(g, h) редуцируется к нулю
в g, и старший моном полинома h делит наибольшее общее крат-
ное НОК(
e
f,
e
g) старших мономов
e
f,
e
g полиномов f и g, то S(f, g)
редуцируется к нулю (т.е. его можно не рассматривать).
Остаётся вопрос о наиболее рациональном порядке рассмотре-
ния S-полиномов для полиномов множества g и о сложности та-
ких вычислений. П оказано, что сложность вычисления стандартно-
го базиса (объём памяти) растёт экспоненциально с ростом числа
переменных.
В случае двух переменных показано, что если все данные имеют
степени ограниченные числом d, то степени элементов стандартно-
го базиса ограничены числом 2d − 1 при использовании степенно-
логарифмического порядка, а число элементов стандартного базиса
не превосходит k + 1, где k – минимум стпеней старших мономов
всех данных (в примере k=4).
Замечание 5. Алгоритм Бухбергера в случае одной переменной
и двух полиномов эквивалентен отысканию НОД этих полиномов.
Любой S-полином это потином наивысшей степени минус второй
полином с некоторым множителем, исключающий наивысшую сте-
пень. Расширение базиса с помощью этого S-полинома позволяет
отбросить полином старшей степени.
Для случая нескольких переменных и линейных полиномов ал-
горитм Бухбергера соответствует исключению Гаусса, поскольку
78
Страницы
- « первая
- ‹ предыдущая
- …
- 75
- 76
- 77
- 78
- 79
- …
- следующая ›
- последняя »
