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

गणित और कम्प्यूटिंग में, रूट-फाइंडिंग एल्गोरिदम एक फ़ंक्शन के शून्य को फाइंडिंग के लिए एक एल्गोरिदम होता है, जिसे निरंतर कार्यों की रूट भी कहा जाता है। किसी फ़ंक्शन का शून्य 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 वेरिएशन की दर बड़ी हो।

आईटीपी विधि

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

इंटरपोलेशन

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

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

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

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

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

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

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

सेकेण्ट विधि

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

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

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

फिक्स्ड पॉइंट पुनरावृत्ति विधि

हम किसी फ़ंक्शन का रूट ज्ञात करने के लिए फिक्स्ड-पॉइंट पुनरावृत्ति का उपयोग कर सकते हैं। एक फ़ंक्शन $f(x)$ दिया गया जिसे हमने रूट ज्ञात करने के लिए शून्य ($f(x)=0$) पर सेट किया जाता है, हम समीकरण $x$ को फिर से लिखते हैं जिससे $f(x)=0$ होता है जी $x=g(x)$ बन जाता है (ध्यान दें, अधिकांशतः बहुत सारे $f(x)=0$ फंक्शन के लिए $g(x)$फंक्शन होते है)। इसके पश्चात्, हम समीकरण के प्रत्येक पक्ष को इस प्रकार $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}}}$.

डेरीवेटिव इंटरपोलेशन

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

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

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

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

रिडर्स विधि

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

पोलीनोमियल की रूट

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

उच्च आयामों में रूट फाइंडिंग

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

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

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

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

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

अग्रिम पठन

• 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).