द्विभाजन विधि – क्या है, एल्गोरिथ्म और उदाहरण
सारा चेन
द्विभाजन विधि क्या है?
द्विभाजन विधि बहुपद समीकरण का मूल ज्ञात करने के लिए मूलभूत संख्यात्मक समाधानों में से एक है। यह उस अंतराल को कोष्ठक में रखता है जिसमें समीकरण का मूल स्थित होता है और प्रत्येक पुनरावृत्ति में उन्हें आधे भागों में विभाजित करता है जब तक कि वह मूल नहीं पा लेता। इस प्रकार, द्विभाजन विधि को ब्रैकेटिंग विधि भी कहा जाता है।
हालाँकि, चूँकि इसकी कार्यप्रणाली बाइनरी सर्च एल्गोरिदम के समान है, इसलिए द्विभाजन विधि को बाइनरी सर्च विधि, हॉल्विंग विधि या डाइकोटॉमी विधि के रूप में भी जाना जाता है। यह मुख्य रूप से मध्यवर्ती मान प्रमेय पर आधारित है।
समीकरणों के मूल ज्ञात करना
इस उदाहरण में, हम केवल एक स्वतंत्र चर वाले समीकरणों पर विचार करते हैं। यह रैखिक या अरैखिक हो सकता है। रैखिक समीकरणों का उपयोग सीधी रेखा के ग्राफ को दर्शाने के लिए किया जाता है, जबकि अरैखिक समीकरणों का उपयोग वक्रों को दर्शाने के लिए किया जाता है।
किसी समीकरण का मूल उस स्वतंत्र चर का मान है जो समीकरण को संतुष्ट करता है। उदाहरण के लिए: समीकरण f(x)= 4-x का मूल2 = 0 = 2 क्योंकि f(2) = 4-22 = 0.
आइए f(x) को एक वास्तविक सतत फ़ंक्शन के रूप में लें। मध्यवर्ती मान प्रमेय के अनुसार, समीकरण f(x)=0 में a और b के बीच कम से कम एक मूल होता है यदि f(a)f(b) < 0. फ़ंक्शन f(x) में a और b के बीच एक मूल, “c” होता है।
द्विभाजन विधि का ग्राफिकल प्रतिनिधित्व
निम्न ग्राफ द्विभाजन विधि की कार्य प्रणाली को दर्शाता है। ग्राफ से हम देख सकते हैं कि समीकरण का मूल लाल रंग से चिह्नित है।
शुरुआत के लिए:
- हमने पहले दो प्रारंभिक अनुमान लगाए,1 और बी1, जिसके लिए f(a1)एफ(बी1) < 0. मध्यवर्ती मान प्रमेय के अनुसार, मूल [a1, बी1].
- हम एक समकोण का मध्यबिंदु ज्ञात कर सकते हैं1 और बी1, जो कि बी है2इस प्रकार, प्रारंभिक अंतराल अब घटकर [a1, बी2] क्योंकि f(a1)एफ(बी2) < 0.
- इसी प्रकार, अंतराल को तब तक कम किया जाता है जब तक कि अनुमानित समाधान नहीं मिल जाता।
द्विभाजन विधि एल्गोरिथ्म
समीकरण f(x)=0 का मूल ज्ञात करने के लिए द्विभाजन विधि एल्गोरिथ्म को लागू करने के चरण निम्नानुसार हैं
चरण 1) प्रारंभिक अनुमान a, b, और सहनशीलता दर e चुनें
चरण 2) यदि f(a)f(b) >=0, तो मूल इस अंतराल में नहीं होगा। इस प्रकार, कोई हल नहीं होगा।
चरण 3) मध्यबिंदु ज्ञात करें, c = (a+b)/2
(i) यदि मध्यबिंदु f(c) का फ़ंक्शन मान = 0 है, तो c मूल है। चरण 5 पर जाएँ।
(ii) यदि f(a)f(c) < 0 तो मूल a और c के बीच स्थित है। तो a = a, b = c रखें।
(iii) अन्यथा a = c, b = b रखिए।
चरण 4) यदि निरपेक्ष त्रुटि सहनशीलता दर से अधिक है या (ba) > e है, तो चरण 3 पर जाएँ।
चरण 5) c को अनुमानित मूल के रूप में प्रदर्शित करें.
आइये द्विभाजन विधि एल्गोरिथ्म का एक उदाहरण देखें।
हमें द्विभाजन विधि सूत्र का उपयोग करके निम्नलिखित सतत फलन का मूल ज्ञात करना है।
एफ (एक्स) = एक्स3 - एक्स2 + 2
द्विभाजन विधि का उदाहरण
चरण 1) मान लीजिए,
ए = -10,
बी = 10, और
ई = 1% या 0.01
चरण 2) अब, हम जाँचेंगे कि f(a)f(b) >= 0 है या नहीं।
एफ(ए) = एफ(-10) = (-10)3 – (-10)2 + 2 = -1098
एफ(बी) = एफ(10) = (10)3 – (10)2 + 2 = 902
एफ(ए)एफ(बी) = एफ(-10)एफ(10) = (-1098)(902) < 0
अतः उपरोक्त फलन का मूल इस अंतराल [-10, 10] में स्थित है।
चरण 3) फिर सबसे पहले मध्यबिंदु c की गणना की जाएगी।
अब निम्नलिखित शर्तों की जाँच करना आवश्यक है:
(i) क्या f(c) = 0:
एफ(सी) = एफ(0) = (0)3 – (0)2 + 2 = 2 ≠ 0
(ii) यदि f(a)f(c) < 0:
एफ(सी)एफ(ए) = 2*(-1098) < 0
शर्त पूरी हो गई है। अगले पुनरावृत्ति के लिए, मान होंगे,
ए = ए = -१०
बी = सी = 0
चरण 4) चूँकि (ba) = (0-(-10)) = 10>0.05 है, इसलिए प्रक्रिया दोहराई जाएगी। अगली पुनरावृत्तियाँ तालिका में दर्शाई गई हैं।
| यात्रा | a | b | c | बी ० ए | एफ(सी) |
|---|---|---|---|---|---|
| 1 | -10 | 0 | 0 | 10 | 2 |
| 2 | -5 | 0 | -5 | 5 | -148 |
| 3 | -2.5 | 0 | -2.5 | 2.5 | -19.875 |
| 4 | -1.25 | 0 | -1.25 | 1.25 | -1.52562 |
| 5 | -1.25 | -0.625 | -0.625 | 0.625 | 1.36523 |
| 6 | -1.25 | -0.9375 | -0.9375 | 0.3125 | 0.297119 |
| 7 | -1.09375 | -0.9375 | -1.09375 | 0.15625 | -0.50473 |
| 8 | -1.01562 | -0.9375 | -1.01562 | 0.078125 | -0.0791054 |
| 9 | -1.01562 | -0.976562 | -0.976562 | 0.0390625 | 0.115003 |
| 10 | -1.01562 | -0.996094 | -0.996094 | 0.0195312 | 0.0194703 |
| 11 | -1.00586 | -0.996094 | -1.00586 | 0.00976562 | -0.0294344 |
चरण 5) 11वें पुनरावृत्ति में, चरण 4 की शर्त गलत होगी। इस प्रकार, इस समीकरण का मूल -1.00586 है।
द्विभाजन विधि तार्किक आरेख
झूठाCode
Start
Set a, b, e
if f(a)*f(b) >=0
Output("Root does not exist in this interval")
Stop
while (b-a)>e do
c ← (a + b)/2
if f(c) = 0
break
end if
if f(c)*f(a) < 0 then
b ← c
else
a ← c
end while
Output(c)
Stop
सी/ में द्विभाजन विधि का उदाहरणC++
इनपुट:
#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
if (value(a) * value(b) >= 0)
{
cout << "The root does not lie in this interval\n";
return;
}
double c = a;
while ((b-a) >= Error)
{
c = (a+b)/2;
if (value(c) == 0.0)
break;
else if (value(c)*value(a) < 0)
b = c;
else
a = c;
}
cout << "The root is :" << c;
}
int main()
{
double a =-10 , b = 10;
bisection_method(a, b);
return 0;
}
आउटपुट:
The root is :-1.00586
द्विभाजन विधि का उदाहरण Python
इनपुट:
def value(x):
return x*x*x - x*x + 2
def bisection_method(a,b):
if (value(a) * value(b) >= 0):
return
c = a
while ((b-a) >= 0.01):
c = (a+b)/2
if (value(c) == 0.0):
break
if (value(c)*value(a) < 0):
b = c
else:
a = c
print("The root is : ","%.4f"%c)
a =-10
b = 10
bisection_method(a, b)
आउटपुट:
The root is : -1.0059
द्विभाजन विधि के लाभ और सीमाएं
द्विविभाजन विधि के पक्ष और विपक्ष इस प्रकार हैं:
| फ़ायदे | नुकसान |
|---|---|
| कार्यान्वयन हेतु आसान एवं सरल मूल-खोज विधि। | अभिसरण धीमा है क्योंकि यह केवल अंतराल को आधा करने पर आधारित है। |
| चूँकि यह मूल को कोष्ठक में रखता है, इसलिए यह सदैव अभिसारी होता है। | यदि आरंभिक अनुमानों में से कोई एक मूल के करीब है, तो मूल तक पहुंचने में अधिक पुनरावृत्तियों की आवश्यकता होगी। |
| पुनरावृत्तियों की संख्या बढ़ाकर या घटाकर त्रुटि दर को नियंत्रित किया जा सकता है। |
