Risch-algoritmus

A Risch-algoritmus a határozatlan integrálok kiszámítására fejlesztett módszer.

Az algoritmust Robert Henry Risch, egyesült államokbeli matematikusról nevezték el, aki 1968-ban fejlesztette ki.

A ’zárt alakban’ kifejezhető integrálokra vonatkozó alapvető eredményt Joseph Liouville (1809-1882) francia matematikus 1833-ban találta meg, a megfelelő algoritmikus módszereket Risch 1968-ban fejlesztette ki.

Az algoritmus az integrálás problémáját visszavezeti algebrai megoldásra. A 'zárt alakban' megadható függvények azok a függvények, melyek felépíthetők a racionális függvények, az exponenciális és logaritmus függvény, a trigonometrikus és hiperbolikus függvények és inverzeik, valamint sokkal általánosabban, polinom függvények, és azok inverzei, azaz egyenletek gyökeinek képzése segítségével, és ezen függvények egymásba helyettesítésével.

Risch, az algoritmust döntési folyamatnak nevezte, mert a módszer azt dönti el, hogy a függvénynek van-e elemi függvénye, mely határozatlan integrál, és ha van, akkor azt meghatározza.

A Risch-algoritmus összegzése (több, mint 100 oldal) a ‘Algorithms for Computer Algebra’^[1] könyvben található. Az 1976-ban kifejlesztett Risch–Norman algoritmus (A. C. Norman után) egy gyorsabb módszer, de nem annyira hatékony, mint az eredeti.

Leírás

A Risch-algoritmus az elemi függvényeket használja fel az integráláshoz. Ezek az exponenciális és logaritmus függvények, a trigonometrikus és hiperbolikus függvények és inverzeik, gyökök, a négy aritmetikai művelet (+ − × ÷).

Laplace ezt a problémát a racionális függvényekre megoldotta, kimutatta, hogy egy racionális függvény határozatlan integrálja egy racionális függvény, és a racionális függvény véges számú konstanssal szorzott logaritmusa. Ez az algoritmus rendszerint megtalálható a tankönyvekben; mint számítógépes programot a 60-as években vezették be.

Liouville által megoldott problémát Risch algoritmizálta. Liouville analitikai eszközökkel bizonyította, hogy ha létezik, g′ = f egyenletnek van g elemi megoldása, akkor α_i konstansra, és u_i elemi függvényekre, és v-re a megoldás:

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

Risch kidolgozta a módszert, hogy Liouville formulájából csak egy véges elemi függvény készletet kelljen figyelembe venni.

Az intuíció, a Risch-algoritmusra, az exponenciális, és a logaritmikus függvények differenciálása alatti viselkedéséből jött. Ha f e^g, ahol f és g differenciálható függvények, akkor, kapjuk:

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

így, ha e^g benne volt egy határozatlan integrálás eredményében, akkor várható, hogy benne lesz az integrálban. Tehát:

${\displaystyle (f\cdot \ln ^{n}g)'=f^{\prime }\ln ^{n}{g}+nf{\frac {g^{\prime }}{g}}\ln ^{n-1}{g}}$

és ha lnⁿg benne volt az integrálásban, akkor csak a logaritmusnak csak néhány hatványa várható.

Példák

Egy elemi antideriváltat megtalálni elég kényes feladat. Például, a következő függvénynek van egy elemi antideriváltja:

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

mégpedig:

${\displaystyle {\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{aligned}}}$

Komputeralgebra rendszerek között van olyan, mely kiad egy antideriváltat, nem elemi függvény formában (például: elliptikus integrál), mely azonban nem része a Risch-algoritmusnak.

Ha például a 71-et 72-re változtatjuk, akkor nem lehetséges az antideriváltat elemi függvényekkel kifejezni.

A következő függvény^[2] komplexebb példa:

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

A függvény antideriváltja elég rövid kifejezés:

${\displaystyle F(x)=2({\sqrt {x+\ln x}}+\ln(x+{\sqrt {x+\ln x}}))+C.}$

Megvalósítás

Risch elméleti algoritmusának átalakítása egy számítógép által végrehajtható algoritmussá, komplex feladat, mely hosszú időt igényel.

A tisztán transzcendens függvények (melyek nem tartalmaznak polinomok gyökeit), viszonylag könnyű esetek, és már korai fázisban megvalósította a legtöbb komputeralgebra rendszer. Az első implementációt Joel Moses készítette a Macsyma programban, nem sokkal azután, hogy Risch publikációja megjelent.^[3]

A tisztán algebrai függvényekkel történő magvalósítást a Reduce-ban James H. Davenport készítette.^[4][5]

Az általános megoldást Manuel Bronstein a Scratchpad-ben (az Axiom előfutára) készítette el.^[6]

Eldönthetőség

Az általános elemi függvényekre alkalmazható Risch-algoritmus nem egy algoritmus, hanem egy fél-algoritmus, mert szükséges ellenőrizni - a működés részeként -, hogy egyes kifejezések egyenlőek zérussal, különösen az állandóknál. Ha abszolútérték-függvényt is hozzáadjuk az elemi függvények listájához, akkor tudható, hogy az algoritmus nem működik (lásd: Richardson-tétel). A komputeralgebra rendszereknél az ellenőrzést heurisztikus módszerekkel végzik.

Virtuálisan minden nem triviális polinomokkal kapcsolatos algoritmus használja a polinom döntési algoritmust, ezt a Risch-algoritmus is tartalmazza.^[7]

Ha konstans mező számítható, azaz x-től független elemekre a zéró-ekvivalencia eldönthető, ekkor a Risch-algoritmus egy komplett algoritmus.

Irodalom

• R. H. Risch: The problem of integration in finite terms". (hely nélkül): Transactions of the American Mathematical Society (American Mathematical Society). 1969.  
• Geddes, Czapor, Labahn: Algorithms for Computer Algebra. (hely nélkül): Transactions of the American Mathematical Society (American Mathematical Society). 1972. ISBN 0-7923-9259-0  
• Manuel Bronstein: Symbolic Integration I. (hely nélkül): Springer. 1969. ISBN 3-540-21493-3  

Kapcsolódó szócikkek

• http://www.ams.org/journals/tran/1969-139-00/S0002-9947-1969-0237477-8/home.html
• http://compalg.inf.elte.hu/~tony/Elektronikus/Informatikai/02H.xml#id4531408
• http://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/issac98.pdf
• Liouville-elmélet 
• Integrálok listája
• Komputeralgebra rendszerek
• Antiderivált
• Macsyma
• Reduce
• Axiom
• Numerikus integrálás
• Szimbolikus integrálás
• Döntési folyamat

Jegyzetek