Алгоритм Риша

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

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

Полное описание алгоритма Риша занимает более 100 страниц. Алгоритм Риша-Нормана — более простой, быстрый, но менее мощный вариант, разработанный в 1976 году Артуром Норманом .

Некоторый значительный прогресс был достигнут в вычислении логарифмической части смешанного трансцендентно-алгебраического интеграла Брайаном Л. Миллером.

Описание

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

Лиувилль сформулировал задачу, которая решается алгоритмом Риша. что если существует элементарное решение g уравнения g ′ = f , то существуют константы α _i и функции ui _v и Лиувилль аналитическим путем доказал , в поле, порожденном f, такие, что решение имеет вид

$g=v+\sum _{i<n}\alpha _{i}\ln(u_{i})$

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

Интуиция алгоритма Риша исходит из поведения экспоненциальной и логарифмической функций при дифференцировании. Для функции f e ^г , где f и g — дифференцируемые функции , имеем

$\left(f\cdot e^{g}\right)^{\prime }=\left(f^{\prime }+f\cdot g^{\prime }\right)\cdot e^{g},\,$

так что если е ^г были результатом неопределенного интегрирования, то следует ожидать, что оно окажется внутри интеграла. Также, как

$\left(f\cdot (\ln g)^{n}\right)^{\prime }=f^{\prime }\left(\ln g\right)^{n}+nf{\frac {g^{\prime }}{g}}\left(\ln g\right)^{n-1}$

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

Примеры проблем

Поиск элементарной первообразной очень чувствителен к деталям. Например, следующая алгебраическая функция (опубликованная в sci.math.symbolic Анри Коэном в 1993 году) ) имеет элементарную первообразную, как показывает Wolfram Mathematica начиная с версии 13 (однако Mathematica не использует алгоритм Риша для вычисления этого интеграла):

$f(x)={\frac {x}{\sqrt {x^{4}+10x^{2}-96x-71}}},$

а именно:

${\begin{aligned}F(x)=-{\frac {1}{8}}\ln &\,{\Big (}(x^{6}+15x^{4}-80x^{3}+27x^{2}-528x+781){\sqrt {x^{4}+10x^{2}-96x-71}}{\Big .}\\&{}-{\Big .}(x^{8}+20x^{6}-128x^{5}+54x^{4}-1408x^{3}+3124x^{2}+10001){\Big )}+C.\end{aligned}}$

Но если постоянный член 71 заменить на 72, первообразную невозможно представить в терминах элементарных функций: как показывает и FriCAS . Некоторые системы компьютерной алгебры могут здесь возвращать первообразную в терминах неэлементарных функций (т.е. эллиптических интегралов ), которые выходят за рамки алгоритма Риша. Например, Mathematica возвращает результат с помощью функций EllipticPi и EllipticF. Этот интеграл решил Чебышев (и в каких случаях он элементарен), но строгое доказательство этого было в конечном итоге сделано Золотаревым .

Ниже приведен более сложный пример, включающий как алгебраические, так и трансцендентные функции :

$f(x)={\frac {x^{2}+2x+1+(3x+1){\sqrt {x+\ln x}}}{x\,{\sqrt {x+\ln x}}\left(x+{\sqrt {x+\ln x}}\right)}}.$

На самом деле первообразная этой функции имеет достаточно короткую форму, которую можно найти с помощью подстановки $u=x+{\sqrt {x+\ln x}}$ ( SymPy может решить эту проблему, в то время как FriCAS терпит неудачу с ошибкой «реализация неполная (постоянные остатки)» в алгоритме Риша):

$F(x)=2\left({\sqrt {x+\ln x}}+\ln \left(x+{\sqrt {x+\ln x}}\right)\right)+C.$

Некоторые «теоремы» Давенпорта еще уточняются. Например, в 2020 году был найден контрпример такой «теореме», где оказывается, что элементарная первообразная все-таки существует.

Реализация

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

Случай чисто трансцендентных функций (которые не содержат корней многочленов) относительно прост и был реализован рано в большинстве систем компьютерной алгебры . Первая реализация была осуществлена ​​Джоэлом Мозесом в Macsyma вскоре после публикации статьи Риша.

Случай чисто алгебраических функций был решен и реализован в книге «Reduce» Джеймса Х. Давенпорта , хотя для простоты он мог иметь дело только с квадратными корнями и повторяющимися квадратными корнями, а не с общими радикалами или другими неквадратичными алгебраическими отношениями между переменными.

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

Разрешимость

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

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

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

См. также

• Аксиома (система компьютерной алгебры)
• Выражение в закрытой форме
• Неполная гамма-функция
• Списки интегралов
• Теорема Лиувилля (дифференциальная алгебра)
• Неэлементарный интеграл
• Символическая интеграция

Ссылки

• Бронштейн, Мануэль (1990). «Интегрирование элементарных функций». Журнал символических вычислений . 9 (2): 117–173. дои : 10.1016/s0747-7171(08)80027-2 .

• Бронштейн, Мануэль (1998). «Учебное пособие по символьной интеграции» (PDF) . ISSAC'98, Росток (август 1998 г.) и Семинар по дифференциальной алгебре, Рутгерс .

• Бронштейн, Мануэль (2005). Символическая интеграция I. Спрингер. ISBN  3-540-21493-3 .

• Давенпорт, Джеймс Х. (1981). Об интегрировании алгебраических функций . Конспекты лекций по информатике . Том. 102. Спрингер. ISBN  978-3-540-10290-8 .

• Геддес, Кейт О .; Чапор, Стивен Р.; Лабан, Джордж (1992). Алгоритмы компьютерной алгебры . Бостон, Массачусетс: Издательство Kluwer Academic Publishers. стр. XXII+585. Бибкод : 1992afca.book.....G . дои : 10.1007/b102438 . ISBN  0-7923-9259-0 .

• Моисей, Джоэл (2012). «Масима: личная история». Журнал символических вычислений . 47 (2): 123–130. дои : 10.1016/j.jsc.2010.08.018 .

• Риш, Р.Х. (1969). «Проблема интегрирования в конечных терминах» . Труды Американского математического общества . 139 . Американское математическое общество: 167–189. дои : 10.2307/1995313 . JSTOR   1995313 .

• Риш, Р.Х. (1970). «Решение задачи интегрирования в конечных терминах» . Бюллетень Американского математического общества . 76 (3): 605–608. дои : 10.1090/S0002-9904-1970-12454-5 .

• Розенлихт, Максвелл (1972). «Интеграция в конечных терминах». Американский математический ежемесячник . 79 (9). Математическая ассоциация Америки: 963–972. дои : 10.2307/2318066 . JSTOR   2318066 .

Внешние ссылки

• Бхатт, Бхуванеш. «Алгоритм Риша» . Математический мир .