Базис Ширшова. дипломная работа Мурзагалиева М.Б.. Дипломная работа использование базиса ГрёбнераШиршова при решении систем алгебраических уравнений 5B010900 Математика
 Скачать 152.02 Kb.
|
|
Костанайский государственный педагогический университет им. У. Султангазина Естественно-математический факультет Кафедра физико-математических дисциплин Допущен к защите «__» ______201__г Подпись _____________Телегина О.С. (и.о. зав. кафедрой) ДИПЛОМНАЯ РАБОТА Использование базиса Грёбнера-Ширшова при решении систем алгебраических уравнений 5B010900 – Математика Выполнил: Научный руководитель: Мурзагалиева М.Б. Алимбаев А.А., магистр математик, ст. преподаватель кафедры Костанай 2019 Костанайский государственный педагогический университет имени У.Султангазина Естественно-математический факультет Специальность «Математика» Кафедра физико-математических дисциплин «Утверждаю» и.о. зав. кафедрой ФМД ______________ Телегина О.С. «____» _____________20___г. ЗАДАНИЕ на выполнение дипломной работы Студенту _________________________________________________________________ Тема работы: __________________________________________________________________ Утверждена приказом по вузу № ______ от « _____ » _______________ 20___г. Срок сдачи законченного проекта (работы) « _____ » _______________ 20___г. Исходные данные к работе ______________________________________________________ Перечень подлежащих разработке в дипломном проекте вопросов или краткое содержание дипломной работы: а) ________________________________________________________________ б) ________________________________________________________________ в) ________________________________________________________________ Перечень графического материала (с точным указанием обязательных чертежей) Рекомендуемая основная литература Консультации по работе с указанием относящихся к ним разделов работы
Дата выдачи задания ___________________________________________________________ И.о. зав. кафедрой ФМД ___________________________________________Телегина О.С. (подпись) (Ф.И.О.) Руководитель работы __________________________________________________________ (подпись) (Ф.И.О.) Задание принял к исполнению студент __________________________________________________________________ ( подпись) (Ф.И.О.) График подготовки дипломной работы
С ОДЕРЖАНИЕ ВВЕДЕНИЕ За последние сорок лет был достигнут значительный прогресс в области компьютерной алгебре, одной из приоритетных задач которой является развитие методов решения систем нелинейных алгебраических уравнений от нескольких переменных, а также изучения алгебраических идеалов, [1] порожденных нелинейными полиномиальными системами. Изначально теория базисов Грёбнера была предпринята независимо Ширшовым для неассоциативных алгебр. [2] В настоящее время эта теория широко используется в различных областях математики. Наиболее известной формой базисов полиномиальных идеалов являются базисы Грёбнера-Ширшова коммутативно-ассоциативного кольца, алгоритм вычисления которого был предложен Бухбергером ещё в середине 1960 года. Базисы Грёбнера [3] позволяют искать решения систем нелинейных алгебраических уравнений от нескольких переменных, раскладывать на множители целые числа, решать задачу принадлежности полинома идеалу и другие алгоритмические задачи в полиномиальных идеалах. [2] Актуальность: в настоящее время базис Грёбнера-Ширшова активно используются как в теоретических исследованиях, так и в вычислительной алгебре. Одно из достоинств данного метода состоит в том, что с его помощью можно алгоритмизировать процесс поиска ответов на большое число вопросов. Как следствие, становится возможным применением вычислительной техники для решения систем алгебраических уравнений. Целью дипломной работы является исследование алгоритма Бухбергера для вычисления базиса Грёбнера-Ширшова, при решении систем алгебраических уравнений от нескольких переменных. Задачи: рассмотреть и проанализировать построение базиса Грёбнера-Ширшова; изучить алгоритм Бухбергера для построения базисов Грёбнера-Ширшова; показать типовые решения системы алгебраических уравнений от двух и от трёх неизвестных. Объект исследования: система алгебраических уравнений. Предмет исследования: базис Грёбнера-Ширшова коммутативно-ассоциативного кольца. Методы исследования, используемые в данной дипломной работе: анализ, для выявления алгоритма Бухбергера; синтез, для описания алгоритма Бухбергера при решении систем алгебраических уравнений ассоциативного, коммутативного кольца; анализ литературы по данной работе. Новизна: в данной дипломной работе получены результаты для определения базисов Грёбнера-Ширшова. Все самостоятельно полученные результаты являются новыми. Соответствующих аналогов по полученным результатам нет. Практическая значимость: материалы данной дипломной работы могут использоваться при чтении спецкурсов, для студентов специальностей математика и информатика. Данная дипломная работа состоит из введения, двух глав, заключения и списка используемых источников. Глава 1 Система алгебраических уравнений. Кольцо многочленов от нескольких переменных. Идеалы в кольцах многочлена 1.1 Основные понятия и определения В этом параграфе вводятся некоторые основные обозначения, понятия и утверждения, которыми в дальнейшем часто пользуются. Фиксируются натуральное число и некоторое поле 𝕂 (можно считать, что 𝕂 есть поле рациональных чисел, поле действительных чисел или поле комплексных чисел). Определение 1.1.1 Системой алгебраических уравнений называется система вида: , (1) где – переменные, – набор многочленов от переменных с коэффициентами в поле 𝕂. [4] Определение 1.1.2Система алгебраических уравнений называется конечной, если в нее входит лишь конечное число уравнений. Определение 1.1.3 Всякий набор многочленов равному набору чисел из поля 𝕂 называют решением (4). Определение 1.1.4 Две системы алгебраических уравнений называют равносильными, если всякое решение одной системы является решением другой, и наоборот, или в обеих системах решений нет. Решить систему – это значит найти такие уравнения системы, которые обращают каждое уравнение в верное числовое равенство, или доказать, что решений нет. Одним из примеров системы алгебраических уравнений является система линейных уравнений, вида (2) Определение 1.1.5Система (2) называется совместной, если имеет хотя бы одно решение. Определение 1.1.6 Система (2) называется определенной, если она имеет ровно одно решение. Определение 1.1.7 Матрицу называют матрицей коэффициентов системы (2), а матрицу – расширенной. [4] Для решения системы линейных алгебраических уравнений используют: метод Гаусса (метод последовательного исключения неизвестных); метод Крамера, у которых определитель матрицы системы не равен нулю; геометрический метод, в котором множество решений системы алгебраических уравнений над 󠇛полем действительных чисел, есть некоторое подмножество пространства 󠇛 . 1.2 Некоторые сведения о кольцах многочлена от нескольких переменных Функцию , где – целое число, называют многочленом. Число – степень многочлена, а – коэффициенты, действительных или комплексных чисел. [5] Коэффициенты многочлена берутся из определённого коммутативного кольца 𝕂 (чаще всего поля, например, поля вещественных или поля комплексных чисел). Относительно операции сложения и умножения многочлены образуют кольцо (более того, ассоциативно-коммутативную алгебру над кольцом 𝕂 без делителей нуля), обозначают как 𝕂 [ . Если 𝕂 есть коммутативное кольцо с единицей, то кольцо многочленов от одной переменной над кольцом 𝕂 является коммутативным кольцом с единицей. [6] Кольцо называют кольцом многочленов от двух переменных и над кольцом . [5] Определение 1.2.1 Многочлен из кольца записывается в виде: где . Элементы называются коэффициентами многочлена Определение 1.2.2 Многочлен равен многочлену если для всех . Определение 1.2.3 Если 𝕂 – кольцо многочленов от переменных над кольцом 𝕂 , то кольцо многочленов 𝕂 называют кольцом многочленов от переменных над кольцом 𝕂. [5] 1.3 Идеал Определение 1.3.1Непустое множество , на котором заданы две операции сложения и умножения , называется кольцом, если выполняются следующие условия: Относительно операции множество – коммутативная группа; Относительно операции множество – ассоциативна; Операции и связаны законом дистрибутивности. Определение 1.3.2Кольцо многочленов – кольцо, образованное многочленами от одной или нескольких переменных с коэффициентами из другого кольца. [3] Определение 1.3.3 Непустое подмножество кольца называют идеалом в записывают как , которое удовлетворяет двум свойствам: элемент ; элемент . Предложение 1.3.4 В кольце целых чисел всякий идеал имеет вид (порождаются одним элементом Доказательство. Рассматривают некоторый ненулевой идеал кольца и -минимальное натуральное число в . Если каждое натуральное число идеала делится на , то имеют идеал . Если натуральное число , которое не делиться на , разделив на с остатком, получим . Так как , то – противоречие с выбором . Итак, Задача 1.3.1 Докажите, что в поле нет нетривиальных идеалов. Решение: пусть𝕂 – поле, а – идеал. Пусть нетривиален и содержит некоторый элемент . Тогда существует , так как это поле, получается, что . То есть единица принадлежит идеалу. Тогда , – идеал Задача 1.3.2 Проверьте, что множество есть идеал кольца для всякого фиксированного . Решение. Проверим для : коммутативность сложения; ассоциативность сложения; существование нейтрального элемента; противоположность; дистрибутивность умножения на скаляр относительно сложения; дистрибутивность умножения на вектор; умножение на нейтральный элемент; ассоциативность умножения на скаляр. Определение 1.3.5 Кольцо , в котором все идеалы главные, называют кольцом главных идеалов. [1] Пусть – произвольные элементы кольца . Определение 1.3.6 Элементы образуют базис идеала Говорят, что идеал образует конечный базис, если в нем найдутся такие элементы , что [5] 1.4 Идеалы в кольцах многочлена. Теорема Гильберта о базисе Предложение 1.4.1 Кольцо есть кольцо главных идеалов для любого поля . Как уже указывалось, кольца многочленов от многих переменных не является кольцами главных идеалов. Тем не менее, для них справедлива теорема, доказанная Д. Гильбертом на рубеже XX веков: Теорема Гильберта о базисе. Каждый идеалдопускает конечный базис, т.е. найдутся такие , что Со всякой системы алгебраических уравнений (3) можно связать идеал , порожденный многочленами, отвечающими уравнениям системы: Если систему (3) обозначим буквой , то соответствующий идеал обозначиться как . Лемма 1.4.2 Если , то для всякого решения системы . Доказательство. , откуда Предложение 1.4.3 Пусть и два базиса одного идеала . Тогда системы (*) и (**) эквивалентны. Доказательство. Пусть – решение системы (*). Показывают, что она является решением системы (**). Поскольку по условию, из леммы следует, что . Аналогично, каждое решение (**) является решением (*). Следствие 1.4.4 Всякая система алгебраических уравнений от одного неизвестного эквивалентна системе из одного уравнения. [6] Доказательство. Следуя о теореме Гильберта, во всяком идеале ] можно выбрать конечный базис. [7] Глава 2 Базис Грёбнера-Ширшова идеала 2.1 Лексикографический порядок на множестве одночленов Для нахождения базиса Грёбнера-Ширшова идеала , требуется ввести понятие упорядочивания членов многочлена из , и определить для многочлена понятие старшего члена. Старший член многочлена есть одночлен . Чтобы определить старший член у многочлена от нескольких переменных, например, у , можно пользоваться так называемое, лексикографическим способом. Определение 2.1.1 Многочлен, который состоит из одного члена , , называется одночленом или мономом. Старшим членом многочлена является один из его одночленов . Каждому одночлену можно сопоставить набор целых неотрицательных чисел, называемое набором степеней. Например, при одночлену отвечает набор (3,5,0,0). Набор ( ) больше набора , если существует такое , где , что Такой способ упорядочения наборов называют лексикографическим способом. [2] Например, при , и , . Указанным способом можно сравнить любые два различных набора одной длины. Определение 2.1.2 Одночлен больше одночлена , если ( . Замечание 2.1.3 Существуют много лексикографических упорядочивании, и каждому такому упорядочиванию переменных отвечает свое. Рассматривается также однородный лексикографический порядок: у двух наборов ( и сначала сравниваются степени и если степени совпадают, наборы сравниваются лексикографически. Определение 2.1.4 Старшим членом многочлена называют наибольший ненулевой одночлен , находящегося в . [2] Например, старший член многочлена есть , а старший член многочлена есть (нумеруется . Лемма о старшем члене. Старший член произведения многочленов есть произведение старших членов и . Доказательство. Если ( и ( , то ( ( . 2.2 Определение базиса Грёбнера-Ширшова. Задача вхождения Для любого многочлена , , где – старший член , а – сумма остальных членов. Например, для имеем , Операция редукции. Предполагают, что старший член многочлена делится на старший член некоторого из многочленов т.е. , где – одночлен. Тогда положим . При этом старший член многочлена меньше старшего члена многочлена . [8] Лемма 2.2.1 Доказательство. Достаточно проверить, что разность принадлежит Имеем Задачу вхождения можно решить не для , а для и здесь вновь можно применить редукцию. Если за конечное число редукций многочлен редуцируется к нулю, то так как нуль принадлежит любому идеалу. Пример 2.2.1 . делится на . РЕДУКЦИЯ 1 . Тут делится на РЕДУКЦИЯ 2 (редукция произведена дважды). Тут делится на РЕДУКЦИЯ 3 Определение 2.2.2 Пусть – конечное множество многочленов из . Многочлен редуцирован относительно , если никакой член многочлена не делится на старший член многочлена для всех [3] Определение 2.2.3 Базис идеала называют базисом Грёбнера-Ширшова идеала , если всякий многочлен редуцируется к нулю при помощи . Определение 2.2.4 Набор многочленов – базис Грёбнера-Ширшова в если одночлен делится на один из одночленов . Как определить лежит ли многочлен главному идеалу . Для этого необходимо делить многочлен на «в столбик», и если разделиться без остатка то иначе Задача вхождения. Пусть идеал ] задан свои базисом Требуется найти алгоритм, позволяющий за конечное число шагов выяснить, принадлежит ли данный многочлен идеалу , т.е. существует ли такие многочлены что . Решение задачи вхождения. Пусть известен базис Грёбнера-Ширшова идеала и дан многочлен . Производят всевозможные редукции с помощью элементов базиса (любая операция редукции конечна). Многочлен лежит в тогда и только тогда, когда в результате редукции получим ноль. Из задачи 4.16 и теоремы Гильберта о базисе вытекает существование базиса Грёбнера-Ширшова в любом идеале. [7] Очевидно, рассматривают идеал, порожденный старшими членами элементов идеала, и выбирают в нем конечный базис из числа образующих. Тогда элементы исходного идеала, старшие члены которых образуют базис идеала старших членов, составляют конечный базис Грёбнера-Ширшова исходного идеала. [2] Для построения базиса Грёбнера-Ширшова идеала, по некоторому его исходному базису, пользуются алгоритмом, который представлен в следующем параграфе. 2.3 Алгоритм Бухбергера Пусть – идеал. – базис идеала т.е. существуют такие многочлены , где . Для построения базиса Грёбнера-Ширшова используют следующие определения. Определение 3.3.1 Многочлены и имеют зацепление, тогда и только тогда, когда старшие члены и делятся одновременно на некоторый одночлен , отличный от константы. [9] Если и имеют зацепление, т.е. , где – наибольший общий делитель и , то рассмотренный многочлен Многочлен называют -многочленом пары и обозначают или . Редуцируют многочлен с помощью базиса до все возможности. В итоге получают нередуцируемый многочлен . Если , то зацепление разрешимо. Иначе добавляют к базису идеала : . [2] В новом базисе снова ищут всевозможные зацепления и редуцируют соответствующие многочлены . Пример 3.3.1 Идеал . . Имеется зацепление , в результате получают, что . Добавляя к базисам идеала , Других зацеплений нет. Пример 3.3.2 Пусть , Зацепление имеют только и : Редукция с помощью Дальше редуцировать нельзя, поэтому . Других зацеплений нет. Теорема 3.3.2 Для каждого набора многочленов при завершении редукции конечного число зацеплений, получим набор , где каждое зацепление разрешимо. Теорема 3.3.3 Базис идеала I является базисом Грёбнера-Ширшова, если в нем нет зацеплений либо каждое зацепление разрешимо. [3] Из теоремы 3.10 непосредственно следует алгоритм для построения базиса Грёбнера-Ширшова. Он заключается в том, что множество многочленов , заданное изначально, порождающее идеал, не является базисом Грёбнера-Ширшова; добавляют в него -многочлены каждой пары многочленов, редуцируя предварительно эти -многочлены по всему множеству . В найденном базисе Грёбнера-Ширшова можно редуцировать каждый многочлен по множеству всех остальных для минимизации числа многочленов. Этот алгоритм называется алгоритмом Бухбергера. [10] Алгоритм Бухбергера состоит из следующих шагов: 1. Необходимо проверить, есть ли в наборе многочленов , являющийся базисом идеала зацепления. Если зацеплений нет, то набор является базисом Грёбнера идеала , не то переходим ко 2 шагу. 2. По найденному зацеплению многочленови положим , , где – наибольший общий делитель и . Рассмотривают многочлен . Многочлен называют -многочленом пары и обозначают или По возможности редуцируют многочлен с помощью базиса . Если многочлен редуцировался к нулевому многочлену , то мы переходим к 3 шагу, не то к 4 шагу. Редуцируемость многочлена к нулю и вид многочлена зависят от выбранной последовательности, применяемых редукций. В алгоритме используют любую применимую последовательность редукций и, получив нередуцируемый многочлен , переходим к 3 шагу, более никогда зацепление не рассматривая. [10] 3. Добавляют многочлен к набору в качестве и переходим к 4 шагу. 4. В построенному к настоящему моменту множестве многочленов рассматривают зацепление, которое не было рассмотрено ранее, и переходят ко 2 шагу. Алгоритм завершится тогда, когда рассмотрятся все имеющиеся зацепления. За конечное число шагов получают набор многочленов , , в котором каждое зацепление разрешимо. Это и будет базисом Грёбнера-Ширшова идеала . [3] Базис Грёбнера-Ширшова можно упростить: Если и – элементы базиса Грёбнера-Ширшова идеала и делится на , то можно удалить. Оставшиеся элементы по-прежнему образуют базис Грёбнера-Ширшова идеала . Определение 3.3.4 Базис Грёбнера идеала называется минимальным, если не делится на при всех . [11] Касается не старших членов многочленов . Пусть некоторый член многочлена делится на старший член многочлена . Редуцируют с помощью , полученный результат запизывают в вместо . При данной операции число элементов в базисе Грёбнера-Ширшова не изменится, но понижаются степени членов многочленов . 2.4 Базис свободных неассоциативных алгебр А.И. Ширшов в 1962 году и Б. Бухбергер в 1965 году ввели одни и те же, по существу, идеи для лиевых многочленов (Ширшов) и коммутативных многочленов (Бухбергер). Это, во-первых понятие композиции двух многочленов (Ширшов) или -многочлена (Бухбергер) и понятие множества многочленов, «полного» относительно взятия композиций или -многочлена (позднее Бухбергер назвал эти множества базисами Грёбнера; Л.А. Бокуть назвал эти множества «замкнутыми относительно компзиции»; в последнее время эти множества для алгебр Ли в ассоциативных алгебр стали называть «Базисами Грёбнера-Ширшова»; в широком смысле «некоммутативные базисы Грёбнера»). Во-вторых, алгоритмы пополнения Ширшова и Бухбергера, присоединение к множеству всех нетривиальных после приведения относительно (исключения старших слов многочленов ) композиций [12], до тех пор, пока не получится полное множество; Ширшов ввел специальное обозначение для результата пополнения множества -множество . [13] В-третьих, лемма Ширшова о композиции и теорема Бухбергера. Эти последние утверждения говорят, что если – полное относительно копозиции множество, и , то старшее слово , для некоторого . Разница в интерпретации заключается в том, что Бухбергер брал последнее свойство за определение «базиса Грёбнера», в то время как Ширшов формулировал свою лемму для любого . [14] В 1972 году Л.А. Бокуть сформулировал лемму Ширшова о композиции в современном мире. Работа Ширшова долгое время оставалась практически неизвестной за рубежом. В настоящее время работа получила всеобщее признание как новый метод в комбинаторике слов и как одна из идей, приведших Е.И. Зельманова к решению ослабленной проблемы Э.Э. Бернсайда и А.Р. Кемера к решению проблемы Шпехта. Целью данного образа являлось рассказать то, что было сделано в рассматриваемой области (базисы Грёбнера-Ширшова). Пусть – упорядоченное множество, , если – свободная ассоциативная алгебра над полем . – свободная алгебра Ли, порожденная в множеством относительно лиевого умножения [15] Базисными словами алгебры являются правильные в смысле Ширшова слова . Сейчас они называются словами Линдона-Ширшова. Определение 3.4.1 Слово называется правильным, если в лексикографическом смысле . На каждом правильном ассоциативном слове можно расставить скобки по правилу: где – самый длинный правильный конец слова , – некоторое правильное начало . Слова Линдона-Ширшова упорядочиваются следующим образов: В упорядоченности (сначала по степени, потом лексикографически). Пусть – старшее ассоциативное слово многочлена . Если – лиев многочлен, то – правильное слово где – правильные слова, меньшие . Многочлен называется унитарным, если . Композиция двух лиевых многочленов правильного слова , такого, что , , определяется так: где – некоторая специальная расстановка скобок на и . Для образования лиевой композиции и , необходимо взять ассоциативную композицию , а затем расставить скобки «специальным» образом. Основное свойство композиции: Пусть – два унитарных лиевых многочлена, таких, что . Тогда преобразование где – специальная расстановка скобок, называется исключением старшего слова. Определение-Лемма 3.4.2 Пусть – правильное слово с выделенным правильным подсловом . Тогда в слове Линдона-Ширшова одна пара скобок имеет вид : гдеслово может быть пустым. Слово представим в виде где – правильные слова и Такое представление существует и единственно. Заменим на слово . Полученное слово и есть специальная расстановка скобок на относительно . [16] Определение 3.4.3 Множество лиевых многочленов называется замкнутым относительно композиции (базисом Грёбнера-Ширшова), если любая композиция многочленов преобразуется в ноль с помощью исключения старшего слова многочленов [12] Лемма о композиции. Пусть множество унитарных лиевых многочленов, замкнутое относительно композции (т.е. базис Грёбнера-Ширшова). Если , то для некоторого . [11] 2.5 Постановка задачи. Применение алгоритма Бухбергера Задача 1: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : Редукция с помощью . Редукция с помощью . Зацепление Редукция с помощью . Зацепление Редукция с помощью Редукция с помощью Зацепление Редукция с помощью Редукция с помощью Зацепление Редукция с помощью Редукция с помощью Зацепление Редукция с помощью Редукция с помощью Редукция с помощью . Зацепление Редукция с помощью Редукция с помощью Редукция с помощью = . Зацепление Редукция с помощью Зацепление . Зацепление Редукция с помощью Зацепление Редукция с помощью . Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы , , Из этого следует конечность числа решений. Найдем решения. Из уравнения , подставив в получим, что или . Из . Ответ: при базисами Грёбнера-Ширшова являются элементы: , , , , или , , . Задача 2: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : Редукция с помощью Зацепление : . Зацепление : Редукция с помощью Зацепление : Зацепление : . Зацепление : Редукция с помощью Зацепление : Редукция с помощью Зацепление : Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы , Из этого следует конечность числа решений. Из уравнения . Из Ответ: при базисами Грёбнера-Ширшова являются элементы: , Задача 3: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : Зацепление : Редукция с помощью Зацепление : Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью . Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью : Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью . Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью . Зацепление : Редукция с помощью : Редукция с помощью : Зацепление : Редукция с помощью : Редукция с помощью Редукция с помощью : Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью . Редукция с помощью : . Редукция с помощью : Редукция с помощью Зацепление : В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы Из этого следует конечность числа решений. Найдем решения. Из при При и . При , Ответ: при базисами Грёбнера-Ширшова являются элементы: или . Задача 4: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : . Редукция с помощью . Редукция с помощью Зацепление : . Редукция с помощью . Зацепление : . Редукция с помощью . Редукция с помощью Редукция с помощью . Редукция с помощью Зацепление : . Зацепление : . Редукция с помощью Зацепление : . Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью . Зацепление : Зацепление : Редукция с помощью Редукция с помощью . Зацепление : Зацепление : Редукция с помощью . Редукция с помощью . Редукция с помощью Зацепление : . В итоге вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы: Из этого следует конечность числа решений. Найдем неизвестные переменные. Из . При и и При и и . При , . При . Ответ: при элементами базиса Грёбнера-Ширшова являются: Задача 5: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать Зацепление : Редукция с помощью . В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы: Из этого следует конечность числа решений. Теперь найдем решения. Из , , подставив в получим, что ; подставив в получим, что . Ответ: при элементами базиса Грёбнера-Ширшова являются: . Задача 6: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : Зацепление : Редукция с помощью . Редукция с помощью Редукция с помощью . Зацепление : Редукция с помощью . Редукция с помощью . Зацепление : Редукция с помощью . Редукция с помощью . Редукция с помощью . Редукция с помощью Редукция с помощью Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы: Найдем неизвестные переменные. Из . Подставив в получим, что . Из Ответ: При элементами базиса Грёбнера-Ширшова являются: . Задача7: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : Редукция с помощью Зацепление : Редукция с помощью Зацепление : Зацепление : Редукция с помощью Редукция с помощью . Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Зацепление : Зацепление : Редукция с помощью Редукция с помощью . Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью . Зацепление : Редукция с помощью Редукция с помощью Зацепление : Зацепление и : Редукция с помощью Зацепление и : Редукция с помощью Редукция с помощью Зацепление и : Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы: Из этого следует конечность числа решений. Теперь найдем решения. Из , , подставив в получим, что ; подставив в получим, что . Из , . Ответ: при базисами Грёбнера-Ширшова являются: или . Задача 8: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать Зацепление : Редукция с помощью . Зацепление : Зацепление : Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы Из этого следует конечность числа решений. Теперь найдем решения. Из , подставив в получим, что в получим, что . Из . Ответ: при базисами Грёбнера-Ширшова являются: , , , . Задача 9: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы Из этого следует конечность числа решений. Найдем решения. Из Подставив в уравнение . Из Ответ: при базисами Грёбнера-Ширшова являются: , , Задача 10: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Будем считать . Пусть Зацепление : Зацепление : Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы Ответ: базисами Грёбнера-Ширшова являются элементы: . Задача 11: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : Редукция с помощью Зацепление : Редукция с помощью Зацепление : Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера-Ширшова лежат элементы Из этого следует конечность числа решений. Найдем решения. Из , подставив , получим . Из . Ответ: базисами Грёбнера-Ширшова являются элементы: . Задача 12: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : Зацепление Зацепление Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью . Зацепление Редукция с помощью Редукция с помощью Редукция с помощью . Редукция с помощью Зацепление Редукция с помощью Редукция с помощью Редукция с помощью Зацепление Редукция с помощью Редукция с помощью Зацепление Редукция с помощью Редукция с помощью Редукция с помощью Зацепление Редукция с помощью Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера лежат элементы: . Из этого следует конечность числа решений. Найдем решения. Из уравнения . Подставив в уравнение ; подставив в уравнение . Подставив в уравнение ; подставив в уравнение . Ответ: При базисами Грёбнера-Ширшова являются элементы: или или Задача 13: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Будем считать . Пусть Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера лежат элементы: Из этого следует конечность числа решений. Найдем их. Из . Посдтавив в уравнение Ответ: При базисами Грёбнера-Ширшова являются элементы: Задача 14: используем алгоритм Бухбергера в системе для нахождения базисов Грёбнера-Ширшова. Пусть Будем считать . Зацепление : Редукция с помощью Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью Зацепление : Редукция с помощью Редукция с помощью Зацепление : Редукция с помощью В результате вычисления мы получили, что в базисе Грёбнера лежат элементы: . Из этого следует конечность числа решений. Найдем их. Из уравнения Подставив в уравнение или . Из уравнения Ответ: При базисами Грёбнера-Ширшова являются элементы: ЗАКЛЮЧЕНИЕ Рассмотрение работ Грёбнера-Ширшова послужила фундаментом данной дипломной работы. Одна из проблем, а именно нахождения базиса Грёбнера-Ширшова алгоритмом Бухбергера, была выбрана для рассмотрения и разрешения в данной работе. Задачи, которые были поставлены в ходе выполнения исследовательской работы, были решены. В первую очередь был проведен анализ данных из литературных источников об истории изучения базисов Грёбнера-Ширшова для решения систем алгебраических уравнений от нескольких переменных. Был изучен алгоритм Бухбергера для нахождения базисов Грёбнера-Ширшова идеала , который состоит из четырех шагов, в конечном итоге мы получаем набор многочленов , , в котором каждое зацепление разрешимо. Это и будет базисом Грёбнера-Ширшова идеала . После подобной работы были решены системы алгебраических уравнений от нескольких переменный, взятые из [1]. Составлен сборник индивидуальных задач от двух и трёх неизвестных переменных для самостоятельной работы. В итоге проведенной исследовательской работы, поставленная цель дипломной работы, а именно исследование алгоритма Бухбергера для вычисления базиса Грёбнера-Ширшова системы алгебраических уравнений от нескольких переменных, была достигнута, аналогов полученным результатам нет. Все решенные задачи производились самостоятельно. По данной дипломной работе была представлена на очной региональной студенческой научно-практической конференции, посвященной 80-летию Костанайского государственного педагогического универрситета им. У. Султангазина « Миссия молодого поколения в науке и образовании: традиции, инновации» г. Костанай, Казахстан, в которой было занято третье место. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Кокс Д., Литтл Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. – М.: Изд-во МГУ, 2000. – 687 с. 2.Бухбергер Б. Алгоритмический метод в теории полиномиальных идеалом. –Тула: Изд-во ТГПУ им. Л.Н. Толстого, 1986. – 372 с. 3. Аржанцев И.В. Базисы Грёбнера и системы алгебраических уравнений. – М.: Изд-во Моск. центр непрерывного матем. образования, 2003. – 68 с. 4.http://www.cleverstudents.ru/systems/solving_systems_of_linear_equations.html 5. Прасолов В.В. Многочлены. – М.: Изд-во Моск. центр непрерывного матем. образования, 2003. – 336 с. 6. Латышев В.Н. Комбинаторная теория колец. Стандартные базисы. – М.: Изд-во МГУ, 1988. – 687 с. 7. Бокуть Л.А. Вложения в простые ассоциативные алгебры. Алгебра и логика. – Новосиб.: Изд-во Новосиб. гос. ун-т, 1977. – 142 с. 8. Балаба И.Н., Пихтильков С.А., Абстрактная и компьютерная алгебра. – Тула: Изд-во ТГПУ им. Л.Н. Толстого, 2008. – 129 с. 9. Панкратьев Е.В. Введение в компьютерную алгебру. – М.: Изд-во МГУ, 1987. – 272 с. 10. https://www.youtube.com/watch?v=MEnak_neRo0 . – видео-лекция. 11. Ширшов А.И. Некоторые алгоритмические проблемы для алгебр Ли. – Сиб.: Изд-во Сиб.мат.журнал, 1962. – 296 с. 12. Бокуть Л.А., Колесников П.С. Базисы Гребнера - Ширшова от зарождения до наших дней. – Сибирь: Изд-во Сиб.мат.журнал, 2000. – 67 с. 13. Адян С.И. Определяющие соотношения и алгоритмические проблемы для групп и полугрупп. – М.: Изд-во Мат. Инст. им. Стеклова, 1966. – 85 с. 14. Ширшов А.И. О свободных кольцах Ли. – М.: Изд-во Мат. сб., 1958. – 184 с. 15. Бокуть Л.А. Вложение алгебр в алгебраически замкнутые алгебры. – М.: Изд-во Докл. Акад. наук СССР, 1962. – 964 с. 16. Бокуть Л.А., Ке B.Ф., Колесников П.С., Фонг Ю. Базисы Гребнера -Ширшова в алгебре и конформных алгебрах, Фундаментальная и прикладная математика. – Сибирь: Изд-во Сиб.мат.журнал, 2000. – 716 с. |