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

Revision as of 13:59, 3 August 2023

गणित और कम्प्यूटिंग में, रूट-फाइंडिंग एल्गोरिदम एक फ़ंक्शन के शून्य को फाइंडिंग के लिए एक एल्गोरिदम होता है, जिसे निरंतर कार्यों की रूट भी कहा जाता है। किसी फ़ंक्शन का शून्य $f$ , वास्तविक संख्याओं से वास्तविक संख्याओं तक या सम्मिश्र संख्याओं से सम्मिश्र संख्याओं तक, एक संख्या होती है $x$ ऐसा है कि $f (x) = 0$ होता है। चूँकि, सामान्यतः, किसी फ़ंक्शन के शून्य की स्पष्ट गणना नहीं की जा सकती है और न ही इसे संवृत रूप में व्यक्त किया जा सकता है, रूट-फाइंडिंग एल्गोरिदम शून्य का सन्निकटन प्रदान करते हैं, जिसे या तो फ़्लोटिंग-पॉइंट अंकगणित संख्याओं या छोटे पृथक इंटरवेल के रूप में व्यक्त किया जाता है। या काम्प्लेक्स रूट्स के लिए डिस्क (एक इंटरवेल या डिस्क आउटपुट एक एरर बाउंड के साथ एप्रोक्सीमेट आउटपुट के सामान्तर होता है)।^[1]

समीकरण हल करना $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वीं सदी तक बीजगणित का अर्थ अनिवार्य रूप से पोलीनोमियल समीकरणों का सिद्धांत था।

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

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

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

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

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

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

यह भी देखें

ब्रोयडेन की विधि

क्रिप्टोग्राफ़िक रूप से सुरक्षित जनरेटर स्यूडो रैंडम
जीएनयू वैज्ञानिक पुस्तकालय
ग्रेफ़ की विधि
लिल की विधि
एमपीसॉल्व
Multiplicity (mathematics)
Nवां रूट एल्गोरिथम| $n$ वें रूट एल्गोरिथ्म
पोलीनोमियल समीकरण का सिस्टम
कांटोरोविच थ्योरम

संदर्भ

↑ Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Chapter 9. Root Finding and Nonlinear Sets of Equations". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
↑ ^2.0 ^2.1 Mourrain, B.; Vrahatis, M. N.; Yakoubsohn, J. C. (2002-06-01). "वास्तविक जड़ों को अलग करने और निश्चितता के साथ टोपोलॉजिकल डिग्री की गणना करने की जटिलता पर". Journal of Complexity (in English). 18 (2): 612–640. doi:10.1006/jcom.2001.0636. ISSN 0885-064X.
↑ Vrahatis, Michael N. (2020). Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). "सतत कार्यों के निश्चित बिंदुओं और शून्यों का अनुमान लगाने के लिए मध्यवर्ती मूल्य प्रमेय का सामान्यीकरण". Numerical Computations: Theory and Algorithms. Lecture Notes in Computer Science (in English). Cham: Springer International Publishing. 11974: 223–238. doi:10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5. S2CID 211160947.
↑ "कई चरों में अरेखीय समीकरणों का पुनरावृत्तीय समाधान". Guide books (in English). Retrieved 2023-04-16.
↑ Stenger, Frank (1975-03-01). "मैपिंग इनआरएन की टोपोलॉजिकल डिग्री की गणना करना". Numerische Mathematik (in English). 25 (1): 23–38. doi:10.1007/BF01419526. ISSN 0945-3245. S2CID 122196773.
↑ Kearfott, Baker (1979-06-01). "द्विभाजन की सामान्यीकृत विधि के लिए एक कुशल डिग्री-गणना विधि". Numerische Mathematik. 32 (2): 109–127. doi:10.1007/BF01404868. ISSN 0029-599X. S2CID 122058552.
↑ ^7.0 ^7.1 Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01). "गैर-रेखीय समीकरणों की प्रणालियों को हल करने के लिए द्विभाजन की एक तीव्र सामान्यीकृत विधि". Numerische Mathematik (in English). 49 (2): 123–138. doi:10.1007/BF01389620. ISSN 0945-3245.
↑ Vrahatis, Michael N. (2020-04-15). "निश्चित बिंदुओं और शून्यों के सरल सन्निकटन के लिए सरलताओं के लिए मध्यवर्ती मूल्य प्रमेय". Topology and its Applications (in English). 275: 107036. doi:10.1016/j.topol.2019.107036. ISSN 0166-8641.

अग्रिम पठन

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

[1] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Chapter 9. Root Finding and Nonlinear Sets of Equations". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.

[:0-2] 2.0 ^2.1 Mourrain, B.; Vrahatis, M. N.; Yakoubsohn, J. C. (2002-06-01). "वास्तविक जड़ों को अलग करने और निश्चितता के साथ टोपोलॉजिकल डिग्री की गणना करने की जटिलता पर". Journal of Complexity (in English). 18 (2): 612–640. doi:10.1006/jcom.2001.0636. ISSN 0885-064X.

[3] Vrahatis, Michael N. (2020). Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). "सतत कार्यों के निश्चित बिंदुओं और शून्यों का अनुमान लगाने के लिए मध्यवर्ती मूल्य प्रमेय का सामान्यीकरण". Numerical Computations: Theory and Algorithms. Lecture Notes in Computer Science (in English). Cham: Springer International Publishing. 11974: 223–238. doi:10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5. S2CID 211160947.

[4] "कई चरों में अरेखीय समीकरणों का पुनरावृत्तीय समाधान". Guide books (in English). Retrieved 2023-04-16.

[5] Stenger, Frank (1975-03-01). "मैपिंग इनआरएन की टोपोलॉजिकल डिग्री की गणना करना". Numerische Mathematik (in English). 25 (1): 23–38. doi:10.1007/BF01419526. ISSN 0945-3245. S2CID 122196773.

[6] Kearfott, Baker (1979-06-01). "द्विभाजन की सामान्यीकृत विधि के लिए एक कुशल डिग्री-गणना विधि". Numerische Mathematik. 32 (2): 109–127. doi:10.1007/BF01404868. ISSN 0029-599X. S2CID 122058552.

[:2-7] 7.0 ^7.1 Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01). "गैर-रेखीय समीकरणों की प्रणालियों को हल करने के लिए द्विभाजन की एक तीव्र सामान्यीकृत विधि". Numerische Mathematik (in English). 49 (2): 123–138. doi:10.1007/BF01389620. ISSN 0945-3245.

[8] Vrahatis, Michael N. (2020-04-15). "निश्चित बिंदुओं और शून्यों के सरल सन्निकटन के लिए सरलताओं के लिए मध्यवर्ती मूल्य प्रमेय". Topology and its Applications (in English). 275: 107036. doi:10.1016/j.topol.2019.107036. ISSN 0166-8641.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
 {{Short description|Algorithms for zeros of functions}}
-गणित और [[ कम्प्यूटिंग |कम्प्यूटिंग]] में, रूट-फाइंडिंग [[कलन विधि]] एक फ़ंक्शन के शून्य को खोजने के लिए एक एल्गोरिदम है, जिसे निरंतर कार्यों की जड़ें भी कहा जाता है। [[किसी फ़ंक्शन का शून्य]] {{math|''f''}}, [[वास्तविक संख्या]]ओं से वास्तविक संख्याओं तक या सम्मिश्र संख्याओं से सम्मिश्र संख्याओं तक, एक संख्या है {{math|''x''}} ऐसा है कि {{math|1=''f''(''x'') = 0}}. चूँकि, आम तौर पर, किसी फ़ंक्शन के शून्य की सटीक गणना नहीं की जा सकती है और न ही इसे बंद रूप में व्यक्त किया जा सकता है, रूट-फाइंडिंग एल्गोरिदम शून्य का सन्निकटन प्रदान करते हैं, जिसे या तो [[फ़्लोटिंग-पॉइंट अंकगणित]]ीय | फ़्लोटिंग-पॉइंट संख्याओं या छोटे पृथक [[अंतराल (गणित)]] के रूप में व्यक्त किया जाता है। या जटिल जड़ों के लिए [[डिस्क (गणित)]] (एक अंतराल या डिस्क आउटपुट एक त्रुटि बाध्यता के साथ अनुमानित आउटपुट के बराबर होता है)।<ref>{{Cite book |last1=Press |first1=W. H. |title=Numerical Recipes: The Art of Scientific Computing |last2=Teukolsky |first2=S. A. |last3=Vetterling |first3=W. T. |last4=Flannery |first4=B. P. |publisher=Cambridge University Press |year=2007 |isbn=978-0-521-88068-8 |edition=3rd |publication-place=New York |chapter=Chapter 9. Root Finding and Nonlinear Sets of Equations |chapter-url=http://apps.nrbook.com/empanel/index.html#pg=442}}</ref>
+गणित और [[ कम्प्यूटिंग |कम्प्यूटिंग]] में, '''रूट-फाइंडिंग [[कलन विधि|एल्गोरिदम]]''' एक फ़ंक्शन के शून्य को फाइंडिंग के लिए एक एल्गोरिदम होता है, जिसे निरंतर कार्यों की रूट भी कहा जाता है। [[किसी फ़ंक्शन का शून्य]] {{math|''f''}}, [[वास्तविक संख्या]]ओं से वास्तविक संख्याओं तक या सम्मिश्र संख्याओं से सम्मिश्र संख्याओं तक, एक संख्या होती है {{math|''x''}} ऐसा है कि {{math|1=''f''(''x'') = 0}} होता है। चूँकि, सामान्यतः, किसी फ़ंक्शन के शून्य की स्पष्ट गणना नहीं की जा सकती है और न ही इसे संवृत रूप में व्यक्त किया जा सकता है, रूट-फाइंडिंग एल्गोरिदम शून्य का सन्निकटन प्रदान करते हैं, जिसे या तो [[फ़्लोटिंग-पॉइंट अंकगणित]] संख्याओं या छोटे पृथक [[अंतराल (गणित)|इंटरवेल]] के रूप में व्यक्त किया जाता है। या काम्प्लेक्स रूट्स के लिए [[डिस्क (गणित)|डिस्क]] (एक इंटरवेल या डिस्क आउटपुट एक एरर बाउंड के साथ एप्रोक्सीमेट आउटपुट के सामान्तर होता है)।<ref>{{Cite book |last1=Press |first1=W. H. |title=Numerical Recipes: The Art of Scientific Computing |last2=Teukolsky |first2=S. A. |last3=Vetterling |first3=W. T. |last4=Flannery |first4=B. P. |publisher=Cambridge University Press |year=2007 |isbn=978-0-521-88068-8 |edition=3rd |publication-place=New York |chapter=Chapter 9. Root Finding and Nonlinear Sets of Equations |chapter-url=http://apps.nrbook.com/empanel/index.html#pg=442}}</ref>
-[[समीकरण हल करना]] {{math|1=''f''(''x'') = ''g''(''x'')}} फ़ंक्शन की जड़ें ढूंढने के समान है {{math|1=''h''(''x'') = ''f''(''x'') – ''g''(''x'')}}. इस प्रकार रूट-फाइंडिंग एल्गोरिदम निरंतर कार्यों द्वारा परिभाषित किसी भी [[समीकरण (गणित)]] को हल करने की अनुमति देता है। हालाँकि, अधिकांश रूट-फाइंडिंग एल्गोरिदम यह गारंटी नहीं देते हैं कि वे सभी जड़ें ढूंढ लेंगे; विशेष रूप से, यदि ऐसे एल्गोरिदम को कोई रूट नहीं मिलता है, तो इसका मतलब यह नहीं है कि कोई रूट मौजूद नहीं है।
-अधिकांश संख्यात्मक मूल-खोज विधियाँ पुनरावृत्ति का उपयोग करती हैं, जिससे संख्याओं का एक [[अनुक्रम]] तैयार होता है जो उम्मीद है कि [[अनुक्रम की सीमा]] के रूप में मूल की ओर अभिसरण होता है। उन्हें शुरुआती मूल्यों के रूप में रूट के एक या अधिक प्रारंभिक अनुमानों की आवश्यकता होती है, फिर एल्गोरिदम का प्रत्येक पुनरावृत्ति रूट के लिए क्रमिक रूप से अधिक सटीक सन्निकटन उत्पन्न करता है। चूँकि पुनरावृत्ति को किसी बिंदु पर रोका जाना चाहिए, ये विधियाँ मूल का एक अनुमान उत्पन्न करती हैं, सटीक समाधान नहीं। कई विधियाँ पूर्ववर्ती मानों पर एक सहायक फ़ंक्शन का मूल्यांकन करके बाद के मानों की गणना करती हैं। इस प्रकार सीमा सहायक फ़ंक्शन का एक [[निश्चित बिंदु (गणित)]] है, जिसे मूल समीकरण की जड़ों को निश्चित बिंदुओं के रूप में रखने और इन निश्चित बिंदुओं पर तेजी से परिवर्तित करने के लिए चुना जाता है।
+[[समीकरण हल करना]] {{math|1=''f''(''x'') = ''g''(''x'')}} फ़ंक्शन की रूट फाइंडिंग {{math|1=''h''(''x'') = ''f''(''x'') – ''g''(''x'')}} के समान होता है। इस प्रकार रूट-फाइंडिंग एल्गोरिदम निरंतर कार्यों द्वारा परिभाषित किसी भी [[समीकरण (गणित)|समीकरण]] को हल करने की अनुमति देता है। यघपि, अधिकांश रूट-फाइंडिंग एल्गोरिदम यह गारंटी नहीं देते हैं कि वे सभी रूट फाइंड कर लेंगे; विशेष रूप से, यदि ऐसे एल्गोरिदम को कोई रूट नहीं मिलता है, तो इसका मतलब यह नहीं है कि कोई रूट उपस्थित नहीं है।
-[[संख्यात्मक विश्लेषण]] में सामान्य रूट-फाइंडिंग एल्गोरिदम के व्यवहार का अध्ययन किया जाता है। हालाँकि, [[बहुपद]]ों के लिए, मूल-खोज अध्ययन आम तौर पर [[कंप्यूटर बीजगणित]] से संबंधित होता है, क्योंकि बहुपदों के बीजगणितीय गुण सबसे कुशल एल्गोरिदम के लिए मौलिक होते हैं। किसी एल्गोरिदम की दक्षता दिए गए कार्यों की विशेषताओं पर नाटकीय रूप से निर्भर हो सकती है। उदाहरण के लिए, कई एल्गोरिदम इनपुट फ़ंक्शन के व्युत्पन्न का उपयोग करते हैं, जबकि अन्य प्रत्येक निरंतर फ़ंक्शन पर काम करते हैं। सामान्य तौर पर, संख्यात्मक एल्गोरिदम किसी फ़ंक्शन के सभी रूट ढूंढने की गारंटी नहीं देते हैं, इसलिए रूट ढूंढने में विफल होने से यह साबित नहीं होता है कि कोई रूट नहीं है। हालाँकि, बहुपदों के लिए, ऐसे विशिष्ट एल्गोरिदम हैं जो यह प्रमाणित करने के लिए बीजगणितीय गुणों का उपयोग करते हैं कि कोई जड़ नहीं छूटी है, और जड़ों को अलग-अलग अंतराल (या जटिल जड़ों के लिए डिस्क (गणित)) में स्थित करते हैं जो संख्यात्मक तरीकों के अभिसरण को सुनिश्चित करने के लिए काफी छोटे होते हैं ( आमतौर पर न्यूटन की विधि) इस प्रकार स्थित अद्वितीय जड़ तक।
+अधिकांश संख्यात्मक रूट-फाइंडिंग विधियाँ पुनरावृत्ति का उपयोग करती हैं, जिससे संख्याओं का एक [[अनुक्रम]] निर्मित होता है जो उम्मीद है कि [[अनुक्रम की सीमा|अनुक्रम की लिमिट]] के रूप में रूट की ओर कन्वर्जेज़ होता है। उन्हें प्रारंभिक रूट के रूप में रूट के एक या अधिक प्रारंभिक अनुमानों की आवश्यकता होती है, फिर एल्गोरिदम का प्रत्येक पुनरावृत्ति रूट के लिए क्रमिक रूप से अधिक स्पष्ट सन्निकटन उत्पन्न करता है। चूँकि पुनरावृत्ति को किसी बिंदु पर रोका जाना चाहिए, ये विधियाँ रूट का एक अनुमान उत्पन्न करती हैं, स्पष्ट समाधान नहीं। कई विधियाँ पूर्ववर्ती मानों पर एक सहायक फ़ंक्शन का मुल्यांकन करके पश्चात् के मानों की गणना करती हैं। इस प्रकार लिमिट सहायक फ़ंक्शन का एक [[निश्चित बिंदु (गणित)|फिक्स्ड पॉइंट]] होता है, जिसे रूट समीकरण की रूट्स को फिक्स्ड पॉइंट्स के रूप में रखने और इन फिक्स्ड पॉइंट्स पर शीघ्रता से परिवर्तित करने के लिए चयन किया जाता है।
+[[संख्यात्मक विश्लेषण]] में सामान्य रूट-फाइंडिंग एल्गोरिदम के व्यवहार का अध्ययन किया जाता है। यघपि, [[बहुपद|बहुपदों]] के लिए, रूट-फाइंडिंग अध्ययन सामान्यतः [[कंप्यूटर बीजगणित]] से संबंधित होता है, क्योंकि बहुपदों के बीजगणितीय गुण सबसे कुशल एल्गोरिदम के लिए मौलिक होते हैं। किसी एल्गोरिदम की दक्षता दिए गए कार्यों की विशेषताओं पर ड्रामाटिकली रूप से निर्भर हो सकती है। उदाहरण के लिए, कई एल्गोरिदम इनपुट फ़ंक्शन के डेरीवेटिव का उपयोग करते हैं, जबकि अन्य प्रत्येक निरंतर फ़ंक्शन पर काम करते हैं। सामान्य तौर पर, संख्यात्मक एल्गोरिदम किसी फ़ंक्शन के सभी रूट फाइंडिंग की गारंटी नहीं देते हैं, इसलिए रूट फाइंडिंग में विफल होने से यह सिद्ध नहीं होता है कि कोई रूट नहीं है। यघपि, बहुपदों के लिए, ऐसे विशिष्ट एल्गोरिदम होता हैं जो यह प्रमाणित करने के लिए बीजगणितीय गुणों का उपयोग करते हैं कि कोई रूट नहीं मिस हुई है, और रूट्स को अलग-अलग इंटरवेल (या काम्प्लेक्स रूट्स के लिए डिस्क) में रूट्स का पता लगाना जो इतने छोटे हों कि इस प्रकार स्थित यूनिक रूट में संख्यात्मक विधियों (सामान्यतः न्यूटन की विधि) का कन्वर्जेन्स सुनिश्चित हो सके।
 == ब्रैकेटिंग विधियाँ ==
-ब्रैकेटिंग विधियाँ क्रमिक रूप से छोटे अंतराल (कोष्ठक) निर्धारित करती हैं जिनमें एक जड़ होती है। जब अंतराल काफी छोटा होता है, तो एक जड़ मिल जाती है। वे आम तौर पर [[मध्यवर्ती मूल्य प्रमेय]] का उपयोग करते हैं, जो दावा करता है कि यदि किसी निरंतर फ़ंक्शन में अंतराल के अंतिम बिंदुओं पर विपरीत संकेतों के मान होते हैं, तो फ़ंक्शन के अंतराल में कम से कम एक जड़ होती है। इसलिए, उन्हें एक अंतराल से शुरू करने की आवश्यकता होती है जैसे कि फ़ंक्शन अंतराल के अंतिम बिंदुओं पर विपरीत संकेत लेता है। हालाँकि, बहुपद के मामले में एक अंतराल में जड़ों की संख्या के बारे में जानकारी प्राप्त करने के लिए अन्य विधियाँ (डेसकार्टेस के संकेतों का नियम, बुडान का प्रमेय और स्टर्म का प्रमेय) हैं। वे बहुपदों के वास्तविक-मूल अलगाव के लिए कुशल एल्गोरिदम का नेतृत्व करते हैं, जो गारंटीकृत सटीकता के साथ सभी वास्तविक जड़ों को ढूंढना सुनिश्चित करते हैं।
+ब्रैकेटिंग विधियाँ क्रमिक रूप से छोटे इंटरवेल (ब्रैकेट्स) निर्धारित करती हैं जिनमें एक रूट होती है। जब इंटरवेल अत्यधिक छोटा होता है, तो एक रूट प्राप्त हो जाती है। वे सामान्यतः [[मध्यवर्ती मूल्य प्रमेय|इंटरमीडिएट वैल्यू थ्योरम]] का उपयोग करते हैं, जो अस्सेर्ट करता है कि यदि किसी निरंतर फ़ंक्शन में इंटरवेल के अंतिम बिंदुओं पर विपरीत संकेतों के मान होते हैं, तो फ़ंक्शन के इंटरवेल में कम से कम एक रूट होती है। इसलिए, उन्हें एक इंटरवेल से प्रारम्भ करने की आवश्यकता होती है जैसे कि फ़ंक्शन इंटरवेल के अंतिम बिंदुओं पर विपरीत संकेत लेता है। यघपि, बहुपद के सिग्नस्स्थ्ती में एक इंटरवेल में रूट्स की संख्या के बारे में जानकारी प्राप्त करने के लिए अन्य विधियाँ (डेसकार्टेस के संकेतों का नियम, बुडान का प्रमेय और स्टर्म का प्रमेय) हैं। वे बहुपदों के वास्तविक-रूट आइसोलेशन के लिए कुशल एल्गोरिदम का नेतृत्व करते हैं, जो गारंटीकृत स्पष्टता के साथ सभी वास्तविक रूट्स को फाइंड सुनिश्चित करते हैं।
 ===[[द्विभाजन विधि]] ===
-सबसे सरल जड़-खोज एल्गोरिथ्म द्विभाजन विधि है। होने देना {{math|''f''}} एक सतत फलन हो, जिसके लिए कोई अंतराल जानता हो {{math|[''a'', ''b'']}} ऐसा है कि {{math|''f''(''a'')}} और {{math|''f''(''b'')}} विपरीत चिह्न (कोष्ठक) हैं। होने देना {{math|1=''c'' = (''a'' +''b'')/2}} अंतराल का मध्य हो (मध्यबिंदु या वह बिंदु जो अंतराल को समद्विभाजित करता है)। तो कोई {{math|''f''(''a'')}} और {{math|''f''(''c'')}}, या {{math|''f''(''c'')}} और {{math|''f''(''b'')}} विपरीत चिह्न हैं, और एक को अंतराल के आकार से दो से विभाजित किया गया है। यद्यपि द्विभाजन विधि मजबूत है, यह प्रत्येक पुनरावृत्ति के साथ एक और केवल एक [[ अंश |अंश]] सटीकता प्राप्त करती है। इसलिए, ε-अनुमानित रूट खोजने के लिए आवश्यक फ़ंक्शन मूल्यांकन की संख्या है <math>\log_2\frac{b-a}{\varepsilon}</math>. अन्य विधियाँ, उपयुक्त परिस्थितियों में, तेजी से सटीकता प्राप्त कर सकती हैं।
+सबसे सरल रूट-फाइंडिंग एल्गोरिथ्म द्विभाजन विधि है। होने देना {{math|''f''}} एक सतत फलन हो, जिसके लिए कोई इंटरवेल {{math|[''a'', ''b'']}} जानता है जैसे कि {{math|''f''(''a'')}} और {{math|''f''(''b'')}} विपरीत चिह्न (एक ब्रैकेट) होते हों। मान लीजिए {{math|1=''c'' = (''a'' +''b'')/2}} इंटरवेल का मध्य हो (मध्यबिंदु या वह बिंदु जो इंटरवेल को समद्विभाजित करता है)। तो कोई {{math|''f''(''a'')}} और {{math|''f''(''c'')}}, या {{math|''f''(''c'')}} और {{math|''f''(''b'')}} विपरीत चिह्न होता हैं, और एक को इंटरवेल के आकार से दो से विभाजित किया जाता है। यद्यपि द्विभाजन विधि रोबस्ट होती है, यह प्रत्येक पुनरावृत्ति के साथ एक और मात्र एक [[ अंश |अंश]] स्पष्टता प्राप्त करती है। इसलिए, ε-एप्रोक्सीमेट रूट फाइंडिंग के लिए आवश्यक फ़ंक्शन मूल्यांकन की संख्या होती है।
-=== गलत स्थिति (रेगुला फाल्सी) ===
+<math>\log_2\frac{b-a}{\varepsilon}</math>. अन्य विधियाँ, उपयुक्त परिस्थितियों में, शीघ्रता से स्पष्टता प्राप्त कर सकती हैं।
-[[झूठी स्थिति विधि]], जिसे रेगुला फाल्सी विधि भी कहा जाता है, द्विभाजन विधि के समान है, लेकिन अंतराल के मध्य में द्विभाजन खोज का उपयोग करने के बजाय यह एक्स-इंटरसेप्ट का उपयोग करता है|{{math|''x''}}-उस रेखा का अवरोधन जो अंतराल के अंतिम बिंदुओं पर प्लॉट किए गए फ़ंक्शन मानों को जोड़ता है
+=== फाल्स पोजीशन (रेगुला फाल्सी) ===
+[[झूठी स्थिति विधि|फाल्स पोजीशन विधि]], जिसे रेगुला फाल्सी विधि भी कहा जाता है, द्विभाजन विधि के समान होता है, परन्तु इंटरवेल के मध्य में द्विभाजन फाइंडिंग का उपयोग करने के अतिरिक्त यह एक्स-इंटरसेप्ट का उपयोग करता है। {{math|''x''}}-उस रेखा का अवरोधन जो इंटरवेल के अंतिम बिंदुओं पर प्लॉट किए गए फ़ंक्शन मानों को जोड़ता है
 :<math>c= \frac{af(b)-bf(a)}{f(b)-f(a)}.</math>
-गलत स्थिति [[छेदक विधि]] के समान है, सिवाय इसके कि, अंतिम दो बिंदुओं को बनाए रखने के बजाय, यह मूल के दोनों ओर एक बिंदु को रखना सुनिश्चित करता है। झूठी स्थिति विधि द्विभाजन विधि से तेज़ हो सकती है और छेदक विधि की तरह कभी भी विचलन नहीं करेगी; हालाँकि, यह राउंडऑफ़ त्रुटियों के कारण कुछ सरल कार्यान्वयनों में परिवर्तित होने में विफल हो सकता है जिससे गलत संकेत मिल सकता है {{math|''f''(''c'')}}; आम तौर पर, ऐसा तब हो सकता है जब [[भिन्नता की दर]] हो {{mvar|f}} जड़ के पड़ोस में बड़ा है।
+फाल्स पोजीशन [[छेदक विधि|सेकेण्ट विधि]] के समान होती है, अतिरिक्त इसके कि, अंतिम दो बिंदुओं को बनाए रखने के अतिरिक्त, यह रूट के दोनों ओर एक बिंदु को रखना सुनिश्चित करता है। फाल्स पोजीशन विधि द्विभाजन विधि से शीघ्र हो सकती है और सेकेण्ट विधि की तरह कभी भी विचलन नहीं करेगी; यघपि, यह राउंडऑफ़ एरर के कारण कुछ सरल कार्यान्वयनों में परिवर्तित होने में विफल हो सकता है जिससे {{math|''f''(''c'')}} के लिए गलत संकेत मिल सकता है ; सामान्यतः, ऐसा तब हो सकता है जब रूट के समीप में {{mvar|f}} [[भिन्नता की दर|वेरिएशन की दर]] बड़ी हो।
 === [[आईटीपी विधि]] ===
-आईटीपी विधि द्विभाजन विधि की समान सबसे खराब स्थिति की गारंटी के साथ रूट को ब्रैकेट करने की एकमात्र ज्ञात विधि है, जबकि सेकेंट विधि के रूप में सुचारू कार्यों की जड़ के लिए एक सुपरलीनियर अभिसरण की गारंटी देती है। यह रूट के स्थान पर किसी भी निरंतर वितरण के लिए औसतन द्विभाजन विधि से बेहतर प्रदर्शन करने की गारंटी देने वाली एकमात्र ज्ञात विधि है (आईटीपी विधि#विश्लेषण देखें)। यह ब्रैकेटिंग अंतराल के साथ-साथ मिनमैक्स अंतराल दोनों का ट्रैक रखकर ऐसा करता है जिसमें कोई भी बिंदु द्विभाजन विधि के रूप में तेजी से परिवर्तित होता है। पूछे गए बिंदु सी का निर्माण तीन चरणों का पालन करता है: इंटरपोलेशन (रेगुला फाल्सी के समान), ट्रंकेशन (रेगुला फाल्सी के समान रेगुला फाल्सी को समायोजित करना#सुधार%20in%20regula%20falsi|रेगुला फाल्सी §रेगुला फाल्सी में सुधार) और फिर प्रक्षेपण न्यूनतम अधिकतम अंतराल पर. इन चरणों का संयोजन सुचारू कार्यों के लिए इंटरपोलेशन आधारित तरीकों के समान गारंटी के साथ एक साथ मिनमैक्स इष्टतम विधि का उत्पादन करता है, और व्यवहार में, सुचारू और गैर-सुचारू दोनों कार्यों के तहत द्विभाजन विधि और इंटरपोलेशन आधारित तरीकों दोनों से बेहतर प्रदर्शन करेगा।
+आईटीपी विधि द्विभाजन विधि की समान सबसे व्यर्थ स्थिति की गारंटी के साथ रूट को ब्रैकेट करने की एकमात्र ज्ञात विधि है, जबकि सेकेंट विधि के रूप में सुचारू कार्यों की रूट के लिए एक सुपरलीनियर कन्वर्जेज़ की गारंटी देती है। यह रूट के स्थान पर किसी भी निरंतर वितरण के लिए औसतन द्विभाजन विधि से बेहतर प्रदर्शन करने की गारंटी देने वाली एकमात्र ज्ञात विधि है (आईटीपी विधि#विश्लेषण देखें)। यह ब्रैकेटिंग इंटरवेल के साथ-साथ मिनमैक्स इंटरवेल दोनों का ट्रैक रखकर ऐसा करता है जिसमें कोई भी बिंदु द्विभाजन विधि के रूप में शीघ्रता से परिवर्तित होता है। पूछे गए बिंदु सी का निर्माण तीन चरणों का पालन करता है: इंटरपोलेशन (रेगुला फाल्सी के समान), ट्रंकेशन (रेगुला फाल्सी के समान रेगुला फाल्सी को समायोजित रेगुला फाल्सी §रेगुला फाल्सी में सुधार) और फिर इंटरपोलेशनण न्यूनतम अधिकतम इंटरवेल पर प्रोजेक्शन होता है। इन स्टेप्स का संयोजन सुचारू कार्यों के लिए इंटरपोलेशन आधारित विधियों के समान गारंटी के साथ एक साथ मिनमैक्स इष्टतम विधि का उत्पादन करता है, और व्यवहार में, सुचारू और गैर-सुचारू दोनों कार्यों के तहत द्विभाजन विधि और इंटरपोलेशन आधारित विधियों दोनों से बेहतर प्रदर्शन करता है।
-== अंतर्वेशन ==
+== इंटरपोलेशन ==
-कई जड़-खोज प्रक्रियाएँ [[प्रक्षेप]] द्वारा कार्य करती हैं। इसमें निम्न डिग्री के बहुपद द्वारा फ़ंक्शन का अनुमान लगाने के लिए मूल के अंतिम गणना किए गए अनुमानित मानों का उपयोग करना शामिल है, जो इन अनुमानित जड़ों पर समान मान लेता है। फिर बहुपद के मूल की गणना की जाती है और फ़ंक्शन के मूल के नए अनुमानित मान के रूप में उपयोग किया जाता है, और प्रक्रिया को दोहराया जाता है।
+कई रूट-फाइंडिंग प्रक्रियाएँ [[प्रक्षेप|इंटरपोलेशन]] द्वारा कार्य करती हैं। इसमें निम्न डिग्री के बहुपद द्वारा फ़ंक्शन का अनुमान लगाने के लिए रूट के अंतिम गणना किए गए एप्रोक्सीमेट मानों का उपयोग करना सम्मलित होता है, जो इन एप्रोक्सीमेट रूट्स पर समान मान लेता है। फिर बहुपद के रूट की गणना की जाती है और फ़ंक्शन के रूट के नए एप्रोक्सीमेट मान के रूप में उपयोग किया जाता है, और प्रक्रिया को दोहराया जाता है।
-दो मान किसी फ़ंक्शन को डिग्री एक के बहुपद द्वारा प्रक्षेपित करने की अनुमति देते हैं (अर्थात फ़ंक्शन के ग्राफ़ को एक रेखा द्वारा अनुमानित करना)। यह सेकेंट विधि का आधार है। तीन मान एक द्विघात फ़ंक्शन को परिभाषित करते हैं, जो एक [[परवलय]] द्वारा फ़ंक्शन के ग्राफ़ का अनुमान लगाता है। यह मुलर की विधि है.
+दो मान किसी फ़ंक्शन को डिग्री एक के बहुपद द्वारा इंटरपोलेशन करने की अनुमति देते हैं (अर्थात फ़ंक्शन के ग्राफ़ को एक रेखा द्वारा एप्रोक्सीमेट करना)। यह सेकेंट विधि का आधार है। तीन मान एक द्विघात फ़ंक्शन को परिभाषित करते हैं, जो एक [[परवलय]] द्वारा फ़ंक्शन के ग्राफ़ का अनुमान लगाता है। यह मुलर की एक विधि होती है।
-रेगुला फाल्सी भी एक प्रक्षेप विधि है, जो एक रेखा द्वारा प्रक्षेप करने के लिए, दो बिंदुओं का उपयोग करके सेकेंट विधि से भिन्न होती है, जो जरूरी नहीं कि अंतिम दो गणना बिंदु हों।
+रेगुला फाल्सी भी एक इंटरपोलेशन विधि है, जो एक रेखा द्वारा इंटरपोलेशन करने के लिए, दो बिंदुओं का उपयोग करके सेकेंट विधि से भिन्न होती है, जो जरूरी नहीं कि अंतिम दो गणना बिंदु हों।
 == पुनरावृत्त विधियाँ ==
-हालाँकि सभी रूट-फाइंडिंग एल्गोरिदम पुनरावृत्ति द्वारा आगे बढ़ते हैं, एक पुनरावृत्त विधि रूट-फाइंडिंग विधि आम तौर पर एक विशिष्ट प्रकार के पुनरावृत्ति का उपयोग करती है, जिसमें एक सहायक फ़ंक्शन को परिभाषित करना शामिल होता है, जिसे एक नया सन्निकटन प्राप्त करने के लिए रूट के अंतिम गणना किए गए अनुमानों पर लागू किया जाता है। पुनरावृत्ति तब रुक जाती है जब सहायक फ़ंक्शन का एक [[निश्चित-बिंदु पुनरावृत्ति]] (वांछित परिशुद्धता [[तक]]) पहुंच जाता है, अर्थात जब नया गणना मूल्य पिछले वाले के पर्याप्त करीब होता है।
+यघपि सभी रूट-फाइंडिंग एल्गोरिदम पुनरावृत्ति द्वारा आगे बढ़ते हैं, एक पुनरावृत्त विधि रूट-फाइंडिंग विधि सामान्यतः एक विशिष्ट प्रकार के पुनरावृत्ति का उपयोग करती है, जिसमें एक सहायक फ़ंक्शन को परिभाषित करना सम्मलित होती है, जिसे एक नया सन्निकटन प्राप्त करने के लिए रूट के अंतिम गणना किए गए एप्रोक्सीमेट पर प्रयुक्त किया जाता है। पुनरावृत्ति तब रुक जाती है जब सहायक फ़ंक्शन का एक [[निश्चित-बिंदु पुनरावृत्ति|फिक्स्ड पॉइंट पुनरावृत्ति]] पहुंच जाता है, अर्थात जब नया गणना रूट्स पिछले वाले के पर्याप्त समीप होता है।
-=== न्यूटन की विधि (और समान व्युत्पन्न-आधारित विधियाँ) ===
+=== न्यूटन की विधि (और समान डेरीवेटिव-आधारित विधियाँ) ===
-न्यूटन की विधि फलन f को एक सतत अवकलज मानती है। यदि जड़ से बहुत दूर से प्रारंभ किया गया तो न्यूटन की विधि अभिसरित नहीं हो सकेगी। हालाँकि, जब यह अभिसरण होता है, तो यह द्विभाजन विधि से तेज़ होता है, और आमतौर पर द्विघात होता है। न्यूटन की विधि इसलिए भी महत्वपूर्ण है क्योंकि यह उच्च-आयामी समस्याओं को आसानी से सामान्यीकृत करती है। अभिसरण के उच्च क्रम वाली न्यूटन-जैसी विधियाँ हाउसहोल्डर की विधियाँ हैं। न्यूटन की विधि के बाद पहली विधि अभिसरण के घन क्रम वाली हैली की विधि है।
+न्यूटन की विधि फलन f को एक सतत डेरीवेटिव मानती है। यदि रूट से बहुत दूर से प्रारंभ किया गया तो न्यूटन की विधि कनवर्ज नहीं हो सकेगी। यघपि, जब यह कन्वर्जेज़ होता है, तो यह द्विभाजन विधि से शीघ्र होता है, और सामान्यतः द्विघात होता है। न्यूटन की विधि इसलिए भी महत्वपूर्ण है क्योंकि यह उच्च-आयामी समस्याओं को आसानी से सामान्यीकृत करती है। कन्वर्जेज़ के उच्च क्रम वाली न्यूटन-जैसी विधियाँ हाउसहोल्डर की विधियाँ हैं। न्यूटन की विधि के बाद प्रथम विधि कन्वर्जेज़ के क्यूबिक क्रम वाली हैली की विधि होती है।
-=== छेदक विधि ===
+=== सेकेण्ट विधि ===
-न्यूटन की विधि में व्युत्पन्न को एक सीमित अंतर के साथ प्रतिस्थापित करने पर, हमें छेदक विधि प्राप्त होती है। इस पद्धति में किसी व्युत्पन्न की गणना (न ही अस्तित्व) की आवश्यकता होती है, लेकिन कीमत धीमी गति से अभिसरण होती है (ऑर्डर लगभग 1.6 ([[सुनहरा अनुपात]]) है)। उच्च आयामों में सेकेंट विधि का सामान्यीकरण ब्रोयडेन की विधि है।
+न्यूटन की विधि में डेरीवेटिव को एक सीमित अंतर के साथ प्रतिस्थापित करने पर, हमें सेकेण्ट विधि प्राप्त होती है। इस पद्धति में किसी डेरीवेटिव की गणना (न ही अस्तित्व) की आवश्यकता होती है, परन्तु मूल्य धीमी गति से कन्वर्जेज़ होती है (ऑर्डर लगभग 1.6 ([[सुनहरा अनुपात]]) है)। उच्च आयामों में सेकेंट विधि का सामान्यीकरण ब्रोयडेन की विधि होती है।
 === स्टीफ़ेंसन की विधि ===
-यदि हम सेकेंट विधि में प्रयुक्त परिमित अंतर के द्विघात भाग को हटाने के लिए एक बहुपद फिट का उपयोग करते हैं, ताकि यह व्युत्पन्न का बेहतर अनुमान लगा सके, तो हमें स्टेफेंसन की विधि प्राप्त होती है, जिसमें द्विघात अभिसरण होता है, और जिसका व्यवहार (अच्छा और बुरा दोनों) अनिवार्य रूप से होता है न्यूटन की विधि के समान लेकिन इसके लिए किसी व्युत्पन्न की आवश्यकता नहीं है।
+यदि हम सेकेंट विधि में प्रयुक्त परिमित अंतर के द्विघात भाग को हटाने के लिए एक बहुपद फिट का उपयोग करते हैं, जिससे यह डेरीवेटिव का बेहतर अनुमान लगा सके, तो हमें स्टेफेंसन की विधि प्राप्त होती है, जिसमें द्विघात कन्वर्जेज़ होता है, और जिसका व्यवहार (अच्छा और बुरा दोनों) अनिवार्य रूप से होता है न्यूटन की विधि के समान परन्तु इसके लिए किसी डेरीवेटिव की आवश्यकता नहीं होती है।
-=== निश्चित बिंदु पुनरावृत्ति विधि ===
+=== फिक्स्ड पॉइंट पुनरावृत्ति विधि ===
-हम किसी फ़ंक्शन का मूल ज्ञात करने के लिए निश्चित-बिंदु पुनरावृत्ति का उपयोग कर सकते हैं। एक फ़ंक्शन दिया गया <math> f(x) </math> जिसे हमने मूल ज्ञात करने के लिए शून्य पर सेट किया है (<math> f(x)=0 </math>), हम समीकरण को फिर से लिखते हैं <math> x </math> ताकि <math> f(x)=0 </math> बन जाता है <math> x=g(x) </math> (ध्यान दें, अक्सर बहुत सारे होते हैं <math> g(x) </math> प्रत्येक के लिए कार्य <math> f(x)=0 </math> समारोह)। इसके बाद, हम समीकरण के प्रत्येक पक्ष को इस प्रकार पुनः लेबल करते हैं <math> x_{n+1}=g(x_{n}) </math> ताकि हम पुनरावृत्ति कर सकें। इसके बाद, हम इसके लिए एक मान चुनते हैं <math> x_{1} </math> और पुनरावृत्ति तब तक करें जब तक यह फ़ंक्शन की जड़ की ओर परिवर्तित न हो जाए। यदि पुनरावृत्ति अभिसरण होती है, तो यह जड़ में परिवर्तित हो जाएगी। पुनरावृत्ति केवल तभी एकत्रित होगी यदि <math> |g'(root)|<1 </math>.
+हम किसी फ़ंक्शन का रूट ज्ञात करने के लिए फिक्स्ड-पॉइंट पुनरावृत्ति का उपयोग कर सकते हैं। एक फ़ंक्शन <math> f(x) </math> दिया गया जिसे हमने रूट ज्ञात करने के लिए शून्य (<math> f(x)=0 </math>) पर सेट किया जाता है, हम समीकरण <math> x </math> को फिर से लिखते हैं जिससे <math> f(x)=0 </math> होता है जी <math> x=g(x) </math> बन जाता है (ध्यान दें, अधिकांशतः बहुत सारे <math> f(x)=0 </math> फंक्शन के लिए <math> g(x) </math>फंक्शन होते है)। इसके पश्चात्, हम समीकरण के प्रत्येक पक्ष को इस प्रकार <math> x_{n+1}=g(x_{n}) </math> पुनः लेबल करते हैं जिससे हम पुनरावृत्ति कर सकें। इसके पश्चात्, हम इसके लिए एक मान <math> x_{1} </math> चयन करते हैं और पुनरावृत्ति तब तक करें जब तक यह फ़ंक्शन की रूट की ओर परिवर्तित न हो जाए। यदि पुनरावृत्ति कन्वर्जेज़ होती है, तो यह रूट में परिवर्तित हो जाएगी। पुनरावृत्ति मात्र तभी एकत्रित होगी यदि <math> |g'(root)|<1 </math> होता है।
-परिवर्तित करने के उदाहरण के रूप में <math> f(x)=0 </math> को <math> x=g(x) </math>, यदि फ़ंक्शन दिया गया है <math> f(x)=x^2+x-1 </math>, हम इसे निम्नलिखित समीकरणों में से एक के रूप में फिर से लिखेंगे।
+परिवर्तित करने के उदाहरण के रूप में <math> f(x)=0 </math> को <math> x=g(x) </math>, यदि फ़ंक्शन <math> f(x)=x^2+x-1 </math>दिया गया है, हम इसे निम्नलिखित समीकरणों में से एक के रूप में फिर से लिखेंगे।
 :<math> x_{n+1}=(1/x_n) - 1 </math>,
 :<math> x_{n+1}=1/(x_n+1) </math>,
@@ Line 51: / Line 54: @@
 :<math> x_{n+1}=\pm \sqrt{1-x_n} </math>.
-=== व्युत्क्रम प्रक्षेप ===
+=== डेरीवेटिव इंटरपोलेशन ===
-प्रक्षेप विधियों में जटिल मानों की उपस्थिति को एफ के व्युत्क्रम फ़ंक्शन को प्रक्षेपित करके टाला जा सकता है, जिसके परिणामस्वरूप [[व्युत्क्रम द्विघात प्रक्षेप]] विधि प्राप्त होती है। फिर से, अभिसरण सेकेंट विधि की तुलना में स्पर्शोन्मुख रूप से तेज है, लेकिन व्युत्क्रम द्विघात प्रक्षेप अक्सर खराब व्यवहार करता है जब पुनरावृत्त जड़ के करीब नहीं होते हैं।
+इंटरपोलेशन विधियों में काम्प्लेक्स मानों की उपस्थिति को एफ के डेरीवेटिव फ़ंक्शन को इंटरपोलेशन करके अवॉयड किया जा सकता है, जिसके परिणामस्वरूप [[व्युत्क्रम द्विघात प्रक्षेप|डेरीवेटिव द्विघात इंटरपोलेशन]] विधि प्राप्त होती है। फिर से, कन्वर्जेज़ सेकेंट विधि की तुलना में स्पर्शोन्मुख रूप से शीघ्र होता है, परन्तु डेरीवेटिव द्विघात इंटरपोलेशन अधिकांशत अनुपयुक्त व्यवहार करता है जब पुनरावृत्त रूट के क्लोज नहीं होते हैं।
 == विधियों का संयोजन ==
 === ब्रेंट की विधि ===
-ब्रेंट की विधि द्विभाजन विधि, छेदक विधि और व्युत्क्रम द्विघात प्रक्षेप का एक संयोजन है। प्रत्येक पुनरावृत्ति पर, ब्रेंट की विधि यह तय करती है कि इन तीनों में से कौन सी विधि सबसे अच्छा काम करेगी, और उस विधि के अनुसार एक कदम उठाकर आगे बढ़ती है। यह एक मजबूत और तेज़ तरीका देता है, जो काफी लोकप्रिय है।
+ब्रेंट की विधि द्विभाजन विधि, सेकेण्ट विधि और डेरीवेटिव द्विघात इंटरपोलेशन का एक संयोजन है। प्रत्येक पुनरावृत्ति पर, ब्रेंट की विधि यह तय करती है कि इन तीनों में से कौन सी विधि सबसे अच्छा काम करेगी, और उस विधि के अनुसार एक कदम उठाकर आगे बढ़ती है। यह एक रोबस्ट और फ़ास्ट विधि होती है, जो अत्यधिक लोकप्रिय होती है।
 === रिडर्स विधि ===
-रिडर्स विधि एक हाइब्रिड विधि है जो रूट पर घातांकीय प्रक्षेप करने के लिए अंतराल के मध्य बिंदु पर फ़ंक्शन के मान का उपयोग करती है। यह द्विभाजन विधि के रूप में पुनरावृत्तियों की अधिकतम दोगुनी संख्या के गारंटीकृत अभिसरण के साथ एक तेज़ अभिसरण देता है।
+रिडर्स विधि एक हाइब्रिड विधि है जो रूट पर घातांकीय इंटरपोलेशन करने के लिए इंटरवेल के मध्य बिंदु पर फ़ंक्शन के मान का उपयोग करती है। यह द्विभाजन विधि के रूप में पुनरावृत्तियों की अधिकतम दोगुनी संख्या के गारंटी कन्वर्जेज़ के साथ एक फ़ास्ट कन्वर्जेज़ देता है।
-== बहुपदों की जड़ें ==
-{{excerpt|Polynomial root-finding algorithms}}
-== उच्च आयामों में जड़ें ढूँढना ==
+== पोलीनोमियल की रूट ==
+पोलीनोमियल रूट फाइंडिंग एक लंबे समय से चली आ रही समस्या है जो पूरे इतिहास में बहुत शोध का विषय रही है। इसका एक प्रमाण यह है कि 19वीं सदी तक बीजगणित का अर्थ अनिवार्य रूप से पोलीनोमियल समीकरणों का सिद्धांत था।
-द्विभाजन विधि को उच्च आयामों के लिए सामान्यीकृत किया गया है; इन विधियों को सामान्यीकृत द्विभाजन विधियाँ कहा जाता है।<ref name=":0">{{Cite journal |last1=Mourrain |first1=B. |last2=Vrahatis |first2=M. N. |last3=Yakoubsohn |first3=J. C. |date=2002-06-01 |title=वास्तविक जड़ों को अलग करने और निश्चितता के साथ टोपोलॉजिकल डिग्री की गणना करने की जटिलता पर|url=https://www.sciencedirect.com/science/article/pii/S0885064X01906363 |journal=Journal of Complexity |language=en |volume=18 |issue=2 |pages=612–640 |doi=10.1006/jcom.2001.0636 |issn=0885-064X}}</ref><ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=2020 |editor-last=Sergeyev |editor-first=Yaroslav D. |editor2-last=Kvasov |editor2-first=Dmitri E. |title=सतत कार्यों के निश्चित बिंदुओं और शून्यों का अनुमान लगाने के लिए मध्यवर्ती मूल्य प्रमेय का सामान्यीकरण|url=https://link.springer.com/chapter/10.1007/978-3-030-40616-5_17 |journal=Numerical Computations: Theory and Algorithms |series=Lecture Notes in Computer Science |language=en |location=Cham |publisher=Springer International Publishing |volume=11974 |pages=223–238 |doi=10.1007/978-3-030-40616-5_17 |isbn=978-3-030-40616-5 |s2cid=211160947}}</ref> प्रत्येक पुनरावृत्ति पर, डोमेन को दो भागों में विभाजित किया जाता है, और एल्गोरिदम निर्णय लेता है - फ़ंक्शन मूल्यांकन की एक छोटी संख्या के आधार पर - इन दोनों भागों में से किसमें रूट होना चाहिए। एक आयाम में, निर्णय की कसौटी यह है कि फ़ंक्शन में विपरीत संकेत होते हैं। विधि को कई आयामों तक विस्तारित करने में मुख्य चुनौती एक ऐसा मानदंड ढूंढना है जिसकी गणना आसानी से की जा सके, और जड़ के अस्तित्व की गारंटी दे।
+== उच्च आयामों में रूट फाइंडिंग ==
+द्विभाजन विधि को उच्च आयामों के लिए सामान्यीकृत किया गया है; इन विधियों को सामान्यीकृत द्विभाजन विधियाँ कहा जाता है।<ref name=":0">{{Cite journal |last1=Mourrain |first1=B. |last2=Vrahatis |first2=M. N. |last3=Yakoubsohn |first3=J. C. |date=2002-06-01 |title=वास्तविक जड़ों को अलग करने और निश्चितता के साथ टोपोलॉजिकल डिग्री की गणना करने की जटिलता पर|url=https://www.sciencedirect.com/science/article/pii/S0885064X01906363 |journal=Journal of Complexity |language=en |volume=18 |issue=2 |pages=612–640 |doi=10.1006/jcom.2001.0636 |issn=0885-064X}}</ref><ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=2020 |editor-last=Sergeyev |editor-first=Yaroslav D. |editor2-last=Kvasov |editor2-first=Dmitri E. |title=सतत कार्यों के निश्चित बिंदुओं और शून्यों का अनुमान लगाने के लिए मध्यवर्ती मूल्य प्रमेय का सामान्यीकरण|url=https://link.springer.com/chapter/10.1007/978-3-030-40616-5_17 |journal=Numerical Computations: Theory and Algorithms |series=Lecture Notes in Computer Science |language=en |location=Cham |publisher=Springer International Publishing |volume=11974 |pages=223–238 |doi=10.1007/978-3-030-40616-5_17 |isbn=978-3-030-40616-5 |s2cid=211160947}}</ref> प्रत्येक पुनरावृत्ति पर, डोमेन को दो भागों में विभाजित किया जाता है, और एल्गोरिदम निर्णय लेता है - फ़ंक्शन मुल्यांकन की एक छोटी संख्या के आधार पर - इन दोनों भागों में से किसमें रूट होना चाहिए। एक आयाम में, निर्णय की मानदंड यह है कि फ़ंक्शन में विपरीत संकेत होते हैं। विधि को कई आयामों तक विस्तारित करने में मुख्य चुनौती एक ऐसा मानदंड फाइंडिंग होता है जिसकी गणना आसानी से की जा सके, और जो रूट के अस्तित्व की गारंटी दे सके।
-पोंकारे-मिरांडा प्रमेय एक आयत में जड़ के अस्तित्व के लिए एक मानदंड देता है, लेकिन इसे सत्यापित करना कठिन है, क्योंकि इसके लिए त्रिभुज की संपूर्ण सीमा पर फ़ंक्शन का मूल्यांकन करना आवश्यक है।
+पोंकारे-मिरांडा प्रमेय एक आयत में रूट के अस्तित्व के लिए एक मानदंड देता है, परन्तु इसे सत्यापित करना कठिन है, क्योंकि इसके लिए त्रिभुज की संपूर्ण लिमिट पर फ़ंक्शन का मुल्यांकन करना आवश्यक होता है।
-एक अन्य मानदंड क्रोनकर के एक प्रमेय द्वारा दिया गया है।<ref>{{Cite web |title=कई चरों में अरेखीय समीकरणों का पुनरावृत्तीय समाधान|url=https://dl.acm.org/doi/abs/10.5555/335947 |access-date=2023-04-16 |website=Guide books |language=EN }}</ref> इसमें कहा गया है कि, यदि किसी आयत पर फ़ंक्शन f की निरंतर मैपिंग की डिग्री गैर-शून्य है, तो आयत में f की कम से कम एक जड़ होनी चाहिए। यह मानदंड कई जड़-खोज विधियों का आधार है, जैसे कि स्टेंगर द्वारा<ref>{{Cite journal |last=Stenger |first=Frank |date=1975-03-01 |title=मैपिंग इनआरएन की टोपोलॉजिकल डिग्री की गणना करना|url=https://doi.org/10.1007/BF01419526 |journal=Numerische Mathematik |language=en |volume=25 |issue=1 |pages=23–38 |doi=10.1007/BF01419526 |s2cid=122196773 |issn=0945-3245}}</ref> और केयरफोट.<ref>{{Cite journal |last=Kearfott |first=Baker |date=1979-06-01 |title=द्विभाजन की सामान्यीकृत विधि के लिए एक कुशल डिग्री-गणना विधि|url=https://doi.org/10.1007/BF01404868 |journal=Numerische Mathematik |volume=32 |issue=2 |pages=109–127 |doi=10.1007/BF01404868 |s2cid=122058552 |issn=0029-599X}}</ref> हालाँकि, टोपोलॉजिकल डिग्री की गणना करने में समय लग सकता है।
+एक अन्य मानदंड क्रोनकर के एक प्रमेय द्वारा दिया गया है।<ref>{{Cite web |title=कई चरों में अरेखीय समीकरणों का पुनरावृत्तीय समाधान|url=https://dl.acm.org/doi/abs/10.5555/335947 |access-date=2023-04-16 |website=Guide books |language=EN }}</ref> इसमें कहा गया है कि, यदि किसी आयत पर फ़ंक्शन f की निरंतर मैपिंग की डिग्री गैर-शून्य है, तो आयत में f की कम से कम एक रूट होनी चाहिए। यह मानदंड कई रूट-फाइंडिंग विधियों का आधार होता है, जैसे कि स्टेंगर द्वारा<ref>{{Cite journal |last=Stenger |first=Frank |date=1975-03-01 |title=मैपिंग इनआरएन की टोपोलॉजिकल डिग्री की गणना करना|url=https://doi.org/10.1007/BF01419526 |journal=Numerische Mathematik |language=en |volume=25 |issue=1 |pages=23–38 |doi=10.1007/BF01419526 |s2cid=122196773 |issn=0945-3245}}</ref> और केयरफोट द्वारा।<ref>{{Cite journal |last=Kearfott |first=Baker |date=1979-06-01 |title=द्विभाजन की सामान्यीकृत विधि के लिए एक कुशल डिग्री-गणना विधि|url=https://doi.org/10.1007/BF01404868 |journal=Numerische Mathematik |volume=32 |issue=2 |pages=109–127 |doi=10.1007/BF01404868 |s2cid=122058552 |issn=0029-599X}}</ref> यघपि, टोपोलॉजिकल डिग्री की गणना करने में समय लग सकता है।
-तीसरा मानदंड एक विशिष्ट बहुफलक पर आधारित है। इस मानदंड का उपयोग कैरेक्टरिस्टिक बिसेक्शन नामक विधि द्वारा किया जाता है।<ref name=":0" />{{Rp|page=19--}} इसमें टोपोलॉजिकल डिग्री की गणना करने की आवश्यकता नहीं है - इसमें केवल फ़ंक्शन मानों के संकेतों की गणना करने की आवश्यकता है। आवश्यक मूल्यांकनों की संख्या कम से कम है <math>\log_2(D/\epsilon)</math>, जहां D विशिष्ट बहुफलक के सबसे लंबे किनारे की लंबाई है।<ref name=":2">{{Cite journal |last=Vrahatis |first=M. N. |last2=Iordanidis |first2=K. I. |date=1986-03-01 |title=गैर-रेखीय समीकरणों की प्रणालियों को हल करने के लिए द्विभाजन की एक तीव्र सामान्यीकृत विधि|url=https://doi.org/10.1007/BF01389620 |journal=Numerische Mathematik |language=en |volume=49 |issue=2 |pages=123–138 |doi=10.1007/BF01389620 |issn=0945-3245}}</ref>{{Rp|page=11|location=Lemma.4.7}} ध्यान दें कि <ref name=":2" />मूल्यांकनों की संख्या पर निचली सीमा साबित करें, न कि ऊपरी सीमा।
+तीसरा मानदंड एक विशिष्ट बहुफलक पर आधारित है। इस मानदंड का उपयोग कैरेक्टरिस्टिक बिसेक्शन नामक विधि द्वारा किया जाता है।<ref name=":0" />{{Rp|page=19--}} इसमें टोपोलॉजिकल डिग्री की गणना करने की आवश्यकता नहीं है - इसमें मात्र फ़ंक्शन मानों के संकेतों की गणना करने की आवश्यकता होती है। आवश्यक मुल्यांकनों की संख्या कम से कम <math>\log_2(D/\epsilon)</math>होती है, जहां D विशिष्ट बहुफलक के सबसे लंबे किनारे की लंबाई है।<ref name=":2">{{Cite journal |last=Vrahatis |first=M. N. |last2=Iordanidis |first2=K. I. |date=1986-03-01 |title=गैर-रेखीय समीकरणों की प्रणालियों को हल करने के लिए द्विभाजन की एक तीव्र सामान्यीकृत विधि|url=https://doi.org/10.1007/BF01389620 |journal=Numerische Mathematik |language=en |volume=49 |issue=2 |pages=123–138 |doi=10.1007/BF01389620 |issn=0945-3245}}</ref>{{Rp|page=11|location=Lemma.4.7}} ध्यान दें कि <ref name=":2" />मुल्यांकनों की संख्या पर निचली लिमिट सिद्ध करें, न कि ऊपरी लिमिट।
-चौथी विधि सरलताओं पर एक मध्यवर्ती-मूल्य प्रमेय का उपयोग करती है।<ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=2020-04-15 |title=निश्चित बिंदुओं और शून्यों के सरल सन्निकटन के लिए सरलताओं के लिए मध्यवर्ती मूल्य प्रमेय|url=https://www.sciencedirect.com/science/article/pii/S0166864119304420 |journal=Topology and its Applications |language=en |volume=275 |pages=107036 |doi=10.1016/j.topol.2019.107036 |issn=0166-8641}}</ref> फिर, प्रश्नों की संख्या पर कोई ऊपरी सीमा नहीं दी गई है।
+चौथी विधि सरलताओं पर एक मध्यवर्ती-रूट्स प्रमेय का उपयोग करती है।<ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=2020-04-15 |title=निश्चित बिंदुओं और शून्यों के सरल सन्निकटन के लिए सरलताओं के लिए मध्यवर्ती मूल्य प्रमेय|url=https://www.sciencedirect.com/science/article/pii/S0166864119304420 |journal=Topology and its Applications |language=en |volume=275 |pages=107036 |doi=10.1016/j.topol.2019.107036 |issn=0166-8641}}</ref> फिर, प्रश्नों की संख्या पर कोई ऊपरी लिमिट नहीं दी गई है।
 == यह भी देखें ==
 {{cols}}
-* [[रूट खोज एल्गोरिदम की सूची]]
+* [[रूट फाइंडिंग एल्गोरिदम की लिस्ट]]
-* [[निश्चित-बिंदु गणना]]
+* [[फिक्स्ड-पॉइंट कम्प्यूटेशन]]
-{{annotated link|Broyden's method}}
+{{annotated link|ब्रोयडेन की विधि}}
-* {{annotated link|Cryptographically secure pseudorandom number generator}}
+* {{annotated link|क्रिप्टोग्राफ़िक रूप से सुरक्षित जनरेटर स्यूडो रैंडम}}
 * [[जीएनयू वैज्ञानिक पुस्तकालय]]
-* {{annotated link|Graeffe's method}}
+* {{annotated link|ग्रेफ़ की विधि}}
-* {{annotated link|Lill's method}}
+* {{annotated link|लिल की विधि}}
-* {{annotated link|MPSolve}}
+* {{annotated link|एमपीसॉल्व}}
 * {{annotated link|Multiplicity (mathematics)}}
 * Nवां रूट एल्गोरिथम|{{math|''n''}}वें रूट एल्गोरिथ्म
-* {{annotated link|System of polynomial equations}}
+* {{annotated link|पोलीनोमियल समीकरण का सिस्टम }}
-* {{annotated link|Kantorovich theorem}}
+* {{annotated link|कांटोरोविच थ्योरम }}
 {{colend}}

v t e Root-finding algorithms
Bracketing (no derivative)	Bisection method Regula falsi ITP Method
Newton	Newton's method
Quasi-Newton	Muller's method Secant method
Hybrid methods	Brent's method Ridders' method
Polynomial methods	Bairstow's method Jenkins–Traub method Laguerre's method

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 13:59, 3 August 2023

Contents

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

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

फाल्स पोजीशन (रेगुला फाल्सी)

आईटीपी विधि

इंटरपोलेशन

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

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

सेकेण्ट विधि

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

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

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

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

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

रिडर्स विधि

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 13:59, 3 August 2023

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

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

फाल्स पोजीशन (रेगुला फाल्सी)

आईटीपी विधि

इंटरपोलेशन

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

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

सेकेण्ट विधि

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

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

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

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

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

रिडर्स विधि

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Hidden categories