WikiSort.ru - Не сортированное

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

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

Описание

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

Лиувилль сформулировал проблему, решенную в алгоритме Риша. Он доказал аналитически, что если есть элементарное решение g для уравнения 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^{\prime }+f\cdot g^{\prime })\cdot e^{g},}$

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

${\displaystyle (f\cdot (\ln g)^{n})'=f^{\prime }(\ln {g})^{n}+nf{\frac {g^{\prime }}{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}}}$

Но если в выражении выше 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({\sqrt {x+\ln x}}+\ln(x+{\sqrt {x+\ln x}}))+C.}$

Реализация

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

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

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

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

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

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

Примечания

Ссылки

• R. H. Risch (1969). “The problem of integration in finite terms”. Transactions of the American Mathematical Society. American Mathematical Society. 139: 167—189. DOI:10.2307/1995313. JSTOR 1995313.
• R. H. Risch (1970). “The solution of the problem of integration in finite terms”. Bulletin of the American Mathematical Society. 76 (3): 605—608. DOI:10.1090/S0002-9904-1970-12454-5.
• Maxwell Rosenlicht (1972). “Integration in finite terms”. American Mathematical Monthly. Mathematical Association of America. 79 (9): 963—972. DOI:10.2307/2318066. JSTOR 2318066.
• 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). “Symbolic Integration Tutorial” (PDF).
• Bhatt, Bhuvanesh. Risch Algorithm (англ.) на сайте Wolfram MathWorld.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.