Risch algoritme - Risch algorithm

Del av en serie artikler om
Kalkulator
Grunnleggende setning Leibniz integrert regel Funksjonsgrenser Kontinuitet Gjennomsnittlig setning Rolles teorem
Differensial Definisjoner Derivat  ( generaliseringer ) Differensial uendelig liten av en funksjon Total Begreper Differensieringsnotasjon Andre derivat Implisitt differensiering Logaritmisk differensiering Relaterte priser Taylors teorem Regler og identiteter Sum Produkt Kjede Makt Quotient L'Hôpitals regel Omvendt General Leibniz Faà di Brunos formel
Integrert Lister over integraler Integrert transformasjon Definisjoner Antiderivativ Integrert  ( upassende ) Riemann integrert Lebesgue-integrasjon Konturintegrasjon Integrering av inverse funksjoner Integrasjon av Deler Skiver Sylindriske skall Substitusjon  ( trigonometrisk , Weierstrass , Euler ) Eulers formel Delvise brøker Endrer rekkefølge Reduksjonsformler Differensiering under det integrerte tegnet Risch algoritme
Serie Geometrisk  ( aritmetisk-geometrisk ) Harmonisk Alternerende Makt Binomial skredder Konvergens tester Summand limit (term test) Forhold Rot Integrert Direkte sammenligning Begrens sammenligning Vekslende serier Cauchy kondens Dirichlet Abel
Vector Gradient Divergens Krølle Laplacian Retningsavledet Identiteter Setninger Gradient Green's Stokes ' Divergens generaliserte Stokes
Multivariabel Formalismer Matrise Tensor Ytre Geometrisk Definisjoner Delvis avledet Flere integraler Linjeintegral Overflate integrert Volum integrert Jacobian Hessian
Spesialist Brøk Malliavin Stokastisk Variasjoner
Diverse Precalculus Historie Ordliste Liste over emner Integrasjon Bee Analyse
v t e

I symbolsk beregning er Risch-algoritmen en metode for ubestemt integrasjon som brukes i noen datamaskinalgebra-systemer for å finne antiderivativer . Den er oppkalt etter den amerikanske matematikeren Robert Henry Risch , en spesialist innen datamaskinalgebra som utviklet den i 1968.

Den algoritmen forvandler problemet med integrering inn i et problem i algebra . Den er basert på formen for funksjonen som integreres og på metoder for å integrere rasjonelle funksjoner , radikaler , logaritmer og eksponensielle funksjoner . Risch kalte det en beslutningsprosedyre , fordi det er en metode for å avgjøre om en funksjon har en elementær funksjon som en ubestemt integral, og hvis den gjør det, for å bestemme den ubestemte integralen.

Den komplette beskrivelsen av Risch-algoritmen tar over 100 sider. Den Risch-Norman algoritmen er en enklere, raskere, men mindre kraftig variant som ble utviklet i 1976 av Arthur Norman .

Beskrivelse

Risch-algoritmen brukes til å integrere elementære funksjoner . Dette er funksjoner oppnådd ved å komponere eksponensialer, logaritmer, radikaler, trigonometriske funksjoner og de fire aritmetiske operasjonene ( + - × ÷ ). Laplace løste dette problemet i tilfelle rasjonelle funksjoner , da han viste at den ubestemte integralen til en rasjonell funksjon er en rasjonell funksjon og et endelig antall konstante multipler av logaritmer av rasjonelle funksjoner. Algoritmen foreslått av Laplace er vanligvis beskrevet i kalkulære lærebøker; som et dataprogram, ble det endelig implementert på 1960-tallet.

Liouville formulerte problemet som løses av Risch-algoritmen. Liouville beviste med analytiske midler at hvis det er en elementær løsning g til ligningen g ′ = f , eksisterer det konstanter α _i og fungerer u _i og v i feltet generert av f slik at løsningen er av formen

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

Risch utviklet en metode som gjør det mulig å bare vurdere et endelig sett med funksjoner i Liouvilles form.

Intuisjonen for Risch-algoritmen kommer fra oppførselen til de eksponensielle og logaritmefunksjonene under differensiering. For funksjonen f e ^g , der f og g er differensierbare funksjoner , har vi

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

så hvis e ^g var i resultatet av en ubestemt integrasjon, bør det forventes å være inne i integral. Også, som

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

så hvis (ln g ) ⁿ var resultatet av en integrasjon, så ville bare noen få krefter i logaritmen forventes.

Problemeksempler

Å finne et elementært antiderivativ er veldig følsomt for detaljer. For eksempel har følgende algebraiske funksjon en elementær antiderivativ:

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

nemlig:

${\ displaystyle F (x) = - {\ tfrac {1} {8}} \ ln \ left (\ left (x ^ {6} + 15x ^ {4} -80x ^ {3} + 27x ^ {2} -528x + 781 \ høyre) {\ sqrt {x ^ {4} + 10x ^ {2} -96x-71}} - \ left (x ^ {8} + 20x ^ {6} -128x ^ {5} + 54x ^ {4} -1408x ^ {3} + 3124x ^ {2} +10001 \ høyre) \ høyre) + C.}$

Men hvis det konstante begrepet 71 endres til 72, er det ikke mulig å representere det antiderivative når det gjelder elementære funksjoner. Noen datamaskinalgebra-systemer kan her returnere et antiderivativ når det gjelder ikke-elementære funksjoner (dvs. elliptiske integraler ), som ligger utenfor omfanget av Risch-algoritmen.

Følgende er et mer komplekst eksempel som involverer både algebraiske og transcendentale funksjoner:

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

Faktisk har antiderivativet til denne funksjonen en ganske kort form:

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

Gjennomføring

Å transformere Rischs teoretiske algoritme til en algoritme som effektivt kan utføres av en datamaskin var en kompleks oppgave som tok lang tid.

Tilfellet med de rent transcendentale funksjonene (som ikke involverer røtter av polynomer) er relativt enkelt og ble implementert tidlig i de fleste datamaskinalgebra-systemer . Den første implementeringen ble gjort av Joel Moses i Macsyma kort tid etter publisering av Rischs avis.

Saken om rent algebraiske funksjoner ble løst og implementert i Reduser av James H. Davenport .

Den generelle saken ble løst og implementert i Scratchpad, en forløper for Axiom , av Manuel Bronstein.

Avgjørbarhet

Risch-algoritmen som brukes på generelle grunnleggende funksjoner, er ikke en algoritme, men en semi-algoritme fordi den, som en del av driften, må kontrollere om visse uttrykk tilsvarer null ( konstant problem ), spesielt i det konstante feltet. For uttrykk som bare involverer funksjoner som ofte blir betegnet som elementære , er det ikke kjent om en algoritme som utfører en slik sjekk eksisterer eller ikke (nåværende datamaskinalgebrasystemer bruker heuristikk); dessuten, hvis man legger til absoluttverdifunksjonen til listen over elementære funksjoner, er det kjent at ingen slik algoritme eksisterer; se Richardsons setning .

Merk at dette problemet også oppstår i algoritmen for polynomavdeling ; denne algoritmen vil mislykkes hvis den ikke kan bestemme riktig om koeffisientene forsvinner identisk. Nesten alle ikke-trivielle algoritmer knyttet til polynomer bruker polynomial divisjonsalgoritme, inkludert Risch-algoritmen. Hvis det konstante feltet kan beregnes , dvs. for elementer som ikke er avhengige av x , kan problemet med nullekvivalens avgjøres, så er Risch-algoritmen en komplett algoritme. Eksempler på beregnbare konstante felt er henholdsvis Q og Q ( y ) , dvs. rasjonelle tall og rasjonelle funksjoner i y med rasjonelle tallkoeffisienter, der y er en ubestemt som ikke er avhengig av x .

Dette er også et problem i den Gaussiske eliminasjonsmatrisealgoritmen (eller en hvilken som helst algoritme som kan beregne nullrommet til en matrise), noe som også er nødvendig for mange deler av Risch-algoritmen. Eliminering av Gauss vil gi feil resultater hvis den ikke kan avgjøre riktig om en pivot er identisk null.

Se også

• Symbolsk integrasjon
• Liouvilles teorem (differensial algebra)
• Axiom (datamaskinalgebrasystem)
• Ufullstendig gammafunksjon
• Ikke-elementær integral
• Lister over integraler

Merknader

Referanser

• Bronstein, Manuel (1990). "Integrering av elementære funksjoner" . Journal of Symbolic Computation . 9 (2): 117–173. doi : 10.1016 / s0747-7171 (08) 80027-2 .

• Bronstein, Manuel (1998). "Tutorial for symbolsk integrering" (PDF) . Sitatjournal krever |journal=( hjelp )

• Bronstein, Manuel (2005). Symbolsk Integrasjon jeg . Springer. ISBN 3-540-21493-3.

• Davenport, James H. (1981). Om integrering av algebraiske funksjoner . Forelesningsnotater i informatikk . 102 . Springer. ISBN 978-3-540-10290-8.

• Geddes, Keith O .; Czapor, Stephen R .; Labahn, George (1992). Algoritmer for datamaskinalgebra . Boston, MA: Kluwer Academic Publishers. s. xxii + 585. Bibcode : 1992afca.book ..... G . doi : 10.1007 / b102438 . ISBN 0-7923-9259-0.

• Moses, Joel (2012). "Macsyma: En personlig historie" . Journal of Symbolic Computation . 47 (2): 123–130. doi : 10.1016 / j.jsc.2010.08.018 .

• Risch, RH (1969). "Problemet med integrering i endelige termer" . Transaksjoner fra American Mathematical Society . American Mathematical Society. 139 : 167–189. doi : 10.2307 / 1995313 . JSTOR  1995313 .

• Risch, RH (1970). "Løsningen på problemet med integrering i endelige termer" . Bulletin of the American Mathematical Society . 76 (3): 605–608. doi : 10.1090 / S0002-9904-1970-12454-5 .

• Rosenlicht, Maxwell (1972). "Integrering i endelige termer". Amerikansk matematisk månedlig . Mathematical Association of America. 79 (9): 963–972. doi : 10.2307 / 2318066 . JSTOR  2318066 .

Eksterne linker

• Bhatt, Bhuvanesh. "Risch Algorithm" . MathWorld .