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

Назван в честь . Сам Риш, который разработал алгоритм в 1968 году, называл его «разрешающей процедурой», поскольку метод решает, является ли первообразная от функции элементарной функцией. Наиболее подробное исследование алгоритма представлено на 100 страницах книги « Алгоритмы компьютерной алгебры » Кейта Геддеса, Стефана Цапора и Джорджа Лабана.

Описание

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

Лиувилль сформулировал проблему, решенную в алгоритме Риша. Он доказал аналитически, что если есть элементарное решение g для уравнения ${\displaystyle g'=f}$ , то для констант ${\displaystyle \alpha _{i}}$ и элементарных функций ${\displaystyle u_{i}}$ и ${\displaystyle v}$ решение существует в форме

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

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

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

Для функции f e ^g , где f и g дифференцируемые , имеем

${\displaystyle (f\cdot e^{g})'=(f'+f\cdot g')\cdot e^{g},}$

так что если функция e ^g содержится в результате неопределённого интегрирования, она должна входить и в состав исходного подынтегрального выражения. Аналогично, поскольку

${\displaystyle {\big (}f\cdot (\ln g)^{n}{\big )}'=f'(\ln g)^{n}+nf{\frac {g'}{g}}(\ln g)^{n-1},}$

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

Примеры решаемых задач

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

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

а именно:

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

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

Следующие функции являются более сложными примерами:

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

Первообразная этой функции имеет короткую форму

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

Реализация

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

Случай же чистых алгебраических функций был решён и реализован в системе Reduce . Общий случай был решён и реализован Мануэлем Бронштейном в (предшественнице системы Axiom ) .

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

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

Почти каждый нетривиальный алгоритм, использующий многочлены, использует алгоритм их деления, как и алгоритм Риша. Если поле констант вычислимо, то проблема равенства нулю решаема, тогда алгоритм Риша полон. Примерами вычислимых полей констант являются ${\displaystyle \mathbb {Q} }$ и ${\displaystyle \mathbb {Q} (y)}$ .

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

Примечания

Ссылки

• R. H. Risch. The problem of integration in finite terms (англ.) // Transactions of the American Mathematical Society . — American Mathematical Society, 1969. — Vol. 139 . — P. 167—189 . — doi : . — JSTOR .
• R. H. Risch. The solution of the problem of integration in finite terms (англ.) // Bulletin of the American Mathematical Society : journal. — 1970. — Vol. 76 , no. 3 . — P. 605—608 . — doi : .
• Maxwell Rosenlicht. (англ.) // American Mathematical Monthly : journal. — Mathematical Association of America, 1972. — Vol. 79 , no. 9 . — P. 963—972 . — doi : . — JSTOR .
• Geddes, Czapor, Labahn. Algorithms for Computer Algebra (англ.) . — Kluwer Academic Publishers , 1992. — ISBN 0-7923-9259-0 .
• Manuel Bronstein. Symbolic Integration I (англ.) . — Springer, 2005. — ISBN 3-540-21493-3 .
• Manuel Bronstein. (англ.) . — 1998.
• Bhatt, Bhuvanesh. (англ.) на сайте Wolfram MathWorld .