Gazdag algoritmus

A Risch -algoritmus határozatlan integrálok analitikus kiszámítására szolgáló algoritmus differenciálalgebra módszereivel . Az integrálható függvény típusán és a racionális függvények , gyökök, logaritmusok és exponenciális függvények integrálásának módszerein alapul .

Robert Henry Risch nevéhez fűződik . Maga Risch, aki 1968-ban kidolgozta az algoritmust, "feloldó eljárásnak" nevezte, mivel a módszer eldönti, hogy egy függvény antideriváltja elemi függvény-e. Az algoritmus legrészletesebb tanulmányát Keith Geddes, Stefan Tzapor és George Laban Computer Algebra Algorithms című 100 oldalas könyve mutatja be.

Leírás

A Risch algoritmus elemi függvényeket integrál . Laplace ezt a problémát a racionális függvényekre úgy oldotta meg, hogy megmutatta, hogy a racionális függvény határozatlan integrálja maga is racionális függvény, amelynek véges számú állandója megszorozva a racionális függvények logaritmusával. Az 1960-as évek elején szoftveresen implementálták.

Liouville megfogalmazta a Risch-algoritmusban megoldott problémát. Analitikusan bebizonyította, hogy ha van g elemi megoldása az egyenletnek , akkor konstansokra és elemi függvényekre és a megoldás a következő formában létezik $g'=f$ $\alpha_i$ $u_{i}$ $v$

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

Rish megalkotott egy olyan módszert, amely lehetővé teszi, hogy csak véges elemi függvényhalmazt vegyünk figyelembe Liouville formában.

A Risch-algoritmust az exponenciális és logaritmikus függvények differenciálás közbeni viselkedése ihlette.

Egy f e g függvényre , ahol f és g differenciálható , van

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

tehát ha az e g függvény határozatlan integráció eredményeként szerepel, akkor az eredeti integrandusban is szerepelnie kell. Ugyanígy, mivel

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

ha (ln g ) n szerepel az integrálás eredménye, akkor az eredeti integrandusnak tartalmaznia kell a logaritmus több hatványát.

Példák a megoldandó feladatokra

Az elemi antiderivált megtalálása nagyon érzékeny a kisebb változásokra. Például a következő függvénynek van egy elemi antideriváltja:

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

ugyanis:

{\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{igazított} }

De ha az f ( x ) kifejezésben 71-et 72-re változtatunk, akkor lehetetlen elemi antideriváltat találni. (Egyes számítógépes algebrai rendszerek ebben az esetben nem elemi függvényként , elliptikus integrálként adják vissza a választ , amelyet azonban a Risch-algoritmus nem fed le.)

A következő függvények bonyolultabb példák:

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

Ennek a függvénynek az antideriváltja rövid formája van

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

Megvalósítás

Az elméletileg felépített algoritmus hatékony szoftveres megvalósítása nehéz feladatnak bizonyult. A tiszta transzcendentális függvények esetében (gyökök és polinomok nélkül) ez viszonylag könnyen megvalósítható volt a legtöbb számítógépes algebrai rendszerben. [egy]

A tiszta algebrai függvények esetét a Reduce rendszerben oldotta meg és implementálta James Davenport [2] [3] . Az általános esetet Manuel Bronstein oldotta meg és implementálta a Scratchpadben (az Axiom rendszer elődje ) [4] .

Feloldhatóság

Az elemi függvények általános esetére alkalmazott Risch-algoritmus nem a szoros értelemben vett algoritmus, mert munkája során meg kell határoznia, hogy egyes kifejezések megegyeznek-e nullával ( konstansok problémája ). Azoknál a kifejezéseknél, amelyeknek a függvényei elemi, nem ismert, hogy létezik-e olyan algoritmus, amely ilyen ellenőrzést végez (a modern rendszerek heurisztikát használnak ). Sőt, ha abszolút értéket adunk az elemi függvények listájához , akkor nem létezik ilyen algoritmus ( Richardson tétele ). Ez a probléma a polinomok oszlopos osztásakor is fennáll : nem lesz megoldható, ha lehetetlen meghatározni az együtthatók nullával való egyenlőségét.

Szinte minden nem triviális, polinomokat használó algoritmus polinomosztási algoritmust használ, akárcsak a Risch-algoritmus. Ha az állandók mezője kiszámítható, akkor a nullával való egyenlőség problémája megoldható, akkor a Risch-algoritmus kész. Példák a kiszámítható állandó mezőkre és . $\mathbb {Q}$ ${\mathbb {Q}}(y)$

Ugyanez a probléma létezik a Gauss-módszerben is, amely szintén szükséges a Risch-algoritmus sok részéhez. A Gauss-módszer hibás eredményt ad, ha nem lehet pontosan meghatározni, hogy az alap megegyezik-e a nullával.

Jegyzetek

↑ Joel Moses (2012), Macsyma: A Personal History , Journal of Symbolic Computation 47. kötet: 123–130 , DOI 10.1016/j.jsc.2010.08.018.
↑ Nem tévesztendő össze az apjával, Harold Davenporttal
↑ James H. Davenport. Az algebrai függvények integrálásáról . — Springer, 1981. - 1. évf. 102. - (Számítástechnikai előadásjegyzetek). - ISBN 0-387-10290-6 , 3-540-10290-6.
↑ Manuel Bronstein (1990), Integration of elementary functions, Journal of Symbolic Computation , 9. kötet (2): 117–173

Linkek

R. H. Rish. Az integráció problémája véges terminusokban // Transactions of the American Mathematical Society . - American Mathematical Society, 1969. - Vol. 139 . - 167-189 . o . - doi : 10.2307/1995313 . — .
R. H. Rish. Az integráció problémájának megoldása véges kifejezésekkel // Bulletin of the American Mathematical Society : folyóirat . - 1970. - 1. évf. 76 , sz. 3 . - P. 605-608 . - doi : 10.1090/S0002-9904-1970-12454-5 .
Maxwell Rosenlicht. Integráció véges kifejezésekkel (angol) // American Mathematical Monthly : folyóirat. - Mathematical Association of America, 1972. - Vol. 79 , sz. 9 . - P. 963-972 . - doi : 10.2307/2318066 . — .
Geddes, Czapor, Labahn. Algoritmusok számítógépes algebra számára . - Kluwer Academic Publishers , 1992. - ISBN 0-7923-9259-0 .
Manuel Bronstein. Szimbolikus integráció I. - Springer, 2005. - ISBN 3-540-21493-3 .
Manuel Bronstein. Szimbolikus integrációs oktatóanyag . – 1998.
Bhatt, Bhuvanesh. Risch Algorithm (angol) a Wolfram MathWorld webhelyen .