Кіріспе
Белгісіз интегралдарды бағалау әдісі
Символдық есептеуде Риш алгоритмі – кейбір компьютерлік алгебра жүйелерінде антитуындыларды табу үшін қолданылатын белгісіз интеграциялау әдісі. Бұл алгоритм 1968 жылы компьютерлік алгебра саласындағы маман, американдық математик Роберт Генри Риштің есімімен аталған. Алгоритм интеграциялау мәселесін алгебрадағы мәселеге түрлендіреді. Ол интеграцияланатын функцияның түріне және рационалды функцияларды, радикалдарды, логарифмдерді және экспоненциалдық функцияларды интеграциялау әдістеріне негізделген. Риш оны шешім қабылдау процедурасы деп атады, себебі ол функцияның элементар функция түрінде белгісіз интегралы бар-жоғын анықтау әдісі және егер бар болса, сол белгісіз интегралды табуға мүмкіндік береді. Дегенмен, алгоритм әрқашан берілген функцияның антитуындысын элементар функциялар арқылы өрнектеуге болатынын анықтай бермейді. Риш алгоритмінің толық сипаттамасы 100 беттен астам. Риш-Норман алгоритмі – Артур Норманның 1976 жылы әзірлеген, қарапайым, жылдам, бірақ тиімділігі төмен нұсқасы. Брайан Л. Миллер аралас трансценденттік алгебралық интегралдың логарифмдік бөлігін есептеуде маңызды прогресс жасады.
Сипаттама
Риш алгоритмі элементар функцияларды интеграциялау үшін қолданылады. Бұл функциялар экспоненталар, логарифмдер, радикалдар, тригонометриялық функциялар және төрт арифметикалық амал (+ - × ÷) арқылы құрастырылады. Лаплас рационал функциялар жағдайында осы мәселені шешті, себебі ол рационал функцияның белгісіз интегралы рационал функция және рационал функциялардың логарифмдерінің шекті саны тұрақты еселіктері екенін көрсетті. Лаплас ұсынған алгоритм әдетте математикалық анализ оқулықтарында сипатталады; компьютерлік бағдарлама ретінде ол 1960 жылдары іске асырылды. Лиувилл Риш алгоритмімен шешілетін мәселені формулировкалады. Лиувилл аналитикалық жолмен 1=g′ = f теңдеуіне элементар шешім g болса, онда f өрісінде туындаған ui және v функцияларымен бірге αi тұрақтылары бар екенін дәлелдеді. Риш Лиувилл түріндегі функциялардың шекті жиынтығын қарастыруға мүмкіндік беретін әдіс әзірледі. Риш алгоритмінің түйсігі дифференциалдаудағы экспоненциалдық және логарифмдік функциялардың мінез-құлқынан туындайды. f e^(g) функциясы үшін, мұнда f және g дифференциалданатын функциялар, егер e^(g) белгісіз интегралдың нәтижесінде болса, онда оның интегралдың ішінде болуы күтіледі. Сондай-ақ, егер (ln g)^(n) интеграцияның нәтижесінде болса, онда логарифмнің тек бірнеше дәрежесі ғана күтіледі.
Risch developed a method that allows one to consider only a finite set of 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
so if e^(g) were in the result of an indefinite integration, it should be expected to be inside the integral. Also, as
then if (ln g)^(n) were in the result of an integration, then only a few powers of the logarithm should be expected.
Іске асыру
Риштың теориялық алгоритмін компьютерде тиімді орындалатын алгоритмге түрлендіру – ұзақ уақытқа созылған күрделі міндет болды. Полином түбірлерін қамтымайтын таза трансценденттік функциялар жағдайы салыстырмалы түрде оңай болды және көптеген компьютерлік алгебра жүйелерінде ерте орындалды. Бірінші іске асыруды Джоэл Мозес Риштің мақаласы жарияланғаннан кейін көп ұзамай Macsyma жүйесінде жасады. Таза алгебралық функциялар жағдайын Джеймс Х. Давенпорт Reduce жүйесінде шешіп, іске қосты, бірақ қарапайымдылық үшін ол тек квадрат түбірлермен және қайталама квадрат түбірлермен ғана жұмыс істей алды, жалпы радикалдармен немесе айнымалылар арасындағы квадраттық емес алгебралық қатынастармен емес. Жалпы жағдайды Мануэль Бронштейн Axiom-ның алдын бағышқысы Scratchpad-те шешіп, дерлік толыққанды іске қосты, ал қазір Axiom-ның FriCAS тармағында дамытылуда. Дегенмен, іске асыруда кейбір ерекше жағдайларға арналған тармақтар толыққанды қамтылмады. Қазіргі таңда Риш алгоритмінің толыққанды іске асырылғаны белгілі емес.
Шешімділік
Жалпы элементарлық функцияларға қолданылатын Риш алгоритмі – алгоритм емес, жартылай алгоритм, себебі ол өзінің жұмыс істеуінің бір бөлігі ретінде, белгілі бір өрнектердің нөлге теңдігін тексеруі керек (тұрақты мәселе), әсіресе тұрақты өрісте. Әдетте элементар деп есептелетін функцияларды ғана қамтитын өрнектер үшін, мұндай тексеруді жүзеге асыратын алгоритмнің бар-жоғы белгісіз (қазіргі компьютерлік алгебра жүйелері эвристика қолданады); сондай-ақ, егер абсолют мән функциясы элементар функциялар тізіміне қосылса, онда мұндай алгоритмнің жоқ екені белгілі; Ричардсон теоремасын қараңыз. Бұл мәселе полиномдық бөлу алгоритмінде де туындайды; егер ол коэффициенттердің толыққанды жоғалып кеткенін дұрыс анықтамаса, алгоритм сәтсіз аяқталады. Полиномдармен байланысты барлық маңызды алгоритмдер полиномдық бөлу алгоритмін қолданады, оның ішінде Риш алгоритмі де бар. Егер тұрақты өріс есептеуге болатын болса, яғни x-ке тәуелді емес элементтер үшін нөлдік теңдестік мәселесі шешілсе, онда Риш алгоритмі толыққанды алгоритм болып табылады. Есептелетін тұрақты өрістердің мысалдары – «Q» және «Q(y)», яғни рационал сандар және y айнымалысы бойынша рационал функциялар, олардың коэффициенттері рационал сандардан тұрады, мұнда y – x-ке тәуелді емес белгісіз шама. Бұл мәселе Гаусс жою матрицалық алгоритмінде (немесе матрицаның ядросын есептей алатын кез келген алгоритмде) де кездеседі, ол Риш алгоритмінің көптеген бөліктері үшін қажет. Гаусс жоюы, егер ол бағыттық элементтің толыққанды нөлге тең екенін дұрыс анықтамаса, дұрыс емес нәтижелер береді.