Чуркин В.А. - СИСТЕМЫ ПОЛИНОМИАЛЬНЫХ УРАВНЕНИЙ, ИДЕАЛЫ И ИХ БАЗИСЫ-ДЕЛИТЕЛИ
Методическая разработка для 1 курса ММФ
Russian | / | 36 pages | PDF | 514 KB
Алгебру обычно понимают как искусство символьных вычислений. Такие вычисления
часто возникают при моделировании практических задач, а искусство заключается не
только в решении одной конкретной задачи, но и в умении разделить класс данных сим-
вольных задач на разрешимые и неразрешимые, оценить трудоемкость решения, найти
наиболее экономное решение и т.п.
Одна из старейших символьных систем - алгебра многочленов от одной или несколь-
ких переменных - казалось бы хорошо известна. Более двух тысяч лет алгоритму Евклида
для вычисления наибольшего общего делителя, позволяющего, в частности, определить
совместность конечной системы полиномиальных уравнений от одной переменной. Раз-
ложение на множители, отыскание точной формулы для корней многочлена от одной
переменной или приближенный поиск корней - классические задачи алгебры. Успех в
частных случаях и понимание причин сложности решения задач в общем случае были до-
стигнуты трудом многих математиков. Здесь можно вспомнить славные имена Ньютона,
Гаусса, Галуа, Лобачевского ....
Для многочленов от нескольких переменных метод их исключения в системах линей-
ных уравнений, часто называемый методом Гаусса, на самом деле был известен в Китае
по крайней мере за два тысячелетия до нашего времени. Решение нелинейных систем
полиномиальных уравнений от нескольких переменных - гораздо более трудная зада-
ча. Только в прошлом веке появились методы исследования некоторых таких систем с
помощью результантов Сильвестра (аналогов детерминантов) в предположении, что уда-
ется решить полиномиальные уравнения от одной переменной. Чуть позднее появились
результаты общего характера - знаменитые теоремы Гильберта о базисе и о корнях для
полиномиальных идеалов. Стало ясно, что, во-первых, всякая бесконечная система поли-
номиальных уравнений от конечного числа переменных равносильна некоторой конечной
подсистеме и, во-вторых, имеется взаимно однозначное соответствие между алгебраиче-
скими многообразиями (множествами решений систем полиномиальных уравнений) над
алгебраически замкнутым полем и радикальными идеалами в алгебре многочленов. Оба
факта лежат в основе алгебраической геометрии, недавно увенчавшей свой путь решени-
ем великой проблемы Ферма. Тем не менее и после Гильберта на вопрос: "Как решить
данную систему полиномиальных уравнений?" - ответа не было. Многие другие задачи
конструктивного характера о многочленах оставались нерешенными. Отметим, что здесь
нас интересуют, в основном, точные решения систем, а не их аппроксимация.
Удивительный сдвиг произошел в этой области на наших глазах в последние тридцать
лет. В 1965 г. молодой австрийский математик Бруно Бухбергер защитил докторскую дис-
сертацию под руководством алгебро-геометра Вольфганга Грёбнера. В диссертации был
представлен метод вычисления базиса (как векторного пространства) для фактор-алгебры
K[X]/I алгебры многочленов от нескольких переменных над полем K, если идеал I задан
конечным порождающим множеством. Заключается он в переработке данного порождаю-
щего множества идеала в такой конечный "базис", что старший член любого многочлена
идеала делится на старший член подходящего многочлена этого базиса. Через 10-15 лет
этот, на первый взгляд, рядовой результат привел к серьезным успехам в символьном
решении широкого класса математических задач - от решения систем полиномиальных
и дифференциальных уравнений к конструктивизации части алгебраической геометрии,
теории инвариантов, теории Галуа вплоть до проблемы автоматического доказательства
геометрических теорем и построения криптографических систем.
Сама идея вычисления "базиса-делителя" идеала по старшим членам настолько проста,
что могла бы с успехом излагаться в средней школе, и настолько естественна, что алго-
ритм Евклида и метод Гаусса - частные случаи метода вычислений. И ранее, и позднее
подобные идеи возникала и развивалась независимо другими математиками для решения
аналогичных задач. Так А.И. Ширшов еще в 1962 г. реализовал ее для некоторых иде-
алов свободных алгебр Ли, используя представимость элементов свободной алгебры Ли
в виде многочленов от нескольких переменных с некоммутативным, но ассоциативным
умножением. Кнут и Бендикс в 1970 г. предложили аналогичный "метод переписывающих
систем", годный для очень широкого класса символьных языков. Поэтому мы будем ис-
пользовать для такого базиса идеала нейтральное и напоминающее его основное свойство
название "базис-делитель", хотя более распространены названия "базис Грёбнера", "базис Грёбнера-Ширшова", "стандартный базис" и др.
Вместе с серьезными достижениями прежних лет в области кодирования информации
и ввиду успешной реализации символьных вычислений на компьютерах эти результаты
позволили в итоге заявить о новой области математики - компьютерной алгебре. В ко-
роткое время по этой теме было опубликовано не менее пятисот статей. Параллельно были
созданы мощные пакеты прикладных программ, основанные на символьных вычислениях.
Появилась явная необходимость познакомить с новыми идеями и студентов-математиков.
Наша цель - изложить достаточно подробно, с полными доказательствами, метод по-
строения базисов-делителей идеалов и показать на примерах, как они используются для
решения конкретных задач.
Отметим, что вплоть до недавнего времени на русском языке не было учебной литера-
туры по данной теме, доступной для студентов. Недавно появился перевод [3] замечатель-
ной книги Кокса, Литтла и О'Ши, которую мы рекомендуем для всех желающих глубже
познакомиться с теорией базисов-делителей. Изложенный там материал конечно шире и
богаче примерами, чем это краткое пособие для студентов 1 курса.
Download from RapidGator
Download from NitroFlare
