न्यूटन की विधि

This article is about मूल खोजने की न्यूटन की विधि. For न्यूनतम खोजने के लिए न्यूटन की विधि, see अनुकूलन में न्यूटन की विधि.

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

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}$

मूल का x₀ से उत्तम सन्निकटन है। ज्यामितीय रूप से, (x₁, 0) x-अक्ष का प्रतिच्छेदन है और (x₀, f(x₀)) पर f के ग्राफ की स्पर्शरेखा है, जो कि उत्रतम अनुमान है, प्रारंभिक बिंदु पर रैखिक सन्निकटन की अद्वितीय मूल है। प्रक्रिया के रूप में दोहराया जाता है

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$

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

विवरण

विचार प्रारंभिक अनुमान के साथ प्रारंभ करना है, फिर इसकी स्पर्शरेखा रेखा द्वारा फलन को अनुमानित करना और अंत में इसकी गणना करना है x-इस स्पर्श रेखा का अवरोधन। यह x-अवरोधन सामान्यतः पहले अनुमान की तुलना में मूल फलन की मूल के लिए उत्तम सन्निकटन होगा, और विधि पुनरावृत्त विधि हो सकती है।

यदि वक्र को स्पर्शरेखा रेखा f(x) पर x = x_n इंटरसेप्ट करता है x-अक्ष पर x_n+1 तो प्रवणता है

$f'(x_{n})={\dfrac {f(x_{n})-0}{x_{n}-x_{n+1}}}$.

x_n+1 के लिए समाधान करना देता है

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.$

हम कुछ स्वैच्छिक प्रारंभिक मान x₀ के साथ प्रक्रिया प्रारंभ करते हैं। (शून्य के जितना निकट हो उतना बेहतर है। किन्तु, शून्य कहां हो सकता है, इसके बारे में किसी भी अंतर्ज्ञान की अनुपस्थिति में, "अनुमान और जांच" विधि मध्यवर्ती मान प्रमेय की अपील करके संभावनाओं को यथोचित छोटे अंतराल तक सीमित कर सकती है।) विधि सामान्यतः अभिसरण होगा, बशर्ते यह प्रारंभिक अनुमान अज्ञात शून्य के काफी निकट हो, और वह f′(x₀) ≠ 0. इसके अलावा, बहुलता (गणित) 1 के शून्य के लिए, अभिसरण शून्य के निकट (गणित) में कम से कम द्विघात (अभिसरण की दर देखें) है, जिसका सहज अर्थ है कि प्रत्येक चरण में सही अंकों की संख्या सामान्यतः दोगुनी हो जाती है। अधिक विवरण नीचे § विश्लेषण में पाया जा सकता है।

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

इतिहास

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

हो सकता है कि न्यूटन ने अपनी पद्धति फ्रांसिस लाइफ द्वारा समान, कम त्रुटिहीन विधि से प्राप्त की हो। मध्यकालीन इस्लाम शराफ अल-दीन अल-तुसी में गणित के काम में वीटा की पद्धति का सार पाया जा सकता है, जबकि उनके उत्तराधिकारी जमशीद अल-काशी ने समाधान करने के लिए न्यूटन की विधि का रूप इस्तेमाल किया x^P − N = 0 की मूले खोजने के लिए N (वाईपीएमए 1995)। वर्गमूलों की गणना के लिए न्यूटन की विधि का विशेष मामला प्राचीन काल से जाना जाता था और इसे अक्सर बेबीलोनियन विधि कहा जाता है।

17वीं शताब्दी के जापानी गणितज्ञ सेकी कोवा द्वारा एकल-चर समीकरणों को समाधान करने के लिए न्यूटन की विधि का उपयोग किया गया था, चूंकि कलन के साथ संबंध गायब था। न्यूटन की विधि पहली बार 1685 में जॉन वालिस द्वारा हिस्टोरिकल एंड प्रैक्टिकल दोनों में बीजगणित के ग्रंथ में प्रकाशित हुई थी। 1690 में, जोसेफ रैफसन ने सार्वभौम समीकरणों के विश्लेषण में सरलीकृत विवरण प्रकाशित किया। रैफसन ने भी इस विधि को केवल बहुपदों पर प्रायुक्त किया, किन्तु उन्होंने मूल बहुपद से प्रत्येक क्रमिक सुधार को निकाल कर न्यूटन की थकाऊ पुनर्लेखन प्रक्रिया से परहेज किया। इसने उन्हें प्रत्येक समस्या के लिए पुन: प्रयोज्य पुनरावृत्त अभिव्यक्ति प्राप्त करने की अनुमति दी। अंत में, 1740 में, थॉमस सिम्पसन ने न्यूटन की विधि को कैलकुलस का उपयोग करके सामान्य अरैखिक समीकरणों को समाधान करने के लिए पुनरावृत्ति विधि के रूप में वर्णित किया, अनिवार्य रूप से उपरोक्त विवरण दिया। उसी प्रकाशन में, सिम्पसन भी दो समीकरणों की प्रणालियों का सामान्यीकरण करता है और नोट करता है कि न्यूटन की विधि का उपयोग ढाल को शून्य पर सेट करके अनुकूलन समस्याओं को समाधान करने के लिए किया जा सकता है।

न्यूटन-फूरियर काल्पनिक समस्या में 1879 में आर्थर केली 2 से अधिक डिग्री और जटिल प्रारंभिक मानों वाले बहुपदों की जटिल मूलों के लिए न्यूटन की विधि को सामान्य बनाने में कठिनाइयों पर ध्यान देने वाले पहले व्यक्ति थे। इसने तर्कसंगत कार्यों के जूलिया सेट के अध्ययन का रास्ता खोल दिया।

व्यावहारिक विचार

न्यूटन की विधि शक्तिशाली तकनीक है - सामान्यतः अभिसरण की दर द्विघात होती है: जैसे-जैसे विधि मूल पर अभिसरण करती है, मूल और सन्निकटन के बीच का अंतर चुकता होता है (त्रुटिहीन अंकों की संख्या सामान्यतः दोगुनी हो जाती है)। चूँकि, विधि के साथ कुछ कठिनाइयाँ हैं।

किसी फलन के व्युत्पन्न की गणना करने में कठिनाई

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

मूल में एकाग्र होने की विधि की विफलता

इसे प्रायुक्त करने से पहले न्यूटन की न्यूटन की विधि के पुनरावृत्त विधि के लिए द्विघात अभिसरण के प्रमाण की समीक्षा करना महत्वपूर्ण है। विशेष रूप से, किसी को प्रमाण में की गई धारणाओं की समीक्षा करनी चाहिए। #विफलता विश्लेषण के लिए, ऐसा इसलिए है क्योंकि इस प्रमाण में की गई धारणाएँ पूरी नहीं हुई हैं।

ओवरशूट

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

$f(x)=|x|^{a},\quad 0<a<{\tfrac {1}{2}}$

जिसके लिए मूल ओवरशूट होगा और का क्रम x विचलन करेगा। के लिए a = 1/2, मूल अभी भी ओवरशूट होगा, किन्तु अनुक्रम दो मानों के बीच दोलन करेगा। के लिए 1/2 < a < 1, मूल अभी भी ओवरशूट होगा किन्तु अनुक्रम अभिसरण करेगा, और के लिए a ≥ 1 मूल बिल्कुल भी ओवरशूट नहीं होगा।

कुछ स्थितियों में, क्रमिक अति-विश्राम#विधि के अन्य अनुप्रयोगों|क्रमिक अति-विश्राम का उपयोग करके न्यूटन की विधि को स्थिर किया जा सकता है, या समान विधि का उपयोग करके अभिसरण की गति को बढ़ाया जा सकता है।

स्थिर बिंदु

यदि फलन का स्थिर बिंदु सामने आया है, तो व्युत्पन्न शून्य है और शून्य से विभाजन के कारण विधि समाप्त हो जाएगी।

खराब प्रारंभिक अनुमान

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

गैर-अभिसरण का शमन

न्यूटन की विधि के मजबूत कार्यान्वयन में, पुनरावृत्तियों की संख्या पर सीमाएं लगाना आम है, मूल को समाहित करने के लिए ज्ञात अंतराल के समाधान को बाध्य करना, और अधिक मजबूत मूल खोज विधि के साथ विधि को संयोजित करना।

1 से अधिक बहुलता की मूलों के लिए धीमा अभिसरण

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

$x_{n+1}=x_{n}-m{\frac {f(x_{n})}{f'(x_{n})}}.$

यह क्रमिक अति-विश्राम का उपयोग करने के बराबर है। दूसरी ओर, यदि बहुलता m का मूल ज्ञात नहीं है, इसका अनुमान लगाया जा सकता है m या दो पुनरावृत्तियों को पूरा करने के बाद, और फिर अभिसरण की दर बढ़ाने के लिए उस मान का उपयोग करें।

यदि मूल की बहुलता m परिमित है तो g(x) = f(x)/f′(x) की बहुलता 1 के साथ ही स्थान पर मूल होगी। g(x) के मूल को खोजने के लिए न्यूटन की विधि को प्रायुक्त करना ठीक हो जाता है कई स्थितियों में द्विघात अभिसरण चूंकि इसमें सामान्यतः f(x) का दूसरा अवकलज सम्मिलित होता है। विशेष रूप से सरल स्थिति में, यदि f(x) = x^m तब g(x) = x/m और न्यूटन की विधि मूल को एकल पुनरावृत्ति में खोजती है

$x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{\frac {\;{\frac {x_{n}}{m}}\;}{\frac {1}{m}}}=0\,.$

विश्लेषण

मान लीजिए कि फ़ंक्शन f का α पर शून्य है, अर्थात, f(α) = 0, और f, α के टोपोलॉजिकल निकट में अवकलनीय है।

यदि f निरंतर अवकलनीय है और इसका व्युत्पन्न α पर अशून्य है, तो α का सामयिक निकट उपस्थित है जैसे कि सभी प्रारंभिक मानों के लिए x₀ उस निकट में, अनुक्रम (x_n)α अनुक्रम की सीमा को सीमित कर देगा।

यदि f निरंतर अवकलनीय है, इसका व्युत्पन्न α पर अशून्य है, और इसका α पर दूसरा व्युत्पन्न है, तो अभिसरण द्विघात या तेज है। यदि α पर दूसरा व्युत्पन्न 0 नहीं है तो अभिसरण केवल द्विघात है। यदि तीसरा व्युत्पन्न उपस्थित है और α के निकट में घिरा हुआ है , तब:

$\Delta x_{i+1}={\frac {f''(\alpha )}{2f'(\alpha )}}\left(\Delta x_{i}\right)^{2}+O\left(\Delta x_{i}\right)^{3}\,,$

जहाँ

$\Delta x_{i}\triangleq x_{i}-\alpha \,.$

यदि व्युत्पन्न α पर 0 है, तो अभिसरण आमतौर पर केवल रैखिक होता है। विशेष रूप से, यदि f लगातार दो बार भिन्न होता है, f′(α) = 0 और f″(α) ≠ 0, तो α का निकट उपस्थित है α जैसे कि, सभी प्रारंभिक मानों के लिए x₀ उस निकट में, पुनरावृति का क्रम अभिसरण की दर 1/2 के साथ रैखिक रूप से अभिसरित होता है। वैकल्पिक रूप से, यदि f′(α) = 0 और f′(x) ≠ 0 के लिए x ≠ α, x α के सामयिक निकट U में, α बहुलता r का शून्य होना (गणित), और यदि f ∈ C^r(U), तो वहाँ α का निकट उपस्थित है जैसे कि, सभी प्रारंभिक मानों x₀ के लिए उस निकट में, पुनरावृत्तियों का क्रम रैखिक रूप से परिवर्तित होता है।

चूंकि, पैथोलॉजिकल स्थितियों में भी रैखिक अभिसरण की गारंटी नहीं है।

व्यवहार में, ये परिणाम स्थानीय हैं, और अभिसरण का निकट पहले से ज्ञात नहीं है। किन्तु वैश्विक अभिसरण पर भी कुछ परिणाम हैं: उदाहरण के लिए, α का सही निकट U₊ दिया गया है यदि f U₊में दो बार अवकलनीय है और यदि f′ ≠ 0, f · f″ > 0 U₊ में है, तो, U₊ में प्रत्येक x₀ के लिए अनुक्रम x_k मोनोटोनिक रूप से α तक घट रहा है।

न्यूटन की पुनरावृत्ति विधि के लिए द्विघात अभिसरण का प्रमाण

टेलर प्रमेय के अनुसार कोई भी फलन f(x) जिसका लगातार दूसरा अवकलज है, को उस बिंदु के बारे में विस्तार द्वारा दर्शाया जा सकता है जो की मूल f(x) के निकट है। मान लीजिए यह मूल α है। फिर का विस्तार f(α) के बारे में x_n है:

$f(\alpha )=f(x_{n})+f'(x_{n})(\alpha -x_{n})+R_{1}\,$

(1)

जहां लैग्रेंज शेष है

$R_{1}={\frac {1}{2!}}f''(\xi _{n})\left(\alpha -x_{n}\right)^{2}\,,$

जहाँ ξ_n, x_n और α के बीच में है।

तब से α मूल है, (1) बन जाता है:

$0=f(\alpha )=f(x_{n})+f'(x_{n})(\alpha -x_{n})+{\tfrac {1}{2}}f''(\xi _{n})\left(\alpha -x_{n}\right)^{2}\,$

(2)

विभाजित समीकरण (2) द्वारा f′(x_n) और पुनर्व्यवस्थित करता है

${\frac {f(x_{n})}{f'(x_{n})}}+\left(\alpha -x_{n}\right)={\frac {-f''(\xi _{n})}{2f'(x_{n})}}\left(\alpha -x_{n}\right)^{2}$

(3)

यह याद रखना x_{n + 1} द्वारा परिभाषित किया गया है

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\,,$

(4)

पाता है

$\underbrace {\alpha -x_{n+1}} _{\varepsilon _{n+1}}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}{(\,\underbrace {\alpha -x_{n}} _{\varepsilon _{n}}\,)}^{2}\,.$

वह है,

$\varepsilon _{n+1}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}\cdot \varepsilon _{n}^{2}\,.$

(5)

दोनों पक्षों का निरपेक्ष मान लेने पर प्राप्त होता है

$\left|{\varepsilon _{n+1}}\right|={\frac {\left|f''(\xi _{n})\right|}{2\left|f'(x_{n})\right|}}\cdot \varepsilon _{n}^{2}\,.$

(6)

समीकरण (6) दर्शाता है कि अभिसरण का क्रम कम से कम द्विघात है यदि निम्नलिखित शर्तें पूरी होती हैं:

1. f′(x) ≠ 0; सभी के लिए x ∈ I, जहाँ I अंतराल है [α − |ε₀|, α + |ε₀|];
2. f″(x) सभी के लिए निरंतर है x ∈ I;
3. M |ε₀| < 1

जहां एम द्वारा दिया गया है

$M={\frac {1}{2}}\left(\sup _{x\in I}\vert f''(x)\vert \right)\left(\sup _{x\in I}{\frac {1}{\vert f'(x)\vert }}\right).\,$

यदि ये शर्तें बनी रहती हैं,

$\vert \varepsilon _{n+1}\vert \leq M\cdot \varepsilon _{n}^{2}\,.$

आकर्षण का केंद्र

आकर्षण के बेसिन के असंबद्ध उपसमुच्चय - वास्तविक संख्या रेखा के क्षेत्र जैसे कि प्रत्येक क्षेत्र के भीतर किसी भी बिंदु से पुनरावृति विशेष मूल की ओर ले जाती है - संख्या में अनंत और स्वैच्छिक विधि से छोटा हो सकता है। उदाहरण के लिए, फलन के लिए f(x) = x³ − 2x² − 11x + 12 = (x − 4)(x − 1)(x + 3), निम्नलिखित प्रारंभिक स्थितियाँ आकर्षण के क्रमिक आधारों में हैं:

2.35287527	में परिवर्तित होता है	4;
2.35284172	में परिवर्तित होता है	−3;
2.35283735	में परिवर्तित होता है	4;
2.352836327	में परिवर्तित होता है	−3;
2.352836323	में परिवर्तित होता है	1.

विफलता विश्लेषण

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

खराब प्रारंभिक बिंदु

कुछ स्थितियों में फलन पर शर्तें जो अभिसरण के लिए आवश्यक हैं, संतुष्ट हैं, किन्तु प्रारंभिक बिंदु के रूप में चुना गया बिंदु उस अंतराल में नहीं है जहां विधि अभिसरण करती है। यह हो सकता है, उदाहरण के लिए, यदि वह फलन जिसकी मूल खोजी गई है शून्य विषमता के रूप में पहुँचता है क्योंकि x ∞ या −∞ में जाता है। ऐसे स्थितियों में अलग विधि, जैसे कि द्विभाजन विधि, का उपयोग शून्य के प्रारंभिक बिंदु के रूप में उपयोग करने के लिए उत्तम अनुमान प्राप्त करने के लिए किया जाना चाहिए।

पुनरावृति बिंदु स्थिर है

फलन पर विचार करें:

$f(x)=1-x^{2}.$

यह x = 0 पर अधिकतम है और f(x) = 0 का समाधान x = ±1 पर है। अगर हम स्थिर बिंदु x₀ = 0 (जहां व्युत्पन्न शून्य है) से पुनरावृति शुरू करते हैं, तो x₁ अपरिभाषित होगा, क्योंकि (0, 1) पर स्पर्शरेखा x-अक्ष के समानांतर है:

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}=0-{\frac {1}{0}}.$

वही समस्या तब होती है, जब प्रारंभिक बिंदु के अतिरिक्त, कोई पुनरावृत्ति बिंदु स्थिर होता है। यहां तक ​​​​कि यदि व्युत्पन्न छोटा है, किन्तु शून्य नहीं है, तो अगला पुनरावृत्ति बहुत खराब सन्निकटन होगा।

प्रारंभिक बिंदु चक्र में प्रवेश करता है

की स्पर्श रेखाएँ x³ − 2x + 2 पर 0 और 1 प्रतिच्छेद करते हैं x-अक्ष क्रमशः 1 और 0 पर, यह दर्शाता है कि क्यों न्यूटन की विधि कुछ प्रारंभिक बिंदुओं के लिए इन मानों के बीच दोलन करती है।

कुछ कार्यों के लिए, कुछ प्रारंभिक बिंदु अभिसरण को रोकते हुए अनंत चक्र में प्रवेश कर सकते हैं। मान लीजिये

$f(x)=x^{3}-2x+2\!$

और 0 को प्रारंभिक बिंदु के रूप में लें। पहला पुनरावृति 1 उत्पन्न करता है और दूसरा पुनरावृति 0 पर लौटता है, इसलिए अनुक्रम दोनों के बीच मूल में परिवर्तित हुए बिना वैकल्पिक होगा। वास्तव में, यह 2-चक्र स्थिर है: 0 और 1 के आस-पास निकट हैं, जहां से सभी बिंदु 2-चक्र (और इसलिए फलन की मूल तक नहीं) के लिए समान रूप से पुनरावृत्त होते हैं। सामान्य तौर पर, अनुक्रम का व्यवहार बहुत जटिल हो सकता है (न्यूटन फ्रैक्टल देखें)। इस समीकरण का वास्तविक समाधान −1.76929235…. है।

व्युत्पन्न समस्याएँ

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

व्युत्पन्न मूल पर उपस्थित नहीं है

फलन का सरल उदाहरण जहां न्यूटन की विधि विचलन करती है, शून्य का घनमूल खोजने का प्रयास कर रहा है। घनमूल निरंतर और अनंत रूप से अलग-अलग है, को छोड़कर x = 0, जहां इसकी व्युत्पत्ति अपरिभाषित है:

$f(x)={\sqrt[{3}]{x}}.$

किसी भी पुनरावृत्ति बिंदु के लिए x_n, अगला पुनरावृति बिंदु होगा:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {{x_{n}}^{\frac {1}{3}}}{{\frac {1}{3}}{x_{n}}^{-{\frac {2}{3}}}}}=x_{n}-3x_{n}=-2x_{n}.$

एल्गोरिथ्म समाधान को ओवरशूट करता है और y-अक्ष के दूसरी ओर लैंड करता है, प्रारंभ में न्यूटन की विधि को प्रायुक्त करने की तुलना में दूर, वास्तव में प्रत्येक पुनरावृत्ति पर समाधान से दूरी को दोगुना कर देता है।

वास्तव में, प्रत्येक f(x) = |x|^α, जहाँ 0 < α < 1/2 के लिए पुनरावृत्तियाँ अनंत तक जाती हैं। α = 1/2 (वर्गमूल) के सीमित स्थिति में, पुनरावृत्तियाँ बिंदुओं x₀ और −x₀ के बीच अनिश्चित काल तक वैकल्पिक रहेंगी, इसलिए वे इस स्थिति में भी अभिसरण नहीं करते हैं।

असंतुलित व्युत्पन्न

यदि व्युत्पन्न मूल पर निरंतर नहीं है, तो मूल के किसी भी निकट में अभिसरण विफल हो सकता है। फलन पर विचार करें

$f(x)={\begin{cases}0&{\text{if }}x=0,\\x+x^{2}\sin {\frac {2}{x}}&{\text{if }}x\neq 0.\end{cases}}$

इसका व्युत्पन्न है:

$f'(x)={\begin{cases}1&{\text{if }}x=0,\\1+2x\sin {\frac {2}{x}}-2\cos {\frac {2}{x}}&{\text{if }}x\neq 0.\end{cases}}$

मूल के किसी भी निकट के भीतर, यह व्युत्पन्न चिन्ह के रूप में बदलता रहता है x दाएँ (या बाएँ से) 0 तक पहुँचता है जबकि f(x) ≥ x − x² > 0 के लिए 0 < x < 1.

इसलिए f(x)/f′(x) मूल के पास अबाधित है, और न्यूटन की विधि इसके किसी भी निकट में लगभग हर जगह अलग हो जाएगी, तथापि:

• फलन हर जगह अलग-अलग (और इस प्रकार निरंतर) है;
• मूल पर व्युत्पन्न अशून्य है;
• f मूल को छोड़कर अनंत रूप से भिन्न है; और
• व्युत्पन्न मूल (विपरीत f(x)/f′(x)) के निकट में घिरा है.

गैर द्विघात अभिसरण

कुछ स्थितियों में पुनरावृति अभिसरण करती है किन्तु जितनी जल्दी वादा किया गया है उतनी जल्दी अभिसरण नहीं करती है। इन स्थितियों में सरल विधियाँ न्यूटन की विधि जितनी जल्दी अभिसरित होती हैं।

शून्य व्युत्पन्न

यदि प्रथम अवकलज मूल पर शून्य है, तो अभिसरण द्विघात नहीं होगा। मान लीजिये

$f(x)=x^{2}\!$

तब f′(x) = 2x और इसके परिणामस्वरूप

$x-{\frac {f(x)}{f'(x)}}={\frac {x}{2}}.$

इसलिए अभिसरण द्विघात नहीं है, तथापि फलन हर जगह अपरिमित रूप से भिन्न हो।

इसी तरह की समस्या तब भी होती है जब मूल केवल लगभग दोगुनी होती है। उदाहरण के लिए, मान लो

$f(x)=x^{2}(x-1000)+1.$

फिर प्रारंभ होने वाले पहले कुछ पुनरावृत्तियों x₀ = 1 हैं

x₀ = 1

x₁ = 0.500250376…

x₂ = 0.251062828…

x₃ = 0.127507934…

x₄ = 0.067671976…

x₅ = 0.041224176…

x₆ = 0.032741218…

x₇ = 0.031642362…

उस बिंदु तक पहुँचने में छह पुनरावृत्तियाँ लगती हैं जहाँ अभिसरण द्विघात प्रतीत होता है।

कोई दूसरा व्युत्पन्न नहीं

यदि मूल पर कोई दूसरा व्युत्पन्न नहीं है, तो अभिसरण द्विघात होने में विफल हो सकता है। मान लीजिये

$f(x)=x+x^{\frac {4}{3}}.$

तब

$f'(x)=1+{\tfrac {4}{3}}x^{\frac {1}{3}}.$

और

$f''(x)={\tfrac {4}{9}}x^{-{\frac {2}{3}}}$

सिवाय कब x = 0 जहां यह अपरिभाषित है। x_n दिया गया हैं,

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {{\frac {1}{3}}{x_{n}}^{\frac {4}{3}}}{1+{\tfrac {4}{3}}{x_{n}}^{\frac {1}{3}}}}$

जिसमें x_n की तुलना में लगभग 4/3 गुना शुद्धता है। यह द्विघात अभिसरण के लिए आवश्यक 2 गुना से कम है। तो न्यूटन की विधि का अभिसरण (इस स्थिति में) द्विघात नहीं है, तथापि: फलन हर जगह लगातार भिन्न होता है; व्युत्पन्न मूल पर शून्य नहीं है; और f वांछित मूल को छोड़कर अपरिमित रूप से अवकलनीय है।

सामान्यीकरण

जटिल फलन

के लिए आकर्षण का केंद्र x⁵ − 1 = 0; गहरे रंग का अर्थ है अभिसरण के लिए अधिक पुनरावृत्तियों।

Main article: न्यूटन फ्रैक्टल

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

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

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

समीकरणों की प्रणाली

k चर, k फलन करता है

k समीकरणों की प्रणालियों को हल करने के लिए कोई भी न्यूटन की विधि का उपयोग कर सकता है, जो कि k निरंतर भिन्न होने वाले फलनों $f:\mathbb {R} ^{k}\to \mathbb {R}$ के (एक साथ) शून्यों को खोजने के लिए है। यह एकल वेक्टर-मूल्यवान फलन $F:\mathbb {R} ^{k}\to \mathbb {R} ^{k}$ के शून्यों को खोजने के बराबर है। ऊपर दिए गए फॉर्मूलेशन में, स्केलर्स x_n को वैक्टर x_n द्वारा प्रतिस्थापित किया जाता है और फलन f(x_n) को इसके व्युत्पन्न f′(x_n) से विभाजित करने के अतिरिक्त इसके k × k जैकबियन मैट्रिक्स J_F(x_n) के व्युत्क्रम से फलन F(x_n) को उसके को गुणा करना पड़ता है। इसका परिणाम अभिव्यक्ति में होता है

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-J_{F}(\mathbf {x} _{n})^{-1}F(\mathbf {x} _{n})$.

वास्तव में जेकोबियन मैट्रिक्स के व्युत्क्रम की गणना करने के अतिरिक्त, रैखिक समीकरणों की प्रणाली को समाधान करके समय की बचत की जा सकती है और संख्यात्मक स्थिरता में वृद्धि की जा सकती है।

$J_{F}(\mathbf {x} _{n})(\mathbf {x} _{n+1}-\mathbf {x} _{n})=-F(\mathbf {x} _{n})$

अज्ञात के लिए x_{n + 1} − x_n.

k चर, m समीकरण, m > k के साथ

न्यूटन की विधि के k-आयामी संस्करण का उपयोग k (नॉनलाइनियर) समीकरणों से अधिक के सिस्टम को हल करने के लिए भी किया जा सकता है, यदि एल्गोरिथ्म गैर-स्क्वायर जैकोबियन मैट्रिक्स J⁺ = (J^TJ)⁻¹J^T के व्युत्क्रम के अतिरिक्त सामान्यीकृत व्युत्क्रम J का उपयोग करता है। यदि गैर-रैखिक समीकरणों की प्रणाली का कोई समाधान नहीं है, तो विधि गैर-रैखिक कम से कम वर्गों के अर्थ में समाधान खोजने का प्रयास करती है। अधिक जानकारी के लिए गॉस-न्यूटन एल्गोरिथम देखें।

बनच स्थान में

अन्य सामान्यीकरण कार्यात्मक (गणित) की मूल खोजने के लिए न्यूटन की विधि है। F बनच स्थान में परिभाषित किया गया है। इस स्थिति में फॉर्मूलेशन है

$X_{n+1}=X_{n}-{\bigl (}F'(X_{n}){\bigr )}^{-1}F(X_{n}),\,$

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

ओवर p-आदिक संख्या

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

न्यूटन–फूरियर विधि

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

ये मान लीजिए कि [a, b] पर f(x) लगातार दो बार अलग-अलग है और इस अंतराल में f में मूल है। ये मान लीजिए f′(x), f″(x) ≠ 0 इस अंतराल पर (उदाहरण के लिए यह स्थिति है f(a) < 0, f(b) > 0, और f′(x) > 0, और f″(x) > 0 इस अंतराल पर)। यह गारंटी देता है कि इस अंतराल पर अद्वितीय मूल है, इसे α कहते हैं। यदि यह अवतल के अतिरिक्त अवतल है तो f(x) को −f(x) प्रतिस्थापित करें क्योंकि उनके मूले समान हैं।

मान लीजिये x₀ = b अंतराल का दाहिना समापन बिंदु बनें और z₀ = a अंतराल का बायां समापन बिंदु है। दिया गया x_n परिभाषित करें

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}},$

जो पहले की तरह ही न्यूटन की विधि है। फिर परिभाषित करें

$z_{n+1}=z_{n}-{\frac {f(z_{n})}{f'(x_{n})}},$

जहां भाजक f′(x_n) है और f′(z_n) नहीं है। पुनरावृत्तियों x_n को सख्ती से जड़ तक कम किया जाएगा जबकि पुनरावृत्तियों z_n को सख्ती से जड़ तक बढ़ाया जाएगा। भी,

$\lim _{n\to \infty }{\frac {x_{n+1}-z_{n+1}}{(x_{n}-z_{n})^{2}}}={\frac {f''(\alpha )}{2f'(\alpha )}}$

ताकि बीच की दूरी x_n और z_n द्विघात रूप से घटता है।

क्वैसी-न्यूटन विधियाँ

जब जेकोबियन अनुपलब्ध हो या प्रत्येक पुनरावृत्ति पर गणना करने के लिए बहुत महंगा हो, तो अर्ध-न्यूटन विधि का उपयोग किया जा सकता है।

q-एनालॉग

न्यूटन की विधि को सामान्य व्युत्पन्न के q-एनालॉग के साथ सामान्यीकृत किया जा सकता है।

संशोधित न्यूटन विधि

माहली की प्रक्रिया

गैर-रैखिक समीकरण के सामान्य रूप से कई समाधान होते हैं। किन्तु यदि प्रारंभिक मान उपयुक्त नहीं है, तो न्यूटन की विधि वांछित समाधान में अभिसरण नहीं कर सकती है या पहले पाए गए समान समाधान में अभिसरण कर सकती है। जब हमने पहले ही $f(x)=0$ का N समाधान ढूंढ लिया है, तो अगला मूल न्यूटन की विधि को अगले समीकरण में प्रायुक्त करके पाया जा सकता है:

$$F(x)={\frac {f(x)}{\prod _{i=1}^{N}(x-x_{i})}}=0.$$

इस विधि का उपयोग दूसरे प्रकार के बेसेल फलन के शून्य प्राप्त करने के लिए किया जाता है।

हिरानो की संशोधित न्यूटन विधि

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

अंतराल न्यूटन की विधि SSSSSS

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

विचार करना f → C¹(X), जहाँ X वास्तविक अंतराल है, और मान लीजिए कि हमारे पास अंतराल विस्तार है F′ का f′, मतलब है कि F′ इनपुट के रूप में Y ⊆ X अंतराल लेता है और अंतराल आउटपुट करता है F′(Y) ऐसा है कि:

${\begin{aligned}F'([y,y])&=\{f'(y)\}\\[5pt]F'(Y)&\supseteq \{f'(y)\mid y\in Y\}.\end{aligned}}$

हम यह भी मानते हैं 0 ∉ F′(X), इसलिए विशेष रूप से f में अधिक से अधिक मूल X है .

इसके बाद हम अंतराल न्यूटन ऑपरेटर को परिभाषित करते हैं:

$N(Y)=m-{\frac {f(m)}{F'(Y)}}=\left\{\left.m-{\frac {f(m)}{z}}~\right|~z\in F'(Y)\right\}$

जहाँ m ∈ Y. ध्यान दें कि परिकल्पना पर F′ इसका आशय है N(Y) अच्छी तरह से परिभाषित है और अंतराल है (अंतराल संचालन पर अधिक विवरण के लिए अंतराल अंकगणितीय देखें)। यह स्वाभाविक रूप से निम्नलिखित अनुक्रम की ओर जाता है:

${\begin{aligned}X_{0}&=X\\X_{k+1}&=N(X_{k})\cap X_{k}.\end{aligned}}$

औसत मान प्रमेय यह सुनिश्चित करता है कि यदि कोई मूल है f में X_k, तो यह अंदर भी है X_{k + 1}. इसके अलावा, पर परिकल्पना F′ निश्चित करता है की X_{k + 1} का अधिकतम आधा आकार है X_k कब m का मध्यबिंदु है Y, तो यह क्रम की ओर अभिसरित होता है [x*, x*], जहाँ x* का मूल है f में X.

यदि F′(X) में सख्ती से 0 होता है, विस्तारित अंतराल विभाजन का उपयोग दो अंतरालों का संघ बनाता है N(X); कई मूले इसलिए स्वचालित रूप से अलग और बंधी हुई हैं।

अनुप्रयोग

न्यूनीकरण और अधिकतमकरण की समस्याएं

Main article: Newton's method in optimization

न्यूटन की विधि का उपयोग न्यूनतम या अधिकतम फलन खोजने के लिए किया जा सकता है f(x). डेरिवेटिव न्यूनतम या अधिकतम पर शून्य है, इसलिए डेरिवेटिव के लिए न्यूटन की विधि को प्रायुक्त करके स्थानीय मिनिमा और मैक्सिमा पाया जा सकता है। पुनरावृत्ति बन जाती है:

$x_{n+1}=x_{n}-{\frac {f'(x_{n})}{f''(x_{n})}}.$

संख्याओं और घात श्रृंखला का गुणनात्मक व्युत्क्रम

महत्वपूर्ण अनुप्रयोग डिवीजन एल्गोरिथम#न्यूटन-रैफसन डिवीजन|न्यूटन-रैफसन डिवीजन है, जिसका उपयोग किसी संख्या के गुणात्मक व्युत्क्रम को जल्दी से खोजने के लिए किया जा सकता है a, केवल गुणा और घटाव का उपयोग करते हुए, यानी संख्या कहना x ऐसा है कि 1/x = a. हम इसे शून्य का पता लगाने के रूप में फिर से लिख सकते हैं f(x) = 1/x − a. अपने पास f′(x) = −1/x².

न्यूटन का पुनरावृत्ति है

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}+{\frac {{\frac {1}{x_{n}}}-a}{\frac {1}{x_{n}^{2}}}}=x_{n}(2-ax_{n}).$

इसलिए, न्यूटन के पुनरावृत्ति को केवल दो गुणा और घटाव की आवश्यकता होती है।

यह विधि किसी घात श्रेणी के गुणक व्युत्क्रम की गणना करने के लिए भी बहुत कुशल है।

अनुवांशिक समीकरणों को समाधान करना

न्यूटन की विधि का उपयोग करके कई पारलौकिक समीकरणों को समाधान किया जा सकता है। समीकरण दिया गया है

$g(x)=h(x),$

साथ g(x) और/या h(x) पारलौकिक फलन, कोई लिखता है

$f(x)=g(x)-h(x).$

के मान x जो मूल समीकरण को समाधान करते हैं, तब के मूल हैं f(x), जो न्यूटन की विधि द्वारा पाया जा सकता है।

विशेष कार्यों के शून्य प्राप्त करना

इसकी मूल प्राप्त करने के लिए न्यूटन की विधि बेसल कार्यों के अनुपात पर प्रायुक्त होती है।

अरेखीय समीकरणों के समाधान के लिए संख्यात्मक सत्यापन

न्यूटन की विधि का कई बार उपयोग करके और समाधान उम्मीदवारों का सेट बनाकर गैर-रैखिक समीकरणों के समाधान के लिए संख्यात्मक सत्यापन स्थापित किया गया है।

उदाहरण

वर्गमूल

किसी संख्या का वर्गमूल ज्ञात करने की समस्या पर विचार करें a, अर्थात धनात्मक संख्या x ऐसा है कि x² = a. न्यूटन की विधि वर्गमूल की गणना करने की कई विधियों में से है#हीरॉन की विधि। हम इसे शून्य का पता लगाने के रूप में फिर से लिख सकते हैं f(x) = x² − a. अपने पास f′(x) = 2x.

उदाहरण के लिए, प्रारंभिक अनुमान के साथ 612 का वर्गमूल निकालने के लिए x₀ = 10, न्यूटन की विधि द्वारा दिया गया क्रम है:

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\times 10}}&=&35.6\qquad \qquad \qquad \quad \;\,{}\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\dfrac {35.6^{2}-612}{2\times 35.6}}&=&{\underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\,492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}$

जहां सही अंकों को रेखांकित किया गया है। केवल कुछ पुनरावृत्तियों के साथ कई दशमलव स्थानों के लिए त्रुटिहीन समाधान प्राप्त किया जा सकता है।

सूत्र को निम्नानुसार पुनर्व्यवस्थित करने से वर्गमूलों की गणना करने की विधियाँ प्राप्त होती हैं # हीरोन की विधि:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}={\frac {1}{2}}{\biggl (}2x_{n}-{\Bigl (}x_{n}-{\frac {a}{x_{n}}}{\Bigr )}{\biggr )}={\frac {1}{2}}{\Bigl (}x_{n}+{\frac {a}{x_{n}}}{\Bigr )}$

यानी अनुमान का अंकगणितीय माध्य, x_n और a/x_n.

का समाधान cos(x) = x³

धनात्मक संख्या ज्ञात करने की समस्या पर विचार करें ${\textstyle x}$ साथ ${\textstyle \cos x=x^{3}}$. हम इसे शून्य का पता लगाने के रूप में फिर से लिख सकते हैं ${\textstyle f(x)=\cos(x)-x^{3}}$. अपने पास ${\textstyle f'(x)=-\sin(x)-3x^{2}}$. तब से ${\textstyle \cos(x)\leq 1}$ सभी के लिए ${\textstyle x}$ और ${\textstyle x^{3}>1}$ के लिए ${\textstyle x>1}$, हम जानते हैं कि हमारा समाधान 0 और 1 के बीच है।

उदाहरण के लिए, प्रारंभिक अनुमान के साथ x₀ = 0.5, न्यूटन की विधि द्वारा दिया गया अनुक्रम है (ध्यान दें कि 0 का प्रारंभिक मान अपरिभाषित परिणाम की ओर ले जाएगा, जो प्रारंभिक बिंदु का उपयोग करने के महत्व को दर्शाता है जो समाधान के निकट है):

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,102}}\dots \end{matrix}}$

उपरोक्त उदाहरण में सही अंकों को रेखांकित किया गया है। विशेष रूप से, x₆ 12 दशमलव स्थानों तक सही है। हम देखते हैं कि दशमलव बिंदु के बाद सही अंकों की संख्या 2 से बढ़ जाती है (के लिए x₃) से 5 और 10, द्विघात अभिसरण को दर्शाते हुए।

कोड

निम्नलिखित पायथन (प्रोग्रामिंग लैंग्वेज) (संस्करण 3.x) प्रोग्रामिंग लैंग्वेज में न्यूटन की विधि का कार्यान्वयन उदाहरण है, जो किसी फलन की मूल को खोजने के लिए है f जिसका व्युत्पन्न है f_prime.

प्रारंभिक अनुमान होगा x₀ = 1 और फलन होगा f(x) = x² − 2 ताकि f′(x) = 2x.

न्यूटन की विधि के प्रत्येक नए पुनरावृत्ति को द्वारा निरूपित किया जाएगा x1. हम गणना के समय जांच करेंगे कि क्या भाजक (yprime) बहुत छोटा हो जाता है (से छोटा epsilon), जो कि मामला होगा यदि f′(x_n) ≈ 0, अन्यथा बड़ी मात्रा में त्रुटि पेश की जा सकती है। <वाक्यविन्यास लैंग = पायथन 3 लाइन = 1> डेफ एफ (एक्स): रिटर्न x**2 - 2 # f(x) = x^2 - 2

डीईएफ़ f_prime(x): रिटर्न 2*x # f'(x) = 2x

डेफ़ न्यूटन_विधि (

   x0, # प्रारंभिक अनुमान
   f, # वह फलन जिसकी मूल हम खोजने का प्रयास कर रहे हैं
   f_prime, # फलन का व्युत्पन्न
   सहिष्णुता, # 7 अंकों की सटीकता वांछित है
   एप्सिलॉन, # इससे छोटी संख्या से विभाजित न करें
   max_iterations, # निष्पादित करने के लिए पुनरावृत्तियों की अधिकतम संख्या
   ):
   मैं सीमा में (max_iterations) के लिए:
       वाई = एफ (एक्स 0)
       yprime = f_prime(x0)

       यदि एब्स (वाईप्राइम) <एप्सिलॉन: # रुकें यदि भाजक बहुत छोटा है
           तोड़ना

       x1 = x0 - y / yprime # न्यूटन की गणना करें

       यदि एब्स (X1 - x0) <= सहनशीलता: # रुकें जब परिणाम वांछित सहनशीलता के भीतर हो
           वापसी x1 # X1 सहिष्णुता और पुनरावृत्तियों की अधिकतम संख्या के भीतर समाधान है

       x0 = X1 # प्रक्रिया को फिर से प्रारंभ करने के लिए x0 को अपडेट करें

   वापसी कोई नहीं # न्यूटन की विधि अभिसरण नहीं हुई

</वाक्यविन्यास हाइलाइट>

यह भी देखें

• ऐटकेन की डेल्टा-स्क्वेर्ड प्रक्रिया
• द्विभाजन विधि
• यूलर विधि
• तेजी से उलटा वर्गमूल
• स्कोरिंग एल्गोरिथ्म # फिशर स्कोरिंग
• ढतला हुआ वंश
• पूर्णांक वर्गमूल
• कांटोरोविच प्रमेय
• लैगुएरे की विधि
• वर्गमूल की गणना करने की विधियाँ
• अनुकूलन में न्यूटन की विधि
• रिचर्डसन एक्सट्रपलेशन
• रूट-खोज एल्गोरिदम
• सेकेंट विधि
• स्टीफेंसन की विधि
• सबग्रेडिएंट विधि

संदर्भ

• Gil, A.; Segura, J.; Temme, N. M. (2007). Numerical methods for special functions. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-634-4.
• Süli, Endre; Mayers, David (2003). An Introduction to Numerical Analysis. Cambridge University Press. ISBN 0-521-00794-1.

अग्रिम पठन

• Kendall E. Atkinson, An Introduction to Numerical Analysis, (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6
• Tjalling J. Ypma, Historical development of the Newton–Raphson method, SIAM Review 37 (4), 531–551, 1995. doi:10.1137/1037125.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.
• P. Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin, 2004. ISBN 3-540-21099-7.
• C. T. Kelley, Solving Nonlinear Equations with Newton's Method, no 1 in Fundamentals of Algorithms, SIAM, 2003. ISBN 0-89871-546-6.
• J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics, SIAM, 2000. ISBN 0-89871-461-3.
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Chapter 9. Root Finding and Nonlinear Sets of Equations Importance Sampling". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.. See especially Sections 9.4, 9.6, and 9.7.
• Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice Hall. pp. 216–221. ISBN 0-13-623603-0.

बाहरी संबंध

• "Newton method", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Newton's Method". MathWorld.
• Newton's method, Citizendium.
• Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
• Wu, X., Roots of Equations, Course notes.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}