Czy istnieje pełna implementacja algorytmu Rischa?

Oct 15 2020

Czy istnieje ogólnie dostępna (komercyjna lub nie) pełna implementacja algorytmu Rischa do określania, czy funkcja elementarna ma elementarną funkcję pierwotną?

Artykuł Wikipedii dotyczący integracji symbolicznej twierdzi, że ogólny przypadek algorytmu Rischa został rozwiązany i zaimplementowany w Axiom przez Manuela Bronsteina, a odpowiedź na inne pytanie MO mówi to samo. Jednak mam pewne wątpliwości, na podstawie następującego komentarza samego Manuela Bronsteina na grupie dyskusyjnej USENET sci.math.symbolicz 5 września 2003 r .:

Jeśli Axiom zwraca nieocenioną całkę, to udowodniono, że nie istnieje elementarna funkcja pierwotna. Są jednak przypadki, w których Axiom może zwrócić komunikat o błędzie informujący, że trafiłeś w niezaimplementowaną gałąź algorytmu, w którym to przypadku nie może zakończyć. Więc Richard miał rację wskazując, że algorytm Rischa również nie jest tam w pełni zaimplementowany. Aksjomat jest wyjątkowy w różnicowaniu między niezaimplementowanymi rozgałęzieniami a dowodami niecałkowalności, a także w faktycznym dowodzeniu algebraicznej niezależności elementów składowych całki przed stwierdzeniem nierozłączności (inni zazwyczaj przyjmują tę niezależność po wykonaniu pewnych heurystycznych sprawdzeń zależności).

Bronstein niestety zmarł 6 czerwca 2005 roku . Możliwe, że ukończył wdrażanie przed śmiercią, ale nie byłem w stanie tego potwierdzić. Wiem, że Bronstein nigdy nie skończył swojej zamierzonej książki o całkowaniu funkcji algebraicznych. [ EDYCJA: W ramach dalszego sprawdzenia wysłałem e-mail do Barry'ego Tragera. Potwierdził, że realizacja, nad którą pracował z Bronsteinem, nie była kompletna. Nie wiedział zbyt wiele o innych wdrożeniach, ale nie był świadomy żadnych pełnych wdrożeń.]

Mam dostęp do Maple 2018 i wygląda na to, że nie ma też pełnej implementacji. Użytecznym przypadkiem testowym jest następująca całka, zaczerpnięta z (pozornie niepublikowanego) artykułu Algorytm Tragera do całkowania funkcji algebraicznych, który ponownie omówił Daniel Schultz:$$\int \frac{29x^2+18x-3}{\sqrt{x^6+4x^5+6x^4-12x^3+33x^2-16x}}\,dx$$ Schultz wyraźnie podaje elementarną funkcję pierwotną w swoim artykule, ale Maple 2018 zwraca całkę nieocenioną.

Odpowiedzi

20 SamBlake Oct 15 2020 at 08:43

Żaden system algebry komputerowej nie implementuje pełnego procesu decyzyjnego dla integracji mieszanych funkcji transcendentalnych i algebraicznych.

Całka z doskonałego papieru Schultza może zostać rozwiązana przez Maple, jeśli przekonwertujesz całkę na notację RootOf (dlaczego nie jest to zrobione wewnętrznie w Maple, to interesujące pytanie?)

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

Moje eksperymenty sugerują, że Maple ma najlepszą implementację algorytmu Rischa-Tragera-Bronsteina do całkowania czysto algebraicznych całek w kategoriach funkcji elementarnych (odniesienie: tabela 1, sekcja 3 Sam Blake, A Simple Method for Computing Some Pseudo-Elliptic Integrals w zakresie funkcji elementarnych , arXiv: 2004.04910 ). Jednak implementacja Maple nie integruje wyrażeń zawierających parametry lub zagnieżdżonych rodników (z których oba mają pewne wsparcie w AXIOM i FriCAS).

Wydawałoby się, że w obliczaniu logarytmicznej części mieszanej całki transcendentalnej-algebraicznej Miller [1] dokonał znaczącego postępu. Chociaż, o ile wiem, żaden system algebry komputerowej nie zaimplementował swojego algorytmu. Nie jest również jasne, czy algorytm Millera radzi sobie z parametrami, na przykład algorytm Rischa-Tragera-Bronsteina ma trudności z następującą całką pseudoeliptyczną

$$\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),$$ gdzie $y=\sqrt{2 p^2 x^4+2 p x^3+(4 pq+1)x^2+2 q x+2 q^2}$. Moja heurystyka w poprzednio połączonym artykule szybko oblicza tę całkę z podstawieniem$u=\frac{px^2+q}{p x}$.

W odniesieniu do mieszanego przypadku algebraiczno-transcendentalnego algorytmu Rischa-Tragera-Bronsteina, całka, której nie można rozwiązać za pomocą Maple, Mathematica, AXIOM lub FriCAS (i prawdopodobnie innych CAS) jest

$$\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.$$

Ta całka jest interesująca, ponieważ zwraca dwa różne komunikaty z AXIOM i FriCAS sugerujące, że ich implementacje są niekompletne. FriCAS powraca

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

Podczas gdy AXIOM powraca

(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). „ O integracji funkcji elementarnych: obliczanie części logarytmicznej ”. Praca magisterska (Ph.D.) Texas Tech University, Wydział Matematyki i Statystyki.

12 DimaPasechnik Oct 15 2020 at 20:11

Fricas , klon Axiom o otwartym kodzie źródłowym, implementuje znaczną część Rischahttp://fricas-wiki.math.uni.wroc.pl/RischImplementationStatus