Rikas algoritmi

Risch -algoritmi on algoritmi epämääräisten integraalien analyyttiseen laskemiseen käyttämällä differentiaalialgebran menetelmiä . Se perustuu integroitavan funktion tyyppiin ja rationaalisten funktioiden , juurien, logaritmien ja eksponentiaalisten funktioiden integrointimenetelmiin .

Nimetty Robert Henry Risch mukaan . Risch itse, joka kehitti algoritmin vuonna 1968, kutsui sitä "resoluutiomenettelyksi", koska menetelmä päättää, onko funktion antiderivaata perusfunktio . Yksityiskohtaisin tutkimus algoritmista on esitetty Keith Geddesin, Stefan Tzaporin ja George Labanin 100-sivuisessa kirjassa Computer Algebra Algorithms .

Kuvaus

Risch-algoritmi integroi perusfunktiot . Laplace ratkaisi tämän rationaalisten funktioiden ongelman osoittamalla, että rationaalisen funktion epämääräinen integraali on itse rationaalinen funktio, jolla on äärellinen määrä vakioita kerrottuna rationaalisten funktioiden logaritmeilla. Se otettiin käyttöön ohjelmistoissa 1960-luvun alussa.

Liouville muotoili Risch-algoritmilla ratkaistun ongelman. Hän todisti analyyttisesti, että jos yhtälölle on alkeisratkaisu g , niin vakioille ja alkeisfunktioille ja ratkaisu on olemassa muodossa $g'=f$ $\alpha_i$ $u_{i}$ $v$

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

Rish loi menetelmän, jonka avulla voimme tarkastella vain rajallista joukkoa perusfunktioita Liouville-muodossa.

Risch-algoritmi sai inspiraationsa eksponentiaalisten ja logaritmisten funktioiden käyttäytymisestä differentioinnin aikana.

Meillä on funktiolle f e g , jossa f ja g ovat differentioituvia

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

joten jos funktio e g sisältyy määräämättömän integroinnin seurauksena, se on sisällytettävä myös alkuperäiseen integrandiin. Samoin, koska

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

jos (ln g ) n sisältyy integrointitulokseen, niin alkuperäisen integrandin tulee sisältää useita logaritmin potenssia.

Esimerkkejä ratkaistavista tehtävistä

Alkuperäisen antiderivaatin löytäminen on erittäin herkkä pienille muutoksille. Esimerkiksi seuraavalla funktiolla on alkeellinen antiderivaatti:

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

nimittäin:

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

Mutta jos lausekkeessa f ( x ) muutamme 71:stä 72:een, on mahdotonta löytää alkeisantiderivaata. (Jotkut tietokonealgebrajärjestelmät voivat tässä tapauksessa palauttaa vastauksen ei-alkeisfunktiona eli elliptisenä integraalina , jota Risch-algoritmi ei kuitenkaan kata.)

Seuraavat toiminnot ovat monimutkaisempia esimerkkejä:

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

Tämän funktion antijohdannaisella on lyhyt muoto

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

Toteutus

Teoreettisesti rakennetun algoritmin tehokas ohjelmistototeutus osoittautui vaikeaksi tehtäväksi. Puhtaiden transsendenttisten funktioiden (ilman juuria ja polynomeja) tapauksessa tämä oli suhteellisen helppo toteuttaa useimmissa tietokonealgebrajärjestelmissä. [yksi]

Puhtaiden algebrallisten funktioiden tapauksen ratkaisi ja toteutti Reduce -järjestelmässä James Davenport [2] [3] . Yleisen tapauksen ratkaisi ja toteutti Manuel Bronstein Scratchpadissa ( Axiom -järjestelmän edeltäjä ) [4] .

Ratkaisevuus

Alkeisfunktioiden yleiseen tapaukseen sovellettu Risch-algoritmi ei ole algoritmi varsinaisessa merkityksessä, koska sen on työssään selvitettävä, ovatko jotkin lausekkeet identtisiä nollan kanssa (vakioiden ongelma ). Lausekkeille, joiden funktiot ovat alkeisfunktioita, ei tiedetä, onko olemassa algoritmia, joka suorittaa tällaisen tarkistuksen (nykyaikaiset järjestelmät käyttävät heuristiikkaa ). Lisäksi jos alkeisfunktioiden luetteloon lisätään absoluuttinen arvo , tällaista algoritmia ei ole olemassa ( Richardsonin lause ). Tämä ongelma esiintyy myös polynomien jakamisessa sarakkeella : sitä ei voida ratkaista, jos on mahdotonta määrittää kertoimien yhtäläisyys nollaan.

Melkein jokainen ei-triviaalinen algoritmi, joka käyttää polynomeja, käyttää polynomijakoalgoritmia, kuten myös Risch-algoritmi. Jos vakioiden kenttä on laskettavissa, niin nollan tasa-arvo on ratkaistavissa, niin Risch-algoritmi on valmis. Esimerkkejä laskettavissa olevista vakiokentistä ovat ja . $\mathbb {Q}$ ${\mathbb {Q}}(y)$

Sama ongelma esiintyy Gaussin menetelmässä , joka on myös välttämätön monille Risch-algoritmin osille. Gaussin menetelmä antaa virheellisen tuloksen, jos on mahdotonta määrittää oikein, onko kanta identtinen nollan kanssa.

Muistiinpanot

↑ Joel Moses (2012), Macsyma: Henkilökohtainen historia , Journal of Symbolic Computation , osa 47: 123–130 , DOI 10.1016/j.jsc.2010.08.018
↑ Ei pidä sekoittaa hänen isänsä Harold Davenportiin
↑ James H. Davenport. Algebrallisten funktioiden integroinnista . - Springer, 1981. - Voi. 102. - (Tietojenkäsittelytieteen luentomuistiinpanot). - ISBN 0-387-10290-6 , 3-540-10290-6.
↑ Manuel Bronstein (1990), Alkeisfunktioiden integrointi, Journal of Symbolic Computation , osa 9 (2): 117–173

Linkit

R. H. Rish. Integraation ongelma äärellisillä termeillä // Transactions of the American Mathematical Society . - American Mathematical Society, 1969. - Voi. 139 . - s. 167-189 . - doi : 10.2307/1995313 . — .
R. H. Rish. Integraation ongelman ratkaisu äärellisillä termeillä // Bulletin of the American Mathematical Society : Journal . - 1970. - Voi. 76 , nro. 3 . - s. 605-608 . - doi : 10.1090/S0002-9904-1970-12454-5 .
Maxwell Rosenlicht. Integrointi äärellisillä termeillä (englanniksi) // American Mathematical Monthly : Journal. - Mathematical Association of America, 1972. - Voi. 79 , ei. 9 . - s. 963-972 . - doi : 10.2307/2318066 . — .
Geddes, Czapor, Labahn. Tietokonealgebran algoritmit . - Kluwer Academic Publishers , 1992. - ISBN 0-7923-9259-0 .
Manuel Bronstein. Symbolinen integraatio I. - Springer, 2005. - ISBN 3-540-21493-3 .
Manuel Bronstein. Symbolisen integraation opetusohjelma . – 1998.
Bhatt, Bhuvanesh. Risch Algorithm (englanniksi) Wolfram MathWorld -verkkosivustolla .