Let’s understand the bisection method in numerical analysis and learn how to implement bisection method in C programming with an explanation, output, advantages, disadvantages and much more.
What is Bisection method?
The bisection method is a root-finding method based on simple iterations. It bisects (or divides) the intervals, and thereby, selects another sub-interval in which the root must probably occur. The bisection method is used to solve transcendental equations.
The bisection method is used to find the real roots of a non-linear function. An interval basically consists of an end value and a start value, with which the mid-point is calculated.
Here, the size of the interval is reduced to 50% after every iteration and the number of iterations can be defined a priori.
The bisection method is based on the Intermediate Value Theorem. The bisection method is also popularly known as binary search method, dichotomy method and internal halving method.
The non-linear function used here is: x3 – 4x – 9
Bisection Method Theorem
An equation f(x) = 0, where f(x) is a real continuous function, has at least one root between a and b, if f(a) f(b) < 0.
The first method describes the implementation of bisection method in C programming using For loop whereas the second method demonstrates the use of If-Else method.
Bisection Method Algorithm
- Input an interval(start and end values), continuous function and function values f(a) and f(b).
- Find the mid-point value of the function.
- If the transformation is satisfactory, return the mid-point and then stop the iteration.
- Check the sign value of f(c) and replace the appropriate function and values.
In another way, the algorithm of bisection method can also be represented in the following way:
Given a function f (x) continuous on an interval [a,b] and f (a) * f (b) < 0
1 2 3 4 5 6 | Do midpoint = (start_interval + end_interval) / 2 if(f(start_interval) * f(midpoint) < 0) then end_interval = midpoint else(start_interval = midpoint) while(none of the convergence criteria is satisfied) |
Advantages
- The convergence is guaranteed in bisection method.
- The error can be controlled in this method.
- One function evaluation per iteration.
- The bisection method usually converges in a linear fashion.
Disadvantages
- The convergence of bisection method is very slow compared to other iterative methods.
- The approximate rate of convergence of bisection method is 0.5.
Note: This bisection method in C programming is compiled with GNU GCC compiler using CodeLite IDE on Microsoft Windows 10 operating system.
Method 1: Implement Bisection Method in C Programming using For Loop
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 | #include<stdio.h> void bisection_function(float *mid_point, float interval_start, float interval_end, int *iteration_count); double calc_function(double temp); int main() { int iteration_count, maximum_iteration_count; float mid_point, interval_start, interval_end, error_allowed, root; printf("Enter Interval Start Point:\t"); scanf("%f", &interval_start); printf("Enter Interval End Point:\t"); scanf("%f", &interval_end); printf("Enter Maximum Iterations To Allow:\t"); scanf("%d", &maximum_iteration_count); printf("Enter Allowed Error Point:\t"); scanf("%f", &error_allowed); bisection_function (&mid_point, interval_start, interval_end, &iteration_count); for(iteration_count = 0; iteration_count < maximum_iteration_count; mid_point = root) { if(calc_function(interval_start) * calc_function(mid_point) < 0) { interval_end = mid_point; } else { interval_start = mid_point; } bisection_function (&root, interval_start, interval_end, &iteration_count); if(fabs(root - mid_point) < error_allowed) { printf("\nCalculated Root:\t%f\n", root); return 0; } } printf("\nThe iterations are insufficient\n"); return 0; } void bisection_function(float *mid_point, float interval_start, float interval_end, int *iteration_count) { *mid_point = (interval_start + interval_end) / 2; ++(*iteration_count); printf("Iteration\t%d:\t%f\n", *iteration_count, *mid_point); } double calc_function(double temp) { return(temp * temp * temp - 4 * temp - 9); } |
Method 2: C Program For Bisection Method using Functions
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 | #include<stdio.h> float non_linear_function(float temp); void bisection(float *temp, float start, float end, int *iteration_count); int main() { int iteration_count, maximum_iteration; float temp, start, end, allowed_error, root; printf("Enter Interval Start Point:\t"); scanf("%f", &start); printf("Enter Interval End Point:\t"); scanf("%f", &end); printf("Enter Maximum Iterations To Allow:\t"); scanf("%d", &maximum_iteration); printf("Enter Allowed Error Point:\t"); scanf("%f", &allowed_error); bisection(&temp, start, end, &iteration_count); for(iteration_count = 0; iteration_count < maximum_iteration; temp = root) { if(non_linear_function(start) * non_linear_function(temp) < 0) { end = temp; } else { start = temp; } bisection (&root, start, end, &iteration_count); if(fabs(root - temp) < allowed_error) { printf("\nCalculated Root:\t%f\n", root); return 0; } } printf("\nThe iterations are insufficient\n"); return 0; } float non_linear_function(float temp) { return (temp * temp * temp - 4 * temp - 9); } void bisection(float *temp, float start, float end, int *iteration_count) { *temp = (start + end) / 2; ++(*iteration_count); printf("Iteration\t%d:\t%f\n", *iteration_count, *temp); } |
Output
If you have any doubts about the implementation of Bisection method in C programming, let us know about it in the comment section.
The bisection methods seems to be very similar to Newton Raphson method though.
Thanks for the bisection method. I, now, get to understand the power of C programming. Its really amazing.
The false position method is much faster than bisection method.
This bisection method C program is so informative. Thank you so much for the flowchart.
The bisection method in C programs are described in such an easy manner. Thanks for it. I could now understand the algorithm.
Thank you so much!