Алгоритм Риша

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

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

ОписаниеПравить

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

Лиувилль сформулировал проблему, решенную в алгоритме Риша. Он доказал аналитически, что если есть элементарное решение g для уравнения $g^{\prime }=f$$g'=f$ , то для констант ${\mathrm{\alpha <!--\; \alpha \; -->}}_i$$\alpha_i$  и элементарных функций $u_i$$u_{i}$  и $v$$v$  решение существует в форме

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

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

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

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

$(f\cdot <!--\; \cdot \; -->e^g{)}^{\prime }=(f^{\prime }+f\cdot <!--\; \cdot \; -->g^{\prime })\cdot <!--\; \cdot \; -->e^g,$$(f\cdot e^{g})'=(f'+f\cdot g')\cdot e^{g},$ 

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

$(f\cdot <!--\; \cdot \; -->(\ln <!--\; \; -->g{)}^n{)}^{\prime }=f^{\prime }(\ln <!--\; \; -->g{)}^n+nf\frac{g^{\prime }}{g}(\ln <!--\; \; -->g{)}^{n-<!--\; -\; -->1},$${\big (}f\cdot (\ln g)^{n}{\big )}'=f'(\ln g)^{n}+nf{\frac {g'}{g}}(\ln g)^{n-1},$ 

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

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

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

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

а именно:

${\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, то будет невозможно найти элементарную первообразную. (Некоторые системы компьютерной алгебры могут в данном случае вернуть ответ как неэлементарную функцию — эллиптический интеграл, который, однако, не охватывается алгоритмом Риша.)

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

$f(x)=\frac{x^2+2x+1+(3x+1)\sqrt{x+\ln <!--\; \; -->x}}{x\sqrt{x+\ln <!--\; \; -->x}(x+\sqrt{x+\ln <!--\; \; -->x})}.$$f(x)={\frac {x^{2}+2x+1+(3x+1){\sqrt {x+\ln x}}}{x\,{\sqrt {x+\ln x}}(x+{\sqrt {x+\ln x}})}}.$ 

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

$F(x)=2\left[\sqrt{x+\ln <!--\; \; -->x}+\ln <!--\; \; -->\left(x+\sqrt{x+\ln <!--\; \; -->x}\right)\right]+C.$$F(x)=2\left[{\sqrt {x+\ln x}}+\ln \left(x+{\sqrt {x+\ln x}}\right)\right]+C.$ 

РеализацияПравить

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

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

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

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

Почти каждый нетривиальный алгоритм, использующий многочлены, использует алгоритм их деления, как и алгоритм Риша. Если поле констант вычислимо, то проблема равенства нулю решаема, тогда алгоритм Риша полон. Примерами вычислимых полей констант являются $\mathbb{Q}$$\mathbb {Q}$  и $\mathbb{Q}(y)$${\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:10.2307/1995313. — JSTOR 1995313.
• 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:10.1090/S0002-9904-1970-12454-5.
• Maxwell Rosenlicht. Integration in finite terms (англ.) // American Mathematical Monthly : journal. — Mathematical Association of America, 1972. — Vol. 79, no. 9. — P. 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. Symbolic Integration Tutorial (англ.). — 1998.
• Bhatt, Bhuvanesh. Risch Algorithm (англ.) на сайте Wolfram MathWorld.