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

द्विभाजन विधि के कुछ चरणों को प्रारंभिक सीमा पर लागू किया जाता है [ए₁;बी₁]। बड़ा लाल बिंदु फलन का मूल है।

गणित में, द्विभाजन विधि एक रूट-फाइंडिंग एल्गोरिथम है। इस विधि में इन मानों द्वारा परिभाषित अंतराल (गणित) को बार-बार समद्विभाजित किया जाता है और फिर उपअंतराल का चयन किया जाता है जिसमें फ़ंक्शन साइन बदलता है, और इसलिए इसमें फ़ंक्शन का रूट होना चाहिए। यह एक बहुत ही सरल और मजबूत तरीका है, लेकिन यह अपेक्षाकृत धीमा भी है। इस वजह से, इसका उपयोग अक्सर एक समाधान के लिए एक मोटा सन्निकटन प्राप्त करने के लिए किया जाता है, जो तब अधिक तेजी से अभिसरण विधियों के लिए एक प्रारंभिक बिंदु के रूप में उपयोग किया जाता है।^[1] विधि को अंतराल आधा करने की विधि भी कहा जाता है,^[2] बाइनरी खोज एल्गोरिथम,^[3] या द्विबीजपत्री विधि।^[4]

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

विधि

यह विधि वास्तविक संख्या चर x के लिए समीकरण f(x) = 0 को संख्यात्मक रूप से हल करने के लिए लागू है, जहां f एक अंतराल [a, b] पर परिभाषित एक निरंतर कार्य है और जहां f(a) और f(b) विपरीत हैं संकेत। इस मामले में ए और बी को एक रूट को ब्रैकेट करने के लिए कहा जाता है, क्योंकि इंटरमीडिएट वैल्यू प्रमेय द्वारा, निरंतर फ़ंक्शन एफ में अंतराल (ए, बी) में कम से कम एक रूट होना चाहिए।

प्रत्येक चरण पर विधि अंतराल के मध्यबिंदु c = (a+b) / 2 और उस बिंदु पर फ़ंक्शन f(c) के मान की गणना करके अंतराल को दो भागों/आधा भागों में विभाजित करती है। यदि c स्वयं एक जड़ है तो प्रक्रिया सफल हो जाती है और रुक जाती है। अन्यथा, अब केवल दो संभावनाएँ हैं: या तो f(a) और f(c) के विपरीत संकेत हैं और एक रूट को ब्रैकेट करते हैं, या f(c) और f(b) के विपरीत संकेत हैं और एक रूट को ब्रैकेट करते हैं।^[5] विधि उस सबइंटरवल का चयन करती है जो अगले चरण में उपयोग किए जाने वाले नए अंतराल के रूप में ब्रैकेट होने की गारंटी है। इस तरह एक अंतराल जिसमें f का शून्य होता है, प्रत्येक चरण में चौड़ाई में 50% कम हो जाता है। प्रक्रिया तब तक जारी रहती है जब तक कि अंतराल पर्याप्त रूप से छोटा न हो जाए।

स्पष्ट रूप से, यदि f(c)=0 तो c को समाधान के रूप में लिया जा सकता है और प्रक्रिया रुक जाती है। अन्यथा, यदि f(a) और f(c) के विपरीत संकेत हैं, तो विधि c को b के लिए नए मान के रूप में सेट करती है, और यदि f(b) और f(c) के विपरीत संकेत हैं तो विधि c को नए मान के रूप में सेट करती है। एक। दोनों ही मामलों में, नए f(a) और f(b) के विपरीत संकेत हैं, इसलिए यह विधि इस छोटे अंतराल पर लागू होती है।^[6]

पुनरावृत्ति कार्य

विधि के लिए इनपुट एक निरंतर कार्य एफ, एक अंतराल [ए, बी], और फ़ंक्शन मान एफ (ए) और एफ (बी) है। फ़ंक्शन मान विपरीत चिह्न के हैं (अंतराल के भीतर कम से कम एक शून्य क्रॉसिंग है)। प्रत्येक पुनरावृत्ति इन चरणों को करती है:

सी की गणना करें, अंतराल का मध्य बिंदु, सी = a + b/2.
मध्यबिंदु, f(c) पर फ़ंक्शन मान की गणना करें।
यदि अभिसरण संतोषजनक है (अर्थात, c - a पर्याप्त रूप से छोटा है, या |f(c)| पर्याप्त रूप से छोटा है), तो c वापस करें और पुनरावृति बंद करें।
f(c) के चिह्न की जांच करें और या तो (a, f(a)) या (b, f(b)) को (c, f(c)) से बदलें ताकि नए अंतराल के भीतर एक शून्य क्रॉसिंग हो।

कंप्यूटर पर विधि को लागू करते समय परिमित सटीकता के साथ समस्याएं हो सकती हैं, इसलिए अक्सर अतिरिक्त अभिसरण परीक्षण या पुनरावृत्तियों की संख्या की सीमाएं होती हैं। हालांकि एफ निरंतर है, परिमित सटीकता फ़ंक्शन मान को शून्य होने से रोक सकती है। उदाहरण के लिए विचार करें $f (x) = cos x$ ; अनुमानित कोई फ़्लोटिंग-पॉइंट मान नहीं है $x = π /2$ यह बिल्कुल शून्य देता है। इसके अतिरिक्त, ए और बी के बीच का अंतर फ़्लोटिंग पॉइंट परिशुद्धता द्वारा सीमित है; यानी, जैसे-जैसे a और b के बीच का अंतर घटता है, किसी बिंदु पर [a, b] का मध्य बिंदु संख्यात्मक रूप से a या b के समान (फ्लोटिंग पॉइंट सटीकता के भीतर) होगा।

एल्गोरिथम

विधि को स्यूडोकोड में इस प्रकार लिखा जा सकता है:^[7] इनपुट: फंक्शन एफ,

       समापन बिंदु मान ए, बी,
       सहनशीलता टीओएल,
       अधिकतम पुनरावृति NMAX
शर्तें: ए <'बी,
            या तो f(a) < 0 और f(b) > 0 या f(a) > 0 और f' '(बी) <0
आउटपुट: मान जो f(x) = 0 के मूल से TOL से कम भिन्न है
 
एन ← 1
जबकि N ≤ NMAX // असीमित लूप को रोकने के लिए पुनरावृत्तियों को सीमित करें
    सी ← (ए + बी)/2 // नया मध्यबिंदु
    अगर एफ(सी) = 0 या (बी - ए)/2 <टीओएल तो // समाधान मिला
        आउटपुट(सी)
        रुकना
    अगर अंत
    एन ← एन + 1 // इंक्रीमेंट स्टेप काउंटर
    अगर साइन ( एफ ( सी )) = साइन ( एफ ( ए ')) तो  ए  ←  सी  और  बी  ← सी // नया अंतराल
जबकि समाप्त करें
आउटपुट (विधि विफल।) // चरणों की अधिकतम संख्या पार हो गई

=== उदाहरण: एक बहुपद === की जड़ ढूँढना मान लीजिए कि द्विभाजन विधि का उपयोग बहुपद की जड़ को खोजने के लिए किया जाता है

f(x)=x^{3}-x-2\,.

सबसे पहले, दो नंबर $a$ और $b$ ऐसा पाया जाना चाहिए $f(a)$ और $f(b)$ विपरीत संकेत हैं। उपरोक्त समारोह के लिए, $a=1$ और $b=2$ इस कसौटी को पूरा करें, जैसे

f(1)=(1)^{3}-(1)-2=-2

और

f(2)=(2)^{3}-(2)-2=+4\,.

क्योंकि कार्य निरंतर है, अंतराल [1, 2] के भीतर एक जड़ होना चाहिए।

पहले पुनरावृत्ति में, अंतराल के अंत बिंदु जो जड़ को कोष्ठक करते हैं $a_{1}=1$ और $b_{1}=2$ , तो मध्यबिंदु है

c_{1}={\frac {2+1}{2}}=1.5

मध्यबिंदु पर फ़ंक्शन मान है $f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125$ . चूंकि $f(c_{1})$ नकारात्मक है, $a=1$ से प्रतिस्थापित किया जाता है $a=1.5$ यह सुनिश्चित करने के लिए अगले पुनरावृत्ति के लिए $f(a)$ और $f(b)$ विपरीत संकेत हैं। जैसा कि यह जारी है, बीच का अंतराल $a$ और $b$ तेजी से छोटा होता जाएगा, फलन के मूल में परिवर्तित होता जाएगा। इसे नीचे दी गई तालिका में देखें।

Iteration	$a_{n}$	$b_{n}$	$c_{n}$	$f(c_{n})$
1	1	2	1.5	−0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	−0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0.0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

13 पुनरावृत्तियों के बाद, यह स्पष्ट हो जाता है कि लगभग 1.521 का अभिसरण है: बहुपद के लिए एक मूल।

विश्लेषण

यदि अंतराल [ए, बी] और एफ (ए) और एफ (बी) पर विपरीत संकेत हैं, तो विधि को एफ की जड़ में अभिसरण करने की गारंटी दी जाती है। सन्निकटन त्रुटि प्रत्येक चरण पर आधी हो जाती है इसलिए अभिसरण की विधि दर। विशेष रूप से, यदि सी₁ = a+b/2 प्रारंभिक अंतराल का मध्यबिंदु है, और c_n nवें चरण में अंतराल का मध्यबिंदु है, तो c के बीच का अंतर_n और एक समाधान सी से घिरा हुआ है^[8]

|c_{n}-c|\leq {\frac {|b-a|}{2^{n}}}.

इस सूत्र का उपयोग अग्रिम रूप से पुनरावृत्तियों की संख्या पर एक ऊपरी सीमा निर्धारित करने के लिए किया जा सकता है, जिसे द्विभाजन विधि को एक निश्चित सहनशीलता के भीतर जड़ में परिवर्तित करने की आवश्यकता होती है। एक आवश्यक सहिष्णुता ε प्राप्त करने के लिए आवश्यक पुनरावृत्तियों की संख्या n (अर्थात, अधिकतम ε होने की गारंटी वाली त्रुटि), से घिरा है

n\leq n_{1/2}\equiv \left\lceil \log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)\right\rceil ,

जहां प्रारंभिक ब्रैकेट आकार $\epsilon _{0}=|b-a|$ और आवश्यक ब्रैकेट आकार $\epsilon \leq \epsilon _{0}.$ द्विभाजन विधि का उपयोग करने के लिए मुख्य प्रेरणा यह है कि निरंतर कार्यों के सेट पर, कोई अन्य विधि अनुमान सी उत्पन्न करने की गारंटी नहीं दे सकती है_n समाधान सी के लिए कि सबसे खराब स्थिति में एक है $\epsilon$ एन से कम के साथ पूर्ण त्रुटि_1/2 पुनरावृत्तियों।^[9] यह फ़ंक्शन f और रूट के पड़ोस में फ़ंक्शन के व्यवहार पर कई सामान्य धारणाओं के तहत भी सही है।^[9]^[10] हालाँकि, पूर्ण त्रुटि मानदंड के तहत सबसे खराब स्थिति के प्रदर्शन के संबंध में द्विभाजन विधि इष्टतम होने के बावजूद यह मानक मान्यताओं के तहत औसत प्रदर्शन के संबंध में उप-इष्टतम है। ^[11]^[12] साथ ही स्पर्शोन्मुख प्रदर्शन।^[13] समद्विभाजन विधि के लोकप्रिय विकल्प, जैसे कि छेदक विधि, रिडर्स की विधि या ब्रेंट की विधि (दूसरों के बीच), आम तौर पर बेहतर प्रदर्शन करते हैं क्योंकि वे रूट के अभिसरण की उच्च दर प्राप्त करने के लिए सबसे खराब स्थिति के प्रदर्शन का व्यापार करते हैं। और, आईटीपी विधि के साथ सबसे खराब स्थिति के प्रदर्शन के बिना अभिसरण के उच्च क्रम के साथ द्विभाजन पद्धति में एक सख्त सुधार प्राप्त किया जा सकता है।^[13]^[14]

यह भी देखें

बाइनरी सर्च एल्गोरिथम
लेह्मर-शूर एल्गोरिथम, जटिल तल में समद्विभाजन विधि का सामान्यीकरण
नेस्टेड अंतराल

संदर्भ

↑ Burden & Faires 1985, p. 31
↑ "अंतराल आधा करना (द्विभाजन)". Archived from the original on 2013-05-19. Retrieved 2013-11-07.
↑ Burden & Faires 1985, p. 28
↑ "द्विभाजन विधि - गणित का विश्वकोश". www.encyclopediaofmath.org. Retrieved 2015-12-21.
↑ If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.
↑ Burden & Faires 1985, p. 28 for section
↑ Burden & Faires 1985, p. 29. This version recomputes the function values at each iteration rather than carrying them to the next iterations.
↑ Burden & Faires 1985, p. 31, Theorem 2.1
↑ ^9.0 ^9.1 Sikorski, K. (1982-02-01). "द्विभाजन इष्टतम है". Numerische Mathematik. 40 (1): 111–117. doi:10.1007/BF01459080. ISSN 0945-3245. S2CID 119952605.
↑ Sikorski, K (1985-12-01). "अरेखीय समीकरणों का इष्टतम समाधान". Journal of Complexity. 1 (2): 197–209. doi:10.1016/0885-064X(85)90011-1. ISSN 0885-064X.
↑ Graf, Siegfried; Novak, Erich; Papageorgiou, Anargyros (1989-07-01). "द्विभाजन औसत पर इष्टतम नहीं है". Numerische Mathematik. 55 (4): 481–491. doi:10.1007/BF01396051. ISSN 0945-3245. S2CID 119546369.
↑ Novak, Erich (1989-12-01). "शून्य खोज के लिए औसत-मामला परिणाम". Journal of Complexity. 5 (4): 489–501. doi:10.1016/0885-064X(89)90022-8. ISSN 0885-064X.
↑ ^13.0 ^13.1 Oliveira, I. F. D.; Takahashi, R. H. C. (2020-12-06). "मिनमैक्स ऑप्टिमलिटी को संरक्षित करते हुए द्विभाजन विधि औसत प्रदर्शन का एक संवर्द्धन". ACM Transactions on Mathematical Software. 47 (1): 5:1–5:24. doi:10.1145/3423597. ISSN 0098-3500. S2CID 230586635.
↑ Ivo, Oliveira (2020-12-14). "एक बेहतर द्विभाजन विधि".

Burden, Richard L.; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", Numerical Analysis (3rd ed.), PWS Publishers, ISBN 0-87150-857-5

आगे की पढाई

Corliss, George (1977), "Which root does the bisection algorithm find?", SIAM Review, 19 (2): 325–327, doi:10.1137/1019044, ISSN 1095-7200
Kaw, Autar; Kalu, Egwu (2008), Numerical Methods with Applications (1st ed.), archived from the original on 2009-04-13

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी कड़ियाँ

Weisstein, Eric W. "Bisection". MathWorld.
Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica from Holistic Numerical Methods Institute

श्रेणी:रूट-फाइंडिंग एल्गोरिद्म श्रेणी: स्यूडोकोड उदाहरण के साथ लेख

[1] Burden & Faires 1985, p. 31

[2] "अंतराल आधा करना (द्विभाजन)". Archived from the original on 2013-05-19. Retrieved 2013-11-07.

[3] Burden & Faires 1985, p. 28

[4] "द्विभाजन विधि - गणित का विश्वकोश". www.encyclopediaofmath.org. Retrieved 2015-12-21.

[5] If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.

[6] Burden & Faires 1985, p. 28 for section

[7] Burden & Faires 1985, p. 29. This version recomputes the function values at each iteration rather than carrying them to the next iterations.

[8] Burden & Faires 1985, p. 31, Theorem 2.1

[:0-9] 9.0 ^9.1 Sikorski, K. (1982-02-01). "द्विभाजन इष्टतम है". Numerische Mathematik. 40 (1): 111–117. doi:10.1007/BF01459080. ISSN 0945-3245. S2CID 119952605.

[10] Sikorski, K (1985-12-01). "अरेखीय समीकरणों का इष्टतम समाधान". Journal of Complexity. 1 (2): 197–209. doi:10.1016/0885-064X(85)90011-1. ISSN 0885-064X.

[11] Graf, Siegfried; Novak, Erich; Papageorgiou, Anargyros (1989-07-01). "द्विभाजन औसत पर इष्टतम नहीं है". Numerische Mathematik. 55 (4): 481–491. doi:10.1007/BF01396051. ISSN 0945-3245. S2CID 119546369.

[12] Novak, Erich (1989-12-01). "शून्य खोज के लिए औसत-मामला परिणाम". Journal of Complexity. 5 (4): 489–501. doi:10.1016/0885-064X(89)90022-8. ISSN 0885-064X.

[:1-13] 13.0 ^13.1 Oliveira, I. F. D.; Takahashi, R. H. C. (2020-12-06). "मिनमैक्स ऑप्टिमलिटी को संरक्षित करते हुए द्विभाजन विधि औसत प्रदर्शन का एक संवर्द्धन". ACM Transactions on Mathematical Software. 47 (1): 5:1–5:24. doi:10.1145/3423597. ISSN 0098-3500. S2CID 230586635.

[14] Ivo, Oliveira (2020-12-14). "एक बेहतर द्विभाजन विधि".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v t e Root-finding algorithms
Bracketing (no derivative)	Bisection method Regula falsi ITP Method
Newton	Newton's method
Quasi-Newton	Muller's method Secant method
Hybrid methods	Brent's method Ridders' method
Polynomial methods	Bairstow's method Jenkins–Traub method Laguerre's method