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

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

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

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

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

विवरण

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

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

$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 में हेनरी कोहेन (संख्या सिद्धांतकार) द्वारा sci.math.symbolic पर पोस्ट किया गया)) में एक प्रारंभिक प्रतिअवकलन है, जैसा कि संस्करण 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 में बदल दिया जाए, तो प्रारंभिक कार्यों के संदर्भ में प्रतिअवकलन का प्रतिनिधित्व करना संभव नहीं है,जैसा कि FriCAS भी दिखाता है। कुछ कंप्यूटर बीजगणित प्रणालियाँ यहाँ गैर-प्राथमिक कार्यों (अर्थात अण्डाकार इंटीग्रल्स) के संदर्भ में एक एंटीडेरिवेटिव लौटा सकती हैं, जो रिस्क एल्गोरिदम के दायरे से बाहर हैं। इस अभिन्न अंग को पफनुटी चेबीशेव द्वारा हल किया गया था (और किन मामलों में यह प्राथमिक है), लेकिन इसका पुख्ता सबूत आख़िरकार ईगोर इवानोविच ज़ोलोटारेव ने किया। निम्नलिखित एक अधिक जटिल उदाहरण है जिसमें बीजीय और पारलौकिक दोनों प्रकार के कार्य शामिल हैं:

$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}}$ (SymPy इसे हल कर सकता है जबकि FriCAS रिस्क एल्गोरिदम में कार्यान्वयन अपूर्ण (निरंतर अवशेष) त्रुटि के साथ विफल रहता है):

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

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

कार्यान्वयन

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

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

निर्णायकता

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

ध्यान दें कि यह समस्या बहुपद विभाजन एल्गोरिथ्म में भी उत्पन्न होती है; यह एल्गोरिदम विफल हो जाएगा यदि यह सही ढंग से निर्धारित नहीं कर सकता है कि गुणांक समान रूप से गायब हो जाते हैं या नहीं। वस्तुतः बहुपदों से संबंधित प्रत्येक गैर-तुच्छ एल्गोरिदम बहुपद विभाजन एल्गोरिदम का उपयोग करता है, जिसमें रिस्क एल्गोरिदम भी शामिल है। यदि स्थिर फ़ील्ड गणना योग्य है, यानी, उन तत्वों के लिए जो निर्भर नहीं हैं 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.