मुळे शोधण्यामधील पुनरावृत्ती पद्धत
उपयोजित गणित, भौतिकशास्त्र, अभियांत्रिकी आणि संगणकशास्त्र यांमध्ये 'मूळ शोधण्याची' समस्या वारंवार उद्भवते. मूळ म्हणजे \(x\) ची अशी किंमत जी एखाद्या फलनाला शून्य करते, म्हणजेच, खालील समीकरणाचे उत्तर:
\[
f(x)=0
\]
सर्वच समीकरणांची उकल बंद-स्वरूपाच्या सूत्रांमध्ये व्यक्त करता येत नाही, जसे की वर्गसमीकरणे. अनेक वास्तविक-जगातील प्रकरणांसाठी—जसे की जटिल अरैखिक समीकरणे—आपल्याला संख्यात्मक पद्धतींची आवश्यकता असते. सर्वात महत्त्वाच्या पद्धतींपैकी एक म्हणजे पुनरावृत्ती पद्धत, जी एक अशी प्रक्रिया आहे जी पुनरावृत्तीद्वारे मुळाच्या जवळ जाणारी अंदाजित उकलांची मालिका तयार करते.
या लेखात पुनरावृत्ती पद्धतींच्या मूलभूत संकल्पना, त्यांच्या अभिसरणाच्या अटी आणि मुळे शोधण्यासाठी सामान्यतः वापरल्या जाणाऱ्या काही पुनरावृत्ती पद्धतींवर चर्चा केली आहे.
-
१. पुनरावृत्ती पद्धतीची मूलभूत संकल्पना
पुनरावृत्ती पद्धतीमध्ये सुरुवातीला \(x_0\) चा अंदाज लावला जातो, आणि नंतर अनुक्रम मिळवण्यासाठी त्यात हळूहळू सुधारणा केली जाते:
\[
x_0, x_1, x_2, \dots, x_n
\]
अपेक्षांसह:
\[
x_n \to \alpha
\]
येथे \(\alpha\) हे \(f(x)=0\) या समीकरणाचे खरे मूळ आहे.
सर्वसाधारणपणे, पुनरावृत्ती पद्धत \(f(x)=0\) या समस्येचे समतुल्य स्वरूपात रूपांतर करते:
\[
x = g(x)
\]
त्यानंतर पुनरावृत्ती केली जाते:
\[
x_{n+1} = g(x_n)
\]
जर ही प्रक्रिया अभिसारी असेल, तर \(g(x)\) चा स्थिर बिंदू हा मूळ समीकरणाचा मूळ उकल असतो.
-
२. अभिसरण: पुनरावृत्ती यशस्वी केव्हा होते?
सर्वच फंक्शन्स \(g(x)\) स्थिर पुनरावृत्ती निर्माण करत नाहीत. \(x_{n+1}=g(x_n)\) या पुनरावृत्तीने मूळ \(\alpha\) कडे अभिसरण करण्यासाठी, सामान्यतः वापरल्या जाणाऱ्या अटी खालीलप्रमाणे आहेत:
१. \(g(\alpha)=\alpha\) (मूळ हा एक स्थिर बिंदू आहे)
२. \(|g'(\alpha)| < 1\) (स्थानिक आकुंचन) \(|g'(\alpha)| < 1\) यामागील मूळ कल्पना अशी आहे: उकलीच्या जवळपास, \(g\) हे फलन “फार तीव्र चढ” असलेले नसते, त्यामुळे प्रत्येक पुनरावृत्ती \(x_n\) चे मूल्य दूर न नेता जवळ आणते. अभिसरणावर सुरुवातीच्या अंदाजाचाही परिणाम होतो. त्याच दोन पद्धती \(x_0\) वर अवलंबून यशस्वी किंवा अयशस्वी होऊ शकतात. --- ३. एक साधी पुनरावृत्ती म्हणून द्विविभाजन पद्धत जरी अनेकदा वेगळे वर्गीकृत केले जात असले तरी, द्विविभाजन पद्धतीला एक अत्यंत शक्तिशाली पुनरावृत्ती पद्धत म्हणून पाहिले जाऊ शकते. यासाठीच्या अटी अशा आहेत: \(f(x)\) हे फलन \([a,b]\) या अंतरामध्ये संतत असावे आणि चिन्हात बदल असावा: \[ f(a)\cdot f(b) < 0 \] म्हणजेच, \(a\) आणि \(b\) यांच्या दरम्यान एक मूळ असावे. अल्गोरिदम: १. मध्यबिंदू \(c=\frac{a+b}{2}\) ची गणना करा. २. (चिन्हातील बदलाच्या आधारावर) मूळाला समाविष्ट करणारा उपअंतराल निश्चित करा. ३. सहिष्णुता (टॉलरन्स) गाठेपर्यंत पुनरावृत्ती करा. या पद्धतीचा फायदा: चिन्हातील बदलाची अट पूर्ण झाल्यास, ती निश्चितपणे अभिसरण (कन्व्हर्ज) करेल. तोटा: अभिसरण तुलनेने मंद आहे कारण प्रत्येक पुनरावृत्तीमध्ये त्रुटी अंदाजे निम्मी होते (रेषीय अभिसरण). --- ४. स्थिर-बिंदू पुनरावृत्ती पद्धत (Fixed-Point Iteration Method) हे पुनरावृत्तीचे सर्वात थेट स्वरूप आहे: \[ x_{n+1} = g(x_n) \] पायऱ्या: १. \(f(x)=0\) बदलून \(x=g(x)\) करा. २. एक प्रारंभिक अंदाज \(x_0\) निवडा. ३. \(|x_{n+1}-x_n|\) किंवा \(|f(x_n)|\) सहिष्णुतेपेक्षा लहान होईपर्यंत पुनरावृत्ती करा. याचा फायदा म्हणजे साधेपणा. तथापि, ही पद्धत \(g(x)\) च्या निवडीबाबत खूप संवेदनशील आहे. त्याच समीकरणासाठी, \(x=g(x)\) लिहिण्याचे अनेक मार्ग आहेत, परंतु त्यापैकी फक्त काहीच अभिसारी आहेत.
उदाहरणार्थ, जर आपल्याला \(f(x)=x^3-2x-5\) ची मुळे शोधायची असतील, तर आपण असे लिहू शकतो: - \(x = \sqrt[3]{2x+5}\) जेणेकरून \(g(x)=\sqrt[3]{2x+5}\) होईल. मग आपण \(x_{n+1}=\sqrt[3]{2x_n+5}\) ची पुनरावृत्ती करतो. पुनरावृत्तीचे यश मुळाभोवती \(|g'(x)|<1\) आहे की नाही यावर अवलंबून असते. --- ५. न्यूटन-रॅफसन पद्धत: जलद अवकलज-आधारित पुनरावृत्ती. न्यूटन-रॅफसन पद्धत ही सर्वात लोकप्रिय पद्धतींपैकी एक आहे कारण तिचे अभिसरण सहसा खूप जलद असते. पुनरावृत्तीचे सूत्र आहे: \[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \] अर्थ: \(x_n\) येथे, आपण फलन \(f(x)\) ला एक स्पर्शिका काढतो. स्पर्शिकेचा \(x\)-अक्षासोबतचा छेदबिंदू पुढील अंदाज म्हणून वापरला जातो. फायदे: - जर ते मुळाच्या पुरेसे जवळ असेल आणि \(f'(\alpha)\neq 0\) असेल, तर वर्ग अभिसरण (अतिशय जलद) होते. तोटे: - यासाठी \(f'(x)\) च्या अवकलजाची आवश्यकता असते. - जर सुरुवातीचा अंदाज चुकीचा असेल, किंवा \(f'(x_n)\) शून्याच्या जवळ असेल, तर ही पद्धत अयशस्वी होऊ शकते, ज्यामुळे पुनरावृत्तीची पायरी अस्थिर होते. अनुकूल परिस्थितीत तिच्या कार्यक्षमतेमुळे ही पद्धत ऑप्टिमायझेशन, भौतिकशास्त्र मॉडेलिंग आणि अभियांत्रिकी संगणनामध्ये मोठ्या प्रमाणावर वापरली जाते. --- ६. छेदिका पद्धत: अवकलजांशिवाय न्यूटनचा पर्याय जर अवकलज काढणे कठीण असेल, तर छेदिका पद्धत एक मध्यम मार्ग देते. मुख्य कल्पना म्हणजे परिमित फरकांसह अवकलजाचे अंदाजे मूल्य काढणे: \[ f'(x_n)\approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}} \] म्हणून पुनरावृत्तीचे सूत्र आहे: \[ x_{n+1}=x_n - f(x_n)\,\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} \] या पद्धतीसाठी दोन प्रारंभिक अंदाजांची आवश्यकता असते: \(x_0\) आणि \(x_1\). याचा अभिसरण वेग सामान्यतः साध्या द्विविभाजन आणि स्थिर-बिंदू पद्धतीपेक्षा चांगला असतो, जरी तो सहसा न्यूटन पद्धतीपेक्षा किंचित कमी असतो. तथापि, या पद्धतीत अवकलजांची आवश्यकता नसल्यामुळे, छेदक पद्धत अनेकदा अधिक व्यावहारिक ठरते.
--- ७. थांबण्याचे निकष संख्यात्मक गणनेमध्ये, पुनरावृत्ती पुरेशी अचूक झाल्यावर किंवा ती अभिसरण (कन्व्हर्ज) होत नसल्याचा संशय आल्यास ती थांबवली पाहिजे. सामान्य निकष: १. लहान आंतर-पुनरावृत्ती त्रुटी: \[ |x_{n+1}-x_n|<\varepsilon \] २. फलनाचे मूल्य शून्याच्या जवळ असणे: \[ |f(x_n)|<\varepsilon \] ३. अंतहीन लूप टाळण्यासाठी कमाल पुनरावृत्ती मर्यादा: \[ n \le n_{\max} \] सहिष्णुता \(\varepsilon\) ची निवड गरजेवर अवलंबून असते: अभियांत्रिकी सिम्युलेशनसाठी कडक सहिष्णुतेची आवश्यकता असू शकते, तर ढोबळ गणनेसाठी ती बरीच सैल असते. --- ८. पुनरावृत्ती पद्धतींची संक्षिप्त तुलना सारांश: - बायसेक्शन: सर्वात स्थिर, निश्चितपणे अभिसरण होते (चिन्ह बदलल्यास), परंतु मंद. - फिक्स्ड-पॉइंट: खूप सोपी, परंतु अभिसरणाची नेहमीच हमी नसते. - न्यूटन-रॅफसन: खूप वेगवान, परंतु अवकलजांची (डेरिव्हेटिव्ह्ज) आवश्यकता असते आणि प्रारंभिक अंदाजांप्रति संवेदनशील असते. - सेकंट: अवकलजांची आवश्यकता नसते, बऱ्यापैकी वेगवान, परंतु बायसेक्शनपेक्षा कमी स्थिर असू शकते. व्यवहारात, पद्धतीची निवड फंक्शनचे स्वरूप, अवकलजांची उपलब्धता, वेगाची गरज आणि स्थिरता यावर अवलंबून असते. --- निष्कर्ष अरेखीय समीकरणांसाठी संख्यात्मक मूळ-शोधनामध्ये पुनरावृत्ती पद्धती हा मुख्य आधार आहे. पुनरावृत्तीने अद्ययावत केलेल्या अंदाजे मूल्यांची मालिका तयार करून, जेव्हा विश्लेषणात्मक पद्धती उपलब्ध नसतात तेव्हा आपण उकलीच्या जवळ पोहोचू शकतो. पुनरावृत्तीद्वारे अचूक आणि कार्यक्षम मुळे मिळवण्यासाठी अभिसरण, सुरुवातीच्या अंदाजाची निवड आणि थांबण्याचे निकष समजून घेणे महत्त्वाचे आहे. वास्तविक-जगातील अनुप्रयोगांमध्ये, अनेकदा एक एकत्रित धोरण वापरले जाते: मूळ अंतराल "निश्चित" करण्यासाठी बायसेक्शनसारख्या स्थिर पद्धतीपासून सुरुवात करणे, आणि नंतर अभिसरणाचा वेग वाढवण्यासाठी न्यूटन किंवा सेकंट पद्धतीकडे वळणे. यामुळे विश्वसनीयता आणि वेग यांच्यात संतुलन साधले जाते—जे संख्यात्मक संगणनामध्ये दोन अत्यंत मौल्यवान पैलू आहेत. --- तुमची इच्छा असल्यास, लेख अधिक ठोस करण्यासाठी मी वरीलपैकी कोणत्याही पद्धतीचे टप्प्याटप्प्याने (संख्यात्मक) उदाहरण जोडू शकेन.
