Մասնակից:Ashkhen Khachatryan/Risch algorithm

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

Նկարագրություն խմբագրել

Ռիսքի ալգորիթմը օգտագործվում է պարզ ֆունկցիաներն ինտեգրելու համար: Այս ֆունկցիաները ձեռք բերելու ճանապարհով օրինակներ են ՝ ալոգարիթմներ , եռանկյունաչափական գործառույթների եւ չորս թվաբանություն գործառնությունների(+ − × ÷): Պիեր -Սիմոն Լապլասը լուծել այս խնդիրը ռացիոնալ գործառույթներիհամար , և ցույց տվեց անորոշ անբաժանելի մի ռացիոնալ ֆունկցիա և վերջավոր թվով մշտական կրճատ լոգարիթմներ ռացիոնալ ֆունկցիաներով : Լապլասի կողմից առաջարկված ալգորիթմը սովորաբար նկարագրված է առավելությունների տեսանկյունից, ինչպես օրինակ համակարգչային ծրագիրը, որը վերջնական իրականացվել է 1960 թվականին:

Լուվիլիան անալոգիական ճանապարհով ապացուցեցոր,որ եթե կա հավասարման տարրական լուծում g′ = f ,ապա անընդհատ α եւ տարրական գործառույթները ui և v ունեն լուծուման իրենց ձեւերը :

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

Ռիսքը մշակել է մեթոդ,որը թույլ է տալիս տեսնել միայն վերջին շարքը տարրական գործառույթների վերաբերյա Լուվիլիայի ֆորմայի ֆունկցիայով : Ռիսքի ալգորիթմի համար ինտուիցիան առաջանում է վարքագծից և լոգարիթմի ֆունկցիաների տարբերակման համաձայն : f e^g ֆունկցիայում , որտեղ f և g համարվում են տարբերակման ֆունկցիաներ, ունենք ՝

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

այնպես որ , եթե e^gեղել են անորոշ ինտեգրման պատճառ, ապա ակնկալվում է, որ նրանք ինտեգրալի նշանի տակ են :Բացի այդ, ինչպես

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

Այսպիսով ,եթե (ln g)ⁿինտեգրալի մեջ էր ,ապա մի քանի լիազորությունները լոգարիթմ սպասելի են :

Խնդրի օրինակներ խմբագրել

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

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-ի, հնարավոր չէ ինտեգրալը ներկայացնել տարրական գործառույթների միջոցով:

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

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.

Իրագործումը խմբագրել

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

Զուտ տրանսցենդենտալ գոռծառույթների (որոնք կապված չեն արմատների բազմանդամների հետ ) համեմատաբար պարզ է և իրականացվում էր Համակարգչային համակարգերի հանրահաշիվներում : Առաջին կատարումը եղել է Ջոել Մոսեսի կօղմից Մասիմայումայն բանից հետո. երբ Ռիսքի հոդվածը տպագրվեց.^[2]

Զուտ հանրահաշվական գործառույթներ լուծել և իրականարել է Խամես Հ. Դեվեպորտը (James H. Davenport).^[3]^[4]

Ընդհանուր տարբերակում որոշված էր եւ իրականացվել էր նոթատետրում ԱկսիոմովՄանուել Բրոնստեյնի կողմից : .^[5]

Որոշումը խմբագրել

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

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

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

Տես նաև խմբագրել

Հղումներ խմբագրել

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.

Նշումներ խմբագրել

↑ This example comes from Manuel Bronstein's "Symbolic Integration Tutorial". See the references.
↑ Joel Moses (2012), «Macsyma: A personal history», Journal of Symbolic Computation, 47: 123–130, doi:10.1016/j.jsc.2010.08.018
↑ Not to be confused with his father Harold Davenport
↑ James H. Davenport (1981). On the integration of algebraic functions. Lecture notes in computer science. Vol. 102. Springer. ISBN 0-387-10290-6, 3-540-10290-6. {{cite book}}: Check |isbn= value: invalid character (օգնություն)
↑ Manuel Bronstein (1990), «Integration of elementary functions», Journal of Symbolic Computation, 9 (2): 117–173
↑ «Mathematica 7 Documentation: PolynomialQuotient». Section: Possible Issues. Վերցված է 17 July 2010-ին.

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

[1] This example comes from Manuel Bronstein's "Symbolic Integration Tutorial". See the references.

[2] Joel Moses (2012), «Macsyma: A personal history», Journal of Symbolic Computation, 47: 123–130, doi:10.1016/j.jsc.2010.08.018

[3] Not to be confused with his father Harold Davenport

[4] James H. Davenport (1981). On the integration of algebraic functions. Lecture notes in computer science. Vol. 102. Springer. ISBN 0-387-10290-6, 3-540-10290-6. {{cite book}}: Check |isbn= value: invalid character (օգնություն)

[5] Manuel Bronstein (1990), «Integration of elementary functions», Journal of Symbolic Computation, 9 (2): 117–173

[6] «Mathematica 7 Documentation: PolynomialQuotient». Section: Possible Issues. Վերցված է 17 July 2010-ին.

[1]

[2]

[3]

[4]

[5]

[6]