Existe uma implementação completa do algoritmo de Risch?

Oct 15 2020

Existe uma implementação completa (comercial ou não) geralmente disponível do algoritmo de Risch para determinar se uma função elementar tem uma antiderivada elementar?

O artigo da Wikipedia sobre integração simbólica afirma que o caso geral do algoritmo de Risch foi resolvido e implementado no Axiom por Manuel Bronstein, e uma resposta a outra pergunta do MO diz a mesma coisa. No entanto, tenho algumas dúvidas, com base no seguinte comentário do próprio Manuel Bronstein no newsgroup USENET sci.math.symbolicem 5 de setembro de 2003:

Se Axiom retornar uma integral não avaliada, então ele provou que nenhuma antiderivada elementar existe. No entanto, existem alguns casos em que o Axiom pode retornar uma mensagem de erro dizendo que você atingiu uma ramificação não implementada do algoritmo, caso em que não pode ser concluído. Então, Richard estava certo ao apontar que o algoritmo de Risch também não está totalmente implementado lá. A Axiom é única em fazer a diferença entre ramificações não implementadas e provas de não integrabilidade, e também em realmente provar a independência algébrica dos blocos de construção do integrando antes de concluir a não integrabilidade (outros normalmente assumem essa independência após realizar alguma verificação de dependência heurística).

Bronstein infelizmente faleceu em 6 de junho de 2005 . É possível que ele tenha concluído a implementação antes de morrer, mas não fui capaz de confirmar isso. Eu sei que Bronstein nunca conseguiu terminar seu livro sobre a integração de funções algébricas. [ EDITAR: Como uma verificação adicional, enviei um email para Barry Trager Ele confirmou que a implementação na qual ele e Bronstein trabalharam não estava completa. Ele não sabia muito sobre outras implementações, mas não tinha conhecimento de nenhuma implementação completa.]

Eu tenho acesso ao Maple 2018, e também não parece ter uma implementação completa. Um caso de teste útil é a seguinte integral, tirada do algoritmo de Trager do artigo (aparentemente não publicado) para a integração de funções algébricas revisitado por Daniel Schultz:$$\int \frac{29x^2+18x-3}{\sqrt{x^6+4x^5+6x^4-12x^3+33x^2-16x}}\,dx$$ Schultz fornece explicitamente uma antiderivada elementar em seu artigo, mas o Maple 2018 retorna a integral não avaliada.

Respostas

20 SamBlake Oct 15 2020 at 08:43

Nenhum sistema de álgebra computacional implementa um processo de decisão completo para a integração de funções transcendentais e algébricas mistas.

A integral do excelente artigo de Schultz pode ser resolvida pelo Maple se você converter o integrando para a notação RootOf (por que isso não é feito internamente no Maple é uma questão interessante?)

int(convert((29*x^2+18*x-3)/(x^6+4*x^5+6*x^4-12*x^3+33*x^2-16*x)^(1/2),RootOf),x);

Meus experimentos sugerem que Maple tem a melhor implementação do algoritmo de Risch-Trager-Bronstein para a integração de integrais puramente algébricos em termos de funções elementares (ref: tabela 1, seção 3 de Sam Blake, Um método simples para calcular alguns integrais pseudo-elípticos em Termos de Funções Elementares , arXiv: 2004.04910 ). No entanto, a implementação do Maple não integra expressões contendo parâmetros ou radicais aninhados (ambos com algum suporte em AXIOM e FriCAS).

Parece que algum progresso significativo foi feito no cálculo da parte logarítmica de uma integral algébrica transcendental mista por Miller [1]. Embora, até onde eu saiba, nenhum sistema de álgebra computacional implementou seu algoritmo. Também não está claro se o algoritmo de Miller pode lidar com parâmetros, por exemplo, o algoritmo de Risch-Trager-Bronstein tem dificuldades com a seguinte integral pseudo-elíptica

$$\int\frac{\left(p x^2-q\right) \left(p x^2-x+q\right)dx}{x \left(p x^2+2 x+q\right) \sqrt{2 p^2x^4+2 p x^3+(4 p q+1) x^2+2 q x+2 q^2}} = - \frac{1}{\sqrt{2}}\log (x) + \frac{1}{\sqrt{2}}\log \left(\sqrt{2} y +2 p x^2+x+2q\right) - \frac{3}{\sqrt{5}}\tanh ^{-1}\left(\frac{\sqrt{5} y}{3 p x^2+3 q+x}\right),$$ Onde $y=\sqrt{2 p^2 x^4+2 p x^3+(4 pq+1)x^2+2 q x+2 q^2}$. Minha heurística no artigo previamente vinculado calcula essa integral rapidamente com a substituição$u=\frac{px^2+q}{p x}$.

Em relação ao caso algébrico-transcendental misto do algoritmo de Risch-Trager-Bronstein, uma integral que não pode ser resolvida com Maple, Mathematica, AXIOM ou FriCAS (e possivelmente outro CAS) é

$$\int \frac{\left(\sqrt{x}+1\right) \left(e^{2x \sqrt{x}} -a\right) \sqrt{a^2+2 a x e^{2 \sqrt{x}} +cx e^{2 \sqrt{x}} +x^2 e^{4 \sqrt{x}}}}{x \sqrt{x}e^{\sqrt{x}} \left(a+x e^{2 \sqrt{x}} \right)} dx.$$

Esta integral é interessante, pois retorna duas mensagens distintas de AXIOM e FriCAS, sugerindo que suas respectivas implementações estão incompletas. FriCAS retorna

(1) -> integrate(((-a+exp(2*x^(1/2))*x)*x^(-3/2)*(1+x^(1/2))*(a^2+2*a*exp(2*x^(1/2))*x+c*exp(2*x^(1/2))*x+exp(4*x^(1/2))*x^2)^(1/2))/(exp(x^(1/2))*(a+exp(2*x^(1/2))*x)),x)
                                                                                                        
   >> Error detected within library code:                                                               
   integrate: implementation incomplete (has polynomial part)

Enquanto AXIOM retorna

(1) -> integrate(((-a+exp(2*x^(1/2))*x)*x^(-3/2)*(1+x^(1/2))*(a^2+2*a*exp(2*x^(1/2))*x+c*exp(2*x^(1/2))*x+exp(4*x^(1/2))*x^2)^(1/2))/(exp(x^(1/2))*(a+exp(2*x^(1/2))*x)),x)
                                                                                                        
   >> Error detected within library code:
   integrate: implementation incomplete (constant residues)

[1] Miller, B. (2012). “ On the Integration of Elementary Functions: Computing the Logarithmic Part ”. Tese (Ph.D.) Texas Tech University, Departamento de Matemática e Estatística.

12 DimaPasechnik Oct 15 2020 at 20:11

Fricas , um clone de código aberto da Axiom, implementa uma porção considerável de Risch, consultehttp://fricas-wiki.math.uni.wroc.pl/RischImplementationStatus