रूट-फाइंडिंग एल्गोरिदम

गणित और कम्प्यूटिंग में, रूट-फाइंडिंग कलन विधि एक फ़ंक्शन के शून्य को खोजने के लिए एक एल्गोरिदम है, जिसे निरंतर कार्यों की जड़ें भी कहा जाता है। किसी फ़ंक्शन का शून्य f, वास्तविक संख्याओं से वास्तविक संख्याओं तक या सम्मिश्र संख्याओं से सम्मिश्र संख्याओं तक, एक संख्या है x ऐसा है कि f(x) = 0. चूँकि, आम तौर पर, किसी फ़ंक्शन के शून्य की सटीक गणना नहीं की जा सकती है और न ही इसे बंद रूप में व्यक्त किया जा सकता है, रूट-फाइंडिंग एल्गोरिदम शून्य का सन्निकटन प्रदान करते हैं, जिसे या तो फ़्लोटिंग-पॉइंट अंकगणितीय | फ़्लोटिंग-पॉइंट संख्याओं या छोटे पृथक अंतराल (गणित) के रूप में व्यक्त किया जाता है। या जटिल जड़ों के लिए डिस्क (गणित) (एक अंतराल या डिस्क आउटपुट एक त्रुटि बाध्यता के साथ अनुमानित आउटपुट के बराबर होता है)। समीकरण हल करना f(x) = g(x) फ़ंक्शन की जड़ें ढूंढने के समान है h(x) = f(x) – g(x). इस प्रकार रूट-फाइंडिंग एल्गोरिदम निरंतर कार्यों द्वारा परिभाषित किसी भी समीकरण (गणित) को हल करने की अनुमति देता है। हालाँकि, अधिकांश रूट-फाइंडिंग एल्गोरिदम यह गारंटी नहीं देते हैं कि वे सभी जड़ें ढूंढ लेंगे; विशेष रूप से, यदि ऐसे एल्गोरिदम को कोई रूट नहीं मिलता है, तो इसका मतलब यह नहीं है कि कोई रूट मौजूद नहीं है।

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

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

ब्रैकेटिंग विधियाँ

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

द्विभाजन विधि

सबसे सरल जड़-खोज एल्गोरिथ्म द्विभाजन विधि है। होने देना f एक सतत फलन हो, जिसके लिए कोई अंतराल जानता हो [a, b] ऐसा है कि f(a) और f(b) विपरीत चिह्न (कोष्ठक) हैं। होने देना c = (a +b)/2 अंतराल का मध्य हो (मध्यबिंदु या वह बिंदु जो अंतराल को समद्विभाजित करता है)। तो कोई f(a) और f(c), या f(c) और f(b) विपरीत चिह्न हैं, और एक को अंतराल के आकार से दो से विभाजित किया गया है। यद्यपि द्विभाजन विधि मजबूत है, यह प्रत्येक पुनरावृत्ति के साथ एक और केवल एक अंश सटीकता प्राप्त करती है। इसलिए, ε-अनुमानित रूट खोजने के लिए आवश्यक फ़ंक्शन मूल्यांकन की संख्या है $\log _{2}{\frac {b-a}{\varepsilon }}$. अन्य विधियाँ, उपयुक्त परिस्थितियों में, तेजी से सटीकता प्राप्त कर सकती हैं।

गलत स्थिति (रेगुला फाल्सी)

झूठी स्थिति विधि, जिसे रेगुला फाल्सी विधि भी कहा जाता है, द्विभाजन विधि के समान है, लेकिन अंतराल के मध्य में द्विभाजन खोज का उपयोग करने के बजाय यह एक्स-इंटरसेप्ट का उपयोग करता है|x-उस रेखा का अवरोधन जो अंतराल के अंतिम बिंदुओं पर प्लॉट किए गए फ़ंक्शन मानों को जोड़ता है

$c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.$

गलत स्थिति छेदक विधि के समान है, सिवाय इसके कि, अंतिम दो बिंदुओं को बनाए रखने के बजाय, यह मूल के दोनों ओर एक बिंदु को रखना सुनिश्चित करता है। झूठी स्थिति विधि द्विभाजन विधि से तेज़ हो सकती है और छेदक विधि की तरह कभी भी विचलन नहीं करेगी; हालाँकि, यह राउंडऑफ़ त्रुटियों के कारण कुछ सरल कार्यान्वयनों में परिवर्तित होने में विफल हो सकता है जिससे गलत संकेत मिल सकता है f(c); आम तौर पर, ऐसा तब हो सकता है जब भिन्नता की दर हो f जड़ के पड़ोस में बड़ा है।

आईटीपी विधि

आईटीपी विधि द्विभाजन विधि की समान सबसे खराब स्थिति की गारंटी के साथ रूट को ब्रैकेट करने की एकमात्र ज्ञात विधि है, जबकि सेकेंट विधि के रूप में सुचारू कार्यों की जड़ के लिए एक सुपरलीनियर अभिसरण की गारंटी देती है। यह रूट के स्थान पर किसी भी निरंतर वितरण के लिए औसतन द्विभाजन विधि से बेहतर प्रदर्शन करने की गारंटी देने वाली एकमात्र ज्ञात विधि है (आईटीपी विधि#विश्लेषण देखें)। यह ब्रैकेटिंग अंतराल के साथ-साथ मिनमैक्स अंतराल दोनों का ट्रैक रखकर ऐसा करता है जिसमें कोई भी बिंदु द्विभाजन विधि के रूप में तेजी से परिवर्तित होता है। पूछे गए बिंदु सी का निर्माण तीन चरणों का पालन करता है: इंटरपोलेशन (रेगुला फाल्सी के समान), ट्रंकेशन (रेगुला फाल्सी के समान रेगुला फाल्सी को समायोजित करना#सुधार%20in%20regula%20falsi|रेगुला फाल्सी §रेगुला फाल्सी में सुधार) और फिर प्रक्षेपण न्यूनतम अधिकतम अंतराल पर. इन चरणों का संयोजन सुचारू कार्यों के लिए इंटरपोलेशन आधारित तरीकों के समान गारंटी के साथ एक साथ मिनमैक्स इष्टतम विधि का उत्पादन करता है, और व्यवहार में, सुचारू और गैर-सुचारू दोनों कार्यों के तहत द्विभाजन विधि और इंटरपोलेशन आधारित तरीकों दोनों से बेहतर प्रदर्शन करेगा।

अंतर्वेशन

कई जड़-खोज प्रक्रियाएँ प्रक्षेप द्वारा कार्य करती हैं। इसमें निम्न डिग्री के बहुपद द्वारा फ़ंक्शन का अनुमान लगाने के लिए मूल के अंतिम गणना किए गए अनुमानित मानों का उपयोग करना शामिल है, जो इन अनुमानित जड़ों पर समान मान लेता है। फिर बहुपद के मूल की गणना की जाती है और फ़ंक्शन के मूल के नए अनुमानित मान के रूप में उपयोग किया जाता है, और प्रक्रिया को दोहराया जाता है।

दो मान किसी फ़ंक्शन को डिग्री एक के बहुपद द्वारा प्रक्षेपित करने की अनुमति देते हैं (अर्थात फ़ंक्शन के ग्राफ़ को एक रेखा द्वारा अनुमानित करना)। यह सेकेंट विधि का आधार है। तीन मान एक द्विघात फ़ंक्शन को परिभाषित करते हैं, जो एक परवलय द्वारा फ़ंक्शन के ग्राफ़ का अनुमान लगाता है। यह मुलर की विधि है.

रेगुला फाल्सी भी एक प्रक्षेप विधि है, जो एक रेखा द्वारा प्रक्षेप करने के लिए, दो बिंदुओं का उपयोग करके सेकेंट विधि से भिन्न होती है, जो जरूरी नहीं कि अंतिम दो गणना बिंदु हों।

पुनरावृत्त विधियाँ

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

न्यूटन की विधि (और समान व्युत्पन्न-आधारित विधियाँ)

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

छेदक विधि

न्यूटन की विधि में व्युत्पन्न को एक सीमित अंतर के साथ प्रतिस्थापित करने पर, हमें छेदक विधि प्राप्त होती है। इस पद्धति में किसी व्युत्पन्न की गणना (न ही अस्तित्व) की आवश्यकता होती है, लेकिन कीमत धीमी गति से अभिसरण होती है (ऑर्डर लगभग 1.6 (सुनहरा अनुपात) है)। उच्च आयामों में सेकेंट विधि का सामान्यीकरण ब्रोयडेन की विधि है।

स्टीफ़ेंसन की विधि

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

निश्चित बिंदु पुनरावृत्ति विधि

हम किसी फ़ंक्शन का मूल ज्ञात करने के लिए निश्चित-बिंदु पुनरावृत्ति का उपयोग कर सकते हैं। एक फ़ंक्शन दिया गया $f(x)$ जिसे हमने मूल ज्ञात करने के लिए शून्य पर सेट किया है ($f(x)=0$), हम समीकरण को फिर से लिखते हैं $x$ ताकि $f(x)=0$ बन जाता है $x=g(x)$ (ध्यान दें, अक्सर बहुत सारे होते हैं $g(x)$ प्रत्येक के लिए कार्य $f(x)=0$ समारोह)। इसके बाद, हम समीकरण के प्रत्येक पक्ष को इस प्रकार पुनः लेबल करते हैं $x_{n+1}=g(x_{n})$ ताकि हम पुनरावृत्ति कर सकें। इसके बाद, हम इसके लिए एक मान चुनते हैं $x_{1}$ और पुनरावृत्ति तब तक करें जब तक यह फ़ंक्शन की जड़ की ओर परिवर्तित न हो जाए। यदि पुनरावृत्ति अभिसरण होती है, तो यह जड़ में परिवर्तित हो जाएगी। पुनरावृत्ति केवल तभी एकत्रित होगी यदि $|g'(root)|<1$.

परिवर्तित करने के उदाहरण के रूप में $f(x)=0$ को $x=g(x)$, यदि फ़ंक्शन दिया गया है $f(x)=x^{2}+x-1$, हम इसे निम्नलिखित समीकरणों में से एक के रूप में फिर से लिखेंगे।

$x_{n+1}=(1/x_{n})-1$,

$x_{n+1}=1/(x_{n}+1)$,

$x_{n+1}=1-x_{n}^{2}$,

$x_{n+1}=x_{n}^{2}+2x_{n}-1$, या

$x_{n+1}=\pm {\sqrt {1-x_{n}}}$.

व्युत्क्रम प्रक्षेप

प्रक्षेप विधियों में जटिल मानों की उपस्थिति को एफ के व्युत्क्रम फ़ंक्शन को प्रक्षेपित करके टाला जा सकता है, जिसके परिणामस्वरूप व्युत्क्रम द्विघात प्रक्षेप विधि प्राप्त होती है। फिर से, अभिसरण सेकेंट विधि की तुलना में स्पर्शोन्मुख रूप से तेज है, लेकिन व्युत्क्रम द्विघात प्रक्षेप अक्सर खराब व्यवहार करता है जब पुनरावृत्त जड़ के करीब नहीं होते हैं।

विधियों का संयोजन

ब्रेंट की विधि

ब्रेंट की विधि द्विभाजन विधि, छेदक विधि और व्युत्क्रम द्विघात प्रक्षेप का एक संयोजन है। प्रत्येक पुनरावृत्ति पर, ब्रेंट की विधि यह तय करती है कि इन तीनों में से कौन सी विधि सबसे अच्छा काम करेगी, और उस विधि के अनुसार एक कदम उठाकर आगे बढ़ती है। यह एक मजबूत और तेज़ तरीका देता है, जो काफी लोकप्रिय है।

रिडर्स विधि

रिडर्स विधि एक हाइब्रिड विधि है जो रूट पर घातांकीय प्रक्षेप करने के लिए अंतराल के मध्य बिंदु पर फ़ंक्शन के मान का उपयोग करती है। यह द्विभाजन विधि के रूप में पुनरावृत्तियों की अधिकतम दोगुनी संख्या के गारंटीकृत अभिसरण के साथ एक तेज़ अभिसरण देता है।

उच्च आयामों में जड़ें ढूँढना

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

पोंकारे-मिरांडा प्रमेय एक आयत में जड़ के अस्तित्व के लिए एक मानदंड देता है, लेकिन इसे सत्यापित करना कठिन है, क्योंकि इसके लिए त्रिभुज की संपूर्ण सीमा पर फ़ंक्शन का मूल्यांकन करना आवश्यक है।

एक अन्य मानदंड क्रोनकर के एक प्रमेय द्वारा दिया गया है। इसमें कहा गया है कि, यदि किसी आयत पर फ़ंक्शन f की निरंतर मैपिंग की डिग्री गैर-शून्य है, तो आयत में f की कम से कम एक जड़ होनी चाहिए। यह मानदंड कई जड़-खोज विधियों का आधार है, जैसे कि स्टेंगर द्वारा और केयरफोट. हालाँकि, टोपोलॉजिकल डिग्री की गणना करने में समय लग सकता है।

तीसरा मानदंड एक विशिष्ट बहुफलक पर आधारित है। इस मानदंड का उपयोग कैरेक्टरिस्टिक बिसेक्शन नामक विधि द्वारा किया जाता है। इसमें टोपोलॉजिकल डिग्री की गणना करने की आवश्यकता नहीं है - इसमें केवल फ़ंक्शन मानों के संकेतों की गणना करने की आवश्यकता है। आवश्यक मूल्यांकनों की संख्या कम से कम है $\log _{2}(D/\epsilon )$, जहां D विशिष्ट बहुफलक के सबसे लंबे किनारे की लंबाई है। ध्यान दें कि मूल्यांकनों की संख्या पर निचली सीमा साबित करें, न कि ऊपरी सीमा।

चौथी विधि सरलताओं पर एक मध्यवर्ती-मूल्य प्रमेय का उपयोग करती है। फिर, प्रश्नों की संख्या पर कोई ऊपरी सीमा नहीं दी गई है।

यह भी देखें

• रूट खोज एल्गोरिदम की सूची
• निश्चित-बिंदु गणना

Broyden's method

• Cryptographically secure pseudorandom number generator
• जीएनयू वैज्ञानिक पुस्तकालय
• Graeffe's method
• Lill's method
• MPSolve
• Multiplicity (mathematics)
• Nवां रूट एल्गोरिथम|nवें रूट एल्गोरिथ्म
• System of polynomial equations
• Kantorovich theorem

अग्रिम पठन

• J.M. McNamee: "Numerical Methods for Roots of Polynomials - Part I", Elsevier (2007).
• J.M. McNamee and Victor Pan: "Numerical Methods for Roots of Polynomials - Part II", Elsevier (2013).