2 Root Finding Problem: (Bisection Method)
Savita R. Gandhi
Why study Root-Finding Problem?
Root finding problem occupies important position amidst different scientific computing problems. It occurs in application problems of almost every scientific discipline, be it Physics, Statistics, Chemistry, Forensic Science, Chemistry, Engineering, Biosciences, etc. An unknown to be determined occurs implicitly in the formula. To cite a few examples:
When a detective had to find time of death (t) of a person in certain crime, he came across the equation
whose root gives the time of death. Similarly, in Electrical Engineering problem, one needs to determine the value of Voltage V, satisfying the equation
Introduction
So, in this lecture, we would like to focus on the Root-Finding Problem. As the name indicates, in Root-Finding Problem , we find a root of the equation f(x) = 0, where f(x) is a function of a single variable x. Thus, the problem may be stated as follows:
The Root Finding Problem:Given a function f(x), find x = c such that f(c ) = 0 |
The number c is called a root of f(x) = 0 or a zero of the function f(x). The function f(x) may be algebraic function or transcendental function.
Figure 1
The simplest case to consider is that of polynomials. Polynomials are examples of algebraic equations. In your school days, you worked with quadratic equation, that is, f (x) = a x2+ b x + c . Each of us knows, that the roots of this quadratic equation are given by
This is an easy case, where it is possible to get roots directly from an analytical formula. Besides, the roots of polynomials of degree 3 and 4 can also be found (using the Cardano formula for third-degree equations and the Ferrari formula for degree 4), but application of these are quite complex. Moreover, if f (x) is a polynomial of degree higher than 4, analytical method giving solution in terms of formulas no longer exists. Moreover, when f (x) is any algebraic or transcendental equation, analytic methods for obtaining the desired roots no longer are available. Instead, we have to take recourse to numerical methods, which are approximation methods. In fact, in many cases, approximation methods may quickly provide a solution up to desired accuracy as compared to formulas giving exact roots.
Here, we shall assume that the equation f(x) = 0 has solutions. So, we shall not question, whether f(x) = 0 has a root or not? So assuming solution exists, our efforts would be towards looking for appropriate approximation methods to be applied to determine approximate value of a root. We would not be able to find all the solutions of a given equation in one go as in case of analytical methods, rather, we will find approximate value of a root , correct to desired accuracy, which can be very well accepted as a solution of the equation.
Where are the roots?
Assuming a root exists, we would be interested to determine the interval, within which the root lies. First attempt could be to try to plot the function, to look for the intersection of the graph of y = f(x) with the x-axis, that would give a fairly good idea of location of the root.
Figure 2
The only thing is, it may not be always simple to draw the graph of the function.
Instead, it is sometimes easier is to evaluate function at regular interval points. We need to find a point a for which f (a) < 0, and a point b, for which f (b) > 0 or vice – versa. The application of intermediate value theorem and continuity of f(x) ensures that a root of f(x) = 0 lies within the interval [a,b].
All the numerical methods, we are going to learn are iterative methods. These methods begin with an initial guess or initial guesses of the root and slowly reach the root. A process called method is applied repetitively till the satisfactory answer is obtained. This can be explained by the following diagram :
Nature of Iterative Method
Figure 3
If initial inputs to the process are chosen properly, then the sequence of approximations obtained through well defined iterative processes in majority of cases converges to a solution of the equation.
Iterative Methods used to solve f(x) = 0 can be classified into two types:
(i) Closed or bracketing methods. This simply means we choose two points between which we believe the root lies.
(ii) Open method, where no such constraint is there.
Let us begin with the simplest of closed iterative methods to find roots of an equation, known as
Bisection Method:
Principle on which Bisection method is based is as follows:
If f (x) is continuous in a closed interval [a, b] and f (a), f (b) are of opposite signs, then the equation f (x)= 0 will have at least one real root between a and b. This is based on intermediate value theorem.
Let us understand it graphically in lay person terms:
Since f (x) is continuous on [a, b], the graph of y = f (x) for a £ x £ b shall have no break. That is, it can be drawn from (a, f (a)) to (b, f (b)) without any jump.
Figure 4
No intermediate values can be skipped. Values of f (x) completely occupy the range from f (a) to f (b).
As f (a) and f (b) are of opposite sign, function has to be zero for some a £ x ≤ b. Moreover if f (a). f (b) < 0 (of opposite signs) then one end of the graph is below X axis and other end is above X axis. f(x) being continuous, the graph of y = f(x) has to cross X axis in going from one side of X axis to the other. In lay person terms : It is like, if the stream of river is flowing outside your home and you are permitted to walk only by taking infinite small continuous steps, that is you are not permitted to lift your leg and take jump, you cannot get inside your home from outside without making your feet wet and vice versa.
Without loss of generality, let f (a) < 0. Thus f (b) > 0.
Explanation of the Method
Bisection method begins with two initial guesses a and b, such that f(a).f(b) < 0. This, as explained earlier ensures that at least one root lies between a and b. The interval [a,b] is divided into exactly two equal parts [a,c] and [c,b]. Clearly c = (a+b) /2. This can be visualized from the following graph. c is our estimate of the root. Now, f ( c ) is evaluated and c will take the role of a or b, according to value of f ( c ), to ensure that root always lies within a and b.
Again the process is repeated. We continue the process, till our interval becomes sufficiently small.
Estimate of the root is given by c.
Bisection Method Algorithm: | Let f (x) = 0 be a given equation | |
| Step1 | Determine real nos. a and b such that f (a). f (b) < 0 |
| Step2 | Set k = 1, c0 = a |
| Step3 | Compute c = a + b
k 2 |
| Step4 | Calculate f (ck). |
| Step5 | If f (ck) = 0. Solution is obtained, otherwise: |
| Step6 | If f(a) . f(ck) > 0, set a= ck Else Set b = ck |
| Step7
* |
If | ck – ck-1 | £ e (tolerance) then ck is the required root and Stop. Else set k = k+1 and
go to step 3. |
* There are other stopping criterions also, which we intend to learn in the next modules.
Example 1: 3 x – cos x -1 = 0
f(0) = -2, f(1) = 1.4597, so root lies between 0 and 1, take a = 0, b=1, c0 = a = 0
| k | a | f(a) | b | f(b) | ck | f (ck) |
| 1 | 0 | -2 | 1 | 1.4597 | 0.5 | -0.3776 |
| 2 | 0.5 | -0.3776 | 1 | 1.4597 | 0.75 | 0.51831 |
| 3 | 0.5 | -0.3776 | 0.75 | 0.51831 | 0.625 | 0.06404 |
| 4 | 0.5 | -0.3776 | 0.625 | 0.06404 | 0.5625 | -0.1584 |
| 5 | 0.5625 | -0.1584 | 0.625 | 0.06404 | 0.59375 | -0.0476 |
| 6 | 0.59375 | -0.0476 | 0.625 | 0.06404 | 0.60938 | 0.00814 |
| 7 | 0.59375 | -0.0476 | 0.60938 | 0.00814 | 0.60157 | -0.0197 |
| 8 | 0.60157 | -0.0197 | 0.60938 | 0.00814 | 0.60548 | -0.0058 |
| 9 | 0.60548 | -0.0058 | 0.60938 | 0.00814 | 0.60743 | 0.00117 |
| 10 | 0.60548 | -0.0058 | 0.60743 | 0.00117 | 0.60646 | -0.0023 |
| 11 | 0.60646 | -0.0023 | 0.60743 | 0.00117 | 0.60695 | -0.0005 |
| 12 | 0.60695 | -0.0005 | 0.60743 | 0.00117 | 0.60719 | 0.00032 |
| 13 | 0.60695 | -0.0005 | 0.60719 | 0.00032 | 0.60707 | -0.0001 |
| 14 | 0.60707 | -0.0001 | 0.60719 | 0.00032 | 0.60713 | 0.0001 |
Estimated root of 3x – cos x -1 is 0.60713.
Example 2: x3 + x – 1 = 0
f(0) = -1, f(1) = 1, so root lies between 0 and 1, take a = 0, b=1, c0 = a = 0
| k | a | f(a) | b | f(b) | ck | f (ck) |
| 1 | 0 | -1 | 1 | 1 | 0.5 | -0.375 |
| 2 | 0.5 | -0.375 | 1 | 0.17188 | 0.75 | 0.1719 |
| 3 | 0.5 | -0.375 | 0.75 | 0.17188 | 0.625 | -0.1309 |
| 4 | 0.625 | -0.1309 | 0.75 | 0.01245 | 0.6875 | 0.0125 |
| 5 | 0.625 | -0.1309 | 0.6875 | 0.01245 | 0.65625 | -0.0611 |
| 6 | 0.65625 | -0.0611 | 0.6875 | 0.01245 | 0.67188 | -0.0248 |
| 7 | 0.67188 | -0.0248 | 0.6875 | 0.01245 | 0.67969 | -0.0063 |
| 8 | 0.67969 | -0.0063 | 0.6875 | 0.01245 | 0.6836 | 0.0031 |
| 9 | 0.67969 | -0.0063 | 0.6836 | 0.00305 | 0.68165 | -0.0016 |
| 10 | 0.68165 | -0.0016 | 0.6836 | 0.00305 | 0.68263 | 0.0007 |
| 11 | 0.68165 | -0.0016 | 0.68263 | 0.00072 | 0.68214 | -0.0005 |
| 12 | 0.68214 | -0.0005 | 0.68263 | 0.00072 | 0.68239 | 0.0001 |
| 13 | 0.68214 | -0.0005 | 0.68239 | 0.00015 | 0.68227 | -0.0001 |
| 14 | 0.68227 | -0.0001 | 0.68239 | 0.00015 | 0.68233 | 0 |
Estimated root of
x3 + x -1 = 0 is 0.68233.
Observations:
In each of the succeeding iterations, the size of the bracketing interval becomes half of the previous one. Thus, it is always possible to predict the number of iterations required to achieve desired accuracy. So if e is the tolerance limit then the approximation number of the iterations needed to be performed is given by the formula
Advantages:
(1) It is very simple.
(2) Once initial a, b are known, number of iterations needed to be performed to achieve desired accuracy can be predetermined.
(3) Reliable
(4) Guarantees Convergence.
(5) Function needs to be only continuous.
(6) Only one function evaluation per iteration.
(7) Calculation for making guess of root for the next iteration is very easy. Simply
c = a + b
2
Drawbacks:
(1) Not self starting. To begin with, requires two initial guesses at which function must of opposite sign. Thus, one has to evaluate function at subinterval points to get such a and b.
(2) Slowest method
(3) It does not take into account the nature of function to make next guess of the root.
| you can view video on Root Finding Problem: (Bisection Method) | |
Suggested Reading: