Базис Грёбнера (>g[nv Ij~Quyjg)
Ба́зис Грёбнера — множество, которое порождает идеал заданного кольца многочленов, обладающее специальными свойствами.
Определение
[править | править код]Пусть для поля и коммутирующих переменных заданы: некоторый идеал кольца многочленов от переменных и некоторый полный порядок «» на мономах , где , то есть для . При этом порядок обязан дополнительно удовлетворять двум условиям:
- мультипликативность: влечёт для ;
- минимальность единицы: для , то есть .
Член называется старшим членом (относительно упорядочения ) многочлена , если для всех .
Базисом Грёбнера идеала кольца называется конечное множество многочленов из , порождающее идеал и обладающее свойством: для любого многочлена найдётся многочлен такой, что делится на .
Виды базисов Грёбнера
[править | править код]Минимальный базис Грёбнера
[править | править код]Минимальным базисом Грёбнера полиномиального идеала I называется его базис Грёбнера G, такой, что:
- Коэффициент при старшем мономе каждого равен единице.
- Старший моном каждого не делится ни на один старший моном других элементов базиса.
Редуцированный базис Грёбнера
[править | править код]Редуцированным базисом Грёбнера полиномиального идеала I называется его базис Грёбнера G, такой, что:
- Коэффициент при старшем мономе каждого равен единице.
- Никакой из мономов никакого не делится ни на один старший моном других элементов базиса.
Для редуцированного базиса Грёбнера идеала верно следующее утверждение:
Пусть I — полиномиальный идеал, и задано некоторое мономиальное упорядочение. Тогда существует единственный редуцированный базис Грёбнера идеала I.
Алгоритмы построения
[править | править код]Самым первым алгоритмом построения редуцированного базиса Грёбнера идеала считается алгоритм Бухбергера. Идея алгоритма та же, что в алгоритме Кнута — Бендикса[англ.]. Интересно, что известный метод Гаусса решения систем линейных уравнений является частным случаем алгоритма Бухбергера.
Кроме того, французским математиком Жаном-Шарлем Фожером были предложены алгоритмы F4 и F5 нахождения базиса Грёбнера.
Применения
[править | править код]Базис Грёбнера является важнейшим понятием компьютерной алгебры, алгебраической геометрии и вычислительной коммутативной алгебры.
История
[править | править код]Австрийский математик Вольфганг Грёбнер[англ.] разработал теорию стандартных базисов для свободного коммутативного случая в начале 1930-х годов, а опубликовал её в статье 1950 года[1], где он написал:
Я начал использовать этот метод 17 лет назад для различных примеров, в том числе и очень сложных.
Оригинальный текст (нем.)Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.
В 1964 году аналогичная концепция для локальных колец была разработана Хэйсукэ Хиронакой, получившим Филдсовскую премию в 1970 году. Он назвал введённые системы полиномов стандартным базисом.
Понятие базиса Грёбнера было введено в 1965 году австрийским математиком Бруно Бухбергером, бывшим студентом Грёбнера. Бухбергер предложил конструктивную процедуру построения базиса Грёбнера в виде эффективного компьютерного алгоритма, впоследствии получившего название алгоритма Бухбергера[англ.].
Существование стандартного базиса идеала опирается на «лемму о композиции», которая впервые была доказана для самого сложного из известных случаев (свободных алгебр Ли) А. И. Ширшовым[2]. При этом правильность аналогичного утверждения для свободного ассоциативного и коммутативного случая считалась очевидной и не привлекала особого внимания вплоть до более поздних работ Л. А. Бокутя по теории вложений ассоциативных колец в тела и кольца с заданными свойствами. В 1972 году Л. А. Бокуть опубликовал «лемму Ширшова о композиции» для свободного ассоциативного случая в записках курса по ассоциативным алгебрам Новосибирского университета. Отсюда и из устного общения она стала известна американскому алгебраисту Дж. Бергману, который опубликовал её в 1979 году под названием «Diamond Lemma» («алмазная лемма»). Строгое доказательство в работе отсутствовало, а была обозначена только мнемоническая схема «слияния», необходимая для понимания идеи Ширшова о композиции. После публикации Бергмана «алмазная лемма» стала популярна среди алгебраистов и геометров, она также привлекла внимание к «базису Грёбнера» Бухбергера. В середине 1980-х годов стандартный базис для супералгебр и цветных алгебр Ли был построен московским алгебраистом А. А. Михалёвым.
Примечания
[править | править код]- ↑ W. Gröbner. Über die Eliminationstheorie (англ.) // Monatshefte für Mathematik[англ.] : journal. — 1950. — Vol. 54. — P. 71—78.
- ↑ СМЖ, 1962, т. 3, №2, с. 292-296.
Литература
[править | править код]- Аржанцев И. В. Базисы Грёбнера и системы алгебраических уравнений. — М.: МЦНМО, 2003. — 68 с. — ISBN 5-94057-095-X.
- Бухбергер Б. и другие. Компьютерная алгебра: Символьные и алгебраические вычисления. — М.: Мир, 1986. — 392 с.
- Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. — М.: Мир, 2000. — 687 с. — ISBN 5-03-003320-3.
- Панкратьев Е. В. Введение в компьютерную алгебру. — Интуит. — ISBN 978-5-9556-0099-4.
Ссылки
[править | править код]- Чуркин В. А. Системы полиномиальных уравнений, идеалы и их базисы-делители.
- Bernd Sturmfels. What is a Gröbner basis?
Для улучшения этой статьи желательно:
|