РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ПРИ ПОМОЩИ БАЗИСА ГРЁБНЕРА-ШИРШОВА

РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ПРИ ПОМОЩИ БАЗИСА ГРЁБНЕРА-ШИРШОВА

Мухамедрахымова Айнур Утегеновна

магистрант 2-го курса Костанайского регионального университета им. А. Байтурсынова,

Республика Казахстан, г. Костанай

Утемисова Анар Алтаевна

канд. пед. наук, Костанайский региональный университет им. А. Байтурсынова,

Республика Казахстан, г. Костанай

За последние сорок лет был достигнут значительный прогресс в области компьютерной алгебре, одной из приоритетных задач которой является развитие методов решения систем нелинейных алгебраических уравнений от нескольких переменных, а также изучения алгебраических идеалов, порожденных нелинейными полиномиальными системами [1, с. 47]. Нелинейный системный анализ использует более широкий спектр подходов математических инструментов, чем линейный системный анализ. Одна из возможных причин состоит в том, что для линейных систем существует общее приложение, общая формула, когда нет столь узких подходов к решению нелинейных систем [2, с. 100].

Изначально теория базисов Грёбнера была предпринята независимо Ширшовым для неассоциативных алгебр [3, с. 27]. В настоящее время эта теория широко используется в различных областях математики.

Наиболее известной формой базисов полиномиальных идеалов являются базисы Грёбнера-Ширшова коммутативно-ассоциативного кольца, алгоритм вычисления которого был предложен Бухбергером ещё в середине 1960 года. Базисы Грёбнера позволяют искать решения систем нелинейных алгебраических уравнений от нескольких переменных, раскладывать на множители целые числа, решать задачу принадлежности полинома идеалу и другие алгоритмические задачи в полиномиальных идеалах [4, с. 26].

Со всякой системы алгебраических уравнений

                                              (1)

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

Если систему (1) обозначим буквой , то соответствующий идеал обозначиться как .

Лемма 1. Если , то  для всякого решения  системы .

Предложение 1. Пусть  и  два базиса одного идеала . Тогда системы

   (*)          и             (**)

эквивалентны [5, с. 268].

Следствие. Всякая система алгебраических уравнений от одного неизвестного эквивалентна системе из одного уравнения [5, с. 436].

Определение базиса Грёбнера-Ширшова. Задача вхождения

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

Например, для  имеем ,

Операция редукции. Предполагают, что старший член многочлена  делится на старший член некоторого из многочленов  т.е. , где  – одночлен. Тогда положим . При этом старший член многочлена  меньше старшего члена многочлена  [6, с. 142].

Из теоремы Гильберта о базисе вытекает существование базиса Грёбнера-Ширшова в любом идеале [7, с. 101]. Очевидно, рассматривают идеал, порожденный старшими членами элементов идеала, и выбирают в нем конечный базис из числа образующих. Тогда элементы исходного идеала, старшие члены которых образуют базис идеала старших членов, составляют конечный базис Грёбнера-Ширшова исходного идеала [8, с. 35].

Алгоритм построения базиса Грёбнера-Ширшова заключается в том, что множество многочленов , заданное изначально, порождающее идеал, не является базисом Грёбнера-Ширшова; добавляют в него -многочлены каждой пары многочленов, редуцируя предварительно эти -многочлены по всему множеству . В найденном базисе Грёбнера-Ширшова можно редуцировать каждый многочлен по множеству всех остальных для минимизации числа многочленов. Этот алгоритм называется алгоритмом Бухбергера [9, с. 211].

Алгоритм Бухбергера состоит из следующих шагов:

1. Необходимо проверить, есть ли в наборе многочленов , являющийся базисом идеала  зацепления. Если зацеплений нет, то набор является базисом Грёбнера идеала , не то переходим ко 2 шагу.

2. По найденному зацеплению  многочленов и положим , , где  – наибольший общий делитель и. Рассмотривают многочлен . Многочлен  называют -многочленом пары  и обозначают или  По возможности редуцируют многочлен  с помощью базиса . Если многочлен  редуцировался к нулевому многочлену , то мы переходим к 3 шагу, не то к 4 шагу. Редуцируемость многочлена  к нулю и вид многочлена  зависят от выбранной последовательности, применяемых редукций. В алгоритме используют любую применимую последовательность редукций и, получив нередуцируемый многочлен , переходим к 3 шагу, более никогда зацепление  не рассматривая [10, с. 151].

3. Добавляют многочлен  к набору  в качестве  и переходим к 4 шагу.

4. В построенному к настоящему моменту множестве многочленов рассматривают зацепление, которое не было рассмотрено ранее, и переходят ко 2 шагу. Алгоритм завершится тогда, когда будут рассмотрены все имеющиеся зацепления. За конечное число шагов получают набор многочленов , , в котором каждое зацепление разрешимо. Это и будет базисом Грёбнера-Ширшова идеала .

Постановка задачи. Применение алгоритма Бухбергера

Задача 1. Решить систему, используя алгоритм Бухбергера

для нахождения базисов Грёбнера-Ширшова.

Будем считать . Пусть

 Зацепление :

Зацепление :

Редукция с помощью

Зацепление :

Редукция с помощью

Редукция с помощью

В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы

Ответ:  базисами Грёбнера-Ширшова являются элементы:

.

Задача 2: используем алгоритм Бухбергера в системе

для нахождения базисов Грёбнера-Ширшова.

Пусть Будем считать .

Зацепление :

Редукция с помощью

Зацепление :

Редукция с помощью

Зацепление :

Редукция с помощью

Зацепление :

Редукция с помощью

Редукция с помощью

Редукция с помощью

Зацепление :

Редукция с помощью

Редукция с помощью

Редукция с помощью

Зацепление :

Редукция с помощью

Редукция с помощью

Редукция с помощью

Зацепление :

Редукция с помощью

Редукция с помощью

Редукция с помощью

Редукция с помощью

В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы  Из этого следует конечность числа решений. Найдем решения. Из ,  подставив ,  получим . Из .

Ответ:  базисами Грёбнера-Ширшова являются элементы:

.

Заключение

В данной работе был проведен анализ данных из научных источников об истории изучения базисов Грёбнера-Ширшова для решения систем нелинейных алгебраических уравнений от нескольких переменных.

Был изучен алгоритм Бухбергера для нахождения базисов Грёбнера-Ширшова идеала , который состоит из четырех шагов. Далее был получен набор многочленов , , в котором каждое зацепление разрешимо. Это и будет базисом Грёбнера-Ширшова идеала .

Список литературы:

1. Кокс Д., Литтл Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. [Текст] / Д.Кокс, Д.Литтл // Монография. – М.: Изд-во МГУ, 2000. – 687 с.
2. Мухамедрахымова А.У., Утемисова А.А. Особенности нелинейных систем уравнений и их решений. [Текст] // А.А. Утемисова, А.У. Мухамедрахымова. // Байтурсыновские чтения – 2020. Материалы международной научно-практической конференции. – 370 с.
3. Садовский А.П. Полиномиальные идеалы и многообразия. [Текст] / А.П.Садовский // Учебное пособие. – Минск: Изд-во Белорусский государственный университет, 2004. – 153 с.
4. Аржанцев И.В. Базисы Грёбнера и системы алгебраических уравнений. [Текст] / И.В. Аржанцев. // Учебное пособие. М.: МЦНМО, 2003. – 68 с.
5. Прасолов В.В. Многочлены. [Текст] / В.Н.Прасолов //Учебное пособие. – М.: Изд-во Моск. центр непрерывного матем. образования, 2003. – 336 с.
6. Латышев В.Н. Улучшенная версия стандартных базисов. Формальные степенные ряды и алгебраическая комбинаторика. [Текст] / В.Н.Латышев //  Proc. 12-й Междунар. Конф., FPSAC'00, Москва, Россия, 26-30 июня 2000 г. \ Д. Кроб, ред. - Берлин: Springer, 2000. – 505
7. Бокуть Л.А. Вложения в простые ассоциативные алгебры. Алгебра и логика. [Текст] / Л.А.Бокуть // Учебное пособие. – Новосиб.: Изд-во Новосиб. гос. ун-т, 2001. – 142 с.
8. Балаба И.Н., Пихтильков С.А. Абстрактная и компьютерная алгебра. [Текст] / И.Н.Балаба, С.А.Пихтильков //Учебное пособие. – Тула: Изд-во ТГПУ им. Л.Н. Толстого, 200 – 129 с.
9. Панкратьев Е.В. Введение в компьютерную алгебру. [Текст] / Е.В.Панкратьев // Учебное пособие. – 2-е изд. — НОУ «ИНТУИТ», 2016. — 326 c.
10. Ширшов А.И. Некоторые алгоритмические проблемы для алгебр Ли. [Текст] / А.И.Ширшов // Сибирский математический журнал, 1962. – 296 с.