The bisection method is one of the good computational methods (or numerical method) for finding the root of an equation or polynomial or function. This method is easy to learn and easy to implement in any programming language. But before going to the Bisection Method, let’s first understand the meaning of the root.
Generally, root is defined as the solution to an equation.
for example The solution of this equation is the value of x for which the identity is conserved. For value, , this equation is valid. Hence, 3 is the root of this equation.
Now, let’s consider a function similar to that: . In this case, for x value equal to 3, the f(x) becomes 0. This value 3 is the root of this function. Hence, we can say, for function f(x), the value of x at which f(x) gives 0 is the root of the function.
The variable x is an arbitrary variable (or dummy variable). You can replace variable x by any variable of your choice. So, whether you write or , the function is same.
So whether we are considering function or equation, the meaning of root is same.
The above examples are of the first degree since x is of power 1. But for the second degree(i.e. ), the equation or function becomes quadratic and has two roots.
Let’s try to understand root graphically also.
Let’s plot in the graph. You can use the software of your choice to plot the graph. For now, I am using an online graph calculator by DESMOS. See the graph of this function as shown below:
After we plot the above function considering in the horizontal axis and in the vertical axis, we get a straight line that cuts X-axis at coordinate (3, 0). We already know 3 is the root of this function.
Let’s plot quadratic equation,
The above curve cuts the X-axis at two points. Hence, this function has two roots, as also mentioned in the above NOTE.
Now, you understood the meaning of root or root of the function. Now let’s understand how to find the root.
How to find root?
We can find root in many ways: we can solve the equation to get the value, or we can plot in the graph and see the value.
Solving the equation to get root is not always an easy task. As we go to higher-order, the problem gets more complex and cannot be solved analytically and there are some equations that cannot be solved at all using solving methods.
Let’s have a look at few examples:
The first and second examples are easy to solve but third example cannot be solved in that way. The third equation is called transcendental equation.
Graphical Method works fine in all cases.
But when it comes to performing other complex calculations involving finding the root, it’s not good to find root in either of the ways. Why go through all the hassles of solving and plotting if that can be done with a few lines of code. Yeah, that’s right. So we have lots of computational methods to do that like the Bisection Method, Newton-Rapson Method, Secant Method, etc. One of the simplest methods to understand is the bisection method.
The Bisection method is based on the theorem called Intermediate Value Theorem that says there exists a root of function f in an interval [a, b] where f(a) and f(b) are of opposite sign.
Intermediate Value Theorem: For a continuous function f(x) in an interval [a, b] there exist a root if f(a).f(b) < 0.
Let’s look at the two figures to understand clearly.
In this first figure, both f(a) and f(b) are of the same sign and hence give positive value on their product. So this interval doesn’t contain a root according to the theorem.
In this second figure, both f(a) and f(b) is of the opposite sign and hence give negative value on their product. So this interval contains a root according to the theorem.
In the bisection method of root finding, we first set an interval that contains the root. Then, we divide that interval into two equal halves. We then have to determine the interval that contains the root and that is done using the Intermediate Value Theorem mentioned above. After that, we only take one interval that contains the root and we repeat the bisecting process on that interval until we get very closer to the root.
Since this method involving bisecting the interval into two equal halves, the method is also called interval halving method or dichotomy method.
Steps of the Bisection Method
- Provide an interval, say [a, b] that contains the root.
- Find middle point of that interval, so that there are two intervals now; [a, c] and [c, b].
- Determine which interval contains the root using condition: or and select that interval.
- Find the error and compare with the tolerance value
- If the error is less, then c is the root
- If error is more, we repeat the process from step-2
FORTRAN code for Bisection Method
program bisection implicit none real :: a, b, root integer :: n ! giving interval for bisection process initiating a = 0 b = 1.0 call bisect(a, b, root, n) print*, "The root of this function is", root, "after", n, "iterations" end program real function f(x) implicit none real :: x ! providing function to calculate functional value f = x - cos(x) end function subroutine bisect(a, b, root, n) implicit none real :: a, b real :: c real :: tol, error, f real :: root integer :: n n = 1 tol = 0.001 ! dividing interval into two equal halves 50 c = (a + b) / 2.0 ! checking condition for existence of root if (f(c)*f(b) < 0) then a = c ! changing [a, b] to [a, c] else b = c ! changing [a, b] to [c, b] end if ! calculating relative error error = abs((a-b)/c) ! comparing error with tolerance if (error <= tol) then root = c else n = n + 1 goto 50 end if end subroutine
The output is:
The root of this function is 0.738769531 after 11 iterations
In the above code, we use n for the number of iterations. The iterations required to get the desired root can also be calculated by the formula: , where is the tolerance value.
This process is easy to implement in the code and does the work for us. But the convergence rate to find the root is slower than other methods. So, it’s easy and fast to use this method for simpler functions or equations but it is not suggested to use for more complex problems.