Bisection method with C++ Code

Published by Zahid on

The convergence in the bisection method is linear which is slow as compared to other methods, however it is the simplest method and it never fails.

Learn Basic Working Rule and Algorithm of Bisection Method with C++ code available at the bottom.

Before starting bisection method, we must know what is intermediate value property, click on the underlined words to know what is intermediate value property. Now lets start Bisection method. This method is actually using IVP(intermediate value property) repeatedly. i.e. if a function f(x) is continuous in a closed interval [a,b] and f(a) and f(b) have opposite sign.The root lies between a and b. Then the first approximation of the root is x1=(a+b)/2;

bisection method

Now the root lies between a and x1 or x1 and b accordingly if f(a) and f(x1) have opposite sign or f(b) and f(x1) have opposite sign respectively. Let the root lies between a and x1, then we again bisect the interval to find next approximation of the root i.e. x2=(a+x1)/2 and continue the process until the root is found to desired accuracy.

BISECTION METHOD FIG1

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 ..

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 ε.

The convergence in the bisection method is linear.

Bisection Method with C++ code Below.

#include<iostream>
#include<math.h>//used for fabs() function.
#include<iomanip>//used for setw() and setprecision() you can ignore this if you
                 //don't write these functions. don't worry your program works well without
                 //these functions. 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 1;
}

0 Comments

Leave a Reply

%d bloggers like this: