 ## Bisection Method

The bisection method is an Algorithm or an Iterative Method for finding the roots of a Non-Linear equation.

The convergence in the bisection method is linear which is slow as compared to the other Iterative methods.

However, it is the simplest method and it never fails.

## Rule | Method

This method is actually using Intermediate Value Property repeatedly.

If a function f(x) is continuous in a closed interval [a,b] and f(a) and f(b) have opposite sign.

Then The root lies between a and b and the first approximation of the root is x1=(a+b)/2. Now the root lies between a and x1 or x1 and b accordingly if f(a) and f(x1) have an opposite sign or f(b) and f(x1) have opposite signs respectively.

Let the root lies between a and x1, then we again bisect the interval to find the next approximation of the root i.e. x2=(a+x1)/2, and continue the process until the root is found to the desired accuracy.

In the above figure the f(x1) is positive and f(x0) is negative so the root lies between x1 and x0.

Then we bisect the interval and find x2 and f(x2) is also positive so the root lies between x0 and x2 , and we find x3 and so on ..

## Bisection Method Example

### Find the Root of the equation x^3 – 4x – 9 = 0, using the bisection method correct to three decimal places.

Sol. Let f(x) = x3 – 4x – 9

Some Observations

Since every interval is half of its previous interval, i.e in each step the length of interval is reduced by a factor of 1/2.

So the length of nth interval will be (b-a)/x^n. let ‘e’ be the required accuracy, then (b-a)/x^n ≤ε. taking log on both sides we get ‘n ≥[log(b-a) – logε] / log2. This gives the number of iterations required for achieving an accuracy ε.

MCQ: The convergence in the bisection method is linear.

## Bisection Method C++ code

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```    //Biscection method c++
//wikkihut.com

#include<iostream>
#include<math.h>  //used for fabs() function.
#include<iomanip>//used for setw() and setprecision()
//they are used to just manipulate the output.

using namespace std;
//function definition

//it calculates the value of xsinx-1 for different values of x.
float f(float x)
{
return x*sin(x)-1;
}

//bisects the interval and counts the number of iterations
//by incrementing the value of itr.

void bisect(float *x,float a,float b,int*itr)
{
*x=(a+b)/2;
++(*itr);
cout<<"iteration no. "<<*itr<< " X = "<<setw(3)<< setprecision(5)<< *x<<endl;
}

int main()
{
int itr=0,maxitr;
float x,a,b,aerr,x1;
cout<<"Enter the values of a and b , allowed error, maximum iterations"<<endl;
cin>>a>>b>>aerr>>maxitr;
cout<<fixed;
bisect(&x,a,b,&itr);
do
{
if(f(a)*f(x)<0)
b=x;
else
a=x;
bisect(&x1,a,b,&itr);
if(fabs(x1-x)<aerr)//fabs() calculate the absolute value of (x1-x).
{
cout<<"After "<< itr <<" iterations, root"<< " = "<<setw(6)<< setprecision(4)<<x1<<endl;
return 0;
}
x=x1;
}while(itr<maxitr);
cout<<"Solution does not converege,"<<"iterations not sufficient"<<endl;
return 0;
}
```Code language: PHP (php)```