रिस्च एल्गोरिदम

प्रतीकात्मक गणना में, रिस्क एल्गोरिदम अनिश्चितकालीन एकीकरण की विधि है जिसका उपयोग कुछ कंप्यूटर बीजगणित प्रणालियों में प्रतिव्युत्पन्न खोजने के लिए किया जाता है। इसका नाम अमेरिकी गणितज्ञ रॉबर्ट हेनरी रिस्क के नाम पर रखा गया है, जो कंप्यूटर बीजगणित के विशेषज्ञ थे, जिन्होंने इसे 1968 में विकसित किया था।

एल्गोरिथ्म एकीकरण (कैलकुलस) की समस्या को विभेदक बीजगणित में समस्या में बदल देता है। यह एकीकृत किए जा रहे फलन के रूप और तर्कसंगत कार्य, Nth मूलो, लघुगणक और घातांकीय कार्यों को एकीकृत करने के विधियों पर आधारित है। रिश ने इसे निर्णय प्रक्रिया कहा था, क्योंकि यह यह तय करने की विधि है कि क्या किसी फलन में अनिश्चितकालीन अभिन्न अंग के रूप में प्राथमिक कार्य है, और यदि ऐसा है, तो उस अनिश्चित अभिन्न को निर्धारित करने के लिए चूँकि, एल्गोरिथ्म सदैव यह पहचानने में सफल नहीं होता है कि किसी दिए गए फलन का एंटीडेरिवेटिव वास्तव में प्राथमिक कार्यों के संदर्भ में व्यक्त किया जा सकता है या नहीं किया जा सकता है।

रिस्क एल्गोरिथम का पूरा विवरण 100 से अधिक पृष्ठों का है। रिस्क-नॉर्मन एल्गोरिदम सरल, तेज़, किन्तु कम शक्तिशाली संस्करण है जिसे 1976 में आर्थर नॉर्मन (कंप्यूटर वैज्ञानिक) द्वारा विकसित किया गया था।

ब्रायन एल. मिलर द्वारा मिश्रित ट्रान्सेंडैंटल-बीजगणितीय इंटीग्रल के लघुगणकीय भाग की गणना में कुछ महत्वपूर्ण प्रगति हुई है।

विवरण

प्राथमिक कार्यों को एकीकृत करने के लिए रिस्क एल्गोरिदम का उपयोग किया जाता है। ये घातांक, लघुगणक, रेडिकल, त्रिकोणमितीय फलन और चार अंकगणितीय संचालन (+ − × ÷) की रचना करके प्राप्त किए गए फलन हैं. पियरे-साइमन लाप्लास ने तर्कसंगत कार्य के स्थिति में इस समस्या को हल किया था, क्योंकि उन्होंने दिखाया कि तर्कसंगत फलन का अनिश्चित अभिन्न अंग तर्कसंगत कार्य है और तर्कसंगत कार्यों के लघुगणक के निरंतर गुणकों की सीमित संख्या है . लाप्लास द्वारा सुझाया गया एल्गोरिदम सामान्यतः कैलकुलस पाठ्यपुस्तकों में वर्णित है; कंप्यूटर प्रोग्राम के रूप में, इसे अंततः 1960 के दशक में प्रयुक्त किया गया था।

जोसेफ लिउविल ने उस समस्या को तैयार किया जिसे रिस्क एल्गोरिथम द्वारा हल किया गया है। लिउविले ने विश्लेषणात्मक माध्यमों से सिद्ध किया कि यदि समीकरण g′ = f का कोई प्रारंभिक समाधान g है तो f द्वारा उत्पन्न क्षेत्र में स्थिरांक α_i और फलन u_i और v उपस्थित हैं, जिससे समाधान इस प्रकार हो

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

रिस्क ने ऐसी विधि विकसित की जो किसी को लिउविल के रूप के कार्यों के केवल सीमित समुच्चय पर विचार करने की अनुमति देती है।

रिस्क एल्गोरिथ्म के लिए अंतर्ज्ञान विभेदन के अनुसार घातीय और लघुगणक कार्यों के व्यवहार से आता है। फलन f e^g के लिए, उदाहरण के लिए जहां f और g अवकलनीय फलन हैं, हमारे पास है

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

तो यदि e^g अनिश्चितकालीन एकीकरण के परिणाम में थे, यह अभिन्न के अंदर होने की उम्मीद की जानी चाहिए। इसके अतिरिक्त

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

तो यदि (ln g)ⁿ एकीकरण के परिणाम में थे, तो लघुगणक की केवल कुछ घातो की अपेक्षा की जानी चाहिए।

समस्या उदाहरण

प्राथमिक प्रतिअवकलन खोजना विवरण के प्रति बहुत संवेदनशील है। उदाहरण के लिए, निम्नलिखित बीजगणितीय फलन (1993 में हेनरी कोहेन (संख्या सिद्धांतकार) द्वारा विज्ञान, गणित, प्रतीकात्मक पर पोस्ट किया गया)) में प्रारंभिक प्रतिअवकलन है, जैसा कि संस्करण 13 से वोल्फ्राम मैथमैटिका दिखाता है (चूँकि, मैथमैटिका इस अभिन्न अंग की गणना करने के लिए रिस्क एल्गोरिदम का उपयोग नहीं करता है):

$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}}\left(x+{\sqrt {x+\ln x}}\right)}}.$

वास्तव में, इस फलन के प्रतिअवकलन का अधिक संक्षिप्त रूप है जिसे प्रतिस्थापन $u=x+{\sqrt {x+\ln x}}$ का उपयोग करके पाया जा सकता है (सिम्पी इसे हल कर सकता है जबकि फ़्रीसीएएस रिस्क एल्गोरिदम में कार्यान्वयन अपूर्ण (निरंतर अवशेष) त्रुटि के साथ विफल रहता है):

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

कुछ डेवनपोर्ट प्रमेय अभी भी स्पष्ट किया जा रहा है। उदाहरण के लिए 2020 में ऐसे प्रमेय का प्रतिउदाहरण पाया गया, जहां यह पता चलता है कि प्राथमिक प्रतिअवकलन अन्ततः उपस्थित है।

कार्यान्वयन

रिस्क के सैद्धांतिक एल्गोरिदम को ऐसे एल्गोरिदम में बदलना जिसे कंप्यूटर द्वारा प्रभावी विधि से निष्पादित किया जा सकता है, सम्मिश्र कार्य था जिसमें अधिक समय लगा था।

विशुद्ध रूप से पारलौकिक कार्यों (जिसमें बहुपदों की मूल सम्मिलित नहीं हैं) का स्थिति अपेक्षाकृत सरल है और इसे अधिकांश कंप्यूटर बीजगणित प्रणालियों में जल्दी ही प्रयुक्त किया गया था। पहला कार्यान्वयन जोएल मूसा द्वारा रिस्क के पेपर के प्रकाशन के तुरंत बाद मैकसिमा में किया गया था।

विशुद्ध रूप से बीजगणितीय कार्यों के स्थिति को जेम्स एच. डेवनपोर्ट द्वारा रिड्यूस (कंप्यूटर बीजगणित प्रणाली) में हल और कार्यान्वित किया गया था, चूँकि सादगी के लिए यह केवल वर्गमूलों और दोहराए गए वर्गमूलों से निपट सकता था, न कि सामान्य रेडिकल अभिव्यक्ति या चर के बीच अन्य गैर-द्विघात बीजीय समीकरण से सामान्य स्थिति हल किया गया था और मैनुअल ब्रोंस्टीन द्वारा एक्सिओम (कंप्यूटर बीजगणित प्रणाली) के अग्रदूत स्क्रैचपैड में लगभग पूरी तरह से कार्यान्वित किया गया था, और अब इसे एक्सिओम के फोर्क, फ़्रीसीएएस में विकसित किया जा रहा है। चूँकि, कार्यान्वयन में विशेष स्थितियों के लिए कुछ शाखाओं को पूरी तरह से सम्मिलित नहीं किया गया था। वर्तमान में, रिस्क एल्गोरिथम का कोई ज्ञात पूर्ण कार्यान्वयन नहीं है।

निर्णायकता

सामान्य प्रारंभिक कार्यों पर प्रयुक्त रिस्क एल्गोरिदम एल्गोरिदम नहीं है किन्तु आरई (सम्मिश्रता) या अर्ध-एल्गोरिदम है क्योंकि इसे अपने संचालन के भाग के रूप में जांचने की आवश्यकता है, यदि कुछ अभिव्यक्तियां शून्य (निरंतर समस्या) के समान हैं, विशेष रूप से स्थिर क्षेत्र में उन अभिव्यक्तियों के लिए जिनमें केवल प्राथमिक कार्य माने जाने वाले कार्य सम्मिलित हैं, यह ज्ञात नहीं है कि ऐसी जाँच करने वाला एल्गोरिदम उपस्थित है या नहीं (वर्तमान कंप्यूटर बीजगणित प्रणालियाँ अनुमान का उपयोग करती हैं); इसके अतिरिक्त, यदि कोई प्राथमिक कार्यों की सूची में पूर्ण मान जोड़ता है, तो यह ज्ञात होता है कि ऐसा कोई एल्गोरिदम उपस्थित नहीं है; रिचर्डसन का प्रमेय देखें।

ध्यान दें कि यह समस्या बहुपद विभाजन एल्गोरिथ्म में भी उत्पन्न होती है; यह एल्गोरिदम विफल हो जाएगा यदि यह सही विधि से निर्धारित नहीं कर सकता है कि गुणांक समान रूप से विलुप्त हो जाते हैं या नहीं होते है। वस्तुतः बहुपदों से संबंधित प्रत्येक गैर-सामान्य एल्गोरिदम बहुपद विभाजन एल्गोरिदम का उपयोग करता है, जिसमें रिस्क एल्गोरिदम भी सम्मिलित है। यदि स्थिर क्षेत्र गणना योग्य है, अर्थात, x पर निर्भर नहीं होने वाले तत्वों के लिए, शून्य-समतुल्यता की समस्या निर्णय योग्य है, तो रिस्क एल्गोरिदम एक पूर्ण एल्गोरिदम है। गणना योग्य स्थिर क्षेत्र के उदाहरण Q और Q(y) हैं, अर्थात, क्रमशः तर्कसंगत संख्या गुणांक के साथ y में तर्कसंगत संख्याएं और तर्कसंगत कार्य, जहां y एक अनिश्चित है जो x पर निर्भर नहीं करता है।

यह गाउस विलोपन आव्यूह एल्गोरिदम (या कोई भी एल्गोरिदम जो आव्यूह के नलस्पेस की गणना कर सकता है) में भी उद्देश्य है, जो रिस्क एल्गोरिदम के कई भागो के लिए भी आवश्यक है। गाऊसी उन्मूलन गलत परिणाम देगा यदि यह सही विधि से निर्धारित नहीं कर सकता है कि धुरी समान रूप से शून्य है या नहीं है.

यह भी देखें

• एक्सिओम (कंप्यूटर बीजगणित प्रणाली)
• संवृत-रूप अभिव्यक्ति
• अपूर्ण गामा फलन
• एकीकरण की सूची
• लिउविले का प्रमेय (विभेदक बीजगणित)
• अप्राथमिक एकीकरण
• प्रतीकात्मक एकीकरण

संदर्भ

• Bronstein, Manuel (1990). "Integration of elementary functions". Journal of Symbolic Computation. 9 (2): 117–173. doi:10.1016/s0747-7171(08)80027-2.

• Bronstein, Manuel (1998). "Symbolic Integration Tutorial" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

• Bronstein, Manuel (2005). Symbolic Integration I. Springer. ISBN 3-540-21493-3.

• Davenport, James H. (1981). On the integration of algebraic functions. Lecture Notes in Computer Science. Vol. 102. Springer. ISBN 978-3-540-10290-8.

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

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

• Risch, R. H. (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.

• Risch, R. H. (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.

• Rosenlicht, Maxwell (1972). "Integration in finite terms". American Mathematical Monthly. Mathematical Association of America. 79 (9): 963–972. doi:10.2307/2318066. JSTOR 2318066.

बाहरी संबंध

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