Updated June 28, 2023
Definition
The Bisection Method, also known as the dichotomy or halving interval method, is a widely used root-finding algorithm employed to locate the root of a continuous function within a defined interval. This method works by repeatedly dividing the interval in half and selecting the subinterval that contains the root. This process is repeated until the root is found within a specified degree of accuracy.
What is Bisection Method in C?
The Bisection Method is a numerical technique to find a continuous function’s root (or zero) within an interval. The method involves repeatedly bisecting the interval into smaller subintervals and determining which subinterval contains the root. In C, the Bisection Method can be implemented by defining a function that takes the interval’s left and right endpoints as inputs, calculates the interval’s midpoint, and checks if the value of the function at the midpoint is close enough to zero. If not, the method updates the interval based on the sign of the function value and continues the process until a satisfactory approximation of the root is found.
Explanation
Its explained with an example:
1. Initially. we need to define the function f(x) which we want to find the root for:
You need to write a function in C that takes in a value x and returns the function value you want to find the root of. For example, the function f(x) is defined as x^2 – 4.
2. Define the interval [a, b] that contains the root:
You need to choose an interval [a, b] that contains the root of the function you defined in Step 1. For example, the interval is [1, 5].
3. Set a tolerance value for the error in the approximation of the root:
Choose a tolerance value that represents the error tolerance for your root approximation. For example, let’s say the tolerance value is 10^-6.
4. Initialize variables:
Initialize two variables left and right with values a and b, respectively. Also, initialize a variable mid to store the interval’s midpoint and a variable error to store the error in the root approximation.
5. Evaluate the function at the midpoint:
Calculate the interval’s midpoint by taking a left and right average: mid = (left + right) / 2. Then evaluate the function f(x) at the midpoint and store the result in a variable f_mid.
6. Determine if the deviation from the true value falls within the specified tolerance level:
If f_mid is close enough to 0 (i.e., the error |f_mid| is less than the tolerance value), return the midpoint as the approximate root.
7. Update the interval:
If f_mid is positive, update the interval by setting right = mid. If f_mid is negative, update the interval by setting left = mid.
8. Repeat steps 5 to 7 until the deviation from the true value falls within the specified tolerance level:
Repeat steps 5 to 7 until the error |f_mid| is less than the tolerance value.
9. Return the approximate root:
Once the error is within the tolerance, return the value of mid as the approximate root of the function.
Algorithm for Bisection Method in C
The algorithm for the Bisection Method in C can be described as follows:
- Input the function func whose root is to be found, the left and right endpoints of the interval l and r, and the desired tolerance EPS.
- Calculate the midpoint of the interval (l + r)/2.
- Evaluate the function at the midpoint, f(mid).
- If |f(mid)| < EPS, return mid as the approximation of the root.
- Determine if the root lies in the left or right half of the interval by checking the sign of f(mid) * f(l).
- If f(mid) * f(l) < 0, update r to be mid. If f(mid) * f(l) > 0, update l to be mid.
- Go back to step 2.
This would be an example execution of the Bisection Method in C:
Code:
#include <math.h>
double bisection(double l, double r) {
double mid = (l + r) / 2;
while (fabs(func(mid)) >= EPS) {
if (func(mid) * func(l) < 0)
r = mid;
else
l = mid;
mid = (l + r) / 2;
}
return mid;
}Examples of Bisection Method in C
Below are the different examples of bisection method in C:
Example #1
Code:
#include <stdio.h>
#include <math.h>
double func(double x) {
return pow(x, 3) - x - 2;
}
double bisection(double l, double r) {
double mid = (l + r) / 2;
while (fabs(func(mid)) >= 1e-6) {
if (func(mid) * func(l) < 0)
r = mid;
else
l = mid;
mid = (l + r) / 2;
}
return mid;
}
int main() {
double root = bisection(1, 2);
printf("The root of the function is approximately: %.6f\n", root);
return 0;
}Output:
Explanation:
1. The function func is defined to be x^3 – x – 2.
2. The bisection function takes in two arguments, l and r, which are the left and right endpoints of the interval where the root is to be found.
3. The function calculates the interval’s midpoint and stores it in the mid.
4. The function uses a while loop to repeat the following steps until the absolute value of the function evaluated at the midpoint is less than 1e-6:
- If the product of the function values at the midpoint and one of the endpoints is negative, the interval is updated to be the left half.
- If the product is positive, the interval is updated to be the right half.
- The midpoint is recalculated based on the updated interval.
5. The midpoint is returned as the approximation of the root.
6. In the main function, the bisection function is called with the interval (1, 2), and the result is stored in the root.
7. The outcome is printed to the console, which portrays the approximate root of the function.
Example #2
Code:
#include <stdio.h>
#include <math.h>
double func(double x) {
return pow(x, 2) - 4;
}
double bisection(double l, double r) {
double mid = (l + r) / 2;
while (fabs(func(mid)) >= 1e-6) {
if (func(mid) * func(l) < 0)
r = mid;
else
l = mid;
mid = (l + r) / 2;
}
return mid;
}
int main() {
double root = bisection(1, 4);
printf("The root of the function is approximately: %.6f\n", root);
return 0;
}Output:
Explanation:
1. The function func is defined to be x^2 – 4.
2. The bisection function takes in two arguments, l and r, which are the left and right endpoints of the interval where the root is to be found.
3. The function calculates the interval’s midpoint and stores it in the mid.
4. The function uses a while loop to repeat the following steps until the absolute value of the function evaluated at the midpoint is less than 1e-6:
- If the product of the function values at the midpoint and one of the endpoints is negative, the interval is updated to be the left half.
- If the product is positive, the interval is updated to be the right half.
- The midpoint is recalculated based on the updated interval.
- The midpoint is returned as the approximation of the root.
5. In the main function, the bisection function is called with the interval (1, 4), and the result is stored in the root.
6. The outcome is printed to the console, displaying the approximate root of the function x^2 – 4.
Features of the Bisection Method
- Simple and easy to understand: The Bisection Method is one of the simplest methods for finding the roots of a function and is easy to understand, even for those with limited mathematical knowledge.
- Convergence: The Bisection Method is a convergent method that approaches the root as the number of iterations increases.
- Guaranteed to Converge: The Bisection Method is ensured to meet to a root as long as the settled function is continuous on the considered interval.
- Robustness: The Bisection Method is robust, meaning it is not easily affected by changes in the function or the interval being considered.
- Bracketing the Root: The Bisection Method is a bracketing method that always brackets the root, making it useful in cases where the root may be difficult to determine.
- Slow Convergence: One of the Bisection Method’s main disadvantages is its slow convergence. It requires many iterations to reach a solution that is accurate to a high degree of precision.
- Requires a Starting Interval: The Bisection Method requires that a starting interval be specified, which contains the root being sought. This can present a challenge as the root may not be known beforehand.
Advantages and Disadvantages of the Bisection Method
| Advantages | Disadvantages |
| The Bisection Method is simple to comprehend and execute, making it available to all individuals. | The method only provides approximate solutions, and the degree of accuracy depends on the number of iterations. |
| The method will always approach a root if the function is continuous within the interval. | The method takes longer to find an accurate solution to a high degree of precision, resulting in a slower convergence rate. |
| The method is resilient to modifications in the function or interval. | The method is unsuitable for functions with multiple roots and may converge to a different root than desired. |
| The method always brackets the root, making it useful in cases where the root is difficult to determine. | The method requires a starting interval that contains the root being sought, which can be challenging to determine. In some cases, the method may converge to a value that is not the actual root, as it may become trapped in local minima. |
Conclusion
The Bisection Method is a simple and robust method for finding the roots of a function. It can converge to a root if the function is continuous on the considered interval. The method is easy to understand and implement, making it accessible to people with limited mathematical knowledge. However, it has slow convergence and only provides approximate solutions, and it may sometimes become trapped in local minima. The Bisection Method is also limited to single root functions and requires a starting interval to be specified, which can be challenging to determine in some cases.
Recommended Article
In this article, you learned about Bisection Method in C. To know more about the topic, you can refer to these articles.
