Bisection Method in C and C++ (二分法)

Bisection Method in C and C++

源自於

https://www.thecrazyprogrammer.com/2017/04/bisection-method.html

In this tutorial you will get program for bisection method in C and C++.

To find a root very accurately Bisection Method is used in Mathematics. Bisection method algorithm is very easy to program and it always converges which means it always finds root.

Bisection Method repeatedly bisects an interval and then selects a subinterval in which root lies. It is a very simple and robust method but slower than other methods.

It is also called Interval halving, binary search method and dichotomy method.

Bisection Method calculates the root by first calculating the mid point of the given interval end points.

Image Source

Bisection Method Procedure

The input for the method is a continuous function f, an interval [a, b], and the function values f(a) and f(b). The function values are of opposite sign (there is at least one zero crossing within the interval). Each iteration performs these steps:

1. Calculate the midpoint c = (a + b)/2

2. Calculate the function value at the midpoint, function(c).

3. If convergence is satisfactory (that is, a – c is sufficiently small, or f(c) is sufficiently small), return c and stop iterating.

4. Examine the sign of f(c) and replace either (a, f(a)) or (b, f(b)) with (c, f(c)) so that there is a zero crossing within the new interval.

Pros and Cons

Advantage of the bisection method is that it is guaranteed to be converged and very easy to implement.

Disadvantage of bisection method is that it cannot detect multiple roots and is slower compared to other methods of calculating the roots.

Program for Bisection Method in C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#include<stdio.h>   //function used is x^3-2x^2+3 double func(double x) {     return x*x*x - 2*x*x + 3; }   double e=0.01; double c;   void bisection(double a,double b) {     if(func(a) * func(b) >= 0)     {         printf("Incorrect a and b");         return;     }       c = a;       while ((b-a) >= e)     {         c = (a+b)/2;         if (func(c) == 0.0){             printf("Root = %lf\n",c);             break;         }         else if (func(c)*func(a) < 0){                 printf("Root = %lf\n",c);                 b = c;         }         else{                 printf("Root = %lf\n",c);                 a = c;         }     } }   int main() {     double a,b;     a=-10;     b=20;       printf("The function used is x^3-2x^2+3\n");     printf("a = %lf\n",a);     printf("b = %lf\n",b);     bisection(a,b);     printf("\n");     printf("Accurate Root calculated is = %lf\n",c);       return 0; }

Output

a = -10.000000
b = 20.000000
Root = 5.000000
Root = -2.500000
Root = 1.250000
Root = -0.625000
Root = -1.562500
Root = -1.093750
Root = -0.859375
Root = -0.976563
Root = -1.035156
Root = -1.005859
Root = -0.991211
Root = -0.998535

Accurate Root calculated is = -0.998535

Program for Bisection Method in C++

#include<iostream>   using namespace std;   //function used is x^3-2x^2+3 double func(double x) {     return x*x*x - 2*x*x + 3; }   double e=0.01; double c;   void bisection(double a,double b) {     if(func(a) * func(b) >= 0)     {         cout<<"Incorrect a and b";         return;     }       c = a;       while ((b-a) >= e)     {         c = (a+b)/2;         if (func(c) == 0.0){             cout << "Root = " << c<<endl;             break;         }         else if (func(c)*func(a) < 0){                 cout << "Root = " << c<<endl;                 b = c;         }         else{                 cout << "Root = " << c<<endl;                 a = c;         }     } }   int main() {     double a,b;     a=-10;     b=20;       cout<<"The function used is x^3-2x^2+3\n";     cout<<"a = "<<a<<endl;     cout<<"b = "<<b<<endl;     bisection(a,b);     cout<<"\n";     cout<<"Accurate Root calculated is = "<<c<<endl;       return 0; }

This article is submitted by Rahul Maheshwari.