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

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

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

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

Описание

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

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

{ Displaystyle г = v + сумма _ {я <п} альфа _ {я} ln (и_ {я})}

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

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

{ Displaystyle влево (е cdot e ^ {g} right) ^ { prime} = left (f ^ { prime} + f cdot g ^ { prime} right) cdot e ^ { грамм},,}

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

{ Displaystyle влево (е CDOT ( пер г) ^ {п} вправо) ^ { прайм} = е ^ { прайм} влево ( пер г вправо) ^ {п} + пф { гидроразрыв {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 е (х) = { гидроразрыва {х ^ {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 (у)$ , т.е. рациональные числа и рациональные функции в $у$ с рациональными числовыми коэффициентами соответственно, где $у$ неопределенное, не зависящее от $Икс$ .

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

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

Примечания

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

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

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

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]