जड़-खोज एल्गोरिथ्म

जड़-खोज एल्गोरिद्म गणित में संख्यात्मक तरीकों का एक अनिवार्य हिस्सा हैं। इन्हें समीकरणों का समाधान खोजने के लिए उपयोग किया जाता है जहां कार्य शून्य के बराबर होता है। यह कई वैज्ञानिक और इंजीनियरिंग क्षेत्रों में एक महत्वपूर्ण विषय है, क्योंकि यह जटिल समस्याओं को समझने और हल करने में सहायता करता है। जड़-खोज एल्गोरिद्म का लक्ष्य x के उन मानों की गणना करना है ताकि f(x) = 0 हो, जहां f एक दिया गया कार्य है।

जड़-खोज का परिचय

गणित में कई समस्याओं को समीकरणों की जड़ों को खोजने के रूप में घटित किया जा सकता है। उदाहरण के लिए, द्विघात समीकरण ax^2 + bx + c = 0 को हल करना द्विघात बहुपद की जड़ों को खोजने के बराबर है। जड़-खोज एल्गोरिद्म वे सरल और जटिल समीकरण दोनों को हल कर सकते हैं जिनके पास स्पष्ट समाधान नहीं होता है।

लगातार कार्यों में जड़ें आमतौर पर पाई जाती हैं, विशेष रूप से बहुपदों में, साथ ही अतिरेखी कार्यों में भी। जड़ें खोजने की सबसे आम विधियों में द्विभाजन विधि, न्युटन की विधि, सेकेण्ट विधि और स्थिर-बिंदु पुनरावृत्ति विधि शामिल हैं।

ग्राफिकल समझ

एल्गोरिद्म में गहराई में जाने से पहले, यह समझना उपयोगी है कि जड़ खोजना क्या होता है। कार्य f(x) = x^2 - 4 को विचार करें।

f(x) = x^2 - 4 का ग्राफ एक परवलय है। यह x-अक्ष को उत्पत्ति पर x = -2 और x = 2 पर काटता है। ये x के वे मान हैं जहां f(x) = 0 होता है।

आम जड़-खोज विधियां

द्विभाजन विधि

द्विभाजन विधि सबसे सरल और सबसे विश्वसनीय जड़-खोज विधियों में से एक है। यह एक अंतराल को बार-बार आधा करके और उस उपांतराल का चयन करके काम करता है जिसमें जड़ होनी चाहिए। यह विधि मानती है कि कार्य प्रारंभिक अंतराल [a, b] पर लगातार है और अंतराल पर संकेत बदलता है, अर्थात् f(a) * f(b) < 0।

द्विभाजन विधि में निम्नलिखित चरण शामिल हैं:

1. मध्य बिंदु की गणना करें c = (a + b) / 2।
2. यदि f(c) = 0, तो c जड़ है। अन्यथा, अगले चरण पर जाएं।
3. यदि f(a) * f(c) < 0, तो b = c सेट करें। अन्यथा, a = c सेट करें।
4. इस प्रक्रिया को तब तक दोहराएं जब तक अंतराल पर्याप्त छोटा न हो जाए या एक विशिष्ट संख्या में पुनरावृत्तियों तक पहुंच न जाए।

द्विभाजन विधि समझने में आसान है और हमेशा सम्मिलित होती है, लेकिन यह दूसरी विधियों की तुलना में धीमी हो सकती है।

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

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

न्युटन की विधि इस प्रकार काम करती है:

1. एक प्रारंभिक अनुमाजन x_0 के साथ शुरू करें।
2. अगले अनुमाजन की गणना इस सूत्र का उपयोग करके करें:
   

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

3. इस प्रक्रिया को तब तक दोहराएं जब तक x_n का मूल्य उत्पत्ति के करीब न हो, या एक निश्चित संख्या में पुनरावृत्तियाँ पूरी न कर ली जाएँ।

न्युटन की विधि का उपयोग करते हुए f(x) = x^2 - 4 की जड़ों को खोजने की सोचें, प्रारंभिक अनुमान x_0 = 3 के साथ शुरू करते हुए।

f(x) = x^2 - 4 f'(x) = 2x x_0 = 3 x_1 = x_0 - (f(x_0) / f'(x_0)) = 3 - ((3^2 - 4) / (2*3)) = 3 - (5 / 6) = 2.166...

इस प्रक्रिया को जारी रखने पर जड़ x = 2 पर सम्मिलित हो जाएगी।

सेकेण्ट विधि

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

सेकेण्ट विधि में निम्नलिखित चरण होते हैं:

1. दो प्रारंभिक अनुमाजनों का चयन करें x_0 और x_1।
2. अगले अनुमाजन की गणना इस सूत्र का उपयोग करके करें:
   

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

3. जब तक जड़ नहीं मिल जाती, या पूर्व निर्धारित पुनरावृत्ति संख्या तक नहीं पहुंच जाती तब तक दोहराएं।

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

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

स्थिर-बिंदु पुनरावृत्ति एक कार्य के स्थिर बिंदुओं की गणना करने की विधि है। यह विधि तब लागू होती है जब किसी कार्य को x = g(x) के रूप में पुनर्लिखा जा सकता है। मूल कार्य का एक सरल पुनर्व्यवस्था या परिवर्तन अक्सर स्थिर-बिंदु पुनरावृत्ति के लिए वांछित रूप प्रदान कर सकता है।

स्थिर-बिंदु पुनरावृत्ति के चरण इस प्रकार हैं:

1. एक प्रारंभिक अनुमाजन x_0 का चयन करें।
2. अगले अनुमाजन की गणना x_{n+1} = g(x_n) का उपयोग करके करें।
3. मूल्य एक निश्चित बिंदु तक पहुंच जाए या एक निश्चित संख्या में पुनरावृत्तियाँ पूरी हो जाएं, तब तक दोहराएं।

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

जड़-खोज एल्गोरिद्म का गणितीय विश्लेषण

प्रत्येक जड़-खोज विधि की अपनी विशेषताओं और कमियों होती हैं। संबंधित समस्याओं के लिए सबसे उपयुक्त विधि का चयन करने में शामिल गणितीय सिद्धांतों का अच्छा ज्ञान मदद कर सकता है।

सम्मिलन

सम्मिलन से तात्पर्य है पुनरावृत्ति के साथ उत्पत्ति तक पहुंच जाना। भिन्न विधियों की सम्मिलन की विभिन्न गति होती है और ये रैखिक या घातीय दरों में सम्मिलित हो सकती हैं।

• रैखिक सम्मिलन: प्रत्येक चरण पर गलती लगभग समान गुण से घटती है। द्विभाजन विधि में रैखिक सम्मिलन दर होती है।
• घातीय सम्मिलन: प्रत्येक चरण पर गलती लगभग वर्ग होती है। न्युटन की विधि आमतौर पर घातीय सम्मिलन प्रदान करती है, जिसका अर्थ है कि यह तेज होती है यदि प्रारंभिक अनुमान वास्तविक जड़ के करीब हो और व्युत्पन्न कम न हो।

ताकत

मजबूती से तात्पर्य है कि विभिन्न प्रारंभिक बिंदुओं या विभिन्न परिस्थितियों से सम्मिलित होने की विधि की क्षमता है।

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

अनुप्रयोग और उदाहरण

उदाहरण 1: द्विघात समीकरण

द्विघात समीकरण x^2 - 5x + 6 = 0 को हल करने पर विचार करें। हमें पता है कि जड़ें 2 और 3 हैं। इस उदाहरण के लिए, हम विभिन्न जड़-खोज विधियों का प्रयोग करेंगे।

f(x) = x^2 - 5x + 6 द्विभाजन विधि: प्रारंभिक अंतराल [a, b] = [1, 4] चरण 1: c = (1 + 4) / 2 = 2.5 f(2.5) = 2.5^2 - 5*2.5 + 6 = -0.25 चूंकि f(1) * f(2.5) < 0 है, नया अंतराल [1, 2.5] है ... न्युटन की विधि: f(x) = x^2 - 5x + 6, f'(x) = 2x - 5 x_0 = 2.5 x_1 = 2.5 - ((2.5^2 - 5*2.5 + 6) / (2*2.5 - 5)) = 2.6667, और ऐसे ही।

उदाहरण 2: अपारामितिरीकी समीकरण

f(x) = cos(x) - x की जड़ों को खोजने पर विचार करें। इस समीकरण का कोई प्रत्यक्ष बीजगणितीय समाधान नहीं है, इसलिए संख्यात्मक विधियाँ उपयोगी होती हैं।

f(x) = cos(x) - x द्विभाजन विधि: प्रारंभिक अंतराल [a, b] = [0, 1] जांचे f(a) * f(b) < 0: f(0) = cos(0) - 0 = 1 f(1) = cos(1) - 1 नकारात्मक है, इसलिए संकेत बदलता है। चरण 1: c = (0 + 1) / 2 = 0.5 f(0.5) सकारात्मक है, इसलिए नया अंतराल [0.5, 1] है ... सेकेण्ट विधि: प्रारंभिक अनुम�