Введение

Настоящая брошюра представляет исправленное и дополненное переиздание учебного пособия авторов [6] . Целью, которую авторы ставили себе при подготовке первого издания, было методическое обеспечение соответствующего раздела в общем курсе высшей алгебры, читаемом на факультете прикладной математики - процессов управления СПбГУ. Однако отзывы коллег убедили авторов в том, что изложенные в пособии результаты могли бы оказаться полезными и для более широкого круга читателей. Объяснение этому обстоятельству авторы видят в том, что в отечественной литературе по алгебре этот раздел традиционно освещается недостаточно полно - в отличие, например, от таких классических курсов, как [21] или [25].

При подготовке нового издания авторы решили сохранить уровень сложности изложения, ориентированный на восприятие студента первого курса классического университета, обучающегося по специальности прикладная математика. Предполагается, что студент владеет аппаратом определителей и его применением к задаче установления совместности системы линейных уравнений, а также базовыми понятиями теории полиномов от одной переменной.

Для более же квалифицированного читателя в настоящем введении приведем описание постановок задач и дадим краткий исторический обзор теории.

Итак, объектом теории исключения является система уравнений

f1(x1,...,xn)=0, ..., fn(x1,...,xn)=0, (1)

где f1,..., fn - полиномы по x1,..., xn. Поиск решения такой системы численными (итерационными) методами сложен и, как правило, эффективен только для случая n=1 переменной. Основной целью теории исключения ставится сведение задачи решения системы (1) к одномерному случаю. Именно, с помощью элементарных преобразований систему (1) как правило удается свести к эквивалентной ей (т.е. имеющей тот же набор решений) системе вида

X(x1)=0, x2-J2 (x1)=0, ..., xn-Jn (x1)=0. (2)

Здесь X(x1) - полином, а J2 (x1),..., Jn (x1)- рациональные функции по x1. Следовательно, в этом случае решение системы (1) сведется к решению уравнения от одной переменной; иными словами, все остальные переменные оказываются исключенными. Каждый корень полинома X(x1) задает первую компоненту (координату) решения системы (1), а соответствующие ему остальные компоненты выражаются через первую с помощью оставшихся уравнений системы (2). Еще раз подчеркнем то обстоятельство, что все компоненты решения системы (1) могут быть рационально выражены через какую-то одну, например - как в системе (2) - первую.

Техника, позволяющая осуществить приведение системы (1) к виду (2), основана на понятии результанта. Формально результант двух полиномов f(x) и g(x) можно определить как полиномиальную функцию коэффициентов f(x) и g(x), обращение которой в нуль является условием необходимым и достаточным для существования общего корня указанных полиномов. Вопрос о существовании такой функции ставился еще Ньютоном; однако первое систематическое исследование этого вопроса было предпринято Безу, изложившим свои результаты в книге [17]. В заслугу Безу может быть поставлено распространение идеи результанта на случай полиномов от нескольких переменных. Последнее позволило ему доказать фундаментальный результат теории: число решений системы (1) как правило равно произведению степеней входящих в нее полиномов:

deg (X(x1)) = deg f1 ×... ×deg fn.

XIX век стал веком расцвета теории в трудах Пуассона, Абеля, Коши, Лиувилля, Эрмита, Кронекера, Кэли, Сильвестра, Шлэфли и ряда других ученых.

В тридцатые годы XX века теория стала жертвой общей тенденции к аксиоматической формализации математики - тенденции, намеченной еще Гильбертом и впоследствии реализованной Ван-дер-Варденом и Бурбаки. Результатом явилось то, что в учебниках по алгебре для изложения была выбрана хотя и универсальная, логически последовательная, но, вместе с тем, абсолютно неконструктивная методология изложения теории [3], [22]; все богатство, накопленное предыдущим веком, полностью игнорировалось. Последствия не заставили себя ждать: интерес к теории потеряли сначала прикладные математики, а потом и ``чистые''; она практически исчезает из университетских учебников или же остается в них незначительными фрагментами1.

Интерес возродился в восьмидесятые годы. Ряд факторов благоприятствовал этому. Одним из таких факторов стала потребность в абсолютной достоверности результатов, получаемых в ходе вычислений. Другим же фактором явилась необходимость в оценке влияния на решения параметров, входящих в систему (1). Даже если численные методы и могли решить систему (1) при некоторой специализации параметров, то они оказывались малопригодными для задачи исследования динамики решений при вариации этих параметров. Именно для подобных исследований возможность аналитического представления решений или, хотя бы, преобразования системы (1) к эквивалентной, но более простого вида, может оказаться решающей. Известная трудоемкость символьных алгоритмов потребовала достаточного развития вычислительной техники, но после того как это произошло, область науки, известная как «компьютерная алгебра», стала бурно развиваться. Эта область располагается на стыке математики и информатики; интерес к ней научного сообщества выражается в быстро растущем числе публикаций, из которых укажем только некоторые обзорные монографии и сборники статей [1], [5], [7], [8]. Компьютерная алгебра имеет дело, в основном, с точными числами и алгебраическими выражениями в их символьном представлении. В таких ее системах общего назначения, как REDUCE, MACSYMA, MATHEMATICA, MAPLE, AXIOM, MuPAD алгоритмический базис составляют операции над полиномами и рациональными функциями, поэтому исследования в этой области включают в себя создание, развитие и анализ эффективности методов факторизации, вычисления наибольших общих делителей, отделения (локализации) вещественных корней полиномов, преобразования систем алгебраических уравнений к наиболее простому виду. Поскольку идеологии решения задач двух алгебр - классической и компьютерной - совпали, интерес современных исследователей к разработке научного наследия XIX века значительно возрос.

Интерес к теории исключения был стимулирован еще и потребностью выявить истоки теории базисов Грёбнера, первое конструктивное продвижение которой обеспечили работы Бухбергера в семидесятых годах XX века. Бухбергером был разработан универсальный алгоритм построения базиса идеала, порожденного полиномами f1,..., fn; при некоторых дополнительных условиях искомый базис удается построить в форме X(x1), x2- J2(x1),..., xn-Jn (x1) при полиномиальных X, J2,..., Jn. Тем самым обеспечивается возможность сведения системы (1) к виду (2). К сожалению, алгоритм Бухбергера (и многочисленные последующие модификации) оказался своего рода ``черным ящиком'' - когда для конкретной системы (1) практически невозможно оценить априори время расчета системы (2). В сравнении с методом базисов Грёбнера теория исключения обладает весьма существенным преимуществом, а именно - наглядностью. Представление результанта в виде подходящего определителя оказалось довольно удобным также и с точки зрения оценки влияния вариаций коэффициентов полиномов на решения системы.

Теперь опишем кратко содержание настоящего пособия. В первой его части вводится основополагающее понятие результанта и устанавливаются свойства последнего. Формальное определение основывается на представлении результанта в виде определителя (детерминанта) Сильвестра. Не являясь самым вычислительно оптимальным способом вычисления, этот способ, тем не менее, является наиболее наглядным. Выводятся основные свойства результанта, устанавливается его связь с алгоритмом Евклида вычисления наибольшего общего делителя полиномов, указываются альтернативные детерминантные представления результанта (в форме Кронекера и в форме Безу), обсуждаются его применения для вычисления дискриминанта и преобразования Чирнгауза, для нахождения экстремальных значений полинома и др. Среди этого многообразия выделим два ключевых результата:

  1. результант позволяет по коэффициентам полиномов однозначно установить, имеют ли они общий корень;
  2. если упомянутый корень единственен, то его можно найти как рациональную функцию коэффициентов полиномов - с помощью миноров результанта.

Именно эти результаты используются во второй части для построения алгоритма исключения переменной в системе двух уравнений. Для такой системы мы приводим также доказательство теоремы Безу о ``наиболее вероятном'' числе ее решений, а также обсуждаем такие исключительные случаи как, например, неприводимость системы (1) к виду (2). Рассматриваются также приложения теории исключения к различным задачам алгебры, геометрии и теории дифференциальных уравнений.


1По меткому выражению одного из авторов, теория исключения была фактически исключена из алгебры.