Введение

Метод вычисления неопределённых интегралов

В символьных вычислениях алгоритм Риша — это метод неопределённого интегрирования, используемый в некоторых системах компьютерной алгебры для нахождения первообразных. Он назван в честь американского математика Роберта Генри Риша, специалиста в области компьютерной алгебры, который разработал его в 1968 году. Алгоритм преобразует задачу интегрирования в алгебраическую задачу. Он основан на виде интегрируемой функции и на методах интегрирования рациональных функций, радикалов, логарифмов и экспоненциальных функций. Риш назвал его процедурой разрешения, поскольку это метод определения того, имеет ли функция элементарную функцию в качестве неопределённого интеграла, и, если да, то для определения этого неопределённого интеграла. Однако алгоритм не всегда успешно определяет, может ли первообразная данной функции быть выражена через элементарные функции. Полное описание алгоритма Риша занимает более 100 страниц. Алгоритм Риша — Нормана является более простым, быстрым, но менее мощным вариантом, разработанным в 1976 году Артуром Норманом. Значительный прогресс в вычислении логарифмической части смешанного трансцендентно-алгебраического интеграла был достигнут Брайаном Л. Миллером.

Описание

Алгоритм Риша используется для интегрирования элементарных функций. Это функции, полученные композицией экспонент, логарифмов, радикалов, тригонометрических функций и четырех арифметических операций (+ − × ÷). Лаплас решил эту проблему для случая рациональных функций, показав, что неопределенный интеграл рациональной функции является рациональной функцией и конечным числом констант, умноженных на логарифмы рациональных функций. Алгоритм, предложенный Лапласом, обычно описывается в учебниках по математическому анализу; как компьютерная программа, он был окончательно реализован в 1960-х годах. Лиувилль сформулировал проблему, решаемую алгоритмом Риша. Лиувилль аналитически доказал, что если существует элементарное решение g уравнения 1 = g′ = f, то в поле, порожденном f, существуют константы αi и функции ui и v, такие что решение имеет вид

Риш разработал метод, позволяющий рассматривать лишь конечное множество функций вида Лиувиля. Интуиция алгоритма Риша основана на поведении экспоненциальной и логарифмической функций при дифференцировании. Для функции f e^(g), где f и g – дифференцируемые функции, имеем

, поэтому, если e^(g) входит в результат неопределенного интегрирования, следует ожидать, что она будет находиться внутри интеграла. Также, поскольку

, то, если (ln g)^(n) входит в результат интегрирования, следует ожидать лишь несколько степеней логарифма.

Реализация

Преобразование теоретического алгоритма Риша в алгоритм, который может быть эффективно выполнен на компьютере, оказалось сложной задачей, потребовавшей значительного времени. Случай чисто трансцендентных функций (не содержащих корни многочленов) относительно прост и был реализован на ранних этапах развития большинства систем компьютерной алгебры. Первую реализацию выполнил Джоэль Мозес в системе Macsyma вскоре после публикации работы Риша. Задача чисто алгебраических функций была решена и реализована Джеймсом Х. Давенпортом в системе Reduce, однако для упрощения она поддерживала только квадратные корни и повторные квадратные корни, но не общие радикалы или другие неквадратичные алгебраические соотношения между переменными. Общий случай был решен и почти полностью реализован Мануэлем Бронштейном в Scratchpad, предшественнике системы Axiom, и в настоящее время разрабатывается в ответвлении Axiom, FriCAS. Тем не менее, реализация не включала в себя полное покрытие некоторых ветвей для частных случаев. На данный момент не существует известной полной реализации алгоритма Риша.

Решаемость

Алгоритм Риша, применяемый к общим элементарным функциям, не является алгоритмом, а полуалгоритмом, поскольку в процессе своей работы он должен проверять, эквивалентны ли определенные выражения нулю (проблема с константами), в частности, в константном поле. Для выражений, содержащих только функции, обычно считающиеся элементарными, неизвестно, существует ли алгоритм, выполняющий такую проверку (современные системы компьютерной алгебры используют эвристические методы); более того, если добавить функцию абсолютной величины в список элементарных функций, то известно, что такого алгоритма не существует; см. теорему Ричардсона. Следует отметить, что эта проблема также возникает в алгоритме деления полиномов; этот алгоритм не сможет завершиться успешно, если он не сможет правильно определить, обращаются ли коэффициенты в ноль. Практически любой нетривиальный алгоритм, связанный с полиномами, использует алгоритм деления полиномов, включая алгоритм Риша. Если константное поле вычислимо, то есть для элементов, не зависящих от x, задача об эквивалентности нулю разрешима, то алгоритм Риша является полным алгоритмом. Примерами вычислимых константных полей являются Q и Q(y), то есть рациональные числа и рациональные функции от y с рациональными коэффициентами соответственно, где y — неопределённая переменная, не зависящая от x. Эта проблема также возникает в алгоритме исключения Гаусса (или любом алгоритме, способном вычислить ядро матрицы), который также необходим для многих частей алгоритма Риша. Исключение Гаусса выдаст неверные результаты, если оно не сможет правильно определить, является ли ведущий элемент тождественно равным нулю.