Esiste un'implementazione completa dell'algoritmo Risch?

Oct 15 2020

Esiste un'implementazione completa (commerciale o meno) generalmente disponibile dell'algoritmo di Risch per determinare se una funzione elementare ha un antiderivativo elementare?

L' articolo di Wikipedia sull'integrazione simbolica afferma che il caso generale dell'algoritmo di Risch è stato risolto e implementato in Axiom da Manuel Bronstein, e una risposta a un'altra domanda di MO dice la stessa cosa. Tuttavia, ho qualche dubbio, sulla base del seguente commento dello stesso Manuel Bronstein sul newsgroup USENET sci.math.symbolicdel 5 settembre 2003:

Se Axiom restituisce un integrale non valutato, allora ha dimostrato che non esiste alcuna antiderivativa elementare. Ci sono tuttavia alcuni casi in cui Axiom può restituire un messaggio di errore che dice che hai raggiunto un ramo non implementato dell'algoritmo, nel qual caso non può concludere. Quindi Richard aveva ragione nel sottolineare che l'algoritmo di Risch non è completamente implementato neanche lì. Axiom è unico nel fare la differenza tra rami non implementati e prove di non integrabilità, e anche nel dimostrare effettivamente l'indipendenza algebrica degli elementi costitutivi dell'integrando prima di concludere la non integrabilità (altri tipicamente assumono questa indipendenza dopo aver eseguito alcuni controlli euristici delle dipendenze).

Bronstein purtroppo è morto il 6 giugno 2005 . È possibile che abbia completato l'implementazione prima di morire, ma non sono stato in grado di confermarlo. So che Bronstein non è mai riuscito a finire il suo libro sull'integrazione delle funzioni algebriche. [ EDIT: come ulteriore controllo, ho inviato un'e-mail a Barry Trager. Ha confermato che l'implementazione su cui hanno lavorato lui e Bronstein non era completa. Non sapeva molto di altre implementazioni ma non era a conoscenza di alcuna implementazione completa.]

Ho accesso a Maple 2018 e non sembra nemmeno avere un'implementazione completa. Un utile test case è il seguente integrale, tratto dall'algoritmo (apparentemente inedito) dell'articolo di Trager per l'integrazione di funzioni algebriche rivisitato da Daniel Schultz:$$\int \frac{29x^2+18x-3}{\sqrt{x^6+4x^5+6x^4-12x^3+33x^2-16x}}\,dx$$ Schultz fornisce esplicitamente un antiderivativo elementare nel suo articolo, ma Maple 2018 restituisce l'integrale non valutato.

Risposte

20 SamBlake Oct 15 2020 at 08:43

Nessun sistema di computer algebra implementa un processo decisionale completo per l'integrazione di funzioni miste trascendentali e algebriche.

L'integrale dell'ottimo articolo di Schultz può essere risolto da Maple se converti l'integrando in notazione RootOf (perché questo non viene fatto internamente in Maple è una domanda 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);

I miei esperimenti suggeriscono che Maple abbia la migliore implementazione dell'algoritmo di Risch-Trager-Bronstein per l'integrazione di integrali puramente algebrici in termini di funzioni elementari (rif: tabella 1, sezione 3 di Sam Blake, A Simple Method for Computing Some Pseudo-Elliptic Integrals in termini di funzioni elementari , arXiv: 2004.04910 ). Tuttavia, l'implementazione di Maple non integra espressioni contenenti parametri o radicali annidati (entrambi hanno un certo supporto in AXIOM e FriCAS).

Sembrerebbe che sia stato compiuto qualche progresso significativo nel calcolo della parte logaritmica di un integrale misto trascendentale-algebrico da Miller [1]. Tuttavia, per quanto ne so, nessun sistema di computer algebra ha implementato il suo algoritmo. Inoltre non è chiaro se l'algoritmo di Miller può gestire i parametri, ad esempio, l'algoritmo di Risch-Trager-Bronstein ha difficoltà con il seguente integrale pseudoellittico

$$\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),$$ dove $y=\sqrt{2 p^2 x^4+2 p x^3+(4 pq+1)x^2+2 q x+2 q^2}$. La mia euristica nel documento precedentemente collegato calcola questo integrale rapidamente con la sostituzione$u=\frac{px^2+q}{p x}$.

Per quanto riguarda il caso misto algebrico-trascendentale dell'algoritmo di Risch-Trager-Bronstein, un integrale che non può essere risolto con Maple, Mathematica, AXIOM o FriCAS (e possibilmente altri 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.$$

Questo integrale è interessante in quanto restituisce due messaggi distinti da AXIOM e FriCAS che suggeriscono che le rispettive implementazioni sono incomplete. FriCAS ritorna

(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)

Mentre AXIOM ritorna

(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). " Sull'integrazione delle funzioni elementari: calcolo della parte logaritmica ". Tesi (Ph.D.) Texas Tech University, Dipartimento di Matematica e Statistica.

12 DimaPasechnik Oct 15 2020 at 20:11

Fricas , un clone open source di Axiom, implementa una parte considerevole di Risch, vedihttp://fricas-wiki.math.uni.wroc.pl/RischImplementationStatus