न्यूटन-रैफ़सन विधि

सारांश

बोलत्सानो प्रमेय सुनिश्चित करती है कि चिह्न बदलने वाले संतत फलन का एक मूल होता है, और द्विभाजन विधि प्रत्येक द्विभाजन में एक द्विआधारी अंक प्राप्त करते हुए उसका स्थान निर्धारित करती है। यह पाठ एक ऐसी प्रक्रिया का अध्ययन करता है जो सफल होने पर कहीं अधिक तीव्र है: न्यूटन-रैफ़सन विधि, जो आलेख के स्थान पर उसकी स्पर्श रेखा रखती है और नए सन्निकटन के रूप में वह बिंदु लेती है जहाँ स्पर्श रेखा अक्ष को काटती है। इस प्रकार प्राप्त सन्निकटन पूर्णांकों $n \geq 0$ के लिए एक के बाद एक परिभाषित होते हैं, और उनकी सीमा अनुक्रमों के सिद्धांत के बिना, चर के अनंत की ओर अग्रसर होने पर सीमा की परिभाषा से समझी जाती है। पाठ ऊपर की ओर अवतलता की सहायता से सिद्ध करता है कि यदि अवकलज शून्य नहीं होता और फलन ऊपर की ओर अवतल या नीचे की ओर अवतल है, तो उपयुक्त पक्ष से आरंभ होने वाली पुनरावृत्तियाँ मूल को पार किए बिना उसके निकट आती हैं और उस पर अभिसरित होती हैं; और माध्यमान प्रमेय की सहायता से सिद्ध करता है कि फलन का मान, जिसकी गणना की जाती है, मूल तक की दूरी को, जो ज्ञात नहीं है, परिबद्ध करता है। इसके बाद संख्यात्मक उदाहरणों से दिखाया जाता है कि सही अंकों की संख्या प्रत्येक पुनरावृत्ति में दोगुनी हो जाती है, और वे स्थितियाँ भी जिनमें विधि विफल होती है: शून्य अवकलज, चक्र, अपसरण। प्रश्न बिना विभाजन के घनमूल और व्युत्क्रम निकालते हैं, एक चक्र को तोड़ते हैं, एक द्विक मूल का अध्ययन करते हैं और प्रतिलोम स्पर्शज्या के लिए अभिसरण और अपसरण के बीच की सटीक सीमारेखा ज्ञात करते हैं।

अधिगम उद्देश्य

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

पुनरावृत्ति

मान लीजिए $f$ एक अवकलनीय फलन है जिसका मूल $r$ खोजा जा रहा है, और $x_0$ एक पहला सन्निकटन है। $x_0$ के निकट $f$ का आलेख अपनी स्पर्श रेखा $y = f(x_0) + f'(x_0)(x - x_0)$ जैसा दिखता है, सीमा के रूप में अवकलज वाले पाठ की स्पर्श रेखा की परिभाषा के अनुसार; उच्च कोटि के अवकलज और अवकल वाले पाठ के अवकल की भाषा में, वृद्धि $f(x_0 + \Delta x) - f(x_0)$ लगभग $f'(x_0) \Delta x$ के बराबर है। यदि $f'(x_0) \neq 0$ , तो स्पर्श रेखा अक्ष को केवल एक बिंदु पर काटती है, और उसे नया सन्निकटन लेना स्वाभाविक है: वह स्पर्श रेखा के समीकरण को शून्य के बराबर रखने से प्राप्त होता है। प्राप्त बिंदु से इस प्रक्रिया को दोहराना ही न्यूटन-रैफ़सन विधि है।

परिभाषान्यूटन-रैफ़सन पुनरावृत्तियाँ

मान लीजिए $f$ अंतराल $I$ पर अवकलनीय फलन है और $x_0$ , $I$ का एक बिंदु है। $x_0$ से आरंभ होने वाली न्यूटन-रैफ़सन पुनरावृत्तियाँ वे संख्याएँ हैं जो एक के बाद एक इस सूत्र से परिभाषित होती हैं

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

जब तक $x_n$ , $I$ में है और $f'(x_n) \neq 0$ । यदि ये प्रतिबंध प्रत्येक पूर्णांक $n \geq 0$ के लिए संतुष्ट होते हैं, तो पुनरावृत्तियाँ एक फलन $n \mapsto x_n$ बनाती हैं जो अऋणात्मक पूर्णांकों के समुच्चय पर परिभाषित है, जो ऊपर से परिबद्ध नहीं है, और चर के अनंत की ओर अग्रसर होने पर सीमाएँ वाले पाठ की, चर के अनंत की ओर अग्रसर होने पर सीमा की परिभाषा उस पर लागू होती है। कहा जाता है कि पुनरावृत्तियाँ $r$ पर अभिसरित होती हैं यदि $\lim_{n \to \infty} x_n = r$ , अर्थात् यदि

(\forall \varepsilon > 0)(\exists M)(\forall n \geq 0)\left(n > M \rightarrow \abs{x_n - r} < \varepsilon\right)

प्रत्येक पुनरावृत्ति $(x_n, f(x_n))$ पर स्पर्श रेखा का अक्ष से प्रतिच्छेदन है: $y = 0$ और $x = x_{n+1}$ को समीकरण $y = f(x_n) + f'(x_n)(x - x_n)$ में रखकर अज्ञात को निकालने पर परिभाषा का सूत्र प्राप्त होता है। यह विधि द्विभाजन विधि की तरह यह नहीं माँगती कि फलन किसी दिए गए अंतराल में चिह्न बदले, बल्कि यह कि वह अवकलनीय हो और जिन बिंदुओं से विधि गुज़रती है उन पर उसका अवकलज शून्य न हो; बदले में, कोई चीज़ पहले से सुनिश्चित नहीं करती कि पुनरावृत्तियाँ किसी मूल के निकट आएँगी। आगे दिए गए प्रतिबंध इसे सुनिश्चित करते हैं।

उदाहरण2 का वर्गमूल

$f(x) = x^2 - 2$ पर न्यूटन-रैफ़सन विधि $x_0 = 2$ से आरंभ करके लागू कीजिए। चरण पहली तीन स्पर्श रेखाएँ और अक्ष से उनके प्रतिच्छेदन दिखाते हैं।

प्रमाण

$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \qquad \resaltar{x_1 = \frac{3}{2}}$
अवकलज $f'(x) = 2x$ है, जो $x > 0$ होने पर शून्य नहीं होता। पुनरावृत्ति यह रूप लेती है: प्रत्येक सन्निकटन पूर्ववर्ती सन्निकटन और $2$ को उससे विभाजित करने पर प्राप्त संख्या का औसत है। $x_0 = 2$ से, स्पर्श रेखा $y = 2 + 4(x - 2)$ अक्ष को $\frac{3}{2}$ पर काटती है।
$x_2 = \frac{1}{2}\left(\frac{3}{2} + \frac{4}{3}\right) = \resaltar{\frac{17}{12}} \approx 1.416667$
$\left(\frac{3}{2}, \frac{1}{4}\right)$ पर स्पर्श रेखा अक्ष को मूल के कहीं अधिक निकट काटती है।
$x_3 = \frac{1}{2}\left(\frac{17}{12} + \frac{24}{17}\right) = \resaltar{\frac{577}{408}} \approx 1.4142157, \qquad \sqrt{2} \approx 1.4142136$
तीसरी पुनरावृत्ति में पहले से ही पाँच सही दशमलव अंक हैं। त्रुटियाँ, $x_n - \sqrt{2}$ , लगभग $0.59$ , $0.086$ , $0.0025$ और $0.0000021$ हैं: प्रत्येक पूर्ववर्ती त्रुटि के वर्ग की कोटि की है।

इस उदाहरण में त्रुटि ठीक-ठीक वर्गित होती है। पुनरावृत्ति के सूत्र से, प्रत्येक $x_n > 0$ के लिए, निम्नलिखित सर्वसमिका प्राप्त होती है:

x_{n+1} - \sqrt{2} = \frac{x_n^2 - 2\sqrt{2}\,x_n + 2}{2x_n} = \frac{\left(x_n - \sqrt{2}\right)^2}{2x_n}

अतः पहली से आगे की सभी पुनरावृत्तियाँ $\sqrt{2}$ से बड़ी या उसके बराबर हैं, और यदि $x_n \geq 1$ , तो आगामी त्रुटि वर्तमान त्रुटि के वर्ग की अधिक से अधिक आधी है: चौथी पुनरावृत्ति, $x_4 = \frac{665\,857}{470\,832}$ , में ग्यारह सही दशमलव अंक हैं। $2$ के स्थान पर कोई भी धनात्मक संख्या रखने पर यही प्रक्रिया वर्गमूल निकालती है; यह पहली शताब्दी में अलेक्ज़ान्ड्रिया के हीरोन की मापिकी में ही मिलती है, और इसलिए इसे हीरोन विधि भी कहते हैं।

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

इस पाठ के शेष भाग में

एकदिष्ट अभिसरण और त्रुटि का परिबंध
गति, विफलताएँ और द्विभाजन से तुलना
हल किए गए प्रश्न
गलत पक्ष का प्रारंभिक बिंदु
बिना विभाजन के व्युत्क्रम
एक चक्र
एक द्विक मूल
प्रतिलोम स्पर्शज्या
अभ्यास प्रश्न
केप्लर समीकरण
लघुगणकों से संख्या e
पलायन करती पुनरावृत्तियाँ
एक ही पुनरावृत्ति में मूल देने वाले फलन
दो त्रुटियों का अनुपात

निःशुल्क खाते के साथ पढ़ना जारी रखें

यह पूरा पाठ और हर पाठ्यक्रम के पहले पाठ पढ़ने तथा अपनी प्रगति सहेजने के लिए अपना निःशुल्क खाता बनाएँ।

खाता बनाएँ साइन इन करें

पूरा पाठ्यक्रम पाएँ

इस पाठ का शेष भाग सदस्यता में शामिल है। सदस्यता के साथ आपको हर पाठ्यक्रम के सभी पाठ, उनके प्रश्नों और प्रमाणों के साथ, मिलते हैं।