द्विभाजन विधि क्या है?

द्विभाजन विधि (Bisection Method) किसी सतत फलन $f(x)$ का मूल खोजने की सबसे पुरानी और भरोसेमंद तकनीकों में से एक है — यानी वह मान $x$ जहाँ $f(x) = 0$ हो। यह विधि एक ऐसे अंतराल $[a, b]$ से शुरू होती है जिसमें फलन का चिह्न बदलता है, फिर अंतराल को बार-बार आधा करके वही आधा हिस्सा रखती है जो अब भी मूल को घेरे रहता है। चूँकि हर चरण पर चिह्न-परिवर्तन बना रहता है, इसलिए जब तक $f$ सतत है और $f(a)$ तथा $f(b)$ के चिह्न विपरीत हैं, तब तक यह विधि निश्चित रूप से अभिसरित होती है। यह कैलकुलेटर किसी भी विमारहित वास्तविक फलन के लिए काम करता है और त्रिकोणमिति में रेडियन का उपयोग करता है।

बिंदु a और b के बीच x-अक्ष को काटता हुआ सतत वक्र, मध्यबिंदु दिखाया गया है — द्विभाजन विधि उस मूल को घेरती है जहाँ $f(a)$ और $f(b)$ के चिह्न विपरीत होते हैं।

इस कैलकुलेटर का उपयोग कैसे करें

अपना फलन f(x) बॉक्स में $x$ को चर मानकर डालें (उदाहरण के लिए x-cos(x), x^2-2, या exp(x)-3)। निचला सिरा a और ऊपरी सिरा b इस तरह तय करें कि मूल उनके बीच आए — गुणनफल $f(a)\cdot f(b)$ शून्य या उससे कम होना चाहिए। अधिकतम चरणों की संख्या n चुनें और तय करें कि आप कितने अंक (digits) तक परिणाम देखना चाहते हैं। यह उपकरण अनुमानित मूल, वहाँ फलन का मान (जो शून्य के लगभग होना चाहिए), और वास्तव में कितने चरण लगे, ये सब बताता है।

सूत्र

हर चरण पर अनुमान मध्यबिंदु होता है

$$x_n = \frac{a_n + b_n}{2}$$

यदि $|f(x_n)|$ सहनशीलता (tolerance) से कम है, तो $x_n$ स्वीकार कर लिया जाता है। अन्यथा एल्गोरिथ्म वही आधा हिस्सा रखता है जिसमें अब भी चिह्न-परिवर्तन है: यदि $f(a_n)\cdot f(x_n) > 0$ है तो मूल दाईं ओर है ($a = x_n$ सेट करें), अन्यथा यह बाईं ओर है ($b = x_n$ सेट करें)। अंतराल की चौड़ाई $(b-a)/2^n$ के रूप में सिकुड़ती है, इसलिए अभिसरण रैखिक होता है — मोटे तौर पर हर चरण पर एक अतिरिक्त सही बाइनरी अंक।

मूल की ओर अभिसरित होता हुआ अंतराल का क्रमिक आधा होना — हर पुनरावृत्ति अंतराल को आधा करती है और मूल वाले आधे को रखती है।

हल किया गया उदाहरण

$f(x) = x - \cos(x)$ के लिए $[-10, 10]$ पर: $f(-10) \approx -10.84$ (ऋणात्मक) और $f(10) \approx 10.84$ (धनात्मक), अतः मूल घिरा हुआ है। बार-बार आधा करते रहने पर यह $x \approx 0.7390851332151607$ पर अभिसरित होता है — यह प्रसिद्ध डॉटी संख्या (Dottie number) है जहाँ $x = \cos x$ होता है, और वहाँ $f(x)$ व्यावहारिक रूप से शून्य होता है।

द्विभाजन विधि को हाथ से कैसे करें

द्विभाजन विधि $f(x)=0$ का मूल खोजती है जो बार-बार एक अंतराल को आधा करके पाया जाता है जिसमें मूल होना ज्ञात है। यह मध्यवर्ती मान प्रमेय पर निर्भर करता है: यदि $f$ $[a,b]$ पर सतत है और $f(a)$ और $f(b)$ के विपरीत चिन्ह हैं, तो उनके बीच मूल होना चाहिए।

कोष्ठक सत्यापित करें। पुष्टि करें कि $f(a)\cdot f(b)<0$। यदि गुणनफल सकारात्मक है, तो अंतराल में मूल होने की गारंटी नहीं है — एक अलग $[a,b]$ चुनें।
मध्यबिंदु की गणना करें। $m=\dfrac{a+b}{2}$।
फ़ंक्शन का मूल्यांकन करें। $f(m)$ खोजें। यदि $f(m)=0$ (या सहिष्णुता के भीतर है), तो $m$ मूल है और आप रुक जाते हैं।
चिन्ह के अनुसार अंतबिंदु को प्रतिस्थापित करें। यदि $f(a)\cdot f(m)<0$, तो मूल $[a,m]$ में है, इसलिए $b\leftarrow m$ सेट करें। अन्यथा मूल $[m,b]$ में है, इसलिए $a\leftarrow m$ सेट करें।
दोहराएं चरण 2–4 को जब तक $|b-a|<\text{सहिष्णुता}$ या $|f(m)|<\text{सहिष्णुता}$ न हो, या जब तक आप अधिकतम पुनरावृत्ति गणना तक न पहुंच जाएं।

उदाहरण: $f(x)=x^{3}-x-2$ पर $[1,2]$। जांच: $f(1)=-2$, $f(2)=4$, गुणनफल $<0$ — कोष्ठक वैध है।

पुनरावृत्ति	a	b	m=(a+b)/2	f(m)	नया अंतराल
1	1.0000	2.0000	1.5000	−0.125	[1.5, 2]
2	1.5000	2.0000	1.7500	1.6094	[1.5, 1.75]
3	1.5000	1.7500	1.6250	0.6660	[1.5, 1.625]
4	1.5000	1.6250	1.5625	0.2522	[1.5, 1.5625]
5	1.5000	1.5625	1.5313	0.0591	[1.5, 1.5313]
6	1.5000	1.5313	1.5156	−0.0340	[1.5156, 1.5313]

अधिक पुनरावृत्तियों के बाद अंतराल सही मूल 1.521380 पर बंद हो जाता है, जो घन $x^{3}-x-2=0$ का एकमात्र वास्तविक मूल है जो प्रत्यक्ष समाधानकर्ता द्वारा मिलता है।

पुनरावृत्तियां बनाम सहिष्णुता और कोष्ठक चौड़ाई

प्रत्येक द्विभाजन चरण अंतराल को आधा करता है, इसलिए $n$ पुनरावृत्तियों के बाद कोष्ठक चौड़ाई $(b-a)/2^{\,n}$ है। मूल के स्थान पर सहिष्णुता $\text{सहिष्णुता}$ तक पहुंचने के लिए आपको लगभग

$$n \approx \log_2\!\left(\frac{b-a}{\text{सहिष्णुता}}\right)$$ की आवश्यकता है।

गणना केवल परिशुद्धता के लघुगणक के साथ बढ़ती है, इसलिए बहुत तंग सहिष्णुताओं के लिए भी अपेक्षाकृत कम चरणों की आवश्यकता होती है। तालिका कई संयोजनों के लिए गोल-चढ़ी हुई पुनरावृत्ति गणना दिखाती है।

प्रारंभिक चौड़ाई $b-a$	लक्ष्य सहिष्णुता	$\log_2((b-a)/\text{सहिष्णुता})$	आवश्यक पुनरावृत्तियां
1	$10^{-3}$	9.97	10
1	$10^{-6}$	19.93	20
1	$10^{-10}$	33.22	34
10	$10^{-6}$	23.25	24
20	$10^{-6}$	24.25	25
100	$10^{-8}$	33.22	34
0.5	$10^{-12}$	38.86	39

उदाहरण के लिए, चौड़ाई-20 कोष्ठक $10^{-6}$ में परिष्कृत करने के लिए $\lceil\log_2(20/10^{-6})\rceil=\lceil 24.25\rceil=$ 25 पुनरावृत्तियों की आवश्यकता है, और चौड़ाई-1 कोष्ठक $10^{-10}$ के लिए $\lceil 33.22\rceil=$ 34 की आवश्यकता है। शुरुआती चौड़ाई को आधा करने से बिल्कुल एक पुनरावृत्ति की बचत होती है; परिशुद्धता को वर्ग करना (एक अतिरिक्त दशमलव) लगभग 3.3 पुनरावृत्तियों का खर्च करता है।

मुख्य शर्तें

मूल। एक मान $x^{*}$ जहां फ़ंक्शन शून्य है, $f(x^{*})=0$; इसे शून्य या समीकरण का समाधान भी कहा जाता है।
कोष्ठक / अंतराल $[a,b]$। अंतबिंदुओं की एक जोड़ी जिसे मूल को घेरने के लिए माना जाता है। द्विभाजन के लिए इसे चिन्ह-परिवर्तन शर्त को पूरा करना चाहिए।
चिन्ह परिवर्तन। शर्त $f(a)\cdot f(b)<0$, जिसका अर्थ है कि $f$ अंतबिंदुओं पर विपरीत चिन्ह लेता है। सतत $f$ के लिए यह बीच में कम से कम एक मूल की गारंटी देता है (मध्यवर्ती मान प्रमेय)।
मध्यबिंदु। वर्तमान अंतराल का केंद्र, $m=(a+b)/2$; प्रत्येक चरण इस बिंदु की जांच करता है और आधे को त्यागता है जो मूल को नहीं रख सकता।
सहिष्णुता। सटीकता लक्ष्य जो पुनरावृत्ति को रोकता है, या तो अंतराल चौड़ाई $|b-a|$ या अवशिष्ट $|f(m)|$ पर लागू होता है।
अभिसरण (रैखिक)। द्विभाजन रैखिक रूप से अभिसरित होता है: त्रुटि प्रत्येक चरण में लगभग आधी हो जाती है (त्रुटि $\le (b-a)/2^{n}$), स्थिर लेकिन त्वरान्वित नहीं प्रगति देता है — प्रति पुनरावृत्ति लगभग एक अतिरिक्त सही बाइनरी अंक।
पुनरावृत्ति। मध्यबिंदु की गणना, फ़ंक्शन का मूल्यांकन, और अंतबिंदु को अपडेट करने का एक पूर्ण चक्र। पुनरावृत्ति गणना अधिकतम-पुनरावृत्तियां सेटिंग द्वारा सीमित है।

अक्सर पूछे जाने वाले प्रश्न

मुझे "no sign change" (कोई चिह्न-परिवर्तन नहीं) त्रुटि क्यों मिलती है? द्विभाजन के लिए $f(a)$ और $f(b)$ के चिह्न विपरीत होने चाहिए। $a$ और $b$ को तब तक समायोजित करें जब तक वे मूल को दोनों ओर से घेर न लें।

क्या यह एक से अधिक मूल खोज सकता है? नहीं — यह घेरे गए अंतराल के भीतर केवल एक ही मूल लौटाता है, और ऐसे मूल नहीं पहचान सकता जहाँ वक्र अक्ष को छूता तो है पर पार नहीं करता।

यह न्यूटन विधि (Newton's method) से धीमी क्यों है? द्विभाजन रैखिक रूप से अभिसरित होती है और प्रति चरण लगभग एक बाइनरी अंक जोड़ती है, जबकि न्यूटन विधि वर्गाकार (quadratically) रूप से अभिसरित होती है। द्विभाजन का उपयोग अक्सर एक सुरक्षित प्रारंभिक बिंदु पाने के लिए किया जाता है जिसे बाद में तेज़ विधियाँ और परिष्कृत करती हैं।

मूल पर f(x)	-0.0000000000000263
प्रयुक्त चरण	50
विधि	द्विभाजन (अंतराल अर्धन)

द्विभाजन विधि से मूल (Root) खोजें

गणना दर्ज करें

सूत्र (फॉर्मूला)

परिणाम