Algoritm bogat

Algoritmul Risch este un algoritm pentru calculul analitic al integralelor nedefinite folosind metodele algebrei diferențiale . Se bazează pe tipul funcției integrabile și pe metode de integrare a funcțiilor raționale , rădăcini, logaritmi și funcții exponențiale .

Numit după Robert Henry Risch . Risch însuși, care a dezvoltat algoritmul în 1968, l-a numit „procedură de rezolvare”, deoarece metoda decide dacă antiderivata unei funcții este o funcție elementară . Cel mai detaliat studiu al algoritmului este prezentat în cartea de 100 de pagini Computer Algebra Algorithms de Keith Geddes, Stefan Tzapor și George Laban.

Descriere

Algoritmul Risch integrează funcții elementare . Laplace a rezolvat această problemă pentru funcțiile raționale arătând că integrala nedefinită a unei funcții raționale este ea însăși o funcție rațională cu un număr finit de constante înmulțit cu logaritmii funcțiilor raționale. A fost implementat în software la începutul anilor 1960.

Liouville a formulat problema rezolvată în algoritmul Risch. El a demonstrat analitic că, dacă există o soluție elementară g pentru ecuație , atunci pentru constante și funcții elementare și soluția există sub forma $g'=f$ $\alpha_i$ $tu_{i}$ $v$

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

Rish a creat o metodă care ne permite să luăm în considerare doar un set finit de funcții elementare în forma Liouville.

Algoritmul Risch a fost inspirat de comportamentul funcțiilor exponențiale și logaritmice în timpul diferențierii.

Pentru o funcție f e g , unde f și g sunt diferențiabile , avem

(f\cdot e^{g})'=(f'+f\cdot g')\cdot e^{g},

deci dacă funcția e g este conținută ca urmare a integrării nedefinite, ea trebuie inclusă și în integrandul original. La fel, pentru că

{\big (}f\cdot (\ln g)^{n}{\big )}'=f'(\ln g)^{n}+nf{\frac {g'}{g} }(\ln g)^{n-1},

dacă (ln g ) n este conținută în rezultatul integrării, atunci integrandul original trebuie să conțină mai multe puteri ale logaritmului.

Exemple de sarcini de rezolvat

Găsirea antiderivatului elementar este foarte sensibilă la modificări minore. De exemplu, următoarea funcție are o antiderivată elementară:

f(x)={\frac {x}{{\sqrt {x^{4}+10x^{2}-96x-71)))),

și anume:

{\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{aliniat} }

Dar dacă în expresia f ( x ) schimbăm 71 în 72, atunci va fi imposibil să găsim o antiderivată elementară. (Unele sisteme de algebră computerizată pot returna, în acest caz, răspunsul ca o funcție neelementară , integrala eliptică , care, totuși, nu este acoperită de algoritmul Risch.)

Următoarele funcții sunt exemple mai complexe:

f(x)={\frac {x^{2}+2x+1+(3x+1){\sqrt {x+\ln x)}}{x\,{\sqrt {x+\ln x }}(x+{\sqrt {x+\ln x))))}}.

Antiderivatul acestei funcții are o formă scurtă

F(x)=2\left[{\sqrt {x+\ln x}}+\ln \left(x+{\sqrt {x+\ln x}}\right)\right]+C.

Implementare

Implementarea software eficientă a algoritmului construit teoretic s-a dovedit a fi o sarcină dificilă. În cazul funcțiilor transcendentale pure (fără rădăcini și polinoame), acest lucru a fost relativ ușor de implementat în majoritatea sistemelor de algebră computerizată. [unu]

Cazul funcțiilor algebrice pure a fost rezolvat și implementat în sistemul Reduce de James Davenport [2] [3] . Cazul general a fost rezolvat și implementat de Manuel Bronstein în Scratchpad (predecesorul sistemului Axiom ) [4] .

Rezolvabilitate

Algoritmul Risch aplicat în cazul general al funcțiilor elementare nu este un algoritm în sens strict, deoarece în cursul activității sale trebuie să determine dacă unele expresii sunt identice cu zero ( problema constantelor ). Pentru expresiile ale căror funcții sunt elementare, nu se știe dacă există un algoritm care să facă o astfel de verificare (sistemele moderne folosesc euristica ). Mai mult, dacă la lista funcțiilor elementare se adaugă o valoare absolută , un astfel de algoritm nu există ( teorema lui Richardson ). Această problemă există și în împărțirea polinoamelor pe o coloană : nu va fi rezolvabilă dacă este imposibil să se determine egalitatea coeficienților la zero.

Aproape fiecare algoritm non-trivial care utilizează polinoame folosește un algoritm de divizare polinomială, la fel ca și algoritmul Risch. Dacă câmpul constantelor este calculabil, atunci problema egalității la zero este rezolvabilă, atunci algoritmul Risch este complet. Exemple de câmpuri constante calculabile sunt și . $\mathbb {Q}$ ${\mathbb {Q}}(y)$

Aceeași problemă există și în metoda Gauss , care este necesară și pentru multe părți ale algoritmului Risch. Metoda Gaussiană va da un rezultat incorect dacă este imposibil să se determine corect dacă baza va fi identică cu zero.

Note

↑ Joel Moses (2012), Macsyma: A personal history , Journal of Symbolic Computation vol. 47: 123–130 , DOI 10.1016/j.jsc.2010.08.018
↑ A nu fi confundat cu tatăl său, Harold Davenport
↑ James H. Davenport. Despre integrarea funcţiilor algebrice . — Springer, 1981. - Vol. 102. - (Note de curs în informatică). - ISBN 0-387-10290-6 , 3-540-10290-6.
↑ Manuel Bronstein (1990), Integration of elementary functions, Journal of Symbolic Computation vol. 9 (2): 117–173

Link -uri

R. H. Rish. Problema integrării în termeni finiți // Transactions of the American Mathematical Society . - Societatea Americană de Matematică, 1969. - Vol. 139 . - P. 167-189 . - doi : 10.2307/1995313 . — .
R. H. Rish. Rezolvarea problemei integrării în termeni finiți // Buletinul Societății Americane de Matematică : jurnal . - 1970. - Vol. 76 , nr. 3 . - P. 605-608 . - doi : 10.1090/S0002-9904-1970-12454-5 .
Maxwell Rosenlicht. Integrare în termeni finiți (engleză) // American Mathematical Monthly : jurnal. - Asociația de matematică din America, 1972. - Vol. 79 , nr. 9 . - P. 963-972 . - doi : 10.2307/2318066 . — .
Geddes, Czapor, Labahn. Algoritmi pentru algebră computerizată . - Kluwer Academic Publishers , 1992. - ISBN 0-7923-9259-0 .
Manuel Bronstein. Integrarea simbolică I. - Springer, 2005. - ISBN 3-540-21493-3 .
Manuel Bronstein. Tutorial de integrare simbolică . — 1998.
Bhatt, Bhuvanesh. Algoritmul Risch (engleză) pe site-ul web Wolfram MathWorld .