Интегрирование алгебраических функций- Пер с англ. — М.: Мир, 1985. — 192 с.
„не гитмов -op..B- чПаТностие Гней
представлены известные результаты Риша. Излагаются теоретические основы таких алгоритмов, включающие большой объем сведений из алгебраической геометрии, приведены новые результаты «ииеираическои
мат— • «ля «удеьтов и аспирантов мате-
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Предлагаемая читателю книга является первой в мировой литературе монографией, в которой описаны общие алгоритмы символьного интегрирования или, другими словами, нахождения первообразных в «явном виде». Интерес к вопросам символьного интегрирования или, общее, символьного решения дифференциальных уравнений значительно возрос за последние годы. Это связано прежде всего с тем, что компьютерные системы символьных вычислений оказались мощным средством повышения производительности труда физиков, математиков, инженеров и других специалистов. Сказанное касается как теоретических исследований, так и в особенности прикладных работ, включая промышленные. С помощью таких систем получены как яркие теоретические результаты, так и решение огромного числа прикладных задач, которые вряд ли удалось бы решить достаточно быстро без применения компьютерных систем символьных вычислений.
Компьютерные интеграторы, т. е. комплексы программ для нахождения интегралов в символьном виде, являются, как правило, частью более широких систем символьных вычислений. На Западе из таких систем очень распространены системы MACSYMA и различные версии системы REDUCE. В книге Дэвенпорта описаны эксперименты, выполненные им на базе очень популярной системы REDUCE-2. Она достаточно хорошо известна и в СССР. Однако не нужно думать, что знакомство с системой REDUCE-2 сколько-нибудь существенно для понимания предлагаемой книги или разработки интеграторов. Книга Дэвенпорта посвящена прежде всего алгоритмам — как описанию собственно процедур, так и краткому изложению тех математических знаний, на которых эти алгоритмы основаны.
Как же ставится задача символьного интегрирования? Обычно ее формулируют следующим образом. Пусть задан класс функциональных выражений или, используя термин, принятый в математической логике, термов. Например, задан
иреаисловие реаактора перквииа
класс выражений, которые можно построить с помощью суперпозиции из переменной х, рациональных чисел, числа л, операций сложения, умножения, взятия абсолютной величины, функции sin и какой-нибудь функции, неинтегрируемой в элементарных функциях. Нужно построить алгоритм, который бы по любому терму из рассматриваемого класса давал ответ, имеет ли этот терм первообразную в этом же классе и если да, то находил бы для первообразной соответствующее выражение. Из известной теоремы Д. Ричардсона следует, что для описанного класса термов такой алгоритм невозможен. Таким образом, задача символьного интегрирования в общей постановке неразрешима. Это относится и к задаче нахождения определенных интегралов в «явном виде», и к различным модификациям описанной выше задачи.
Однако наибольший интерес для приложений — а приложениями в данном случае являются компьютерные интеграторы, — представляют частные классы функций. Хорошо из^ вестно, как искать неопределенный интеграл от рациональной функции — его всегда можно построить. Если расширить поле рациональных функций конечным числом алгебраически независимых экспонент, то, хотя мы получим функции, вообще говоря, не интегрируемые в этом классе, задача о существовании первообразной и ее построении, когда она существует, останется алгоритмически разрешимой. Более того, имеется достаточно эффективный алгоритм (алгоритм Ри-ша) для ее решения. Он кратко описан в гл. 4.
Основным результатом Дэвенпорта является разрешающий алгоритм для другого в некотором смысле крайнего случая — случая конечного алгебраического расширения поля рациональных функций. Им же описан ряд полезных соображений о дальнейшем расширении применимости соответствующей методики. Алгоритм Дэвенпорта, конечно, не столь эффективен как алгоритм Риша уже на уровне теоретических оценок вычислительной сложности. Оценки его эффективности упираются в весьма трудные вопросы алгебраической геометрии, которая вообще играет в вопросах символьного интегрирования ключевую роль.
Разумеется, практические интеграторы наряду с общими процедурами типа алгоритмов Риша и Дэвенпорта содержат в том или ином числе различные эвристические приемы интегрирования— например те, которые в изобилии можно найти в учебниках по классическому математическому анализу или соответствующих справочниках. Роль последних может оказаться существенной для ускорения решения простых или очень специальных задач. Однако более принципиальное значение для построения перспективных интегралов играют общие алгоритмы. Имеющаяся в настоящее время алгоритмика
I
позволяет строить довольно хорошие практические интеграторы.
В последние годы весьма интенсивно ведутся исследования в области вычислительных аспектов алгебраической геометрии. Это касается как базисных алгоритмов типа разложения многочленов на неприводимые, так и задач типа вычисления оценки кручения дивизоров на алгебраической кривой. Алгоритмы разложения многочленов на неприводимые являются составной частью всех известных общих алгоритмов интегрирования. Недавно в разработке эффективных алгоритмов для этой задачи был достигнут, по крайней мере в теоретическом плане, существенный прогресс1).
Это полезно иметь в виду, поскольку Дэвенпорт ссылается на более ранние работы, а алгоритмы разложения многочленов на неприводимые во многом определяют эффективность процедур, в которые они входят.
Интересную информацию об алгоритмах символьных вычислений, относящихся к интегрированию, содержит сборник Computer Algebra. Symbolic and Algebraic Computation.— 2nd edition. Eds. B. Buchberger, G. E. Collins, R. Loos, Springer Verlag, 1983.2) Систематическим источником информации об алгоритмах и системах символьных вычислений является ACM SIGSAM Bulletin, а также соответствующие тома серии Lecture Notes in Computer Science, издаваемой издательством Springer. Информация о советских работах в этой области по большей части содержится в трудах конференций по системам символьных вычислений.
При чтении книги Дэвенпорта нужно иметь в виду, что она написана «на скорую руку», по горячим следам разработки и реализации разработанного автором алгоритма интегрирования. Такой стиль изложения имеет свои плюсы и минусы. С одной стороны, можно весьма быстро получить довольно цельное представление об алгоритмах и относящихся к ним вопросах теории. С другой стороны, такое изложение требует значительных усилий при восстановлении деталей, особенно касающихся обоснования правильности алгоритмов. Внимательный читатель найдет широкое поле для работы по усовершенствованию многих из описанных
ОГЛАВЛЕНИЕ
Предисловие редактора перевода.............. 5
От автора....................... 9
Глава 1. Введение..................... 11
Компьютерное интегрирование вообще.......... 11
План книги (1)................... 12
Пример....................... 13
План книги (2) .................... 13
Теоретические ограничения............... 15
Краткий обзор предшествующих работ . . . ;....... 16
Учет машинного времени................ 17
Глава 2. Алгебраические вычисления.............. 19
Алгебраические соотношения............... 19
Единственность алгебраических выражений........ 21
Представление алгебраических выражений......... 23
Соображения, связанные с реализацией......... . 25
Алгебраическая геометрия............' .... 26
Разложения Пюизо.................. 28
Структуры данных для плейсов............. 28
Вычисление разложений Пюизо . . .,.......... 30
Дивизоры...................... 31
Дифференциалы ................... 32
Глава 8. Алгоритм Коутса.................. 34
Введение ...................... 34
Описание алгоритма................. . 35
Доказательство корректности алгоритма. Шаги fll —[3"| . . . 39
Доказательство корректности алгоритма. Шаги [4] — ["51 ... 42
Обобщения ............-........ . 43"
Алгоритм Коутса и дифференциалы............ 4В
Реализация ..................... 49
Выводы....................... 5Э
Глава 4. Теорема Риша . . , ................ 61
Введение...................... 51
Дифференциальная алгебра.............. . 52
Теорема Риша.................... 54
Доказательство теоремы Риша.............. 5^
Алгебраическая часть.......,......... 60
Частичный алгоритм .................. 62
Соображения эффективности...............63
Глава 5. Задача о дивизорах с кручением...........64
Введение.............."........ 64
Эллиптические кривые................. 65
Результат Мазура................... 6*9
Приложение исследований Мазура............ 70
Метод Кэли ...................... 71
Якобиевы многообразия...............• 73
Глава 6. Операторы Гаусса — Манина............75
Введение ...................... 75
Пример....................... 76
Уравнения Пикара — Фукса ............... 78
Операторы Пикара — Фукса как гомоморфизмы....... 80
Дивизоры конечного порядка..............81
Реализация ..................... 84
Специальные значения параметров ............ 86
Глава 7. Эллиптические интегралы. Окончание.........90
Поля алгебраических чисел............... 90
Эллиптические кривые................. 92
Теория Лютца — Нагеля................ 93
Точка зрения Харди.................. 93
Реализация ..................... 98
Глава 8. Кривые над полями алгебраических чисел.......101
Произвольный род.................. 101
Хорошая редукция.................. 102
Кручение над конечными полями............. 104
Пример....................... 106
Вычислительные соображения.............. 108
Пример над алгебраическими полями........... 109
Глава 9. Выводы.....................Ц2
Состояние теории ................... 112
Состояние реализации................. 112
Необходимые дополнительные процедуры.......... 114
Выводы для системы алгебраических вычислений....... 118
Будущие теоретические исследования........... 120
Расширение на трансцендентные функции.......... 121
Виды неинтегрируемости................ 124
Резюме....................... 126
Приложение 1. Изменения, внесенные в систему REDUCE-2 .... 126
1. Распечатка ........,...........126
2. Дифференцирование..........,......127
3. Наибольшие общие делители ..,,,..,.....128
4. Алгебраические выражения . ,............129
[
i
б. Разложение на множители..............130 j
6. Единственность алгебраических выражений ......... 131 ;
I Приложение 2. Примеры..................132
Пример 1. Простое логарифмическое выражение.......132
Пример 2.. 1/SQRT((X**2—.1)*(X**2 — K**2))..........133
Пример 3. Пример с кручением..............137
Пример 4. Модулярная кривая..............139
Пример 5. Интеграл Чебышева............. 142
Пример 6. Вложенные выражения ............153
Пример 7. Логарифмически неинтегрируемая функция.....154
Пример 8. Сумма двух функций .............163
Приложение 3. Алгоритмы работы с алгебраическими выражениями 167
Литература.......................174
Предметный указатель . , , ,......., ,.....185
Цена: 150руб.
