Алгоритм риша - Risch algorithm

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

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

Полное описание алгоритма Риша занимает более 100 страниц.^[1] В Алгоритм Риша – Нормана это более простой, быстрый, но менее мощный вариант, разработанный в 1976 г. Артур Норман.

Описание

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

Liouville сформулировал задачу, которую решает алгоритм Риша. Лиувилль аналитически доказал, что если существует элементарное решение грамм к уравнению грамм′ = ж тогда существуют константы α_я и функции ты_я и v в области, созданной ж такое, что решение имеет вид

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

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

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

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

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

${\displaystyle \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 грамм)^п были в результате интегрирования, то следует ожидать только нескольких степеней логарифма.

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

Поиск элементарного первообразного очень чувствителен к деталям. Например, следующая алгебраическая функция имеет элементарную первообразную:^[2]

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

а именно:

${\displaystyle F(x)=-{\tfrac {1}{8}}\ln \left(\left(x^{6}+15x^{4}-80x^{3}+27x^{2}-528x+781\right){\sqrt {x^{4}+10x^{2}-96x-71}}-\left(x^{8}+20x^{6}-128x^{5}+54x^{4}-1408x^{3}+3124x^{2}+10001\right)\right)+C.}$

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

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

${\displaystyle 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)}}.}$

На самом деле первообразная этой функции имеет довольно краткую форму:

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

Выполнение

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

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

Случай чисто алгебраических функций был решен и реализован в Уменьшать к Джеймс Х. Давенпорт.^[5]

Общий случай был решен и реализован в Scratchpad, предшественнике Аксиома, автор Мануэль Бронштейн.^[6]

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

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

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

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

Смотрите также

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

Примечания

1. Геддес, Чапор и Лабан 1992.
2. Этот пример был отправлен Мануэлем Бронштейном в Usenet Форум comp.soft-sys.math.maple 24 ноября 2000 г.[1]
3. Бронштейн 1998.
4. Моисей 2012.
5. Давенпорт 1981.
6. Бронштейн 1990 г..
7. "Документация по системе Mathematica 7: PolynomialQuotient". Раздел: Возможные проблемы. Получено 17 июля 2010.

Рекомендации

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

• Бронштейн, Мануэль (1998). "Учебное пособие по символической интеграции" (PDF).

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

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

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

• Моисей, Иоиль (2012). «Macsyma: личная история». Журнал символических вычислений. 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.

внешняя ссылка

• Бхатт, Бхуванеш. «Алгоритм Риша». MathWorld.