न्यूटन की विधि: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
{{Short description|Algorithm for finding zeros of functions}} | {{Short description|Algorithm for finding zeros of functions}} | ||
{{About|मूल खोजने की न्यूटन की विधि|न्यूनतम खोजने के लिए न्यूटन की विधि|अनुकूलन में न्यूटन की विधि}} | {{About|मूल खोजने की न्यूटन की विधि|न्यूनतम खोजने के लिए न्यूटन की विधि|अनुकूलन में न्यूटन की विधि}} | ||
[[संख्यात्मक विश्लेषण]] में, न्यूटन की विधि, जिसे न्यूटन-रैफसन विधि के रूप में भी जाना जाता है, जिसका नाम [[आइजैक न्यूटन]] और [[जोसेफ राफसन]] के नाम पर रखा गया है, यह एक [[रूट-फाइंडिंग एल्गोरिदम]] है जो एक [[वास्तविक संख्या]] मूल्यवान फलन (गणित) की मूलों (या शून्य) में क्रमिक रूप से उत्तम संख्यात्मक विश्लेषण उत्पन्न करता है। सबसे मूलभूत संस्करण एक वास्तविक चर {{math|''x''}} फलन के डेरिवेटिव {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''}}′ के लिए परिभाषित एकल-चर फलन {{math|''f''}} से प्रारंभ होता है और {{math|''f''}} की मूल के लिए प्रारंभिक अनुमान {{math|''x''<sub>0</sub>}} है। यदि फलन पर्याप्त मान्यताओं को संतुष्ट करता है और प्रारंभिक अनुमान निकट है, तो | [[संख्यात्मक विश्लेषण]] में, न्यूटन की विधि, जिसे न्यूटन-रैफसन विधि के रूप में भी जाना जाता है, जिसका नाम [[आइजैक न्यूटन]] और [[जोसेफ राफसन]] के नाम पर रखा गया है, यह एक [[रूट-फाइंडिंग एल्गोरिदम|मूल-फाइंडिंग एल्गोरिदम]] है जो एक [[वास्तविक संख्या]] मूल्यवान फलन (गणित) की मूलों (या शून्य) में क्रमिक रूप से उत्तम संख्यात्मक विश्लेषण उत्पन्न करता है। सबसे मूलभूत संस्करण एक वास्तविक चर {{math|''x''}} फलन के डेरिवेटिव {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''}}′ के लिए परिभाषित एकल-चर फलन {{math|''f''}} से प्रारंभ होता है और {{math|''f''}} की मूल के लिए प्रारंभिक अनुमान {{math|''x''<sub>0</sub>}} है। यदि फलन पर्याप्त मान्यताओं को संतुष्ट करता है और प्रारंभिक अनुमान निकट है, तो | ||
:<math>x_{1} = x_0 - \frac{f(x_0)}{f'(x_0)}</math> | :<math>x_{1} = x_0 - \frac{f(x_0)}{f'(x_0)}</math> | ||
Line 13: | Line 13: | ||
विचार एक प्रारंभिक अनुमान के साथ प्रारंभ करना है, फिर इसकी स्पर्शरेखा रेखा द्वारा फलन को अनुमानित करना और अंत में इसकी गणना करना है {{mvar|x}}-इस स्पर्श रेखा का अवरोधन। यह {{mvar|x}}-अवरोधन सामान्यतः पहले अनुमान की तुलना में मूल फलन की मूल के लिए एक उत्तम सन्निकटन होगा, और विधि पुनरावृत्त विधि हो सकती है। | विचार एक प्रारंभिक अनुमान के साथ प्रारंभ करना है, फिर इसकी स्पर्शरेखा रेखा द्वारा फलन को अनुमानित करना और अंत में इसकी गणना करना है {{mvar|x}}-इस स्पर्श रेखा का अवरोधन। यह {{mvar|x}}-अवरोधन सामान्यतः पहले अनुमान की तुलना में मूल फलन की मूल के लिए एक उत्तम सन्निकटन होगा, और विधि पुनरावृत्त विधि हो सकती है। | ||
[[Image:newton iteration.svg|alt=Illustration of Newtonकी विधि|अंगूठा|दाहिना|300पीएक्स|{{math|''x''<sub>''n''+1</sub>}} से उत्तम सन्निकटन है {{math|''x''<sub>''n''</sub>}}<nowiki> मूल के लिए {{math|</nowiki>''x''}समारोह का } {{math|''f''}} (नीला वक्र)]]यदि वक्र को स्पर्शरेखा रेखा {{math|''f''(''x'')}} पर {{math|1=''x'' = ''x''<sub>''n''</sub>}} इंटरसेप्ट करता है {{math|''x''}}-अक्ष पर {{math|''x''<sub>''n''+1</sub>}} तो | [[Image:newton iteration.svg|alt=Illustration of Newtonकी विधि|अंगूठा|दाहिना|300पीएक्स|{{math|''x''<sub>''n''+1</sub>}} से उत्तम सन्निकटन है {{math|''x''<sub>''n''</sub>}}<nowiki> मूल के लिए {{math|</nowiki>''x''}समारोह का } {{math|''f''}} (नीला वक्र)]] | ||
यदि वक्र को स्पर्शरेखा रेखा {{math|''f''(''x'')}} पर {{math|1=''x'' = ''x''<sub>''n''</sub>}} इंटरसेप्ट करता है {{math|''x''}}-अक्ष पर {{math|''x''<sub>''n''+1</sub>}} तो प्रवणता है | |||
: <math>f'(x_n) = \dfrac{f(x_n)-0} {x_n-x_{n+1}} </math>. | : <math>f'(x_n) = \dfrac{f(x_n)-0} {x_n-x_{n+1}} </math>. | ||
{{math|''x''<sub>''n''+1</sub>}} के लिए समाधान करना देता है | |||
: <math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. </math> | : <math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. </math> | ||
[[Image:NewtonIteration Ani.gif|alt=Illustration of Newtonकी विधि|अंगूठे|दाएं|300px|पुनरावृत्ति आमतौर पर सन्निकटन में सुधार करती है]]हम कुछ | [[Image:NewtonIteration Ani.gif|alt=Illustration of Newtonकी विधि|अंगूठे|दाएं|300px|पुनरावृत्ति आमतौर पर सन्निकटन में सुधार करती है]] | ||
हम कुछ स्वैच्छिक प्रारंभिक मान {{math|''x''<sub>0</sub>}} के साथ प्रक्रिया प्रारंभ करते हैं। (शून्य के जितना निकट हो उतना बेहतर है। किन्तु, शून्य कहां हो सकता है, इसके बारे में किसी भी अंतर्ज्ञान की अनुपस्थिति में, एक "अनुमान और जांच" विधि [[मध्यवर्ती मूल्य प्रमेय|मध्यवर्ती मान प्रमेय]] की अपील करके संभावनाओं को यथोचित छोटे अंतराल तक सीमित कर सकती है।) विधि सामान्यतः अभिसरण होगा, बशर्ते यह प्रारंभिक अनुमान अज्ञात शून्य के काफी निकट हो, और वह {{math|''f''{{′}}(''x''<sub>0</sub>) ≠ 0}}. इसके अलावा, [[बहुलता (गणित)]] 1 के शून्य के लिए, अभिसरण शून्य के एक [[पड़ोस (गणित)|निकट (गणित)]] में कम से कम द्विघात ([[अभिसरण की दर]] देखें) है, जिसका सहज अर्थ है कि प्रत्येक चरण में सही अंकों की संख्या सामान्यतः दोगुनी हो जाती है। अधिक विवरण नीचे {{section link|#विश्लेषण}} में पाया जा सकता है। | |||
हाउसहोल्डर्स की विधियाँ समान हैं किन्तु और भी तेजी से अभिसरण के लिए उच्च क्रम हैं। चूँकि, प्रत्येक चरण के लिए आवश्यक अतिरिक्त संगणनाएँ न्यूटन की विधि के सापेक्ष समग्र प्रदर्शन को धीमा कर सकती हैं, विशेष रूप से यदि {{mvar|f}} या इसके डेरिवेटिव मूल्यांकन के लिए कम्प्यूटेशनल रूप से महंगे हैं। | |||
== इतिहास == | == इतिहास == | ||
न्यूटन की विधि का नाम इसहाक न्यूटन के [[अनंत पदों के साथ समीकरणों द्वारा विश्लेषण पर]] (1669 में लिखा गया, [[विलियम जोन्स (गणितज्ञ)]] द्वारा 1711 में प्रकाशित) और डी मेटोडिस फ्लक्सियोनम एट सेरीरम इनफिनिटरम (लिखित) में विधि के एक विशेष | न्यूटन की विधि का नाम इसहाक न्यूटन के [[अनंत पदों के साथ समीकरणों द्वारा विश्लेषण पर]] (1669 में लिखा गया, [[विलियम जोन्स (गणितज्ञ)]] द्वारा 1711 में प्रकाशित) और डी मेटोडिस फ्लक्सियोनम एट सेरीरम इनफिनिटरम (लिखित) में विधि के एक विशेष स्थिति के वर्णन से लिया गया है। 1671 में, [[जॉन कोलसन]] द्वारा 1736 में [[प्रवाह की विधि]] के रूप में अनुवादित और प्रकाशित)। चूँकि, उनकी विधि ऊपर दी गई आधुनिक पद्धति से काफी भिन्न है। न्यूटन ने इस विधि को केवल बहुपदों के लिए प्रायुक्त किया, प्रारंभिक मूल अनुमान से प्रारंभ करके और त्रुटि सुधारों के अनुक्रम को निकाला। उन्होंने शेष त्रुटि के संदर्भ में बहुपद को फिर से लिखने के लिए प्रत्येक सुधार का उपयोग किया, और फिर उच्च-स्तर की शर्तों की उपेक्षा करके एक नए सुधार के लिए समाधान किया। उन्होंने विधि को डेरिवेटिव के साथ स्पष्ट रूप से नहीं जोड़ा या एक सामान्य सूत्र प्रस्तुत नहीं किया। न्यूटन ने इस पद्धति को संख्यात्मक और बीजगणितीय दोनों समस्याओं के लिए प्रायुक्त किया, बाद वाले स्थिति में [[टेलर श्रृंखला]] का निर्माण किया। | ||
हो सकता है कि न्यूटन ने अपनी पद्धति [[ फ्रांसिस लाइफ ]] द्वारा एक समान, कम त्रुटिहीन विधि से प्राप्त की हो। मध्यकालीन इस्लाम [[शराफ अल-दीन अल-तुसी]] में गणित के काम में वीटा की पद्धति का सार पाया जा सकता है, जबकि उनके उत्तराधिकारी जमशीद अल-काशी ने | हो सकता है कि न्यूटन ने अपनी पद्धति [[ फ्रांसिस लाइफ ]] द्वारा एक समान, कम त्रुटिहीन विधि से प्राप्त की हो। मध्यकालीन इस्लाम [[शराफ अल-दीन अल-तुसी]] में गणित के काम में वीटा की पद्धति का सार पाया जा सकता है, जबकि उनके उत्तराधिकारी जमशीद अल-काशी ने समाधान करने के लिए न्यूटन की विधि का एक रूप इस्तेमाल किया {{math|''x<sup>P</sup>'' − ''N'' {{=}} 0}} की मूले खोजने के लिए {{mvar|N}} (वाईपीएमए 1995)। वर्गमूलों की गणना के लिए न्यूटन की विधि का एक विशेष मामला प्राचीन काल से जाना जाता था और इसे अक्सर [[बेबीलोनियन विधि]] कहा जाता है। | ||
17वीं शताब्दी के जापानी गणितज्ञ सेकी कोवा द्वारा एकल-चर समीकरणों को | 17वीं शताब्दी के जापानी गणितज्ञ सेकी कोवा द्वारा एकल-चर समीकरणों को समाधान करने के लिए न्यूटन की विधि का उपयोग किया गया था, चूंकि कलन के साथ संबंध गायब था।<ref>{{cite web |title=Chapter 2. Seki Takakazu |url=http://www.ndl.go.jp/math/e/s1/2.html |website=Japanese Mathematics in the Edo Period |publisher=National Diet Library |access-date=24 February 2019}}</ref> | ||
न्यूटन की विधि पहली बार 1685 में [[जॉन वालिस]] द्वारा हिस्टोरिकल एंड प्रैक्टिकल दोनों में बीजगणित के एक ग्रंथ में प्रकाशित हुई थी।<ref>{{cite book |first=John |last=Wallis |author-link=John Wallis |title=बीजगणित का ग्रंथ, ऐतिहासिक और व्यावहारिक दोनों|publisher=Richard Davis |location=Oxford |date=1685 |url=http://www.e-rara.ch/zut/content/titleinfo/2507537 |doi=10.3931/e-rara-8842}}</ref> 1690 में, जोसेफ रैफसन ने सार्वभौम समीकरणों के विश्लेषण में एक सरलीकृत विवरण प्रकाशित किया।<ref>{{cite book |last=Raphson |first=Joseph |author-link=Joseph Raphson |title=Analysis Æequationum Universalis |edition=2nd |language=la |date=1697 |publisher=Thomas Bradyll |location=London |url=https://archive.org/details/bub_gb_4nlbAAAAQAAJ |doi=10.3931/e-rara-13516}}</ref> रैफसन ने भी इस विधि को केवल बहुपदों पर | न्यूटन की विधि पहली बार 1685 में [[जॉन वालिस]] द्वारा हिस्टोरिकल एंड प्रैक्टिकल दोनों में बीजगणित के एक ग्रंथ में प्रकाशित हुई थी।<ref>{{cite book |first=John |last=Wallis |author-link=John Wallis |title=बीजगणित का ग्रंथ, ऐतिहासिक और व्यावहारिक दोनों|publisher=Richard Davis |location=Oxford |date=1685 |url=http://www.e-rara.ch/zut/content/titleinfo/2507537 |doi=10.3931/e-rara-8842}}</ref> 1690 में, जोसेफ रैफसन ने सार्वभौम समीकरणों के विश्लेषण में एक सरलीकृत विवरण प्रकाशित किया।<ref>{{cite book |last=Raphson |first=Joseph |author-link=Joseph Raphson |title=Analysis Æequationum Universalis |edition=2nd |language=la |date=1697 |publisher=Thomas Bradyll |location=London |url=https://archive.org/details/bub_gb_4nlbAAAAQAAJ |doi=10.3931/e-rara-13516}}</ref> रैफसन ने भी इस विधि को केवल बहुपदों पर प्रायुक्त किया, किन्तु उन्होंने मूल बहुपद से प्रत्येक क्रमिक सुधार को निकाल कर न्यूटन की थकाऊ पुनर्लेखन प्रक्रिया से परहेज किया। इसने उन्हें प्रत्येक समस्या के लिए पुन: प्रयोज्य पुनरावृत्त अभिव्यक्ति प्राप्त करने की अनुमति दी। अंत में, 1740 में, [[थॉमस सिम्पसन]] ने न्यूटन की विधि को कैलकुलस का उपयोग करके सामान्य अरैखिक समीकरणों को समाधान करने के लिए एक पुनरावृत्ति विधि के रूप में वर्णित किया, अनिवार्य रूप से उपरोक्त विवरण दिया। उसी प्रकाशन में, सिम्पसन भी दो समीकरणों की प्रणालियों का सामान्यीकरण करता है और नोट करता है कि न्यूटन की विधि का उपयोग ढाल को शून्य पर सेट करके अनुकूलन समस्याओं को समाधान करने के लिए किया जा सकता है। | ||
न्यूटन-फूरियर काल्पनिक समस्या में 1879 में [[आर्थर केली]] 2 से अधिक डिग्री और जटिल प्रारंभिक | न्यूटन-फूरियर काल्पनिक समस्या में 1879 में [[आर्थर केली]] 2 से अधिक डिग्री और जटिल प्रारंभिक मानों वाले बहुपदों की जटिल मूलों के लिए न्यूटन की विधि को सामान्य बनाने में कठिनाइयों पर ध्यान देने वाले पहले व्यक्ति थे। इसने तर्कसंगत कार्यों के [[जूलिया सेट]] के अध्ययन का रास्ता खोल दिया। | ||
== व्यावहारिक विचार == | == व्यावहारिक विचार == | ||
न्यूटन की विधि एक शक्तिशाली तकनीक है - | न्यूटन की विधि एक शक्तिशाली तकनीक है - सामान्यतः अभिसरण की दर द्विघात होती है: जैसे-जैसे विधि मूल पर अभिसरण करती है, मूल और सन्निकटन के बीच का अंतर चुकता होता है (त्रुटिहीन अंकों की संख्या सामान्यतः दोगुनी हो जाती है)। चूँकि, विधि के साथ कुछ कठिनाइयाँ हैं। | ||
=== किसी फलन के व्युत्पन्न की गणना करने में कठिनाई === | === किसी फलन के व्युत्पन्न की गणना करने में कठिनाई === | ||
न्यूटन की विधि के लिए आवश्यक है कि व्युत्पन्न की सीधे गणना की जा सके। व्युत्पन्न के लिए एक विश्लेषणात्मक अभिव्यक्ति आसानी से प्राप्त करने योग्य नहीं हो सकती है या मूल्यांकन के लिए महंगा हो सकता है। इन स्थितियों में, फलन पर दो पास के बिंदुओं के माध्यम से एक रेखा के | न्यूटन की विधि के लिए आवश्यक है कि व्युत्पन्न की सीधे गणना की जा सके। व्युत्पन्न के लिए एक विश्लेषणात्मक अभिव्यक्ति आसानी से प्राप्त करने योग्य नहीं हो सकती है या मूल्यांकन के लिए महंगा हो सकता है। इन स्थितियों में, फलन पर दो पास के बिंदुओं के माध्यम से एक रेखा के प्रवणता का उपयोग करके व्युत्पन्न को अनुमानित करना उचित हो सकता है। इस सन्निकटन का उपयोग करने से सीकेंट विधि जैसा कुछ होगा जिसका अभिसरण न्यूटन की विधि की तुलना में धीमा है। | ||
=== | ===मूल में एकाग्र होने की विधि की विफलता=== | ||
इसे | इसे प्रायुक्त करने से पहले न्यूटन की न्यूटन की विधि के पुनरावृत्त विधि के लिए द्विघात अभिसरण के प्रमाण की समीक्षा करना महत्वपूर्ण है। विशेष रूप से, किसी को प्रमाण में की गई धारणाओं की समीक्षा करनी चाहिए। #विफलता विश्लेषण के लिए, ऐसा इसलिए है क्योंकि इस प्रमाण में की गई धारणाएँ पूरी नहीं हुई हैं। | ||
==== ओवरशूट ==== | ==== ओवरशूट ==== | ||
यदि पहली व्युत्पत्ति किसी विशेष | यदि पहली व्युत्पत्ति किसी विशेष मूल के निकट में अच्छी तरह से व्यवहार नहीं की जाती है, तो विधि ओवरशूट हो सकती है और उस मूल से अलग हो सकती है। एक मूल के साथ एक फलन का उदाहरण, जिसके लिए मूल के निकट में डेरिवेटिव अच्छी तरह से व्यवहार नहीं किया जाता है | ||
:<math>f(x)=|x|^a,\quad 0 < a < \tfrac{1}{2}</math> | :<math>f(x)=|x|^a,\quad 0 < a < \tfrac{1}{2}</math> | ||
जिसके लिए | जिसके लिए मूल ओवरशूट होगा और का क्रम {{mvar|x}} विचलन करेगा। के लिए {{math|{{var|a}} {{=}} {{sfrac|1|2}}}}, मूल अभी भी ओवरशूट होगा, किन्तु अनुक्रम दो मानों के बीच दोलन करेगा। के लिए {{math|{{sfrac|1|2}} < {{var|a}} < 1}}, मूल अभी भी ओवरशूट होगा किन्तु अनुक्रम अभिसरण करेगा, और के लिए {{math|{{var|a}} ≥ 1}} मूल बिल्कुल भी ओवरशूट नहीं होगा। | ||
कुछ | कुछ स्थितियों में, क्रमिक अति-विश्राम#विधि के अन्य अनुप्रयोगों|क्रमिक अति-विश्राम का उपयोग करके न्यूटन की विधि को स्थिर किया जा सकता है, या समान विधि का उपयोग करके अभिसरण की गति को बढ़ाया जा सकता है। | ||
==== [[स्थिर बिंदु]] ==== | ==== [[स्थिर बिंदु]] ==== | ||
Line 55: | Line 59: | ||
==== खराब प्रारंभिक अनुमान ==== | ==== खराब प्रारंभिक अनुमान ==== | ||
प्रारंभिक अनुमान में एक बड़ी त्रुटि एल्गोरिथम के गैर-अभिसरण में योगदान कर सकती है। इस समस्या को दूर करने के लिए अक्सर उस फलन को रेखीयकृत किया जा सकता है जिसे कलन, लॉग, अंतर, या यहां तक कि विकासवादी एल्गोरिदम का उपयोग करके अनुकूलित किया जा रहा है, जैसे [[स्टोकेस्टिक टनलिंग]]। अच्छा प्रारंभिक अनुमान अंतिम विश्व स्तर पर इष्टतम पैरामीटर अनुमान के | प्रारंभिक अनुमान में एक बड़ी त्रुटि एल्गोरिथम के गैर-अभिसरण में योगदान कर सकती है। इस समस्या को दूर करने के लिए अक्सर उस फलन को रेखीयकृत किया जा सकता है जिसे कलन, लॉग, अंतर, या यहां तक कि विकासवादी एल्गोरिदम का उपयोग करके अनुकूलित किया जा रहा है, जैसे [[स्टोकेस्टिक टनलिंग]]। अच्छा प्रारंभिक अनुमान अंतिम विश्व स्तर पर इष्टतम पैरामीटर अनुमान के निकट है। अरेखीय प्रतिगमन में, चुकता त्रुटियों (SSE) का योग केवल अंतिम पैरामीटर अनुमानों के क्षेत्र में परवलयिक के निकट है। यहां मिले प्रारंभिक अनुमानों से न्यूटन-रेफसन पद्धति को शीघ्रता से अभिसरण करने की अनुमति मिलेगी। यह केवल यहीं है कि एसएसई का [[हेसियन मैट्रिक्स]] सकारात्मक है और एसएसई का पहला व्युत्पन्न शून्य के निकट है। | ||
==== गैर-अभिसरण का शमन ==== | ==== गैर-अभिसरण का शमन ==== | ||
न्यूटन की विधि के एक मजबूत कार्यान्वयन में, पुनरावृत्तियों की संख्या पर सीमाएं लगाना आम है, | न्यूटन की विधि के एक मजबूत कार्यान्वयन में, पुनरावृत्तियों की संख्या पर सीमाएं लगाना आम है, मूल को समाहित करने के लिए ज्ञात अंतराल के समाधान को बाध्य करना, और अधिक मजबूत मूल खोज विधि के साथ विधि को संयोजित करना। | ||
'''1 से अधिक बहुलता की मूलों के लिए धीमा अभिसरण''' | |||
यदि खोजी जा रही मूल में बहुलता (गणित) # एक से अधिक बहुपद की मूल की बहुलता है, तो अभिसरण दर केवल रैखिक है (प्रत्येक चरण पर एक स्थिर कारक द्वारा कम की गई त्रुटियां) जब तक कि विशेष कदम नहीं उठाए जाते। जब दो या दो से अधिक मूले एक-दूसरे के निकट होती हैं, तो द्विघात अभिसरण स्पष्ट होने के लिए पुनरावृति उनमें से किसी एक के काफी निकट आने से पहले कई पुनरावृत्तियों को ले सकती है। चूँकि, यदि बहुलता {{mvar|m}} मूल ज्ञात है, निम्नलिखित संशोधित एल्गोरिथ्म द्विघात अभिसरण दर को संरक्षित करता है:<ref>{{cite web|title=त्वरित और संशोधित न्यूटन तरीके|url=http://mathfaculty.fullerton.edu/mathews/n2003/newtonacceleratemod.html|access-date=4 March 2016|archive-url=https://web.archive.org/web/20190524083302/http://mathfaculty.fullerton.edu/mathews/n2003/NewtonAccelerateMod.html|archive-date=24 May 2019|url-status=dead}}</ref> | |||
यदि खोजी जा रही मूल में बहुलता (गणित) # एक से अधिक बहुपद की मूल की बहुलता है, तो अभिसरण दर केवल रैखिक है (प्रत्येक चरण पर एक स्थिर कारक द्वारा कम की गई त्रुटियां) जब तक कि विशेष कदम नहीं उठाए जाते। जब दो या दो से अधिक | |||
:<math>x_{n+1} = x_n - m\frac{f(x_n)}{f'(x_n)}. </math> | :<math>x_{n+1} = x_n - m\frac{f(x_n)}{f'(x_n)}. </math> | ||
यह | यह क्रमिक अति-विश्राम का उपयोग करने के बराबर है। दूसरी ओर, यदि बहुलता {{mvar|m}} का मूल ज्ञात नहीं है, इसका अनुमान लगाया जा सकता है {{mvar|m}} एक या दो पुनरावृत्तियों को पूरा करने के बाद, और फिर अभिसरण की दर बढ़ाने के लिए उस मान का उपयोग करें। | ||
यदि मूल की बहुलता m परिमित है तो {{math|1=''g''(''x'') = {{sfrac|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'')}}}} की बहुलता 1 के साथ एक ही स्थान पर एक मूल होगी। {{math|''g''(''x'')}} के मूल को खोजने के लिए न्यूटन की विधि को प्रायुक्त करना ठीक हो जाता है कई स्थितियों में द्विघात अभिसरण चूंकि इसमें सामान्यतः {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} का दूसरा अवकलज सम्मिलित होता है। एक विशेष रूप से सरल स्थिति में, यदि {{math|1=''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') = ''x''<sup>''m''</sup>}} तब {{math|1=''g''(''x'') = {{sfrac|''x''|''m''}}}} और न्यूटन की विधि मूल को एकल पुनरावृत्ति में खोजती है | |||
:<math>x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)} = x_n - \frac{\;\frac{x_n}{m}\;}{\frac{1}{m}} = 0\,.</math> | :<math>x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)} = x_n - \frac{\;\frac{x_n}{m}\;}{\frac{1}{m}} = 0\,.</math> | ||
== विश्लेषण == | == विश्लेषण == | ||
मान लीजिए कि | मान लीजिए कि फ़ंक्शन {{mvar|f}} का {{mvar|α}} पर एक शून्य है, अर्थात, {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''α'') {{=}} 0}}, और {{mvar|f}}, {{mvar|α}} के [[टोपोलॉजिकल पड़ोस|टोपोलॉजिकल निकट]] में अवकलनीय है। | ||
यदि {{mvar|f}} निरंतर अवकलनीय है और इसका व्युत्पन्न {{mvar|α}} पर अशून्य है, तो {{mvar|α}} का एक सामयिक निकट उपस्थित है जैसे कि सभी प्रारंभिक मानों के लिए {{math|''x''<sub>0</sub>}} उस निकट में, [[अनुक्रम]] {{math|(''x''<sub>''n''</sub>)}}{{mvar|α}} [[अनुक्रम की सीमा]] को सीमित कर देगा।<ref>{{citation|title=A Theoretical Introduction to Numerical Analysis|first1=Victor S.|last1=Ryaben'kii|first2=Semyon V.|last2=Tsynkov|publisher=CRC Press|year=2006|isbn=9781584886075|page=243|url=https://books.google.com/books?id=V8gWP031-hEC&pg=PA243}}.</ref> | |||
यदि {{mvar|f}} निरंतर अवकलनीय है, इसका व्युत्पन्न {{mvar|α}} पर अशून्य है, और इसका {{mvar|α}} पर [[दूसरा व्युत्पन्न]] है, तो अभिसरण द्विघात या तेज है। यदि {{mvar|α}} पर दूसरा व्युत्पन्न 0 नहीं है तो अभिसरण केवल द्विघात है। यदि तीसरा व्युत्पन्न उपस्थित है और {{mvar|α}} के निकट में घिरा हुआ है , तब: | |||
:<math>\Delta x_{i+1} = \frac{f'' (\alpha)}{2 f' (\alpha)} \left(\Delta x_{i}\right)^2 + O\left(\Delta x_{i}\right)^3 \,,</math> | :<math>\Delta x_{i+1} = \frac{f'' (\alpha)}{2 f' (\alpha)} \left(\Delta x_{i}\right)^2 + O\left(\Delta x_{i}\right)^3 \,,</math> | ||
जहाँ | |||
:<math>\Delta x_i \triangleq x_i - \alpha \,.</math> | :<math>\Delta x_i \triangleq x_i - \alpha \,.</math> | ||
यदि व्युत्पन्न | यदि व्युत्पन्न {{mvar|α}} पर 0 है, तो अभिसरण आमतौर पर केवल रैखिक होता है। विशेष रूप से, यदि {{mvar|f}} लगातार दो बार भिन्न होता है, {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''α'') {{=}} 0}} और {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''α'') ≠ 0}}, तो {{mvar|α}} का एक निकट उपस्थित है {{mvar|α}} जैसे कि, सभी प्रारंभिक मानों के लिए {{math|''x''<sub>0</sub>}} उस निकट में, पुनरावृति का क्रम अभिसरण की दर {{sfrac|1|2}} के साथ रैखिक रूप से अभिसरित होता है।<ref>{{harvnb|Süli|Mayers|2003|loc=Exercise 1.6}}</ref> वैकल्पिक रूप से, यदि {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''α'') {{=}} 0}} और {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') ≠ 0}} के लिए {{math|''x'' ≠ ''α''}}, {{mvar|x}} {{mvar|α}} के एक सामयिक निकट {{mvar|U}} में, {{mvar|α}} बहुलता {{mvar|r}} का शून्य होना (गणित), और यदि {{math|''f'' ∈ ''C''{{isup|''r''}}(''U'')}}, तो वहाँ {{mvar|α}} का एक निकट उपस्थित है जैसे कि, सभी प्रारंभिक मानों {{math|''x''<sub>0</sub>}} के लिए उस निकट में, पुनरावृत्तियों का क्रम रैखिक रूप से परिवर्तित होता है। | ||
चूंकि, पैथोलॉजिकल स्थितियों में भी रैखिक अभिसरण की गारंटी नहीं है। | |||
व्यवहार में, ये परिणाम स्थानीय हैं, और अभिसरण का | व्यवहार में, ये परिणाम स्थानीय हैं, और अभिसरण का निकट पहले से ज्ञात नहीं है। किन्तु वैश्विक अभिसरण पर भी कुछ परिणाम हैं: उदाहरण के लिए, {{mvar|α}} का सही निकट {{math|''U''<sub>+</sub>}} दिया गया है यदि {{mvar|f}} {{math|''U''<sub>+</sub>}}में दो बार अवकलनीय है और यदि {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′'' ≠ 0}}, {{math|''f'' · ''<span style{{=}}"letter-spacing:0.15em">f</span>″'' > 0}} {{math|''U''<sub>+</sub>}} में है, तो, {{math|''U''<sub>+</sub>}} में प्रत्येक {{math|''x''<sub>0</sub>}} के लिए अनुक्रम {{math|''x<sub>k</sub>''}} मोनोटोनिक रूप से {{mvar|α}} तक घट रहा है। | ||
=== न्यूटन की पुनरावृत्ति विधि के लिए द्विघात अभिसरण का प्रमाण === | === न्यूटन की पुनरावृत्ति विधि के लिए द्विघात अभिसरण का प्रमाण === | ||
टेलर प्रमेय के अनुसार कोई भी फलन {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} जिसका लगातार दूसरा अवकलज है, को उस बिंदु के बारे में विस्तार द्वारा दर्शाया जा सकता है जो की मूल | टेलर प्रमेय के अनुसार कोई भी फलन {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} जिसका लगातार दूसरा अवकलज है, को उस बिंदु के बारे में विस्तार द्वारा दर्शाया जा सकता है जो की मूल {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} के निकट है। मान लीजिए यह मूल {{mvar|α}} है। फिर का विस्तार {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''α'')}} के बारे में {{math|''x''<sub>''n''</sub>}} है: | ||
{{NumBlk|:|<math>f(\alpha) = f(x_n) + f'(x_n)(\alpha - x_n) + R_1 \,</math>|{{EquationRef|1}}}} | {{NumBlk|:|<math>f(\alpha) = f(x_n) + f'(x_n)(\alpha - x_n) + R_1 \,</math>|{{EquationRef|1}}}} | ||
जहां | जहां लैग्रेंज शेष है | ||
:<math>R_1 = \frac{1}{2!}f''(\xi_n)\left(\alpha - x_n\right)^{2} \,,</math> | :<math>R_1 = \frac{1}{2!}f''(\xi_n)\left(\alpha - x_n\right)^{2} \,,</math> | ||
जहाँ {{math|''ξ''<sub>''n''</sub>}}, {{math|''x''<sub>''n''</sub>}} और {{mvar|α}} के बीच में है। | |||
तब से {{mvar|α}} मूल है, ({{EquationNote|1}}) बन जाता है: | तब से {{mvar|α}} मूल है, ({{EquationNote|1}}) बन जाता है:{{NumBlk|:|<math>0 = f(\alpha) = f(x_n) + f'(x_n)(\alpha - x_n) + \tfrac12f''(\xi_n)\left(\alpha - x_n\right)^2 \,</math>|{{EquationRef|2}}}} | ||
{{NumBlk|:|<math>0 = f(\alpha) = f(x_n) + f'(x_n)(\alpha - x_n) + \tfrac12f''(\xi_n)\left(\alpha - x_n\right)^2 \,</math>|{{EquationRef|2}}}} | |||
विभाजित समीकरण ({{EquationNote|2}}) द्वारा {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x<sub>n</sub>'')}} और पुनर्व्यवस्थित करता है | विभाजित समीकरण ({{EquationNote|2}}) द्वारा {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x<sub>n</sub>'')}} और पुनर्व्यवस्थित करता है | ||
Line 111: | Line 116: | ||
समीकरण ({{EquationNote|6}}) दर्शाता है कि [[अभिसरण का क्रम]] कम से कम द्विघात है यदि निम्नलिखित शर्तें पूरी होती हैं: | समीकरण ({{EquationNote|6}}) दर्शाता है कि [[अभिसरण का क्रम]] कम से कम द्विघात है यदि निम्नलिखित शर्तें पूरी होती हैं: | ||
# {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') ≠ 0}}; सभी के लिए {{math|''x'' ∈ ''I''}}, | # {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') ≠ 0}}; सभी के लिए {{math|''x'' ∈ ''I''}}, जहाँ {{mvar|I}} अंतराल है {{math|[''α'' − {{abs|''ε''<sub>0</sub>}}, ''α'' + {{abs|''ε''<sub>0</sub>}}]}}; | ||
# {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'')}} सभी के लिए निरंतर है {{math|''x'' ∈ ''I''}}; | # {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'')}} सभी के लिए निरंतर है {{math|''x'' ∈ ''I''}}; | ||
# {{math|''M'' {{abs|''ε''<sub>0</sub>}} < 1}} | # {{math|''M'' {{abs|''ε''<sub>0</sub>}} < 1}} | ||
Line 124: | Line 129: | ||
=== आकर्षण का केंद्र === | === आकर्षण का केंद्र === | ||
आकर्षण के बेसिन के असंबद्ध उपसमुच्चय - वास्तविक संख्या रेखा के क्षेत्र जैसे कि प्रत्येक क्षेत्र के भीतर किसी भी बिंदु से पुनरावृति एक विशेष मूल की ओर ले जाती है - संख्या में अनंत और | आकर्षण के बेसिन के असंबद्ध उपसमुच्चय - वास्तविक संख्या रेखा के क्षेत्र जैसे कि प्रत्येक क्षेत्र के भीतर किसी भी बिंदु से पुनरावृति एक विशेष मूल की ओर ले जाती है - संख्या में अनंत और स्वैच्छिक विधि से छोटा हो सकता है। उदाहरण के लिए,<ref>{{cite journal|last=Dence |first=Thomas |title=क्यूबिक्स, कैओस और न्यूटन की विधि|journal=[[Mathematical Gazette]] |volume=81 |date=Nov 1997 |issue=492 |pages=403–408 |doi=10.2307/3619617|jstor=3619617 |s2cid=125196796 }}</ref> फलन के लिए {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') {{=}} ''x''<sup>3</sup> − 2''x''<sup>2</sup> − 11''x'' + 12 {{=}} (''x'' − 4)(''x'' − 1)(''x'' + 3)}}, निम्नलिखित प्रारंभिक स्थितियाँ आकर्षण के क्रमिक आधारों में हैं: | ||
:{| | :{| | ||
|{{val|2.35287527}}|| | |{{val|2.35287527}}||में परिवर्तित होता है|| align="right" |4; | ||
|- | |- | ||
|{{val|2.35284172}}|| | |{{val|2.35284172}}||में परिवर्तित होता है|| align="right" |−3; | ||
|- | |- | ||
|{{val|2.35283735}}|| | |{{val|2.35283735}}||में परिवर्तित होता है|| align="right" |4; | ||
|- | |- | ||
|{{val|2.352836327}}|| | |{{val|2.352836327}}||में परिवर्तित होता है|| align="right" |−3; | ||
|- | |- | ||
|{{val|2.352836323}}|| | |{{val|2.352836323}}||में परिवर्तित होता है|| align="right" |1. | ||
|} | |} | ||
== विफलता विश्लेषण == | == विफलता विश्लेषण == | ||
न्यूटन की विधि केवल तभी अभिसरण की गारंटी देती है जब कुछ शर्तों को पूरा किया जाता है। यदि द्विघात अभिसरण के प्रमाण में की गई मान्यताएँ पूरी होती हैं, तो विधि अभिसरण होगी। निम्नलिखित उपखंडों के लिए, अभिसरण की विधि की विफलता | न्यूटन की विधि केवल तभी अभिसरण की गारंटी देती है जब कुछ शर्तों को पूरा किया जाता है। यदि द्विघात अभिसरण के प्रमाण में की गई मान्यताएँ पूरी होती हैं, तो विधि अभिसरण होगी। निम्नलिखित उपखंडों के लिए, अभिसरण की विधि की विफलता निरुपित करती है कि प्रमाण में की गई धारणाएं पूरी नहीं हुईं। | ||
=== खराब | === खराब प्रारंभिक बिंदु === | ||
कुछ | कुछ स्थितियों में फलन पर शर्तें जो अभिसरण के लिए आवश्यक हैं, संतुष्ट हैं, किन्तु प्रारंभिक बिंदु के रूप में चुना गया बिंदु उस अंतराल में नहीं है जहां विधि अभिसरण करती है। यह हो सकता है, उदाहरण के लिए, यदि वह फलन जिसकी मूल खोजी गई है शून्य विषमता के रूप में पहुँचता है क्योंकि {{mvar|x}} {{math|∞}} या {{math|−∞}} में जाता है। ऐसे स्थितियों में एक अलग विधि, जैसे कि [[द्विभाजन विधि]], का उपयोग शून्य के प्रारंभिक बिंदु के रूप में उपयोग करने के लिए एक उत्तम अनुमान प्राप्त करने के लिए किया जाना चाहिए। | ||
==== पुनरावृति बिंदु स्थिर है ==== | ==== पुनरावृति बिंदु स्थिर है ==== | ||
फलन पर विचार करें: | |||
:<math>f(x) = 1-x^2.</math> | :<math>f(x) = 1-x^2.</math> | ||
यह {{math|''x'' {{=}} 0}} पर अधिकतम है और {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') {{=}} 0}} का समाधान {{math|''x'' {{=}} ±1}} पर है। अगर हम स्थिर बिंदु {{math|''x''<sub>0</sub> {{=}} 0}} (जहां व्युत्पन्न शून्य है) से पुनरावृति शुरू करते हैं, तो {{math|''x''<sub>1</sub>}} अपरिभाषित होगा, क्योंकि {{math|(0, 1)}} पर स्पर्शरेखा {{mvar|x}}-अक्ष के समानांतर है: | |||
:<math>x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = 0 - \frac{1}{0}.</math> | :<math>x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = 0 - \frac{1}{0}.</math> | ||
वही समस्या तब होती है, जब | वही समस्या तब होती है, जब प्रारंभिक बिंदु के बजाय, कोई पुनरावृत्ति बिंदु स्थिर होता है। यहां तक कि यदि व्युत्पन्न छोटा है, किन्तु शून्य नहीं है, तो अगला पुनरावृत्ति बहुत खराब सन्निकटन होगा। | ||
====प्रारंभिक बिंदु एक चक्र में प्रवेश करता है ==== | ====प्रारंभिक बिंदु एक चक्र में प्रवेश करता है ==== | ||
[[Image:NewtonsMethodConvergenceFailure.svg|thumb|300px|की स्पर्श रेखाएँ {{math|''x''<sup>3</sup> − 2''x'' + 2}} पर 0 और 1 प्रतिच्छेद करते हैं {{mvar|x}}-अक्ष क्रमशः 1 और 0 पर, यह दर्शाता है कि क्यों न्यूटन की विधि कुछ | [[Image:NewtonsMethodConvergenceFailure.svg|thumb|300px|की स्पर्श रेखाएँ {{math|''x''<sup>3</sup> − 2''x'' + 2}} पर 0 और 1 प्रतिच्छेद करते हैं {{mvar|x}}-अक्ष क्रमशः 1 और 0 पर, यह दर्शाता है कि क्यों न्यूटन की विधि कुछ प्रारंभिक बिंदुओं के लिए इन मानों के बीच दोलन करती है।]]कुछ कार्यों के लिए, कुछ प्रारंभिक बिंदु अभिसरण को रोकते हुए एक अनंत चक्र में प्रवेश कर सकते हैं। मान लीजिये | ||
:<math>f(x) = x^3 - 2x + 2 \!</math> | :<math>f(x) = x^3 - 2x + 2 \!</math> | ||
और 0 को | और 0 को प्रारंभिक बिंदु के रूप में लें। पहला पुनरावृति 1 उत्पन्न करता है और दूसरा पुनरावृति 0 पर लौटता है, इसलिए अनुक्रम दोनों के बीच एक मूल में परिवर्तित हुए बिना वैकल्पिक होगा। वास्तव में, यह 2-चक्र स्थिर है: 0 और 1 के आस-पास निकट हैं, जहां से सभी बिंदु 2-चक्र (और इसलिए फलन की मूल तक नहीं) के लिए समान रूप से पुनरावृत्त होते हैं। सामान्य तौर पर, अनुक्रम का व्यवहार बहुत जटिल हो सकता है ([[न्यूटन फ्रैक्टल]] देखें)। इस समीकरण का वास्तविक समाधान {{val|−1.76929235}}…. है। | ||
=== व्युत्पन्न मुद्दे === | === व्युत्पन्न मुद्दे === | ||
यदि मूल के | यदि मूल के निकट में फलन निरंतर अवकलनीय नहीं है तो यह संभव है कि न्यूटन की विधि हमेशा विचलन और विफल होगी, जब तक कि पहली कोशिश में समाधान का अनुमान नहीं लगाया जाता है। | ||
==== व्युत्पन्न | ==== व्युत्पन्न मूल पर उपस्थित नहीं है ==== | ||
फलन का एक सरल उदाहरण जहां न्यूटन की विधि विचलन करती है, शून्य का घनमूल खोजने का प्रयास कर रहा है। घनमूल निरंतर और | फलन का एक सरल उदाहरण जहां न्यूटन की विधि विचलन करती है, शून्य का घनमूल खोजने का प्रयास कर रहा है। घनमूल निरंतर और अनंत रूप से अलग-अलग है, को छोड़कर {{math|''x'' {{=}} 0}}, जहां इसकी व्युत्पत्ति अपरिभाषित है: | ||
:<math>f(x) = \sqrt[3]{x}.</math> | :<math>f(x) = \sqrt[3]{x}.</math> | ||
Line 170: | Line 175: | ||
:<math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{{x_n}^\frac13}{\frac13{x_n}^{-\frac23}} = x_n - 3x_n = -2x_n.</math> | :<math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{{x_n}^\frac13}{\frac13{x_n}^{-\frac23}} = x_n - 3x_n = -2x_n.</math> | ||
एल्गोरिथ्म समाधान को ओवरशूट करता है और {{mvar|y}}-अक्ष के दूसरी ओर लैंड करता है, प्रारंभ में न्यूटन की विधि को प्रायुक्त करने की तुलना में दूर, वास्तव में प्रत्येक पुनरावृत्ति पर समाधान से दूरी को दोगुना कर देता है। | |||
वास्तव में, | वास्तव में, प्रत्येक {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') {{=}} {{abs|''x''}}<sup>''α''</sup>}}, जहाँ {{math|0 < ''α'' < {{sfrac|1|2}}}} के लिए पुनरावृत्तियाँ अनंत तक जाती हैं। {{math|''α'' {{=}} {{sfrac|1|2}}}} (वर्गमूल) के सीमित स्थिति में, पुनरावृत्तियाँ बिंदुओं {{math|''x''<sub>0</sub>}} और {{math|−''x''<sub>0</sub>}} के बीच अनिश्चित काल तक वैकल्पिक रहेंगी, इसलिए वे इस स्थिति में भी अभिसरण नहीं करते हैं। | ||
==== असंतुलित व्युत्पन्न ==== | ==== असंतुलित व्युत्पन्न ==== | ||
यदि व्युत्पन्न मूल पर निरंतर नहीं है, तो | यदि व्युत्पन्न मूल पर निरंतर नहीं है, तो मूल के किसी भी निकट में अभिसरण विफल हो सकता है। फलन पर विचार करें | ||
:<math>f(x) = \begin{cases} | :<math>f(x) = \begin{cases} | ||
Line 186: | Line 191: | ||
1 + 2x\sin \frac{2}{x} - 2\cos \frac{2}{x} & \text{if } x \neq 0. | 1 + 2x\sin \frac{2}{x} - 2\cos \frac{2}{x} & \text{if } x \neq 0. | ||
\end{cases}</math> | \end{cases}</math> | ||
मूल के किसी भी | मूल के किसी भी निकट के भीतर, यह व्युत्पन्न चिन्ह के रूप में बदलता रहता है {{math|''x''}} दाएँ (या बाएँ से) 0 तक पहुँचता है जबकि {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') ≥ ''x'' − ''x''<sup>2</sup> > 0}} के लिए {{math|0 < ''x'' < 1}}. | ||
इसलिए {{math|{{sfrac|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'')}}}} | इसलिए {{math|{{sfrac|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'')}}}} मूल के पास अबाधित है, और न्यूटन की विधि इसके किसी भी निकट में लगभग हर जगह अलग हो जाएगी, तथापि: | ||
* | * फलन हर जगह अलग-अलग (और इस प्रकार निरंतर) है; | ||
*मूल पर व्युत्पन्न अशून्य है; | *मूल पर व्युत्पन्न अशून्य है; | ||
*{{mvar|f}} मूल को छोड़कर | *{{mvar|f}} मूल को छोड़कर अनंत रूप से भिन्न है; और | ||
*व्युत्पन्न मूल | *व्युत्पन्न मूल (विपरीत {{math|{{sfrac|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'')}}}}) के एक निकट में घिरा है. | ||
=== गैर द्विघात अभिसरण === | === गैर द्विघात अभिसरण === | ||
कुछ | कुछ स्थितियों में पुनरावृति अभिसरण करती है किन्तु जितनी जल्दी वादा किया गया है उतनी जल्दी अभिसरण नहीं करती है। इन स्थितियों में सरल विधियाँ न्यूटन की विधि जितनी जल्दी अभिसरित होती हैं। | ||
==== शून्य व्युत्पन्न ==== | ==== शून्य व्युत्पन्न ==== | ||
यदि प्रथम अवकलज मूल पर शून्य है, तो अभिसरण द्विघात नहीं होगा। | यदि प्रथम अवकलज मूल पर शून्य है, तो अभिसरण द्विघात नहीं होगा। मान लीजिये | ||
:<math>f(x) = x^2 \!</math> | :<math>f(x) = x^2 \!</math> | ||
Line 204: | Line 209: | ||
:<math>x - \frac{f(x)}{f'(x)} = \frac{x}{2} .</math> | :<math>x - \frac{f(x)}{f'(x)} = \frac{x}{2} .</math> | ||
इसलिए अभिसरण द्विघात नहीं है, | इसलिए अभिसरण द्विघात नहीं है, तथापि फलन हर जगह अपरिमित रूप से भिन्न हो। | ||
इसी तरह की समस्या तब भी होती है जब मूल केवल लगभग दोगुनी होती है। उदाहरण के लिए, | इसी तरह की समस्या तब भी होती है जब मूल केवल लगभग दोगुनी होती है। उदाहरण के लिए, मान लो | ||
:<math>f(x) = x^2(x-1000)+1.</math> | :<math>f(x) = x^2(x-1000)+1.</math> | ||
Line 221: | Line 226: | ||
==== कोई दूसरा व्युत्पन्न नहीं ==== | ==== कोई दूसरा व्युत्पन्न नहीं ==== | ||
यदि मूल पर कोई दूसरा व्युत्पन्न नहीं है, तो अभिसरण द्विघात होने में विफल हो सकता है। | यदि मूल पर कोई दूसरा व्युत्पन्न नहीं है, तो अभिसरण द्विघात होने में विफल हो सकता है। मान लीजिये | ||
:<math>f(x) = x + x^\frac43.</math> | :<math>f(x) = x + x^\frac43.</math> | ||
तब | तब | ||
Line 227: | Line 232: | ||
और | और | ||
:<math>f''(x) = \tfrac49 x^{-\frac23} </math> | :<math>f''(x) = \tfrac49 x^{-\frac23} </math> | ||
सिवाय कब {{math|''x'' {{=}} 0}} जहां यह अपरिभाषित है। | सिवाय कब {{math|''x'' {{=}} 0}} जहां यह अपरिभाषित है। {{math|''x<sub>n</sub>''}} दिया गया हैं, | ||
:<math>x_{n+1} = x_n - \frac{f(x_n)}{f '(x_n)} = \frac{\frac13{x_n}^\frac43}{1 + \tfrac43{x_n}^\frac13} </math> | :<math>x_{n+1} = x_n - \frac{f(x_n)}{f '(x_n)} = \frac{\frac13{x_n}^\frac43}{1 + \tfrac43{x_n}^\frac13} </math> | ||
जिसमें | जिसमें {{math|''x<sub>n</sub>''}} की तुलना में लगभग {{sfrac|4|3}} गुना शुद्धता है। यह द्विघात अभिसरण के लिए आवश्यक 2 गुना से कम है। तो न्यूटन की विधि का अभिसरण (इस स्थिति में) द्विघात नहीं है, तथापि: फलन हर जगह लगातार भिन्न होता है; व्युत्पन्न मूल पर शून्य नहीं है; और {{mvar|f}} वांछित मूल को छोड़कर अपरिमित रूप से अवकलनीय है। | ||
== सामान्यीकरण == | == सामान्यीकरण == | ||
Line 237: | Line 242: | ||
[[Image:newtroot 1 0 0 0 0 m1.png|thumb|के लिए आकर्षण का केंद्र {{math|''x''<sup>5</sup> − 1 {{=}} 0}}; गहरे रंग का अर्थ है अभिसरण के लिए अधिक पुनरावृत्तियों।]] | [[Image:newtroot 1 0 0 0 0 m1.png|thumb|के लिए आकर्षण का केंद्र {{math|''x''<sup>5</sup> − 1 {{=}} 0}}; गहरे रंग का अर्थ है अभिसरण के लिए अधिक पुनरावृत्तियों।]] | ||
{{main|Newton fractal}} | {{main|Newton fractal}} | ||
[[जटिल विश्लेषण]] से निपटने के दौरान, उनके शून्यों को खोजने के लिए न्यूटन की विधि को सीधे | [[जटिल विश्लेषण]] से निपटने के दौरान, उनके शून्यों को खोजने के लिए न्यूटन की विधि को सीधे प्रायुक्त किया जा सकता है।<ref>{{cite journal|last=Henrici|author-link=Peter Henrici (mathematician)|first=Peter |title= एप्लाइड और कम्प्यूटेशनल जटिल विश्लेषण|volume=1 |date=1974}}</ref> प्रत्येक शून्य में जटिल विमान में आकर्षण का एक आधार होता है, सभी प्रारंभिक मानों का सेट जो विधि को उस विशेष शून्य में अभिसरण करने का कारण बनता है। दिखाए गए चित्र के अनुसार इन सेटों को मैप किया जा सकता है। कई जटिल कार्यों के लिए, आकर्षण के आधारों की सीमाएं [[ भग्न ]] होती हैं। | ||
कुछ | कुछ स्थितियों में जटिल विमान में ऐसे क्षेत्र होते हैं जो आकर्षण के इन बेसिनों में से किसी में नहीं होते हैं, जिसका अर्थ है कि पुनरावृत्त अभिसरण नहीं होते हैं। उदाहरण के लिए,<ref>{{cite journal|last=Strang |first=Gilbert |title=A chaotic search for {{mvar|i}} |journal=[[The College Mathematics Journal]] |volume=22 |date=Jan 1991 |issue=1 |pages=3–12 |doi=10.2307/2686733|jstor=2686733 }}</ref> यदि कोई मूल की तलाश के लिए वास्तविक प्रारंभिक स्थिति का उपयोग करता है {{math|''x''<sup>2</sup> + 1}}, बाद के सभी पुनरावृत्तियाँ वास्तविक संख्याएँ होंगी और इसलिए पुनरावृत्तियाँ किसी भी मूल में परिवर्तित नहीं हो सकती हैं, क्योंकि दोनों मूले गैर-वास्तविक हैं। इस स्थिति में [[लगभग सभी]] वास्तविक प्रारंभिक स्थितियाँ [[अराजकता सिद्धांत]] की ओर ले जाती हैं, जबकि कुछ प्रारंभिक स्थितियाँ या तो अनंत तक या किसी परिमित लंबाई के चक्रों को दोहराती हैं। | ||
कर्ट मैकमुलेन ने दिखाया है कि न्यूटन की विधि के समान किसी भी संभावित विशुद्ध रूप से पुनरावृत्त एल्गोरिदम के लिए, एल्गोरिथ्म डिग्री 4 या उच्चतर के कुछ बहुपदों पर | कर्ट मैकमुलेन ने दिखाया है कि न्यूटन की विधि के समान किसी भी संभावित विशुद्ध रूप से पुनरावृत्त एल्गोरिदम के लिए, एल्गोरिथ्म डिग्री 4 या उच्चतर के कुछ बहुपदों पर प्रायुक्त होने पर जटिल विमान के कुछ खुले क्षेत्रों में अलग हो जाएगा। चूंकि, मैकमुलेन ने डिग्री 3 के बहुपदों के लिए सामान्यतः अभिसरण एल्गोरिथम दिया।<ref>{{cite journal|last=McMullen |first=Curt |title=तर्कसंगत मानचित्रों और पुनरावृत्त रूट-खोज एल्गोरिदम के परिवार|journal=Annals of Mathematics |series=Second Series |volume=125 |date=1987 |issue=3 |pages=467–493 |doi=10.2307/1971408|jstor=1971408 |url=https://dash.harvard.edu/bitstream/handle/1/9876064/McMullen_FamiliesRationalMap.pdf?sequence=1 }}</ref> | ||
Line 252: | Line 257: | ||
=== समीकरणों की प्रणाली === | === समीकरणों की प्रणाली === | ||
===={{math|''k''}} चर, {{math|''k''}} फलन करता है==== | ===={{math|''k''}} चर, {{math|''k''}} फलन करता है==== | ||
की प्रणालियों को | की प्रणालियों को समाधान करने के लिए न्यूटन की विधि का भी उपयोग कर सकते हैं {{mvar|k}} समीकरण, जो (एक साथ) के शून्यों को खोजने के बराबर है {{mvar|k}} लगातार अलग-अलग फलन <math>f:\R^k\to \R.</math> यह एक सदिश-मूल्यवान फलन के शून्यों को खोजने के बराबर है <math>F:\R^k\to \R^k.</math> ऊपर दिए गए फॉर्मूलेशन में, स्केलर्स {{mvar|x<sub>n</sub>}} को वैक्टर द्वारा प्रतिस्थापित किया जाता है {{math|'''x'''<sub>''n''</sub>}} और फलन को विभाजित करने के बजाय {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x<sub>n</sub>'')}} इसके व्युत्पन्न द्वारा {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x<sub>n</sub>'')}} इसके बजाय फलन को गुणा करने के लिए एक को छोड़ना होगा {{math|''F''('''x'''<sub>''n''</sub>)}} इसके व्युत्क्रम द्वारा {{mvar|''k'' × ''k''}} [[जैकबियन मैट्रिक्स]] {{math|''J<sub>F</sub>''('''x'''<sub>''n''</sub>)}}. इसका परिणाम अभिव्यक्ति में होता है | ||
:<math>\mathbf{x}_{n+1} = \mathbf{x}_{n} - J_F(\mathbf{x}_n)^{-1} F(\mathbf{x}_n)</math>. | :<math>\mathbf{x}_{n+1} = \mathbf{x}_{n} - J_F(\mathbf{x}_n)^{-1} F(\mathbf{x}_n)</math>. | ||
वास्तव में जेकोबियन मैट्रिक्स के व्युत्क्रम की गणना करने के बजाय, [[रैखिक समीकरणों की प्रणाली]] को | वास्तव में जेकोबियन मैट्रिक्स के व्युत्क्रम की गणना करने के बजाय, [[रैखिक समीकरणों की प्रणाली]] को समाधान करके समय की बचत की जा सकती है और संख्यात्मक स्थिरता में वृद्धि की जा सकती है। | ||
:<math>J_F(\mathbf{x}_n) (\mathbf{x}_{n+1} - \mathbf{x}_n) = -F(\mathbf{x}_n)</math> | :<math>J_F(\mathbf{x}_n) (\mathbf{x}_{n+1} - \mathbf{x}_n) = -F(\mathbf{x}_n)</math> | ||
अज्ञात के लिए {{math|'''x'''<sub>''n'' + 1</sub> − '''x'''<sub>''n''</sub>}}. | अज्ञात के लिए {{math|'''x'''<sub>''n'' + 1</sub> − '''x'''<sub>''n''</sub>}}. | ||
===={{math|''k''}} चर, {{math|''m''}} समीकरण, के साथ {{math|''m'' > ''k''}}==== वह {{mvar|k}}-न्यूटन की विधि के आयामी संस्करण का उपयोग से अधिक की प्रणालियों को | <nowiki>====</nowiki>{{math|''k''}} चर, {{math|''m''}} समीकरण, के साथ {{math|''m'' > ''k''}}==== वह {{mvar|k}}-न्यूटन की विधि के आयामी संस्करण का उपयोग से अधिक की प्रणालियों को समाधान करने के लिए किया जा सकता है {{mvar|k}} (नॉनलाइनियर) समीकरण भी यदि एल्गोरिद्म गैर-स्क्वायर जैकोबियन मैट्रिक्स और निर्धारक मैट्रिक्स के सामान्यीकृत व्युत्क्रम का उपयोग करता है {{math|''J''{{isup|+}} {{=}} (''J''{{isup|T}}''J'')<sup>−1</sup>''J''{{isup|T}}}} के व्युत्क्रम के बजाय {{mvar|J}}. यदि गैर-रैखिक समीकरणों की प्रणाली का कोई समाधान नहीं है, तो विधि गैर-रैखिक कम से कम वर्गों के अर्थ में समाधान खोजने का प्रयास करती है। अधिक जानकारी के लिए गॉस-न्यूटन एल्गोरिथम देखें। | ||
=== एक बनच स्थान में === | === एक बनच स्थान में === | ||
एक अन्य सामान्यीकरण एक [[कार्यात्मक (गणित)]] की मूल खोजने के लिए न्यूटन की विधि है। {{mvar|F}} [[बनच स्थान]] में परिभाषित किया गया है। इस | एक अन्य सामान्यीकरण एक [[कार्यात्मक (गणित)]] की मूल खोजने के लिए न्यूटन की विधि है। {{mvar|F}} [[बनच स्थान]] में परिभाषित किया गया है। इस स्थिति में फॉर्मूलेशन है | ||
:<math>X_{n+1}=X_n-\bigl(F'(X_n)\bigr)^{-1}F(X_n),\,</math> | :<math>X_{n+1}=X_n-\bigl(F'(X_n)\bigr)^{-1}F(X_n),\,</math> | ||
जहाँ {{math|''F′''(''X<sub>n</sub>'')}} पर परिकलित फ्रेचेट व्युत्पन्न है {{math|''X<sub>n</sub>''}}. प्रत्येक पर बाउंडली इनवर्टिबल होने के लिए किसी को फ्रेचेट डेरिवेटिव की आवश्यकता होती है {{math|''X<sub>n</sub>''}} विधि प्रायुक्त होने के लिए। एक मूल के अस्तित्व और अभिसरण के लिए कंटोरोविच प्रमेय | न्यूटन-कंटोरोविच प्रमेय द्वारा एक शर्त दी गई है।<ref>{{cite book |first=Tetsuro |last=Yamamoto |chapter=Historical Developments in Convergence Analysis for Newton's and Newton-like Methods |pages=241–263 |editor-first=C. |editor-last=Brezinski |editor2-first=L. |editor2-last=Wuytack |title=Numerical Analysis : Historical Developments in the 20th Century |publisher=North-Holland |year=2001 |isbn=0-444-50617-9 }}</ref> | |||
Line 276: | Line 281: | ||
न्यूटन-फूरियर विधि, मूल सन्निकटन की पूर्ण त्रुटि पर सीमा प्रदान करने के लिए न्यूटन की विधि का [[जोसेफ फूरियर]] का विस्तार है, जबकि अभी भी द्विघात अभिसरण प्रदान करता है। | न्यूटन-फूरियर विधि, मूल सन्निकटन की पूर्ण त्रुटि पर सीमा प्रदान करने के लिए न्यूटन की विधि का [[जोसेफ फूरियर]] का विस्तार है, जबकि अभी भी द्विघात अभिसरण प्रदान करता है। | ||
ये मान लीजिए {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} पर लगातार दो बार अवकलनीय है {{math|[''a'', ''b'']}} ओर वो {{mvar|f}} में इस अंतराल में एक मूल है। ये मान लीजिए {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x''), ''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'') ≠ 0}} इस अंतराल पर (उदाहरण के लिए यह मामला है {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''a'') < 0}}, {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''b'') > 0}}, और {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') > 0}}, और {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'') > 0}} इस अंतराल पर)। यह गारंटी देता है कि इस अंतराल पर एक अद्वितीय मूल है, इसे कॉल करें {{mvar|α}}. यदि यह अवतल के बजाय अवतल है तो प्रतिस्थापित करें {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} द्वारा {{math|−''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} क्योंकि उनकी | ये मान लीजिए {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} पर लगातार दो बार अवकलनीय है {{math|[''a'', ''b'']}} ओर वो {{mvar|f}} में इस अंतराल में एक मूल है। ये मान लीजिए {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x''), ''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'') ≠ 0}} इस अंतराल पर (उदाहरण के लिए यह मामला है {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''a'') < 0}}, {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''b'') > 0}}, और {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') > 0}}, और {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'') > 0}} इस अंतराल पर)। यह गारंटी देता है कि इस अंतराल पर एक अद्वितीय मूल है, इसे कॉल करें {{mvar|α}}. यदि यह अवतल के बजाय अवतल है तो प्रतिस्थापित करें {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} द्वारा {{math|−''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} क्योंकि उनकी मूले समान हैं। | ||
मान लीजिये {{math|''x''<sub>0</sub> {{=}} ''b''}} अंतराल का सही समापन बिंदु बनें और दें {{math|''z''<sub>0</sub> {{=}} ''a''}} अंतराल का बायां समापन बिंदु हो। दिया गया {{math|''x<sub>n</sub>''}}, परिभाषित करना | |||
:<math>x_{n + 1} = x_n - \frac{f(x_n)}{f'(x_n)},</math> | :<math>x_{n + 1} = x_n - \frac{f(x_n)}{f'(x_n)},</math> | ||
Line 299: | Line 304: | ||
====माहली की प्रक्रिया ==== | ====माहली की प्रक्रिया ==== | ||
एक गैर-रैखिक समीकरण के सामान्य रूप से कई समाधान होते हैं। | एक गैर-रैखिक समीकरण के सामान्य रूप से कई समाधान होते हैं। किन्तु यदि प्रारंभिक मान उपयुक्त नहीं है, तो न्यूटन की विधि वांछित समाधान में अभिसरण नहीं कर सकती है या पहले पाए गए समान समाधान में अभिसरण कर सकती है। जब हम पहले से ही एन समाधान पा चुके हैं <math>f(x)=0</math>, तो अगला मूल न्यूटन की विधि को अगले समीकरण में प्रायुक्त करके पाया जा सकता है:<ref>{{harvnb|Press|Teukolsky|Vetterling|Flannery|1992}}{{Incomplete short citation|date=February 2019}}</ref><ref>{{harvnb|Stoer|Bulirsch|1980}}{{Incomplete short citation|date=February 2019}}</ref> | ||
:<math display="block">F(x) = \frac{f(x)}{\prod_{i=1}^N(x-x_i)} = 0 .</math> | :<math display="block">F(x) = \frac{f(x)}{\prod_{i=1}^N(x-x_i)} = 0 .</math> | ||
इस विधि का उपयोग दूसरे प्रकार के [[बेसेल समारोह]] के शून्य प्राप्त करने के लिए किया जाता है।<ref>{{harvnb|Zhang|Jin|1996}}{{Incomplete short citation|date=February 2019}}</ref> | इस विधि का उपयोग दूसरे प्रकार के [[बेसेल समारोह|बेसेल फलन]] के शून्य प्राप्त करने के लिए किया जाता है।<ref>{{harvnb|Zhang|Jin|1996}}{{Incomplete short citation|date=February 2019}}</ref> | ||
==== हिरानो की संशोधित न्यूटन विधि ==== | ==== हिरानो की संशोधित न्यूटन विधि ==== | ||
हिरानो की संशोधित न्यूटन विधि न्यूटन विधि के अभिसरण को संरक्षित करने और अस्थिरता से बचने के लिए एक संशोधन है।<ref>{{cite journal |first=Kazuo |last=Murota |date=1982 |doi=10.1137/0719055 |title=बीजगणितीय समीकरणों के लिए एक संशोधित न्यूटन पुनरावृत्ति का वैश्विक अभिसरण|journal=SIAM J. Numer. Anal. |volume=19 |issue=4 |pages=793–799|bibcode=1982SJNA...19..793M }}</ref> यह जटिल बहुपदों को | हिरानो की संशोधित न्यूटन विधि न्यूटन विधि के अभिसरण को संरक्षित करने और अस्थिरता से बचने के लिए एक संशोधन है।<ref>{{cite journal |first=Kazuo |last=Murota |date=1982 |doi=10.1137/0719055 |title=बीजगणितीय समीकरणों के लिए एक संशोधित न्यूटन पुनरावृत्ति का वैश्विक अभिसरण|journal=SIAM J. Numer. Anal. |volume=19 |issue=4 |pages=793–799|bibcode=1982SJNA...19..793M }}</ref> यह जटिल बहुपदों को समाधान करने के लिए विकसित किया गया है। | ||
==== अंतराल न्यूटन की विधि ==== | ==== अंतराल न्यूटन की विधि ==== | ||
[[अंतराल अंकगणित]] के साथ न्यूटन की विधि का संयोजन कुछ संदर्भों में बहुत उपयोगी होता है। यह एक रोक मानदंड प्रदान करता है जो सामान्य लोगों की तुलना में अधिक विश्वसनीय है (जो फलन का एक छोटा मान है या लगातार पुनरावृत्तियों के बीच चर का एक छोटा बदलाव है)। साथ ही, यह उन | [[अंतराल अंकगणित]] के साथ न्यूटन की विधि का संयोजन कुछ संदर्भों में बहुत उपयोगी होता है। यह एक रोक मानदंड प्रदान करता है जो सामान्य लोगों की तुलना में अधिक विश्वसनीय है (जो फलन का एक छोटा मान है या लगातार पुनरावृत्तियों के बीच चर का एक छोटा बदलाव है)। साथ ही, यह उन स्थितियों का पता लगा सकता है जहां न्यूटन की विधि सैद्धांतिक रूप से अभिसरण करती है किन्तु एक अपर्याप्त [[फ़्लोटिंग-पॉइंट अंकगणित]] के कारण संख्यात्मक रूप से अलग हो जाती है। फलन का मान; विल्किन्सन बहुपद देखें)।<ref>Moore, R. E. (1979). ''Methods and applications of interval analysis'' (Vol. 2). Siam.</ref><ref>Hansen, E. (1978). Interval forms of Newtons method. ''Computing'', 20(2), 153–163.</ref> | ||
विचार करना {{math|''f'' → {{mathcal|C}}<sup>1</sup>(''X'')}}, | विचार करना {{math|''f'' → {{mathcal|C}}<sup>1</sup>(''X'')}}, जहाँ {{mvar|X}} एक वास्तविक अंतराल है, और मान लीजिए कि हमारे पास एक अंतराल विस्तार है {{mvar|F′}} का {{mvar|<span style{{=}}"letter-spacing:0.15em">f</span>′}}, मतलब है कि {{mvar|F′}} इनपुट के रूप में एक अंतराल लेता है {{math|''Y'' ⊆ ''X''}} और एक अंतराल आउटपुट करता है {{math|''F′''(''Y'')}} ऐसा है कि: | ||
: <math>\begin{align} | : <math>\begin{align} | ||
F'([y,y]) &= \{f'(y)\}\\[5pt] | F'([y,y]) &= \{f'(y)\}\\[5pt] | ||
Line 318: | Line 323: | ||
: <math>N(Y) = m - \frac{f(m)}{F'(Y)} = \left\{\left.m - \frac{f(m)}{z} ~\right|~ z \in F'(Y)\right\}</math> | : <math>N(Y) = m - \frac{f(m)}{F'(Y)} = \left\{\left.m - \frac{f(m)}{z} ~\right|~ z \in F'(Y)\right\}</math> | ||
जहाँ {{math|''m'' ∈ ''Y''}}. ध्यान दें कि परिकल्पना पर {{mvar|F′}} इसका आशय है {{math|''N''(''Y'')}} अच्छी तरह से परिभाषित है और एक अंतराल है (अंतराल संचालन पर अधिक विवरण के लिए अंतराल अंकगणितीय देखें)। यह स्वाभाविक रूप से निम्नलिखित अनुक्रम की ओर जाता है: | |||
: <math> | : <math> | ||
\begin{align} | \begin{align} | ||
Line 325: | Line 330: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
[[औसत मूल्य प्रमेय|औसत मान प्रमेय]] यह सुनिश्चित करता है कि यदि कोई मूल है {{mvar|f}} में {{mvar|X<sub>k</sub>}}, तो यह अंदर भी है {{math|''X''<sub>''k'' + 1</sub>}}. इसके अलावा, पर परिकल्पना {{mvar|F′}} निश्चित करता है की {{math|''X''<sub>''k'' + 1</sub>}} का अधिकतम आधा आकार है {{mvar|X<sub>k</sub>}} कब {{mvar|m}} का मध्यबिंदु है {{mvar|Y}}, तो यह क्रम की ओर अभिसरित होता है {{math|[''x*'', ''x*'']}}, | [[औसत मूल्य प्रमेय|औसत मान प्रमेय]] यह सुनिश्चित करता है कि यदि कोई मूल है {{mvar|f}} में {{mvar|X<sub>k</sub>}}, तो यह अंदर भी है {{math|''X''<sub>''k'' + 1</sub>}}. इसके अलावा, पर परिकल्पना {{mvar|F′}} निश्चित करता है की {{math|''X''<sub>''k'' + 1</sub>}} का अधिकतम आधा आकार है {{mvar|X<sub>k</sub>}} कब {{mvar|m}} का मध्यबिंदु है {{mvar|Y}}, तो यह क्रम की ओर अभिसरित होता है {{math|[''x*'', ''x*'']}}, जहाँ {{mvar|x*}} का मूल है {{mvar|f}} में {{mvar|X}}. | ||
यदि {{math|''F′''(''X'')}} में सख्ती से 0 होता है, विस्तारित अंतराल विभाजन का उपयोग दो अंतरालों का एक संघ बनाता है {{math|''N''(''X'')}}; कई मूले इसलिए स्वचालित रूप से अलग और बंधी हुई हैं। | |||
== अनुप्रयोग == | == अनुप्रयोग == | ||
Line 333: | Line 338: | ||
===न्यूनीकरण और अधिकतमकरण की समस्याएं=== | ===न्यूनीकरण और अधिकतमकरण की समस्याएं=== | ||
{{main|Newton's method in optimization}} | {{main|Newton's method in optimization}} | ||
न्यूटन की विधि का उपयोग न्यूनतम या अधिकतम फलन खोजने के लिए किया जा सकता है {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}}. डेरिवेटिव न्यूनतम या अधिकतम पर शून्य है, इसलिए डेरिवेटिव के लिए न्यूटन की विधि को | न्यूटन की विधि का उपयोग न्यूनतम या अधिकतम फलन खोजने के लिए किया जा सकता है {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}}. डेरिवेटिव न्यूनतम या अधिकतम पर शून्य है, इसलिए डेरिवेटिव के लिए न्यूटन की विधि को प्रायुक्त करके स्थानीय मिनिमा और मैक्सिमा पाया जा सकता है। पुनरावृत्ति बन जाती है: | ||
:<math>x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}. </math> | :<math>x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}. </math> | ||
Line 348: | Line 353: | ||
यह विधि किसी घात श्रेणी के गुणक व्युत्क्रम की गणना करने के लिए भी बहुत कुशल है। | यह विधि किसी घात श्रेणी के गुणक व्युत्क्रम की गणना करने के लिए भी बहुत कुशल है। | ||
===अनुवांशिक समीकरणों को | ===अनुवांशिक समीकरणों को समाधान करना=== | ||
न्यूटन की विधि का उपयोग करके कई [[पारलौकिक समीकरण]]ों को | न्यूटन की विधि का उपयोग करके कई [[पारलौकिक समीकरण]]ों को समाधान किया जा सकता है। समीकरण दिया गया है | ||
:<math>g(x) = h(x), </math> | :<math>g(x) = h(x), </math> | ||
साथ {{math|''g''(''x'')}} और/या {{math|''h''(''x'')}} एक पारलौकिक फलन, कोई लिखता है | साथ {{math|''g''(''x'')}} और/या {{math|''h''(''x'')}} एक पारलौकिक फलन, कोई लिखता है | ||
:<math>f(x) = g(x) - h(x). </math> | :<math>f(x) = g(x) - h(x). </math> | ||
के मान {{mvar|x}} जो मूल समीकरण को | के मान {{mvar|x}} जो मूल समीकरण को समाधान करते हैं, तब के मूल हैं {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}}, जो न्यूटन की विधि द्वारा पाया जा सकता है। | ||
=== विशेष कार्यों के शून्य प्राप्त करना === | === विशेष कार्यों के शून्य प्राप्त करना === | ||
इसकी मूल प्राप्त करने के लिए न्यूटन की विधि बेसल कार्यों के अनुपात पर | इसकी मूल प्राप्त करने के लिए न्यूटन की विधि बेसल कार्यों के अनुपात पर प्रायुक्त होती है।<ref>{{harvtxt|Gil|Segura|Temme|2007}}{{Incomplete short citation|date=February 2019}}</ref> | ||
Line 388: | Line 393: | ||
धनात्मक संख्या ज्ञात करने की समस्या पर विचार करें <math display="inline">x</math> साथ <math display="inline">\cos x = x^3</math>. हम इसे शून्य का पता लगाने के रूप में फिर से लिख सकते हैं <math display="inline">f(x) = \cos(x)-x^3</math>. अपने पास <math display="inline">f'(x) = -\sin(x)-3x^2</math>. तब से <math display="inline">\cos(x) \le 1</math> सभी के लिए <math display="inline">x</math> और <math display="inline">x^3>1</math> के लिए <math display="inline">x>1</math>, हम जानते हैं कि हमारा समाधान 0 और 1 के बीच है। | धनात्मक संख्या ज्ञात करने की समस्या पर विचार करें <math display="inline">x</math> साथ <math display="inline">\cos x = x^3</math>. हम इसे शून्य का पता लगाने के रूप में फिर से लिख सकते हैं <math display="inline">f(x) = \cos(x)-x^3</math>. अपने पास <math display="inline">f'(x) = -\sin(x)-3x^2</math>. तब से <math display="inline">\cos(x) \le 1</math> सभी के लिए <math display="inline">x</math> और <math display="inline">x^3>1</math> के लिए <math display="inline">x>1</math>, हम जानते हैं कि हमारा समाधान 0 और 1 के बीच है। | ||
उदाहरण के लिए, प्रारंभिक अनुमान के साथ {{math|1=''x''<sub>0</sub> = 0.5}}, न्यूटन की विधि द्वारा दिया गया अनुक्रम है (ध्यान दें कि 0 का प्रारंभिक मान एक अपरिभाषित परिणाम की ओर ले जाएगा, जो प्रारंभिक बिंदु का उपयोग करने के महत्व को दर्शाता है जो समाधान के | उदाहरण के लिए, प्रारंभिक अनुमान के साथ {{math|1=''x''<sub>0</sub> = 0.5}}, न्यूटन की विधि द्वारा दिया गया अनुक्रम है (ध्यान दें कि 0 का प्रारंभिक मान एक अपरिभाषित परिणाम की ओर ले जाएगा, जो प्रारंभिक बिंदु का उपयोग करने के महत्व को दर्शाता है जो समाधान के निकट है): | ||
:<math>\begin{matrix} | :<math>\begin{matrix} | ||
Line 404: | Line 409: | ||
निम्नलिखित पायथन (प्रोग्रामिंग लैंग्वेज) (संस्करण 3.x) प्रोग्रामिंग लैंग्वेज में न्यूटन की विधि का एक कार्यान्वयन उदाहरण है, जो किसी फलन की मूल को खोजने के लिए है <code>f</code> जिसका व्युत्पन्न है <code>f_prime</code>. | निम्नलिखित पायथन (प्रोग्रामिंग लैंग्वेज) (संस्करण 3.x) प्रोग्रामिंग लैंग्वेज में न्यूटन की विधि का एक कार्यान्वयन उदाहरण है, जो किसी फलन की मूल को खोजने के लिए है <code>f</code> जिसका व्युत्पन्न है <code>f_prime</code>. | ||
प्रारंभिक अनुमान होगा {{math|1=''x''<sub>0</sub> = 1}} और | प्रारंभिक अनुमान होगा {{math|1=''x''<sub>0</sub> = 1}} और फलन होगा {{math|1=''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') = ''x''<sup>2</sup> − 2}} ताकि {{math|1=''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') = 2''x''}}. | ||
न्यूटन की विधि के प्रत्येक नए पुनरावृत्ति को द्वारा निरूपित किया जाएगा <code>x1</code>. हम गणना के दौरान जांच करेंगे कि क्या भाजक (<code>yprime</code>) बहुत छोटा हो जाता है (से छोटा <code>epsilon</code>), जो कि मामला होगा | न्यूटन की विधि के प्रत्येक नए पुनरावृत्ति को द्वारा निरूपित किया जाएगा <code>x1</code>. हम गणना के दौरान जांच करेंगे कि क्या भाजक (<code>yprime</code>) बहुत छोटा हो जाता है (से छोटा <code>epsilon</code>), जो कि मामला होगा यदि {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x''<sub>''n''</sub>) ≈ 0}}, अन्यथा बड़ी मात्रा में त्रुटि पेश की जा सकती है। <वाक्यविन्यास लैंग = पायथन 3 लाइन = 1> | ||
डेफ एफ (एक्स): | डेफ एफ (एक्स): | ||
रिटर्न x**2 - 2 # f(x) = x^2 - 2 | रिटर्न x**2 - 2 # f(x) = x^2 - 2 | ||
Line 425: | Line 430: | ||
yprime = f_prime(x0) | yprime = f_prime(x0) | ||
यदि एब्स (वाईप्राइम) <एप्सिलॉन: # रुकें यदि भाजक बहुत छोटा है | |||
तोड़ना | तोड़ना | ||
x1 = x0 - y / yprime # न्यूटन की गणना करें | x1 = x0 - y / yprime # न्यूटन की गणना करें | ||
यदि एब्स (X1 - x0) <= सहनशीलता: # रुकें जब परिणाम वांछित सहनशीलता के भीतर हो | |||
वापसी x1 # X1 सहिष्णुता और पुनरावृत्तियों की अधिकतम संख्या के भीतर एक समाधान है | वापसी x1 # X1 सहिष्णुता और पुनरावृत्तियों की अधिकतम संख्या के भीतर एक समाधान है | ||
Revision as of 17:23, 20 April 2023
संख्यात्मक विश्लेषण में, न्यूटन की विधि, जिसे न्यूटन-रैफसन विधि के रूप में भी जाना जाता है, जिसका नाम आइजैक न्यूटन और जोसेफ राफसन के नाम पर रखा गया है, यह एक मूल-फाइंडिंग एल्गोरिदम है जो एक वास्तविक संख्या मूल्यवान फलन (गणित) की मूलों (या शून्य) में क्रमिक रूप से उत्तम संख्यात्मक विश्लेषण उत्पन्न करता है। सबसे मूलभूत संस्करण एक वास्तविक चर x फलन के डेरिवेटिव f′′ के लिए परिभाषित एकल-चर फलन f से प्रारंभ होता है और f की मूल के लिए प्रारंभिक अनुमान x0 है। यदि फलन पर्याप्त मान्यताओं को संतुष्ट करता है और प्रारंभिक अनुमान निकट है, तो
मूल का x0 से उत्तम सन्निकटन है। ज्यामितीय रूप से, (x1, 0) x-अक्ष का प्रतिच्छेदन है और (x0, f(x0)) पर f के ग्राफ की स्पर्शरेखा है, जो कि उत्रतम अनुमान है, प्रारंभिक बिंदु पर रैखिक सन्निकटन की अद्वितीय मूल है। प्रक्रिया के रूप में दोहराया जाता है
जब तक कि एक पर्याप्त त्रुटिहीन मान प्राप्त नहीं हो जाता। प्रत्येक चरण के साथ सही अंकों की संख्या सामान्यतः दोगुनी हो जाती है। यह एल्गोरिद्म हाउसहोल्डर्स विधियों की श्रेणी में प्रथम है, इसके बाद हैली की विधि आती है। इस विधि को जटिल-मूल्यवान फलन और समीकरणों की प्रणालियों के लिए भी बढ़ाया जा सकता है।
विवरण
विचार एक प्रारंभिक अनुमान के साथ प्रारंभ करना है, फिर इसकी स्पर्शरेखा रेखा द्वारा फलन को अनुमानित करना और अंत में इसकी गणना करना है x-इस स्पर्श रेखा का अवरोधन। यह x-अवरोधन सामान्यतः पहले अनुमान की तुलना में मूल फलन की मूल के लिए एक उत्तम सन्निकटन होगा, और विधि पुनरावृत्त विधि हो सकती है।
यदि वक्र को स्पर्शरेखा रेखा f(x) पर x = xn इंटरसेप्ट करता है x-अक्ष पर xn+1 तो प्रवणता है
- .
xn+1 के लिए समाधान करना देता है
हम कुछ स्वैच्छिक प्रारंभिक मान x0 के साथ प्रक्रिया प्रारंभ करते हैं। (शून्य के जितना निकट हो उतना बेहतर है। किन्तु, शून्य कहां हो सकता है, इसके बारे में किसी भी अंतर्ज्ञान की अनुपस्थिति में, एक "अनुमान और जांच" विधि मध्यवर्ती मान प्रमेय की अपील करके संभावनाओं को यथोचित छोटे अंतराल तक सीमित कर सकती है।) विधि सामान्यतः अभिसरण होगा, बशर्ते यह प्रारंभिक अनुमान अज्ञात शून्य के काफी निकट हो, और वह f′(x0) ≠ 0. इसके अलावा, बहुलता (गणित) 1 के शून्य के लिए, अभिसरण शून्य के एक निकट (गणित) में कम से कम द्विघात (अभिसरण की दर देखें) है, जिसका सहज अर्थ है कि प्रत्येक चरण में सही अंकों की संख्या सामान्यतः दोगुनी हो जाती है। अधिक विवरण नीचे § विश्लेषण में पाया जा सकता है।
हाउसहोल्डर्स की विधियाँ समान हैं किन्तु और भी तेजी से अभिसरण के लिए उच्च क्रम हैं। चूँकि, प्रत्येक चरण के लिए आवश्यक अतिरिक्त संगणनाएँ न्यूटन की विधि के सापेक्ष समग्र प्रदर्शन को धीमा कर सकती हैं, विशेष रूप से यदि f या इसके डेरिवेटिव मूल्यांकन के लिए कम्प्यूटेशनल रूप से महंगे हैं।
इतिहास
न्यूटन की विधि का नाम इसहाक न्यूटन के अनंत पदों के साथ समीकरणों द्वारा विश्लेषण पर (1669 में लिखा गया, विलियम जोन्स (गणितज्ञ) द्वारा 1711 में प्रकाशित) और डी मेटोडिस फ्लक्सियोनम एट सेरीरम इनफिनिटरम (लिखित) में विधि के एक विशेष स्थिति के वर्णन से लिया गया है। 1671 में, जॉन कोलसन द्वारा 1736 में प्रवाह की विधि के रूप में अनुवादित और प्रकाशित)। चूँकि, उनकी विधि ऊपर दी गई आधुनिक पद्धति से काफी भिन्न है। न्यूटन ने इस विधि को केवल बहुपदों के लिए प्रायुक्त किया, प्रारंभिक मूल अनुमान से प्रारंभ करके और त्रुटि सुधारों के अनुक्रम को निकाला। उन्होंने शेष त्रुटि के संदर्भ में बहुपद को फिर से लिखने के लिए प्रत्येक सुधार का उपयोग किया, और फिर उच्च-स्तर की शर्तों की उपेक्षा करके एक नए सुधार के लिए समाधान किया। उन्होंने विधि को डेरिवेटिव के साथ स्पष्ट रूप से नहीं जोड़ा या एक सामान्य सूत्र प्रस्तुत नहीं किया। न्यूटन ने इस पद्धति को संख्यात्मक और बीजगणितीय दोनों समस्याओं के लिए प्रायुक्त किया, बाद वाले स्थिति में टेलर श्रृंखला का निर्माण किया।
हो सकता है कि न्यूटन ने अपनी पद्धति फ्रांसिस लाइफ द्वारा एक समान, कम त्रुटिहीन विधि से प्राप्त की हो। मध्यकालीन इस्लाम शराफ अल-दीन अल-तुसी में गणित के काम में वीटा की पद्धति का सार पाया जा सकता है, जबकि उनके उत्तराधिकारी जमशीद अल-काशी ने समाधान करने के लिए न्यूटन की विधि का एक रूप इस्तेमाल किया xP − N = 0 की मूले खोजने के लिए N (वाईपीएमए 1995)। वर्गमूलों की गणना के लिए न्यूटन की विधि का एक विशेष मामला प्राचीन काल से जाना जाता था और इसे अक्सर बेबीलोनियन विधि कहा जाता है।
17वीं शताब्दी के जापानी गणितज्ञ सेकी कोवा द्वारा एकल-चर समीकरणों को समाधान करने के लिए न्यूटन की विधि का उपयोग किया गया था, चूंकि कलन के साथ संबंध गायब था।[1] न्यूटन की विधि पहली बार 1685 में जॉन वालिस द्वारा हिस्टोरिकल एंड प्रैक्टिकल दोनों में बीजगणित के एक ग्रंथ में प्रकाशित हुई थी।[2] 1690 में, जोसेफ रैफसन ने सार्वभौम समीकरणों के विश्लेषण में एक सरलीकृत विवरण प्रकाशित किया।[3] रैफसन ने भी इस विधि को केवल बहुपदों पर प्रायुक्त किया, किन्तु उन्होंने मूल बहुपद से प्रत्येक क्रमिक सुधार को निकाल कर न्यूटन की थकाऊ पुनर्लेखन प्रक्रिया से परहेज किया। इसने उन्हें प्रत्येक समस्या के लिए पुन: प्रयोज्य पुनरावृत्त अभिव्यक्ति प्राप्त करने की अनुमति दी। अंत में, 1740 में, थॉमस सिम्पसन ने न्यूटन की विधि को कैलकुलस का उपयोग करके सामान्य अरैखिक समीकरणों को समाधान करने के लिए एक पुनरावृत्ति विधि के रूप में वर्णित किया, अनिवार्य रूप से उपरोक्त विवरण दिया। उसी प्रकाशन में, सिम्पसन भी दो समीकरणों की प्रणालियों का सामान्यीकरण करता है और नोट करता है कि न्यूटन की विधि का उपयोग ढाल को शून्य पर सेट करके अनुकूलन समस्याओं को समाधान करने के लिए किया जा सकता है।
न्यूटन-फूरियर काल्पनिक समस्या में 1879 में आर्थर केली 2 से अधिक डिग्री और जटिल प्रारंभिक मानों वाले बहुपदों की जटिल मूलों के लिए न्यूटन की विधि को सामान्य बनाने में कठिनाइयों पर ध्यान देने वाले पहले व्यक्ति थे। इसने तर्कसंगत कार्यों के जूलिया सेट के अध्ययन का रास्ता खोल दिया।
व्यावहारिक विचार
न्यूटन की विधि एक शक्तिशाली तकनीक है - सामान्यतः अभिसरण की दर द्विघात होती है: जैसे-जैसे विधि मूल पर अभिसरण करती है, मूल और सन्निकटन के बीच का अंतर चुकता होता है (त्रुटिहीन अंकों की संख्या सामान्यतः दोगुनी हो जाती है)। चूँकि, विधि के साथ कुछ कठिनाइयाँ हैं।
किसी फलन के व्युत्पन्न की गणना करने में कठिनाई
न्यूटन की विधि के लिए आवश्यक है कि व्युत्पन्न की सीधे गणना की जा सके। व्युत्पन्न के लिए एक विश्लेषणात्मक अभिव्यक्ति आसानी से प्राप्त करने योग्य नहीं हो सकती है या मूल्यांकन के लिए महंगा हो सकता है। इन स्थितियों में, फलन पर दो पास के बिंदुओं के माध्यम से एक रेखा के प्रवणता का उपयोग करके व्युत्पन्न को अनुमानित करना उचित हो सकता है। इस सन्निकटन का उपयोग करने से सीकेंट विधि जैसा कुछ होगा जिसका अभिसरण न्यूटन की विधि की तुलना में धीमा है।
मूल में एकाग्र होने की विधि की विफलता
इसे प्रायुक्त करने से पहले न्यूटन की न्यूटन की विधि के पुनरावृत्त विधि के लिए द्विघात अभिसरण के प्रमाण की समीक्षा करना महत्वपूर्ण है। विशेष रूप से, किसी को प्रमाण में की गई धारणाओं की समीक्षा करनी चाहिए। #विफलता विश्लेषण के लिए, ऐसा इसलिए है क्योंकि इस प्रमाण में की गई धारणाएँ पूरी नहीं हुई हैं।
ओवरशूट
यदि पहली व्युत्पत्ति किसी विशेष मूल के निकट में अच्छी तरह से व्यवहार नहीं की जाती है, तो विधि ओवरशूट हो सकती है और उस मूल से अलग हो सकती है। एक मूल के साथ एक फलन का उदाहरण, जिसके लिए मूल के निकट में डेरिवेटिव अच्छी तरह से व्यवहार नहीं किया जाता है
जिसके लिए मूल ओवरशूट होगा और का क्रम x विचलन करेगा। के लिए a = 1/2, मूल अभी भी ओवरशूट होगा, किन्तु अनुक्रम दो मानों के बीच दोलन करेगा। के लिए 1/2 < a < 1, मूल अभी भी ओवरशूट होगा किन्तु अनुक्रम अभिसरण करेगा, और के लिए a ≥ 1 मूल बिल्कुल भी ओवरशूट नहीं होगा।
कुछ स्थितियों में, क्रमिक अति-विश्राम#विधि के अन्य अनुप्रयोगों|क्रमिक अति-विश्राम का उपयोग करके न्यूटन की विधि को स्थिर किया जा सकता है, या समान विधि का उपयोग करके अभिसरण की गति को बढ़ाया जा सकता है।
स्थिर बिंदु
यदि फलन का एक स्थिर बिंदु सामने आया है, तो व्युत्पन्न शून्य है और शून्य से विभाजन के कारण विधि समाप्त हो जाएगी।
खराब प्रारंभिक अनुमान
प्रारंभिक अनुमान में एक बड़ी त्रुटि एल्गोरिथम के गैर-अभिसरण में योगदान कर सकती है। इस समस्या को दूर करने के लिए अक्सर उस फलन को रेखीयकृत किया जा सकता है जिसे कलन, लॉग, अंतर, या यहां तक कि विकासवादी एल्गोरिदम का उपयोग करके अनुकूलित किया जा रहा है, जैसे स्टोकेस्टिक टनलिंग। अच्छा प्रारंभिक अनुमान अंतिम विश्व स्तर पर इष्टतम पैरामीटर अनुमान के निकट है। अरेखीय प्रतिगमन में, चुकता त्रुटियों (SSE) का योग केवल अंतिम पैरामीटर अनुमानों के क्षेत्र में परवलयिक के निकट है। यहां मिले प्रारंभिक अनुमानों से न्यूटन-रेफसन पद्धति को शीघ्रता से अभिसरण करने की अनुमति मिलेगी। यह केवल यहीं है कि एसएसई का हेसियन मैट्रिक्स सकारात्मक है और एसएसई का पहला व्युत्पन्न शून्य के निकट है।
गैर-अभिसरण का शमन
न्यूटन की विधि के एक मजबूत कार्यान्वयन में, पुनरावृत्तियों की संख्या पर सीमाएं लगाना आम है, मूल को समाहित करने के लिए ज्ञात अंतराल के समाधान को बाध्य करना, और अधिक मजबूत मूल खोज विधि के साथ विधि को संयोजित करना।
1 से अधिक बहुलता की मूलों के लिए धीमा अभिसरण
यदि खोजी जा रही मूल में बहुलता (गणित) # एक से अधिक बहुपद की मूल की बहुलता है, तो अभिसरण दर केवल रैखिक है (प्रत्येक चरण पर एक स्थिर कारक द्वारा कम की गई त्रुटियां) जब तक कि विशेष कदम नहीं उठाए जाते। जब दो या दो से अधिक मूले एक-दूसरे के निकट होती हैं, तो द्विघात अभिसरण स्पष्ट होने के लिए पुनरावृति उनमें से किसी एक के काफी निकट आने से पहले कई पुनरावृत्तियों को ले सकती है। चूँकि, यदि बहुलता m मूल ज्ञात है, निम्नलिखित संशोधित एल्गोरिथ्म द्विघात अभिसरण दर को संरक्षित करता है:[4]
यह क्रमिक अति-विश्राम का उपयोग करने के बराबर है। दूसरी ओर, यदि बहुलता m का मूल ज्ञात नहीं है, इसका अनुमान लगाया जा सकता है m एक या दो पुनरावृत्तियों को पूरा करने के बाद, और फिर अभिसरण की दर बढ़ाने के लिए उस मान का उपयोग करें।
यदि मूल की बहुलता m परिमित है तो g(x) = f(x)/f′(x) की बहुलता 1 के साथ एक ही स्थान पर एक मूल होगी। g(x) के मूल को खोजने के लिए न्यूटन की विधि को प्रायुक्त करना ठीक हो जाता है कई स्थितियों में द्विघात अभिसरण चूंकि इसमें सामान्यतः f(x) का दूसरा अवकलज सम्मिलित होता है। एक विशेष रूप से सरल स्थिति में, यदि f(x) = xm तब g(x) = x/m और न्यूटन की विधि मूल को एकल पुनरावृत्ति में खोजती है
विश्लेषण
मान लीजिए कि फ़ंक्शन f का α पर एक शून्य है, अर्थात, f(α) = 0, और f, α के टोपोलॉजिकल निकट में अवकलनीय है।
यदि f निरंतर अवकलनीय है और इसका व्युत्पन्न α पर अशून्य है, तो α का एक सामयिक निकट उपस्थित है जैसे कि सभी प्रारंभिक मानों के लिए x0 उस निकट में, अनुक्रम (xn)α अनुक्रम की सीमा को सीमित कर देगा।[5]
यदि f निरंतर अवकलनीय है, इसका व्युत्पन्न α पर अशून्य है, और इसका α पर दूसरा व्युत्पन्न है, तो अभिसरण द्विघात या तेज है। यदि α पर दूसरा व्युत्पन्न 0 नहीं है तो अभिसरण केवल द्विघात है। यदि तीसरा व्युत्पन्न उपस्थित है और α के निकट में घिरा हुआ है , तब:
जहाँ
यदि व्युत्पन्न α पर 0 है, तो अभिसरण आमतौर पर केवल रैखिक होता है। विशेष रूप से, यदि f लगातार दो बार भिन्न होता है, f′(α) = 0 और f″(α) ≠ 0, तो α का एक निकट उपस्थित है α जैसे कि, सभी प्रारंभिक मानों के लिए x0 उस निकट में, पुनरावृति का क्रम अभिसरण की दर 1/2 के साथ रैखिक रूप से अभिसरित होता है।[6] वैकल्पिक रूप से, यदि f′(α) = 0 और f′(x) ≠ 0 के लिए x ≠ α, x α के एक सामयिक निकट U में, α बहुलता r का शून्य होना (गणित), और यदि f ∈ Cr(U), तो वहाँ α का एक निकट उपस्थित है जैसे कि, सभी प्रारंभिक मानों x0 के लिए उस निकट में, पुनरावृत्तियों का क्रम रैखिक रूप से परिवर्तित होता है।
चूंकि, पैथोलॉजिकल स्थितियों में भी रैखिक अभिसरण की गारंटी नहीं है।
व्यवहार में, ये परिणाम स्थानीय हैं, और अभिसरण का निकट पहले से ज्ञात नहीं है। किन्तु वैश्विक अभिसरण पर भी कुछ परिणाम हैं: उदाहरण के लिए, α का सही निकट U+ दिया गया है यदि f U+में दो बार अवकलनीय है और यदि f′ ≠ 0, f · f″ > 0 U+ में है, तो, U+ में प्रत्येक x0 के लिए अनुक्रम xk मोनोटोनिक रूप से α तक घट रहा है।
न्यूटन की पुनरावृत्ति विधि के लिए द्विघात अभिसरण का प्रमाण
टेलर प्रमेय के अनुसार कोई भी फलन f(x) जिसका लगातार दूसरा अवकलज है, को उस बिंदु के बारे में विस्तार द्वारा दर्शाया जा सकता है जो की मूल f(x) के निकट है। मान लीजिए यह मूल α है। फिर का विस्तार f(α) के बारे में xn है:
-
(1)
जहां लैग्रेंज शेष है
जहाँ ξn, xn और α के बीच में है।
तब से α मूल है, (1) बन जाता है:
-
(2)
विभाजित समीकरण (2) द्वारा f′(xn) और पुनर्व्यवस्थित करता है
-
(3)
यह याद रखना xn + 1 द्वारा परिभाषित किया गया है
-
(4)
एक पाता है
वह है,
-
(5)
दोनों पक्षों का निरपेक्ष मान लेने पर प्राप्त होता है
-
(6)
समीकरण (6) दर्शाता है कि अभिसरण का क्रम कम से कम द्विघात है यदि निम्नलिखित शर्तें पूरी होती हैं:
- f′(x) ≠ 0; सभी के लिए x ∈ I, जहाँ I अंतराल है [α − |ε0|, α + |ε0|];
- f″(x) सभी के लिए निरंतर है x ∈ I;
- M |ε0| < 1
जहां एम द्वारा दिया गया है
यदि ये शर्तें बनी रहती हैं,
आकर्षण का केंद्र
आकर्षण के बेसिन के असंबद्ध उपसमुच्चय - वास्तविक संख्या रेखा के क्षेत्र जैसे कि प्रत्येक क्षेत्र के भीतर किसी भी बिंदु से पुनरावृति एक विशेष मूल की ओर ले जाती है - संख्या में अनंत और स्वैच्छिक विधि से छोटा हो सकता है। उदाहरण के लिए,[7] फलन के लिए f(x) = x3 − 2x2 − 11x + 12 = (x − 4)(x − 1)(x + 3), निम्नलिखित प्रारंभिक स्थितियाँ आकर्षण के क्रमिक आधारों में हैं:
2.35287527 में परिवर्तित होता है 4; 2.35284172 में परिवर्तित होता है −3; 2.35283735 में परिवर्तित होता है 4; 2.352836327 में परिवर्तित होता है −3; 2.352836323 में परिवर्तित होता है 1.
विफलता विश्लेषण
न्यूटन की विधि केवल तभी अभिसरण की गारंटी देती है जब कुछ शर्तों को पूरा किया जाता है। यदि द्विघात अभिसरण के प्रमाण में की गई मान्यताएँ पूरी होती हैं, तो विधि अभिसरण होगी। निम्नलिखित उपखंडों के लिए, अभिसरण की विधि की विफलता निरुपित करती है कि प्रमाण में की गई धारणाएं पूरी नहीं हुईं।
खराब प्रारंभिक बिंदु
कुछ स्थितियों में फलन पर शर्तें जो अभिसरण के लिए आवश्यक हैं, संतुष्ट हैं, किन्तु प्रारंभिक बिंदु के रूप में चुना गया बिंदु उस अंतराल में नहीं है जहां विधि अभिसरण करती है। यह हो सकता है, उदाहरण के लिए, यदि वह फलन जिसकी मूल खोजी गई है शून्य विषमता के रूप में पहुँचता है क्योंकि x ∞ या −∞ में जाता है। ऐसे स्थितियों में एक अलग विधि, जैसे कि द्विभाजन विधि, का उपयोग शून्य के प्रारंभिक बिंदु के रूप में उपयोग करने के लिए एक उत्तम अनुमान प्राप्त करने के लिए किया जाना चाहिए।
पुनरावृति बिंदु स्थिर है
फलन पर विचार करें:
यह x = 0 पर अधिकतम है और f(x) = 0 का समाधान x = ±1 पर है। अगर हम स्थिर बिंदु x0 = 0 (जहां व्युत्पन्न शून्य है) से पुनरावृति शुरू करते हैं, तो x1 अपरिभाषित होगा, क्योंकि (0, 1) पर स्पर्शरेखा x-अक्ष के समानांतर है:
वही समस्या तब होती है, जब प्रारंभिक बिंदु के बजाय, कोई पुनरावृत्ति बिंदु स्थिर होता है। यहां तक कि यदि व्युत्पन्न छोटा है, किन्तु शून्य नहीं है, तो अगला पुनरावृत्ति बहुत खराब सन्निकटन होगा।
प्रारंभिक बिंदु एक चक्र में प्रवेश करता है
कुछ कार्यों के लिए, कुछ प्रारंभिक बिंदु अभिसरण को रोकते हुए एक अनंत चक्र में प्रवेश कर सकते हैं। मान लीजिये
और 0 को प्रारंभिक बिंदु के रूप में लें। पहला पुनरावृति 1 उत्पन्न करता है और दूसरा पुनरावृति 0 पर लौटता है, इसलिए अनुक्रम दोनों के बीच एक मूल में परिवर्तित हुए बिना वैकल्पिक होगा। वास्तव में, यह 2-चक्र स्थिर है: 0 और 1 के आस-पास निकट हैं, जहां से सभी बिंदु 2-चक्र (और इसलिए फलन की मूल तक नहीं) के लिए समान रूप से पुनरावृत्त होते हैं। सामान्य तौर पर, अनुक्रम का व्यवहार बहुत जटिल हो सकता है (न्यूटन फ्रैक्टल देखें)। इस समीकरण का वास्तविक समाधान −1.76929235…. है।
व्युत्पन्न मुद्दे
यदि मूल के निकट में फलन निरंतर अवकलनीय नहीं है तो यह संभव है कि न्यूटन की विधि हमेशा विचलन और विफल होगी, जब तक कि पहली कोशिश में समाधान का अनुमान नहीं लगाया जाता है।
व्युत्पन्न मूल पर उपस्थित नहीं है
फलन का एक सरल उदाहरण जहां न्यूटन की विधि विचलन करती है, शून्य का घनमूल खोजने का प्रयास कर रहा है। घनमूल निरंतर और अनंत रूप से अलग-अलग है, को छोड़कर x = 0, जहां इसकी व्युत्पत्ति अपरिभाषित है:
किसी भी पुनरावृत्ति बिंदु के लिए xn, अगला पुनरावृति बिंदु होगा:
एल्गोरिथ्म समाधान को ओवरशूट करता है और y-अक्ष के दूसरी ओर लैंड करता है, प्रारंभ में न्यूटन की विधि को प्रायुक्त करने की तुलना में दूर, वास्तव में प्रत्येक पुनरावृत्ति पर समाधान से दूरी को दोगुना कर देता है।
वास्तव में, प्रत्येक f(x) = |x|α, जहाँ 0 < α < 1/2 के लिए पुनरावृत्तियाँ अनंत तक जाती हैं। α = 1/2 (वर्गमूल) के सीमित स्थिति में, पुनरावृत्तियाँ बिंदुओं x0 और −x0 के बीच अनिश्चित काल तक वैकल्पिक रहेंगी, इसलिए वे इस स्थिति में भी अभिसरण नहीं करते हैं।
असंतुलित व्युत्पन्न
यदि व्युत्पन्न मूल पर निरंतर नहीं है, तो मूल के किसी भी निकट में अभिसरण विफल हो सकता है। फलन पर विचार करें
इसका व्युत्पन्न है:
मूल के किसी भी निकट के भीतर, यह व्युत्पन्न चिन्ह के रूप में बदलता रहता है x दाएँ (या बाएँ से) 0 तक पहुँचता है जबकि f(x) ≥ x − x2 > 0 के लिए 0 < x < 1.
इसलिए f(x)/f′(x) मूल के पास अबाधित है, और न्यूटन की विधि इसके किसी भी निकट में लगभग हर जगह अलग हो जाएगी, तथापि:
- फलन हर जगह अलग-अलग (और इस प्रकार निरंतर) है;
- मूल पर व्युत्पन्न अशून्य है;
- f मूल को छोड़कर अनंत रूप से भिन्न है; और
- व्युत्पन्न मूल (विपरीत f(x)/f′(x)) के एक निकट में घिरा है.
गैर द्विघात अभिसरण
कुछ स्थितियों में पुनरावृति अभिसरण करती है किन्तु जितनी जल्दी वादा किया गया है उतनी जल्दी अभिसरण नहीं करती है। इन स्थितियों में सरल विधियाँ न्यूटन की विधि जितनी जल्दी अभिसरित होती हैं।
शून्य व्युत्पन्न
यदि प्रथम अवकलज मूल पर शून्य है, तो अभिसरण द्विघात नहीं होगा। मान लीजिये
तब f′(x) = 2x और इसके परिणामस्वरूप
इसलिए अभिसरण द्विघात नहीं है, तथापि फलन हर जगह अपरिमित रूप से भिन्न हो।
इसी तरह की समस्या तब भी होती है जब मूल केवल लगभग दोगुनी होती है। उदाहरण के लिए, मान लो
फिर प्रारंभ होने वाले पहले कुछ पुनरावृत्तियों x0 = 1 हैं
- x0 = 1
- x1 = 0.500250376…
- x2 = 0.251062828…
- x3 = 0.127507934…
- x4 = 0.067671976…
- x5 = 0.041224176…
- x6 = 0.032741218…
- x7 = 0.031642362…
उस बिंदु तक पहुँचने में छह पुनरावृत्तियाँ लगती हैं जहाँ अभिसरण द्विघात प्रतीत होता है।
कोई दूसरा व्युत्पन्न नहीं
यदि मूल पर कोई दूसरा व्युत्पन्न नहीं है, तो अभिसरण द्विघात होने में विफल हो सकता है। मान लीजिये
तब
और
सिवाय कब x = 0 जहां यह अपरिभाषित है। xn दिया गया हैं,
जिसमें xn की तुलना में लगभग 4/3 गुना शुद्धता है। यह द्विघात अभिसरण के लिए आवश्यक 2 गुना से कम है। तो न्यूटन की विधि का अभिसरण (इस स्थिति में) द्विघात नहीं है, तथापि: फलन हर जगह लगातार भिन्न होता है; व्युत्पन्न मूल पर शून्य नहीं है; और f वांछित मूल को छोड़कर अपरिमित रूप से अवकलनीय है।
सामान्यीकरण
जटिल फलन
जटिल विश्लेषण से निपटने के दौरान, उनके शून्यों को खोजने के लिए न्यूटन की विधि को सीधे प्रायुक्त किया जा सकता है।[8] प्रत्येक शून्य में जटिल विमान में आकर्षण का एक आधार होता है, सभी प्रारंभिक मानों का सेट जो विधि को उस विशेष शून्य में अभिसरण करने का कारण बनता है। दिखाए गए चित्र के अनुसार इन सेटों को मैप किया जा सकता है। कई जटिल कार्यों के लिए, आकर्षण के आधारों की सीमाएं भग्न होती हैं।
कुछ स्थितियों में जटिल विमान में ऐसे क्षेत्र होते हैं जो आकर्षण के इन बेसिनों में से किसी में नहीं होते हैं, जिसका अर्थ है कि पुनरावृत्त अभिसरण नहीं होते हैं। उदाहरण के लिए,[9] यदि कोई मूल की तलाश के लिए वास्तविक प्रारंभिक स्थिति का उपयोग करता है x2 + 1, बाद के सभी पुनरावृत्तियाँ वास्तविक संख्याएँ होंगी और इसलिए पुनरावृत्तियाँ किसी भी मूल में परिवर्तित नहीं हो सकती हैं, क्योंकि दोनों मूले गैर-वास्तविक हैं। इस स्थिति में लगभग सभी वास्तविक प्रारंभिक स्थितियाँ अराजकता सिद्धांत की ओर ले जाती हैं, जबकि कुछ प्रारंभिक स्थितियाँ या तो अनंत तक या किसी परिमित लंबाई के चक्रों को दोहराती हैं।
कर्ट मैकमुलेन ने दिखाया है कि न्यूटन की विधि के समान किसी भी संभावित विशुद्ध रूप से पुनरावृत्त एल्गोरिदम के लिए, एल्गोरिथ्म डिग्री 4 या उच्चतर के कुछ बहुपदों पर प्रायुक्त होने पर जटिल विमान के कुछ खुले क्षेत्रों में अलग हो जाएगा। चूंकि, मैकमुलेन ने डिग्री 3 के बहुपदों के लिए सामान्यतः अभिसरण एल्गोरिथम दिया।[10]
चेबिशेव की तीसरी क्रम विधि
This section is empty. You can help by adding to it. (February 2019) |
नैश-मोजर पुनरावृति
This section is empty. You can help by adding to it. (February 2019) |
समीकरणों की प्रणाली
k चर, k फलन करता है
की प्रणालियों को समाधान करने के लिए न्यूटन की विधि का भी उपयोग कर सकते हैं k समीकरण, जो (एक साथ) के शून्यों को खोजने के बराबर है k लगातार अलग-अलग फलन यह एक सदिश-मूल्यवान फलन के शून्यों को खोजने के बराबर है ऊपर दिए गए फॉर्मूलेशन में, स्केलर्स xn को वैक्टर द्वारा प्रतिस्थापित किया जाता है xn और फलन को विभाजित करने के बजाय f(xn) इसके व्युत्पन्न द्वारा f′(xn) इसके बजाय फलन को गुणा करने के लिए एक को छोड़ना होगा F(xn) इसके व्युत्क्रम द्वारा k × k जैकबियन मैट्रिक्स JF(xn). इसका परिणाम अभिव्यक्ति में होता है
- .
वास्तव में जेकोबियन मैट्रिक्स के व्युत्क्रम की गणना करने के बजाय, रैखिक समीकरणों की प्रणाली को समाधान करके समय की बचत की जा सकती है और संख्यात्मक स्थिरता में वृद्धि की जा सकती है।
अज्ञात के लिए xn + 1 − xn.
====k चर, m समीकरण, के साथ m > k==== वह k-न्यूटन की विधि के आयामी संस्करण का उपयोग से अधिक की प्रणालियों को समाधान करने के लिए किया जा सकता है k (नॉनलाइनियर) समीकरण भी यदि एल्गोरिद्म गैर-स्क्वायर जैकोबियन मैट्रिक्स और निर्धारक मैट्रिक्स के सामान्यीकृत व्युत्क्रम का उपयोग करता है J+ = (JTJ)−1JT के व्युत्क्रम के बजाय J. यदि गैर-रैखिक समीकरणों की प्रणाली का कोई समाधान नहीं है, तो विधि गैर-रैखिक कम से कम वर्गों के अर्थ में समाधान खोजने का प्रयास करती है। अधिक जानकारी के लिए गॉस-न्यूटन एल्गोरिथम देखें।
एक बनच स्थान में
एक अन्य सामान्यीकरण एक कार्यात्मक (गणित) की मूल खोजने के लिए न्यूटन की विधि है। F बनच स्थान में परिभाषित किया गया है। इस स्थिति में फॉर्मूलेशन है
जहाँ F′(Xn) पर परिकलित फ्रेचेट व्युत्पन्न है Xn. प्रत्येक पर बाउंडली इनवर्टिबल होने के लिए किसी को फ्रेचेट डेरिवेटिव की आवश्यकता होती है Xn विधि प्रायुक्त होने के लिए। एक मूल के अस्तित्व और अभिसरण के लिए कंटोरोविच प्रमेय | न्यूटन-कंटोरोविच प्रमेय द्वारा एक शर्त दी गई है।[11]
ओवर 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) क्योंकि उनकी मूले समान हैं।
मान लीजिये x0 = b अंतराल का सही समापन बिंदु बनें और दें z0 = a अंतराल का बायां समापन बिंदु हो। दिया गया xn, परिभाषित करना
जो पहले की तरह ही न्यूटन की विधि है। फिर परिभाषित करें
जहां भाजक है f′(xn) और नहीं f′(zn). पुनरावृत्तियाँ xn पुनरावृत्तियों के दौरान मूल से सख्ती से कम हो जाएगा zn सख्ती से मूल तक बढ़ जाएगा। भी,
ताकि बीच की दूरी xn और zn द्विघात रूप से घटता है।
क्वैसी-न्यूटन विधियाँ
जब जेकोबियन अनुपलब्ध हो या प्रत्येक पुनरावृत्ति पर गणना करने के लिए बहुत महंगा हो, तो अर्ध-न्यूटन विधि का उपयोग किया जा सकता है।
q-एनालॉग
न्यूटन की विधि को क्यू-एनालॉग| के साथ सामान्यीकृत किया जा सकता हैq-सामान्य व्युत्पन्न का अनुरूप।[12]
संशोधित न्यूटन तरीके
माहली की प्रक्रिया
एक गैर-रैखिक समीकरण के सामान्य रूप से कई समाधान होते हैं। किन्तु यदि प्रारंभिक मान उपयुक्त नहीं है, तो न्यूटन की विधि वांछित समाधान में अभिसरण नहीं कर सकती है या पहले पाए गए समान समाधान में अभिसरण कर सकती है। जब हम पहले से ही एन समाधान पा चुके हैं , तो अगला मूल न्यूटन की विधि को अगले समीकरण में प्रायुक्त करके पाया जा सकता है:[13][14]
इस विधि का उपयोग दूसरे प्रकार के बेसेल फलन के शून्य प्राप्त करने के लिए किया जाता है।[15]
हिरानो की संशोधित न्यूटन विधि
हिरानो की संशोधित न्यूटन विधि न्यूटन विधि के अभिसरण को संरक्षित करने और अस्थिरता से बचने के लिए एक संशोधन है।[16] यह जटिल बहुपदों को समाधान करने के लिए विकसित किया गया है।
अंतराल न्यूटन की विधि
अंतराल अंकगणित के साथ न्यूटन की विधि का संयोजन कुछ संदर्भों में बहुत उपयोगी होता है। यह एक रोक मानदंड प्रदान करता है जो सामान्य लोगों की तुलना में अधिक विश्वसनीय है (जो फलन का एक छोटा मान है या लगातार पुनरावृत्तियों के बीच चर का एक छोटा बदलाव है)। साथ ही, यह उन स्थितियों का पता लगा सकता है जहां न्यूटन की विधि सैद्धांतिक रूप से अभिसरण करती है किन्तु एक अपर्याप्त फ़्लोटिंग-पॉइंट अंकगणित के कारण संख्यात्मक रूप से अलग हो जाती है। फलन का मान; विल्किन्सन बहुपद देखें)।[17][18] विचार करना f → C1(X), जहाँ X एक वास्तविक अंतराल है, और मान लीजिए कि हमारे पास एक अंतराल विस्तार है F′ का f′, मतलब है कि F′ इनपुट के रूप में एक अंतराल लेता है Y ⊆ X और एक अंतराल आउटपुट करता है F′(Y) ऐसा है कि:
हम यह भी मानते हैं 0 ∉ F′(X), इसलिए विशेष रूप से f में अधिक से अधिक एक मूल है X. इसके बाद हम अंतराल न्यूटन ऑपरेटर को परिभाषित करते हैं:
जहाँ m ∈ Y. ध्यान दें कि परिकल्पना पर F′ इसका आशय है N(Y) अच्छी तरह से परिभाषित है और एक अंतराल है (अंतराल संचालन पर अधिक विवरण के लिए अंतराल अंकगणितीय देखें)। यह स्वाभाविक रूप से निम्नलिखित अनुक्रम की ओर जाता है:
औसत मान प्रमेय यह सुनिश्चित करता है कि यदि कोई मूल है f में Xk, तो यह अंदर भी है Xk + 1. इसके अलावा, पर परिकल्पना F′ निश्चित करता है की Xk + 1 का अधिकतम आधा आकार है Xk कब m का मध्यबिंदु है Y, तो यह क्रम की ओर अभिसरित होता है [x*, x*], जहाँ x* का मूल है f में X.
यदि F′(X) में सख्ती से 0 होता है, विस्तारित अंतराल विभाजन का उपयोग दो अंतरालों का एक संघ बनाता है N(X); कई मूले इसलिए स्वचालित रूप से अलग और बंधी हुई हैं।
अनुप्रयोग
न्यूनीकरण और अधिकतमकरण की समस्याएं
न्यूटन की विधि का उपयोग न्यूनतम या अधिकतम फलन खोजने के लिए किया जा सकता है f(x). डेरिवेटिव न्यूनतम या अधिकतम पर शून्य है, इसलिए डेरिवेटिव के लिए न्यूटन की विधि को प्रायुक्त करके स्थानीय मिनिमा और मैक्सिमा पाया जा सकता है। पुनरावृत्ति बन जाती है:
संख्याओं और घात श्रृंखला का गुणनात्मक व्युत्क्रम
एक महत्वपूर्ण अनुप्रयोग डिवीजन एल्गोरिथम#न्यूटन-रैफसन डिवीजन|न्यूटन-रैफसन डिवीजन है, जिसका उपयोग किसी संख्या के गुणात्मक व्युत्क्रम को जल्दी से खोजने के लिए किया जा सकता है a, केवल गुणा और घटाव का उपयोग करते हुए, यानी संख्या कहना x ऐसा है कि 1/x = a. हम इसे शून्य का पता लगाने के रूप में फिर से लिख सकते हैं f(x) = 1/x − a. अपने पास f′(x) = −1/x2.
न्यूटन का पुनरावृत्ति है
इसलिए, न्यूटन के पुनरावृत्ति को केवल दो गुणा और एक घटाव की आवश्यकता होती है।
यह विधि किसी घात श्रेणी के गुणक व्युत्क्रम की गणना करने के लिए भी बहुत कुशल है।
अनुवांशिक समीकरणों को समाधान करना
न्यूटन की विधि का उपयोग करके कई पारलौकिक समीकरणों को समाधान किया जा सकता है। समीकरण दिया गया है
साथ g(x) और/या h(x) एक पारलौकिक फलन, कोई लिखता है
के मान x जो मूल समीकरण को समाधान करते हैं, तब के मूल हैं f(x), जो न्यूटन की विधि द्वारा पाया जा सकता है।
विशेष कार्यों के शून्य प्राप्त करना
इसकी मूल प्राप्त करने के लिए न्यूटन की विधि बेसल कार्यों के अनुपात पर प्रायुक्त होती है।[19]
अरेखीय समीकरणों के समाधान के लिए संख्यात्मक सत्यापन
न्यूटन की विधि का कई बार उपयोग करके और समाधान उम्मीदवारों का एक सेट बनाकर गैर-रैखिक समीकरणों के समाधान के लिए एक संख्यात्मक सत्यापन स्थापित किया गया है।[20][21]
उदाहरण
वर्गमूल
किसी संख्या का वर्गमूल ज्ञात करने की समस्या पर विचार करें a, अर्थात धनात्मक संख्या x ऐसा है कि x2 = a. न्यूटन की विधि वर्गमूल की गणना करने की कई विधियों में से एक है#हीरॉन की विधि। हम इसे शून्य का पता लगाने के रूप में फिर से लिख सकते हैं f(x) = x2 − a. अपने पास f′(x) = 2x.
उदाहरण के लिए, प्रारंभिक अनुमान के साथ 612 का वर्गमूल निकालने के लिए x0 = 10, न्यूटन की विधि द्वारा दिया गया क्रम है:
जहां सही अंकों को रेखांकित किया गया है। केवल कुछ पुनरावृत्तियों के साथ कई दशमलव स्थानों के लिए त्रुटिहीन समाधान प्राप्त किया जा सकता है।
सूत्र को निम्नानुसार पुनर्व्यवस्थित करने से वर्गमूलों की गणना करने की विधियाँ प्राप्त होती हैं # हीरोन की विधि:
यानी अनुमान का अंकगणितीय माध्य, xn और a/xn.
का समाधान cos(x) = x3
धनात्मक संख्या ज्ञात करने की समस्या पर विचार करें साथ . हम इसे शून्य का पता लगाने के रूप में फिर से लिख सकते हैं . अपने पास . तब से सभी के लिए और के लिए , हम जानते हैं कि हमारा समाधान 0 और 1 के बीच है।
उदाहरण के लिए, प्रारंभिक अनुमान के साथ x0 = 0.5, न्यूटन की विधि द्वारा दिया गया अनुक्रम है (ध्यान दें कि 0 का प्रारंभिक मान एक अपरिभाषित परिणाम की ओर ले जाएगा, जो प्रारंभिक बिंदु का उपयोग करने के महत्व को दर्शाता है जो समाधान के निकट है):
उपरोक्त उदाहरण में सही अंकों को रेखांकित किया गया है। विशेष रूप से, x6 12 दशमलव स्थानों तक सही है। हम देखते हैं कि दशमलव बिंदु के बाद सही अंकों की संख्या 2 से बढ़ जाती है (के लिए x3) से 5 और 10, द्विघात अभिसरण को दर्शाते हुए।
कोड
निम्नलिखित पायथन (प्रोग्रामिंग लैंग्वेज) (संस्करण 3.x) प्रोग्रामिंग लैंग्वेज में न्यूटन की विधि का एक कार्यान्वयन उदाहरण है, जो किसी फलन की मूल को खोजने के लिए है f
जिसका व्युत्पन्न है f_prime
.
प्रारंभिक अनुमान होगा x0 = 1 और फलन होगा f(x) = x2 − 2 ताकि f′(x) = 2x.
न्यूटन की विधि के प्रत्येक नए पुनरावृत्ति को द्वारा निरूपित किया जाएगा x1
. हम गणना के दौरान जांच करेंगे कि क्या भाजक (yprime
) बहुत छोटा हो जाता है (से छोटा epsilon
), जो कि मामला होगा यदि f′(xn) ≈ 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 को अपडेट करें
वापसी कोई नहीं # न्यूटन की विधि अभिसरण नहीं हुई
</वाक्यविन्यास हाइलाइट>
यह भी देखें
- ऐटकेन की डेल्टा-स्क्वेर्ड प्रक्रिया
- द्विभाजन विधि
- यूलर विधि
- तेजी से उलटा वर्गमूल
- स्कोरिंग एल्गोरिथ्म # फिशर स्कोरिंग
- ढतला हुआ वंश
- पूर्णांक वर्गमूल
- कांटोरोविच प्रमेय
- लैगुएरे की विधि
- वर्गमूल की गणना करने की विधियाँ
- अनुकूलन में न्यूटन की विधि
- रिचर्डसन एक्सट्रपलेशन
- रूट-खोज एल्गोरिदम
- सेकेंट विधि
- स्टीफेंसन की विधि
- सबग्रेडिएंट विधि
टिप्पणियाँ
- ↑ "Chapter 2. Seki Takakazu". Japanese Mathematics in the Edo Period. National Diet Library. Retrieved 24 February 2019.
- ↑ Wallis, John (1685). बीजगणित का ग्रंथ, ऐतिहासिक और व्यावहारिक दोनों. Oxford: Richard Davis. doi:10.3931/e-rara-8842.
- ↑ Raphson, Joseph (1697). Analysis Æequationum Universalis (in Latina) (2nd ed.). London: Thomas Bradyll. doi:10.3931/e-rara-13516.
- ↑ "त्वरित और संशोधित न्यूटन तरीके". Archived from the original on 24 May 2019. Retrieved 4 March 2016.
- ↑ Ryaben'kii, Victor S.; Tsynkov, Semyon V. (2006), A Theoretical Introduction to Numerical Analysis, CRC Press, p. 243, ISBN 9781584886075.
- ↑ Süli & Mayers 2003, Exercise 1.6
- ↑ Dence, Thomas (Nov 1997). "क्यूबिक्स, कैओस और न्यूटन की विधि". Mathematical Gazette. 81 (492): 403–408. doi:10.2307/3619617. JSTOR 3619617. S2CID 125196796.
- ↑ Henrici, Peter (1974). "एप्लाइड और कम्प्यूटेशनल जटिल विश्लेषण". 1.
{{cite journal}}
: Cite journal requires|journal=
(help) - ↑ Strang, Gilbert (Jan 1991). "A chaotic search for i". The College Mathematics Journal. 22 (1): 3–12. doi:10.2307/2686733. JSTOR 2686733.
- ↑ McMullen, Curt (1987). "तर्कसंगत मानचित्रों और पुनरावृत्त रूट-खोज एल्गोरिदम के परिवार" (PDF). Annals of Mathematics. Second Series. 125 (3): 467–493. doi:10.2307/1971408. JSTOR 1971408.
- ↑ Yamamoto, Tetsuro (2001). "Historical Developments in Convergence Analysis for Newton's and Newton-like Methods". In Brezinski, C.; Wuytack, L. (eds.). Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241–263. ISBN 0-444-50617-9.
- ↑ Rajkovic, Stankovic & Marinkovic 2002 [incomplete short citation]
- ↑ Press et al. 1992 [incomplete short citation]
- ↑ Stoer & Bulirsch 1980 [incomplete short citation]
- ↑ Zhang & Jin 1996 [incomplete short citation]
- ↑ Murota, Kazuo (1982). "बीजगणितीय समीकरणों के लिए एक संशोधित न्यूटन पुनरावृत्ति का वैश्विक अभिसरण". SIAM J. Numer. Anal. 19 (4): 793–799. Bibcode:1982SJNA...19..793M. doi:10.1137/0719055.
- ↑ Moore, R. E. (1979). Methods and applications of interval analysis (Vol. 2). Siam.
- ↑ Hansen, E. (1978). Interval forms of Newtons method. Computing, 20(2), 153–163.
- ↑ Gil, Segura & Temme (2007)[incomplete short citation]
- ↑ Kahan (1968)[incomplete short citation]
- ↑ Krawczyk (1969) [incomplete short citation][incomplete short citation]
संदर्भ
- 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 =
| below =
}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म
| below =* सॉफ्टवेयर
}}