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

This article is about Newton's method for finding roots. For Newton's method for finding minima, see Newton's method in optimization.

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

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

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

$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 के शून्य के लिए, अभिसरण शून्य के एक पड़ोस (गणित) में कम से कम द्विघात (अभिसरण की दर देखें) है, जिसका सहज अर्थ है कि प्रत्येक चरण में सही अंकों की संख्या मोटे तौर पर दोगुनी हो जाती है। अधिक विवरण में पाया जा सकता है§ Analysis नीचे।

गृहस्थों के तरीके समान हैं लेकिन और भी तेजी से अभिसरण के लिए उच्च क्रम हैं। हालाँकि, प्रत्येक चरण के लिए आवश्यक अतिरिक्त संगणनाएँ न्यूटन की विधि के सापेक्ष समग्र प्रदर्शन को धीमा कर सकती हैं, खासकर यदि 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 एक या दो पुनरावृत्तियों को पूरा करने के बाद, और फिर अभिसरण की दर बढ़ाने के लिए उस मान का उपयोग करें।

यदि बहुलता {{mvar|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₊, फिर, प्रत्येक के लिए x₀ में U₊ क्रम x_k नीरस रूप से घट रहा है α.

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

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

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

(1)

जहां Lagrange शेष है

$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	converges to	4;
2.35284172	converges to	−3;
2.35283735	converges to	4;
2.352836327	converges to	−3;
2.352836323	converges to	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}}}}$

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

सामान्यीकरण

जटिल कार्य

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

Main article: Newton fractal

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

कुछ मामलों में जटिल विमान में ऐसे क्षेत्र होते हैं जो आकर्षण के इन बेसिनों में से किसी में नहीं होते हैं, जिसका अर्थ है कि पुनरावृत्त अभिसरण नहीं होते हैं। उदाहरण के लिए, अगर कोई जड़ की तलाश के लिए वास्तविक प्रारंभिक स्थिति का उपयोग करता है 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) इसके बजाय फ़ंक्शन को गुणा करने के लिए एक को छोड़ना होगा F(x_n) इसके व्युत्क्रम द्वारा k × k जैकबियन मैट्रिक्स J_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-एडिक्स एक वलय है), हेन्सल के लेम्मा में अभिसरण की वास्तविक रेखा पर शास्त्रीय न्यूटन की विधि की तुलना में बहुत सरल परिकल्पनाओं के तहत गारंटी दी जा सकती है।

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

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

ये मान लीजिए f(x) पर लगातार दो बार अवकलनीय है [a, b] ओर वो 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$, तो अगला मूल न्यूटन की विधि को अगले समीकरण में लागू करके पाया जा सकता है:

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

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

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

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

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

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

}}