Rik algoritm

Risch- algoritmen är en algoritm för analytisk beräkning av obestämda integraler med metoder för differentialalgebra . Den är baserad på typen av den integrerbara funktionen och på metoder för att integrera rationella funktioner , rötter, logaritmer och exponentialfunktioner .

Uppkallad efter Robert Henry Risch . Risch själv, som utvecklade algoritmen 1968, kallade den en "upplösningsprocedur" eftersom metoden avgör om antiderivatan av en funktion är en elementär funktion. Den mest detaljerade studien av algoritmen presenteras i boken Computer Algebra Algorithms på 100 sidor av Keith Geddes, Stefan Tzapor och George Laban.

Beskrivning

Risch-algoritmen integrerar elementära funktioner . Laplace löste detta problem för rationella funktioner genom att visa att den obestämda integralen av en rationell funktion i sig är en rationell funktion med ett ändligt antal konstanter multiplicerat med logaritmerna för de rationella funktionerna. Det implementerades i mjukvara i början av 1960-talet.

Liouville formulerade problemet löst i Risch-algoritmen. Han bevisade analytiskt att om det finns en elementär lösning g för ekvationen , då för konstanter och elementära funktioner och lösningen existerar i formen $g'=f$ $\alpha_i$ $u_{i}$ $v$

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

Rish skapade en metod som tillåter oss att endast överväga en ändlig uppsättning elementära funktioner i Liouville-formen.

Risch-algoritmen inspirerades av beteendet hos exponentiella och logaritmiska funktioner under differentiering.

För en funktion f e g , där f och g är differentierbara , har vi

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

så om funktionen e g finns som ett resultat av obestämd integration måste den också inkluderas i den ursprungliga integranden. Likaså sedan

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

om (lng ) n ingår i integrationsresultatet, måste den ursprungliga integranden innehålla flera potenser av logaritmen.

Exempel på uppgifter som ska lösas

Att hitta det elementära antiderivatet är mycket känsligt för mindre förändringar. Till exempel har följande funktion en elementär antiderivata:

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

nämligen:

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

Men om vi i uttrycket f ( x ) ändrar 71 till 72, kommer det att vara omöjligt att hitta en elementär antiderivata. (Vissa datoralgebrasystem kan i detta fall returnera svaret som en icke-elementär funktion , den elliptiska integralen , som dock inte täcks av Risch-algoritmen.)

Följande funktioner är mer komplexa exempel:

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

Antiderivatet av denna funktion har en kort form

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

Implementering

Effektiv mjukvaruimplementering av den teoretiskt uppbyggda algoritmen visade sig vara en svår uppgift. När det gäller rena transcendentala funktioner (utan rötter och polynom) var detta relativt enkelt att implementera i de flesta datoralgebrasystem. [ett]

Fallet med rena algebraiska funktioner löstes och implementerades i Reduce- systemet av James Davenport [2] [3] . Det allmänna fallet löstes och implementerades av Manuel Bronstein i Scratchpad (föregångaren till Axiom- systemet ) [4] .

Lösbarhet

Risch-algoritmen som tillämpas på det allmänna fallet med elementära funktioner är inte en algoritm i strikt mening, eftersom den under arbetets gång måste avgöra om vissa uttryck är identiska med noll ( problemet med konstanter ). För uttryck vars funktioner är elementära är det inte känt om det finns en algoritm som gör en sådan kontroll (moderna system använder heuristik ). Dessutom, om ett absolut värde läggs till i listan över elementära funktioner , existerar inte en sådan algoritm ( Richardsons teorem ). Detta problem finns också i divisionen av polynom med en kolumn : det kommer inte att vara lösbart om det är omöjligt att bestämma koefficienternas likhet till noll.

Nästan varje icke-trivial algoritm som använder polynom använder en polynom divisionsalgoritm, liksom Risch-algoritmen. Om konstantfältet är beräkningsbart, är problemet med lika med noll lösbart, då är Risch-algoritmen komplett. Exempel på beräkningsbara konstantfält är och . $\mathbb {Q}$ ${\mathbb {Q}}(y)$

Samma problem finns i Gauss-metoden , som också är nödvändig för många delar av Risch-algoritmen. Gaussmetoden ger ett felaktigt resultat om det är omöjligt att korrekt avgöra om basen kommer att vara identisk med noll.

Anteckningar

↑ Joel Moses (2012), Macsyma: A personal history , Journal of Symbolic Computation vol. 47: 123–130 , DOI 10.1016/j.jsc.2010.08.018
↑ Inte att förväxla med sin far, Harold Davenport
↑ James H. Davenport. Om integrationen av algebraiska funktioner . — Springer1981. - Vol. 102. - (Föreläsningsanteckningar i datavetenskap). - 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

Länkar

R.H. Rish. Problemet med integration i ändliga termer // Transactions of the American Mathematical Society . - American Mathematical Society, 1969. - Vol. 139 . - S. 167-189 . - doi : 10.2307/1995313 . — .
R.H. Rish. Lösningen av problemet med integration i ändliga termer // Bulletin of the American Mathematical Society : journal . - 1970. - Vol. 76 , nr. 3 . - s. 605-608 . - doi : 10.1090/S0002-9904-1970-12454-5 .
Maxwell Rosenlicht. Integration i finita termer (engelska) // American Mathematical Monthly : journal. - Mathematical Association of America, 1972. - Vol. 79 , nr. 9 . - P. 963-972 . - doi : 10.2307/2318066 . — .
Geddes, Czapor, Labahn. Algoritmer för datoralgebra . - Kluwer Academic Publishers , 1992. - ISBN 0-7923-9259-0 .
Manuel Bronstein. Symbolisk integration I. - Springer, 2005. - ISBN 3-540-21493-3 .
Manuel Bronstein. Handledning för symbolisk integration . — 1998.
Bhatt, Bhuvanesh. Risch Algorithm (engelska) på Wolfram MathWorld- webbplatsen .