Մասնակից:Ashkhen Khachatryan/Սևագրություն

Risch-ի ալգորիթմը իր անվանումը ստացել է Ռոբերտ Հենրի Ռիսքի անունից: Ռիսքի ալգորիթմը նախատեսված է անորոշ ինտեգրման հաշվարկի համար: Այս ալգորիթմը ինտեգրման խնդիրը վերածում է հանրահաշվական խնդրի: Այն հիմնված է ինտեգրված ֆունկցիայի ձևի և ռացիոնալ ֆունկցիաների, արմատական, լոգարիթմական և էքսպոնենտալ ֆունկցիաների ինտեգրման մեթոդների վրա: Ռիսքը, ով ալգորիթմը մշակել է 1968 թվականին, այն անվանել է որոշման գործընթաց, քանի որ այդ մեթոդը որոշում է, թե արդյոք ֆունկցիան անորոշ ինտեգրալ է, ինչպես նաև եթե այն կատարվում է, դրա որոշման գործընթացը: Ռիսքի ալգորիթմը(ավելի քան 100 էջ) ամփոփված է Համակարգչային հանրահաշվի ալգորիթմներ-ում: Ռիսք-Նորմանի ալգորիթմը մշակվել է 1976 թվականին, այն ավելի արագ է, բայց ունի ավելի քիչ տեխնիկական հզորություն:

Նկարագրություն

Ռիսքի ալգորիթմը օգտագործվում է պարզ ֆունկցիաներն ինտեգրելու համար: These are functions obtained by composing exponentials, logarithms, radicals, trigonometric functions, and the four arithmetic operations (+ − × ÷). Laplace solved this problem for the case of rational functions, as he showed that the indefinite integral of a rational function is a rational function and a finite number of constant multiples of logarithms of rational functions. Լապլասի կողմից առաջարկված ալգորիթմը սովորաբար նկարագրված է առավելությունների տեսանկյունից, ինչպես օրինակ համակարգչային ծրագիրը, որը վերջնական իրականացվել է 1960 թվականին:

Liouville formulated the problem solved by the Risch algorithm. Liouville proved by analytical means that if there is an elementary solution g to the equation g′ = f then for constants α_i and elementary functions u_i and v the solution is of the form

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

Risch developed a method that allows one to only consider a finite set of elementary functions of Liouville's form.

The intuition for the Risch algorithm comes from the behavior of the exponential and logarithm functions under differentiation. For the function f e^g, where f and g are differentiable functions, we have

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

so if e^g were in the result of an indefinite integration, it should be expected to be inside the integral. Also, as

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

then if (ln g)ⁿ were in the result of an integration, then only a few powers of the logarithm should be expected.

Խնդրի օրինակներ

Տարրական ինտեգրալի գտնելը զգայուն է մանրամասնությունների նկատմամբ: Օրինակ` հետևյալ ֆունկցիան ունի պարզ ինտեգրալ.

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

այն է`

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

(Որոշ համակարգչային հանրահաշվի համակարգեր կարող են վերադարձնել ոչ պարզ ֆունկցիայի ինտեգրված տեսքը (էլիպսաձև ինտեգրալ), ինչը, այնուամենայնիվ, դուրս է Ռիսքի ալգորիթմի շրջանակներից:) Բայց եթե 71-ը փոխվում է 72-ի, հնարավոր չէ ինտեգրալը ներկայացնել տարրական գործառույթների միջոցով:

Հետևյալ ֆունկցիան ավելի բարդ օրինակ է:

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

Փաստորեն այս ֆունկցիայի ինտեգրալը ունի բավականին կարճ ձև:

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

Իրագործումը

Ռիսքի ալգորիթմի ձևափոխությունը մի ալգորիթմի, որը կարող է արդյունավետ կատարվել համակարգչի կողմից հանդիսանում է բարդ աշխատանք, որը խատ ժամանակ է խլում:

The case of the purely transcendental functions (which do not involve roots of polynomials) is relatively easy and has been implemented early in most computer algebra systems. Առաջին կատարումը եղել է Ջոել Մոսեսի կօղմից Մասիմայումայն բանից հետո. երբ Ռիսքի հոդվածը տպագրվեց.

The case of purely algebraic functions has been solved and implemented in Reduce by James H. Davenport.

The general case has been solved and implemented in Scratchpad, a precursor of Axiom, by Manuel Bronstein.

Որոշումը

Risch ալգորիթմը օգտագործվում է տարրական ֆունկցիաների համար ալգորիթմ չի համարվում ,այլ կիսաալգորիթմ, քանի որ այն պետք է ստուգի իր աշխատանքի կեսը, եթե որոշ արտահայտություններ, որոնք համարժեք են զրոյի (մշտական ​​խնդիր),մասնավորապես մշտական ​​դաշտում : Արտահայտման համար , որոնք ընդգրկում են միայն հիմնական գործառույթներն սովորաբար համարվում են տարրականարդյոք նման ալգորիթմը կստուգվի թե ոչ (ներկայիս համակարգչային ալգորիթմի սիստեմներ օգտագործված heuristics ); եւ եթե ավելացնել գործառույթի ցուցակում բացարձակ արժեքը հայտնի է, որ նման ալգորիթմ գոյություն ունի, Տես Richardson's տեորիայում:

Նշեք, որ այս հարցը առաջանում է polynomial division algorithm; այս ալգորիթմի չի կարող ճիշտ որոշել ,թե արդյոք դա կսխալվի ,եթե գործակիցները հավասարվեն զրոյին :. Գրեթե ամեն ոչ սովորական ալգորիթմը կապված է polynomial-ի հետ ներառված Risch ալգորիթմում : Եթե ​​անընդհատ դաշտը համարվում է հաշվելի, այսինքն, կախված չէ x էլեմենտից , իսկ զրոյական համարժեքության խնդիրը լուծելի է ,ապա Risch ալգորիթմը համարվում է համարշեք : Անընդհատ դաշտի օրինակները և հաշվողականի $\mathbb {Q}$ and $\mathbb {Q} (y)$, այսինքն ռացիոնալ համարների եւ ռացիոնալ գործառույթների մեջև ,որտեղ y-ը համարվում է ռացիոնալ գործակից ,որը կախված չէ x-ից:

Այն նաեւ Gaussian մատրիցի թողարկում է (ալգորիթմ կամ այնպիսի ալգորիթմ ,որը կարելի է հաշվարկել nullspace մատրիցով), որը նույնպես անհրաժեշտ է Risch ալգորիթմի շատ մասերում  : Gauss-ը կտա սխալ արդյունք, եթե այն չի կարող ճիշտ որոշել արդյոք առանցքային նույնությունը հավասար է զրո : ).

Տես նաև

• Lists of integrals
• Liouville's theorem (differential algebra)
• Symbolic integration
• Axiom (computer algebra system)
• Incomplete Gamma function

Հղումներ

• R. H. Risch (1969). «The problem of integration in finite terms». Transactions of the American Mathematical Society. American Mathematical Society. 139: 167–189. doi:10.2307/1995313. JSTOR 1995313.
• R. H. Risch (1970). «The solution of the problem of integration in finite terms». Bulletin of the American Mathematical Society. 76 (3): 605–608. doi:10.1090/S0002-9904-1970-12454-5.
• Maxwell Rosenlicht (1972). «Integration in finite terms». American Mathematical Monthly. Mathematical Association of America. 79 (9): 963–972. doi:10.2307/2318066. JSTOR 2318066.
• Geddes, Czapor, Labahn (1992). Algorithms for Computer Algebra. Kluwer Academic Publishers. ISBN 0-7923-9259-0.{{cite book}}: CS1 սպաս․ բազմաթիվ անուններ: authors list (link)
• Manuel Bronstein (2005). Symbolic Integration I. Springer. ISBN 3-540-21493-3.
• Manuel Bronstein «Symbolic Integration Tutorial»։
• Bhatt, Bhuvanesh, "Risch Algorithm", MathWorld.

Նշումներ

Category:Integral calculus Category:Differential algebra Category:Computer algebra hy:Risch-ի ալգորիթմ