Элементы компьютерной алгебры

Введение в компьютерную алгебру

2-е издание, исправленное

Панкратьев Е.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК [004:512](07)
ББК 19
П16
Элементы компьютерной алгебры / Панкратьев Е.В. - M.: Национальный Открытый Университет
“ИНТУИТ”, 2016 (Основы информатики и математики)
ISBN 978-5-94774-655-6

Курс посвящён описанию основных структур данных и алгоритмов, применяемых в символьных
вычислениях на ЭВМ.
В курсе затрагивается широкий круг вопросов, связанных с вычислениями в кольцах целых чисел,
многочленов и дифференциальных многочленов.

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Панкратьев Е.В., 2007-2016

3

Введение

В данной лекции рассматриваются основные понятия компьютерной алгебры.
Приведен краткий обзор систем и алгоритмов компьютерной алгебры

Предисловие

Настоящее пособие составлено на основе спецкурсов, читавшихся автором на
механико-математическом факультете в течение более 10 лет. Выбор материала в
значительной мере определялся пристрастиями автора. Наряду с классическими
результатами компьютерной алгебры в этих спецкурсах (и в настоящем пособии)
нашли отражение исследования нашего коллектива. Прежде всего, это относится к
теории дифференциальной размерности. Теорией дифференциальной размерности мы
начали заниматься по инициативе, под руководством и при активном участии А.В.
Михалева в конце 70-х—начале 80-х годов прошлого века [13]. Наряду с
теоретическими исследованиями, нами был разработан комплекс программ на
алгоритмическом языке REFAL для вычислений в дифференциальных и разностных
модулях [11]. Результаты многолетних исследований, связанных с конструктивными
методами в кольцах дифференциальных и разностных многочленов и теорией
дифференциально-разностной размерности, опубликованы в монографии [20].
Частично эти результаты отражены в настоящем курсе. Пользуюсь случаем выразить
глубокую признательность Алексадру Васильевичу Михалеву, в значительной мере
благодаря которому появился этот курс. Я также очень благодарен Марине
Владимировне Кондратьевой, Александру Борисовичу Левину, Андрею Витальевичу
Астрелину, Олегу Дмитриевичу Голубицкому, Алексею Игоревичу Зобнину и другим
коллегам, работавшим вместе с нами в области компьютерной алгебры. Исследования
выполнялись в лаборатории вычислительных методов и на кафедре высшей алгебры
механико-математического факультета МГУ, и я признателен коллективу лаборатории
и кафедры за очень доброжелательное отношение к нашей группе.

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

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

Введение

4

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

Термин “компьютерная алгебра” возник как синоним терминов “символьные
вычисления” , “аналитические вычисления”, “аналитические преобразования” и т. д.
Даже в настоящее время этот термин на французском языке дословно означает
“формальные вычисления “.

В чем основные отличия символьных вычислений от численных и почему возник
термин “компьютерная алгебра” ?

Когда мы говорим о вычислительных методах, то считаем, что все вычисления
выполняются в поле вещественных или комплексных чисел. В действительности же
всякая программа для ЭВМ имеет дело только с конечным набором рациональных
чисел, поскольку только такие числа представляются в компьютере. Для записи целого
числа отводится обычно 16 или 32 двоичных символа (бита), для вещественного—32
или 64 бита. Это множество не замкнуто относительно арифметических операций, что
может выражаться в различных переполнениях, например, при умножении достаточно
больших чисел или при делении на маленькое число. Еще более существенной
особенностью вычислительной математики является то, что арифметические операции
над этими числами, выполняемые компьютером, отличаются от арифметических
операций в поле рациональных чисел,—более того, для компьютерных операций не
выполняются основные аксиомы поля (ассоциативности, дистрибутивности). Эти
особенности компьютерных вычислений оцениваются в терминах погрешности или
точности вычислений. Оценка погрешности представляет одну из основных проблем
вычислительной математики. Каждую задачу требуется решить с использованием
имеющихся ресурсов ЭВМ, за обозримое время, с заданной точностью.

Набор объектов, применяемых в символьных вычислениях, весьма разнообразен, в
частности, в них используется значительно большее множество рациональных чисел.
Это множество все равно остается конечным, но ограничения на допустимые размеры
числа (количество знаков в его записи) связаны обычно с размерами оперативной
памяти ЭВМ, что позволяет пользоваться практически любыми рациональными
числами, операции над которыми выполняются за приемлемое время. При этом
компьютерные операции над рациональными числами совпадают с соответствующими
операциями в поле рациональных чисел. Таким образом, снимается одна из основных
проблем вычислительных методов — оценка погрешности вычислений.

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

5

единственный корень данного многочлена. Многочлены играют в символьных
вычислениях исключительно важную роль. На использовании полиномиальной
арифметики основаны теоретические методы аналитической механики, они
применяются во многих областях математики, физики и других наук. Кроме того, в
компьютерной алгебре рассматриваются такие объекты, как дифференциальные поля
(функциональные поля), допускающие показательные, логарифмические,
тригонометрические функции, матричные кольца (элементы матрицы принадлежат
кольцам достаточно общего вида) и другие. Даже при арифметических операциях над
такими объектами происходит разбухание информации, и для записи промежуточных
результатов вычислений требуется значительный объем памяти ЭВМ.

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

В научных исследованиях и технических расчетах специалистам приходится гораздо
больше заниматься преобразованиями формул, чем собственно численным счетом. Тем
не менее, с появлением ЭВМ основное внимание уделялось автоматизации численных
вычислений, хотя ЭВМ начали применяться для решения таких задач символьных
преобразований, как, например, символьное дифференцирование, еще в 50-х годах
прошлого века. Активная разработка систем компьютерной алгебры началась в конце
60-х годов. С тех пор создано значительное количество различных систем, получивших
различную степень распространения; некоторые системы продолжают развиваться,
другие отмирают, и постоянно появляются новые.

Системы компьютерной алгебры. Системы компьютерной алгебры можно условно
разделить на системы общего назначения и специализированные. К системам общего
назначения относятся MACSYMA, REDUCE, MATEMATICA, MAPLE, AXIOM и
другие системы. В 80-е годы прошлого века широкое распространение в СССР
получила система REDUCE. Она первоначально предназначалась для решения
физических задач, разрабатывалась на наиболее широко распространенных
компьютерах, разработка до определенного времени не носила коммерческого
характера (система до конца 80-х годов распространялась бесплатно), открытый
характер системы позволил привлечь к ее разработке огромную армию пользователей,
обогативших систему многочисленными пакетами для решения отдельных задач.
MACSYMA, так же, как и REDUCE, является “старой” системой. В отличие от
системы REDUCE, MACSYMA разрабатывалась с самого начала как коммерческий
продукт. В ней более тщательно проработаны алгоритмические вопросы, ее
эффективность существенно выше, но меньшее ее распространение можно объяснить
двумя обстоятельствами: длительное время она была реализована только на малом
числе “экзотических” компьютеров и распространялась только на коммерческой
основе. Система MAPLE, созданная в 80-х годах прошлого века в Канаде, с самого
начала была задумана как система для персональных компьютеров, учитывающая их
особенности. Она развивается “вширь и вглубь” , даже ее ядро переписывалось с
одного алгоритмического языка на другой. В настоящее время MAPLE широко
применяется во многих странах (в частности, в США и Канаде) в учебном процессе, а
также в различных областях научных и технических исследований. В конце прошлого

6

века получила широкое распространение и сейчас быстро развивается система
MATEMATICA. Ее успех в значительной степени объясняется ее широкими
графическими возможностями, а также электронной документацией, которую можно
рассматривать как электронную библиотеку, посвященную различным разделам
математики и информатики. Особое место среди систем компьютерной алгебры
занимает система AXIOM. В отличие от остальных систем, представляющих собой
пакеты программ, общение с которыми осуществляется на некотором алголоподобном
языке, система AXIOM, развившаяся из системы SCRATCHPAD-II, имеет дело с более
привычными для математиков объектами. В частности, в ней ключевым понятием
является понятие категории: здесь можно рассматривать, например, категории
множеств, полугрупп, дифференциальных колец, левых модулей и т. д. Система имеет
высокую степень универсальности, требует для своей реализации мощных
компьютеров, распространяется за достаточно высокую плату, поэтому используется
только в ограниченном числе мощных университетских и научных центров.

Специализированные системы отличаются более высокой эффективностью, но область
их применения ограничена. К специализированным системам относятся такие системы,
как CALEY и GAP — специализированные системы для вычислений в теории групп,
MACAULEY, CoCoA, Singular — системы разной степени универсальности для
вычислений в кольце многочленов, SCHOONSHIP — специализированная система для
вычислений в физике высоких энергий, muMATH и ее правонаследница DERIVE —
системы, широко используемые в учебном процессе (в частности, в Австрии лицензия
на установку системы DERIVE приобретена для всех средних школ), и многие другие.

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

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

7

В конце прошлого века бурно развивались исследования в трех областях
компьютерной алгебры — теории базисов Гребнера, факторизации многочленов и
интегрирования в конечном виде. Именно этим вопросам, в первую очередь,
посвящено настоящее пособие.

Оно начинается с рассмотрения проблемы представления данных, которую можно
сформулировать в следующем виде. Имеется множество объектов T и на нем отношение
эквивалентности  Требуется в каждом классе эквивалентных объектов выбрать
единственного представителя этого класса, для основных алгебраических областей:
кольца целых чисел, поля рациональных чисел, конечных полей, кольца многочленов и
поля рациональных функций, алгебраических и трансцендентных расширений полей.
Кроме того, в лекции 1 рассматриваются арифметические операции в этих областях.

Отдельная лекция (лекция 2) посвящена алгоритмам вычисления наибольших общих
делителей целых чисел и многочленов. Здесь же приводятся некоторые оценки для
коэффициентов делителя многочлена от одной переменной.

Задача представления данных для факторколец кольца многочленов приводит к
введению понятия базисов Гребнера полиномиальных идеалов. Рассматривая
образующие полиномиального идеала как систему нелинейных алгебраических
уравнений, базис Гребнера можно трактовать как некоторую каноническую форму этой
системы. Для случая многочленов от одной переменной над некоторым полем в
качестве такой “канонической формы” можно рассматривать наибольший общий
делитель этих многочленов, который может быть получен, например, с помощью
алгоритма Евклида. Для системы линейных уравнений от многих переменных в
качестве “канонической формы” можно взять диагональную форму системы (т. е.
систему вида 
 ), которая может быть получена с помощью метода

Гаусса. В общем случае алгоритмы построения базиса Гребнера можно считать
обобщением алгоритма Евклида и метода Гаусса.

Теория базисов Гребнера рассматривается в лекции 3 . Изложение не ограничивается
случаем полиномиальных идеалов: строится более общая теория, применимая также к
подмодулям свободных полиномиальных, дифференциальных и разностных модулей.
Наряду с классическими базисами Гребнера рассматривается их специальный случай,
называемый инволютивными базисами.

Базисы Гребнера имеют многочисленные приложения. В частности, они позволяют
определить, совместна ли система нелинейных алгебраических уравнений, и, если
система совместна, то определить, сколько эта система имеет решений над
алгебраически замкнутым полем (если множество решений бесконечно, то определить
размерность многообразия решений). Эти вопросы изучаются в рамках теории
размерностных многочленов (многочленов Гильберта). Свойства таких многочленов и
алгоритмы их вычисления приведены в лекции 4.

Лекция 5 посвящена задаче разложения многочленов на неприводимые множители.
Мы рассматриваем эту задачу в следующей постановке: дан многочлен 
 с

целыми коэффициентами от одной переменной, требуется разложить его на
неприводимые множители. С точки зрения “чистого” математика эта задача давно

8

решена полностью и окончательно: получен алгоритм, позволяющий находить
требуемое разложение “за конечное число шагов”. Один из таких алгоритмов получен
в 1882 году Кронекером, чьим именем он и называется в настоящее время, хотя за 100
лет до Кронекера этот алгоритм был известен австрийскому астроному Шуберту.
Следующий шаг в исследовании алгоритмов факторизации был сделан только в 60-х
годах прошлого столетия, когда был найден достаточно эффективный алгоритм для
разложения на множители многочленов с коэффициентами из конечного поля.
Использование этого алгоритма в сочетании с леммой Гензеля позволило получить
алгоритмы факторизации многочленов с целыми коэффициентами, пригодные для
практической реализации. С конца 60-х годов прошлого века появляется большое
количество работ по факторизации. Предлагаются усовершенствования алгоритмов,
направленные на увеличение их быстродействия, на расширение области их
применения, в частности, рассматривается задача факторизации многочленов от одной
и многих переменных с коэффициентами из конечных полей, из полей алгебраических
чисел и т.д. Крупным вкладом в теорию факторизации многочленов явилась работа
[24], позволившая получить алгоритм факторизации, сложность которого оценивается
полиномом от степени исходного многочлена.

Наконец, лекция 6 посвящена одной из проблем дифференциальной компьютерной
алгебры.

Дифференциальные кольца и поля, в которых наряду с арифметическими операциями
имеется одна или несколько операций дифференцирования, - это активно исследуемые
объекты компьютерной алгебры. Важным частным случаем дифференциальных полей
являются поля элементарных функций, получающиеся из поля рациональных функций
от одной переменной последовательным присоединением алгебраических элементов,
экспонент и логарифмов (таким образом формализуется основная масса формул, с
которыми мы привыкли иметь дело в курсе анализа). Алгебраические зависимости,
которые могут существовать между образующими таких расширений, описывает так
называемая структурная теорема. (В общем случае дифференциальные поля имеют
очень сложную структуру и проблема представления данных для них алгоритмически
неразрешима.)

Операция дифференцирования легко описывается алгебраически, и ее реализация не
представляет трудностей. Гораздо сложнее обстоит дело с обратной операцией интегрированием. Если F - дифференциальное поле и 
 то не обязательно

существует 
 такой, что g’=f. Задача интегрирования в конечном виде в общем

случае формулируется следующим образом. Пусть  и 
 - два класса

дифференциальных полей. Требуется построить алгоритм, который для любого
элемента f любого дифференциального поля F из класса  либо находит
дифференциальное поле G в классе 
 и элемент 
 такой, что g’=f, либо

доказывает, что такого элемента не существует ни в каком поле класса 
 В

классической постановке задачи 
 - класс полей элементарных функций.

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

9

позволяли доказать отсутствие элементарного интеграла.

Алгоритм интегрирования в конечном виде функций из чисто трансцендентного
расширения поля рациональных функций, порожденного экспонентами и
логарифмами, был сформулирован в 1969 году Ришем [29]. Проверка, принадлежит ли
подынтегральная функция данному классу, осуществляется с помощью структурной
теоремы. Далее теорема Лиувилля позволяет определить вид элементарного интеграла,
если такой существует. Вычисление интеграла или доказательство его отсутствия
производится методом неопределенных коэффициентов с использованием рекурсии.
Алгоритм интегрирования алгебраических функций (элементов алгебраического
расширения поля рациональных функций от одной переменной) был сформулирован
Дж. Дэвенпортом [6] в 1982 г. Этот алгоритм использует глубокие результаты
алгебраической геометрии и весьма сложен для реализации. Дальнейшее развитие
алгоритмы интегрирования в конечном виде получили в работах различных
математиков, из которых следует отметить Б. Трейгера и М. Бронштейна. Основные
направления исследований — повышение эффективности алгоритмов, расширение
области их применения и исследование более широкого класса дифференциальных
полей, чем поля элементарных функций.

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

случай этой задачи для уравнения первого порядка приходится решать при
интегрировании элементарных функций (в этом случае мы ищем решения в том же
поле, в котором лежат коэффициенты исходного уравнения). Алгоритм нахождения
решения в классе полей элементарных функций для уравнений второго порядка с
коэффициентами из поля рациональных функций был предложен Ковасиком в 1978
году и вскоре был реализован в различных системах компьютерной алгебры.
Обобщение алгоритма на уравнения произвольного порядка было получено М.
Сингером. Сложность алгоритма Сингера очень высока, и трудно рассчитывать на его
реализацию в обозримом будущем (есть реализация для дифференциальных уравнений
3-го порядка). Задачу о разрешимости линейного дифференциального уравнения в
элементарных функциях можно разделить на два этапа. Вначале исследуется
разрешимость уравнения в классе лиувиллевых функций (лиувиллевы функции
получаются путем расширения исходного дифференциального поля последовательным
присоединением элементов, являющихся либо алгебраическими, либо интегралами,
либо экспонентами интегралов). Вопрос о разрешимости уравнения в лиувиллевых
функциях решается дифференциальной теорией Галуа: линейное однородное
дифференциальное уравнение разрешимо в лиувиллевых функциях тогда и только
тогда, когда разрешима связная компонента его группы Галуа, являющейся линейной
алгебраической группой. Далее задача сводится к уже рассмотренной задаче
интегрирования. Рассмотрение задач, сформулированных в этом абзаце, выходит за
рамки настоящего курса.

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

10