Interested Article - Алгоритм Риша
![](/images/009/040/9040280/1.jpg?rand=566876)
![](https://cdn.wafarin.com/avatars/e48a64f384aa17da3c8e66c3b0ead58f.gif)
- 2020-12-05
- 1
Алгори́тм Ри́ша — алгоритм для аналитического вычисления неопределённых интегралов , использующий методы дифференциальной алгебры . Он базируется на типе интегрируемой функции и на методах интегрирования рациональных функций , корней, логарифмов , и экспоненциальных функций .
Назван в честь . Сам Риш, который разработал алгоритм в 1968 году, называл его «разрешающей процедурой», поскольку метод решает, является ли первообразная от функции элементарной функцией. Наиболее подробное исследование алгоритма представлено на 100 страницах книги « Алгоритмы компьютерной алгебры » Кейта Геддеса, Стефана Цапора и Джорджа Лабана.
Описание
Алгоритм Риша интегрирует элементарные функции . Лаплас решил эту проблему для рациональных функций , показав, что неопределённый интеграл рациональной функции сам является рациональной функцией с конечным количеством констант, умноженных на логарифмы рациональных функций. Программно он был реализован в начале 1960-х годов.
Лиувилль сформулировал проблему, решенную в алгоритме Риша. Он доказал аналитически, что если есть элементарное решение g для уравнения , то для констант и элементарных функций и решение существует в форме
Риш создал метод, который позволяет рассматривать только конечное множество элементарных функций в форме Лиувилля.
Алгоритм Риша был вдохновлён поведением экспоненциальных и логарифмических функций во время дифференцирования.
Для функции f e g , где f и g дифференцируемые , имеем
так что если функция e g содержится в результате неопределённого интегрирования, она должна входить и в состав исходного подынтегрального выражения. Аналогично, поскольку
если (ln g ) n содержится в результате интегрирования, то в исходном подынтегральном выражении должно присутствовать несколько степеней логарифма.
Примеры решаемых задач
Нахождение элементарной первообразной очень чувствительно к незначительным изменениям. Например, следующая функция имеет элементарную первообразную:
а именно:
Но если в выражении f ( x ) сменить 71 на 72, то будет невозможно найти элементарную первообразную. (Некоторые системы компьютерной алгебры могут в данном случае вернуть ответ как неэлементарную функцию — эллиптический интеграл , который, однако, не охватывается алгоритмом Риша.)
Следующие функции являются более сложными примерами:
Первообразная этой функции имеет короткую форму
Реализация
Эффективная программная реализация теоретически построенного алгоритма оказалась сложной задачей. В случае чистых трансцендентных функций (не содержащих корней и полиномов) это относительно легко было реализовано в большинстве систем компьютерной алгебры.
Случай же чистых алгебраических функций был решён и реализован в системе Reduce . Общий случай был решён и реализован Мануэлем Бронштейном в (предшественнице системы Axiom ) .
Разрешимость
Алгоритм Риша в приложении к общему случаю элементарных функций не является алгоритмом в строгом смысле, потому как в процессе работы ему требуется определять, тождественны ли некоторые выражения нулю ( ). Для выражений, функции в которых элементарны, неизвестно, существует ли алгоритм, делающий такую проверку (современные системы используют эвристику ). Более того, если в список элементарных функций добавить абсолютную величину , такого алгоритма не существует ( ). Данная проблема имеется и в делении многочленов столбиком : оно не будет разрешимо, если нельзя определить равенство коэффициентов нулю.
Почти каждый нетривиальный алгоритм, использующий многочлены, использует алгоритм их деления, как и алгоритм Риша. Если поле констант вычислимо, то проблема равенства нулю решаема, тогда алгоритм Риша полон. Примерами вычислимых полей констант являются и .
Такая же проблема имеется и в методе Гаусса , который тоже является необходимым для многих частей алгоритма Риша. Метод Гаусса будет давать некорректный результат, если невозможно правильно определить, будет ли базис идентичен нулю.
Примечания
- Joel Moses (2012), "Macsyma: A personal history", Journal of Symbolic Computation , 47 : 123—130, doi :
- Не следует путать с его отцом,
- James H. Davenport. On the integration of algebraic functions (англ.) . — ISBN 0-387-10290-6 , 3-540-10290-6. , 1981. — Vol. 102. — (Lecture notes in computer science). —
- Manuel Bronstein (1990), "Integration of elementary functions", Journal of Symbolic Computation , 9 (2): 117—173
Ссылки
- 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 : . — .
- 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 : . — .
- Geddes, Czapor, Labahn. (англ.) . — 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 .
![](https://cdn.wafarin.com/avatars/e48a64f384aa17da3c8e66c3b0ead58f.gif)
- 2020-12-05
- 1