{"id":39,"date":"2018-07-11T10:23:30","date_gmt":"2018-07-11T10:23:30","guid":{"rendered":"http:\/\/itp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=39"},"modified":"2019-05-15T08:37:46","modified_gmt":"2019-05-15T08:37:46","slug":"root-finding-problem-bisection-method","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/chapter\/root-finding-problem-bisection-method\/","title":{"rendered":"Root Finding Problem: (Bisection Method)"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\nW<\/strong>hy study Root-Finding Problem?<\/strong>\r\n\r\n \r\n

Root finding problem occupies important position amidst different \u00a0scientific \u00a0computing 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:<\/p>\r\n \r\n\r\nWhen a detective had to find time of death (t) of a person in certain crime, he came across the equation\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\nwhose root gives the time of death. Similarly, in Electrical Engineering problem, one needs to determine the value of Voltage V, satisfying the equation\r\n\r\n \r\n\r\n\"\"\r\n\r\nIntroduction\u00a0<\/strong>\r\n\r\n \r\n

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:<\/p>\r\n\r\n<\/div>\r\n\r\n\r\n\r\n
\r\n
The Root Finding Problem:<\/strong><\/h5>\r\nGiven a function f(x), find x = c such that f(c ) = 0<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n
\r\n\r\n \r\n

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.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n

Fi<\/strong>gure 1<\/strong><\/p>\r\n \r\n

The simplest case to consider is that\u00a0 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<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n<\/div>\r\n \r\n

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.<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n

Here, we shall assume that the equation f(x) =\u00a0 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 \u00a0of a root , correct to desired accuracy, which can be very well accepted as a solution of the equation.<\/p>\r\n\r\n<\/div>\r\n \r\n\r\nWhere are the roots?\u00a0<\/span><\/strong>\r\n\r\n \r\n

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.<\/span><\/p>\r\n\r\n

<\/div>\r\n
\r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n

Fi<\/strong>gure 2<\/strong><\/p>\r\n \r\n\r\nThe only thing is, it may not be always simple to draw the graph of the function.\r\n\r\n \r\n

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].<\/p>\r\n \r\n

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 :<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Nature of Iterative Method<\/strong><\/p>\r\n \r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

Fi<\/strong>gure 3<\/strong><\/p>\r\n \r\n

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.<\/p>\r\n\r\n<\/div>\r\n \r\n\r\nIterative Methods used to solve f(x) = 0 can be classified into two types:<\/span>\r\n

\r\n\r\n \r\n\r\n(i) Closed or bracketing methods. This simply means we choose two points between which we believe the root lies.\r\n\r\n(ii) Open method, where no such constraint is there.\r\n\r\n \r\n\r\nLet us begin with the simplest of closed iterative methods to find roots of an equation, known as\r\n\r\n \r\n\r\nB<\/strong>i<\/strong>section Method:<\/strong>\r\n\r\n \r\n\r\nPrinciple <\/strong>on which Bisection method is based is as follows:\r\n\r\n \r\n

If \u00a0<\/span>f <\/em>(<\/span>x<\/em>)\u00a0<\/span>is continuous in a closed interval [a, b] and <\/span>f <\/em>(<\/span>a<\/em>),\u00a0<\/span>f <\/em>(<\/span>b<\/em>) are of opposite signs, then the\u00a0<\/span>equation\u00a0<\/span>f <\/em>(<\/span>x<\/em>)= \u00a00 \u00a0will \u00a0have \u00a0at \u00a0least \u00a0one \u00a0real \u00a0root \u00a0between \u00a0a \u00a0and \u00a0b.\u00a0\u00a0 This \u00a0is \u00a0based \u00a0on\u00a0<\/span>intermediate value theorem.\u00a0<\/span><\/p>\r\n \r\n

Let us understand it graphically in lay person terms:\u00a0<\/span><\/p>\r\n \r\n

Since\u00a0<\/span>f <\/em>(<\/span>x<\/em>) is continuous on [a, b], the graph of <\/span>y <\/em>=\u00a0<\/span>f <\/em>(<\/span>x<\/em>) for a \u00a3 x \u00a3 b shall have no break. That\u00a0<\/span>is, it can be drawn from (a, <\/span>f <\/em>(<\/span>a<\/em>)) to (b, <\/span>f <\/em>(<\/span>b<\/em>)) without any jump.<\/span><\/p>\r\n\r\n<\/div>\r\n

<\/div>\r\n
\r\n\r\n\"\"\r\n

Fi<\/strong>gure 4<\/strong><\/p>\r\n\r\n<\/div>\r\n \r\n\r\nNo intermediate values can be skipped. Values of f <\/em>(x<\/em>) completely occupy the range from\u00a0f <\/em>(a<\/em>) to\u00a0<\/span>f <\/em>(<\/span>b<\/em>).<\/span>\r\n

\r\n\r\n \r\n

As \u00a0<\/span>f <\/em>(<\/span>a<\/em>)\u00a0<\/span>and\u00a0<\/span>f <\/em>(<\/span>b<\/em>) are of opposite sign, function has to be zero for some a \u00a3 x \u2264 b. \u00a0Moreover\u00a0<\/span>if <\/span>f <\/em>(<\/span>a<\/em>). <\/span>f <\/em>(<\/span>b<\/em>) < 0 (of opposite signs) then one end of the graph is below X axis and other end is above X axis. \u00a0<\/span>f<\/em>(x) being continuous, the graph of y = <\/span>f<\/em>(x) has to cross X axis in going from one side\u00a0<\/span>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.<\/span><\/p>\r\n\r\n<\/div>\r\n \r\n\r\nWithout loss of generality, let\u00a0<\/span>f <\/em>(<\/span>a<\/em>) < 0. Thus\u00a0<\/span>f <\/em>(<\/span>b<\/em>) > 0.<\/span>\r\n\r\n\"\"\r\n

Fi<\/strong>gure 5<\/strong><\/div>\r\n \r\n\r\nExplanation of the Method<\/strong>\r\n
\r\n\r\n \r\n

Bisection method begins with two initial guesses a\u00a0 and b, such that f(a).f(b) <\/em>< 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 ) \u00a0is evaluated \u00a0and \u00a0c will take the role of a or b, according to value of f ( c ), to ensure that root always lies within a and b.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"Again the process is repeated. We continue the process, till our interval becomes sufficiently small.<\/span>\r\n\r\n<\/div>\r\n
<\/div>\r\n
<\/div>\r\n\"\"Estimate of the root is given by c.<\/span>\r\n
\r\n\r\n\"\"Bisection Method Algorithm:\u00a0<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
<\/td>\r\nLet f (x) = 0 be a given equation<\/td>\r\n<\/tr>\r\n
Step1<\/td>\r\nDetermine real nos. a and b such that f (a). f (b) < 0<\/td>\r\n<\/tr>\r\n
Step2<\/td>\r\nSet k = 1, c0\u00a0\u00a0 =\u00a0 a<\/td>\r\n<\/tr>\r\n
Step3<\/td>\r\nCompute c \u00a0= \u00a0a <\/em>+ b<\/em>\r\n\r\nk\r\n\r\n2<\/td>\r\n<\/tr>\r\n
Step4<\/td>\r\nCalculate f (ck).<\/td>\r\n<\/tr>\r\n
Step5<\/td>\r\nIf f (ck) = 0. Solution is obtained, otherwise:<\/td>\r\n<\/tr>\r\n
Step6<\/td>\r\nIf f(a) . f(ck) > 0,\u00a0\u00a0 set a= ck\u00a0\u00a0 \u00a0Else Set b = ck<\/td>\r\n<\/tr>\r\n
Step7\r\n\r\n*<\/td>\r\nIf | ck - ck-1 | \u00a3 \u00a0e (tolerance) then ck is the required root and Stop. Else set k = k+1 and\r\n\r\ngo to step 3.<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\n* There are other stopping criterions also, which we intend to learn in the next modules.\r\n\r\n \r\n\r\nExample 1: 3 x \u2013 cos x -1 = 0\r\n\r\nf(0) = -2, f(1) = 1.4597, so root lies between 0 and 1, take a = 0, b=1, c0 = a = 0\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
k<\/strong><\/td>\r\na<\/strong><\/td>\r\nf<\/strong>(a)<\/strong><\/td>\r\nb<\/strong><\/td>\r\nf<\/strong>(b)<\/strong><\/td>\r\nc<\/strong>k<\/strong><\/td>\r\nf (c<\/strong>k<\/strong>)<\/strong><\/td>\r\n<\/tr>\r\n
1<\/td>\r\n0<\/td>\r\n-2<\/td>\r\n1<\/td>\r\n1.4597<\/td>\r\n0.5<\/td>\r\n-0.3776<\/td>\r\n<\/tr>\r\n
2<\/td>\r\n0.5<\/td>\r\n-0.3776<\/td>\r\n1<\/td>\r\n1.4597<\/td>\r\n0.75<\/td>\r\n0.51831<\/td>\r\n<\/tr>\r\n
3<\/td>\r\n0.5<\/td>\r\n-0.3776<\/td>\r\n0.75<\/td>\r\n0.51831<\/td>\r\n0.625<\/td>\r\n0.06404<\/td>\r\n<\/tr>\r\n
4<\/td>\r\n0.5<\/td>\r\n-0.3776<\/td>\r\n0.625<\/td>\r\n0.06404<\/td>\r\n0.5625<\/td>\r\n-0.1584<\/td>\r\n<\/tr>\r\n
5<\/td>\r\n0.5625<\/td>\r\n-0.1584<\/td>\r\n0.625<\/td>\r\n0.06404<\/td>\r\n0.59375<\/td>\r\n-0.0476<\/td>\r\n<\/tr>\r\n
6<\/td>\r\n0.59375<\/td>\r\n-0.0476<\/td>\r\n0.625<\/td>\r\n0.06404<\/td>\r\n0.60938<\/td>\r\n0.00814<\/td>\r\n<\/tr>\r\n
7<\/td>\r\n0.59375<\/td>\r\n-0.0476<\/td>\r\n0.60938<\/td>\r\n0.00814<\/td>\r\n0.60157<\/td>\r\n-0.0197<\/td>\r\n<\/tr>\r\n
8<\/td>\r\n0.60157<\/td>\r\n-0.0197<\/td>\r\n0.60938<\/td>\r\n0.00814<\/td>\r\n0.60548<\/td>\r\n-0.0058<\/td>\r\n<\/tr>\r\n
9<\/td>\r\n0.60548<\/td>\r\n-0.0058<\/td>\r\n0.60938<\/td>\r\n0.00814<\/td>\r\n0.60743<\/td>\r\n0.00117<\/td>\r\n<\/tr>\r\n
10<\/td>\r\n0.60548<\/td>\r\n-0.0058<\/td>\r\n0.60743<\/td>\r\n0.00117<\/td>\r\n0.60646<\/td>\r\n-0.0023<\/td>\r\n<\/tr>\r\n
11<\/td>\r\n0.60646<\/td>\r\n-0.0023<\/td>\r\n0.60743<\/td>\r\n0.00117<\/td>\r\n0.60695<\/td>\r\n-0.0005<\/td>\r\n<\/tr>\r\n
12<\/td>\r\n0.60695<\/td>\r\n-0.0005<\/td>\r\n0.60743<\/td>\r\n0.00117<\/td>\r\n0.60719<\/td>\r\n0.00032<\/td>\r\n<\/tr>\r\n
13<\/td>\r\n0.60695<\/td>\r\n-0.0005<\/td>\r\n0.60719<\/td>\r\n0.00032<\/td>\r\n0.60707<\/td>\r\n-0.0001<\/td>\r\n<\/tr>\r\n
14<\/td>\r\n0.60707<\/td>\r\n-0.0001<\/td>\r\n0.60719<\/td>\r\n0.00032<\/td>\r\n0.60713<\/td>\r\n0.0001<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nEstimated root of 3x <\/em>- cos x <\/em>-1 is 0.60713.\r\n\r\n \r\n\r\nExample 2: x3 + x \u2013 1 = 0\r\n\r\nf(0) = -1, f(1) = 1, so root lies between 0 and 1, take a = 0, b=1, c0 = a = 0\r\n\r\n \r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
k<\/strong><\/td>\r\na<\/strong><\/td>\r\nf<\/strong>(a)<\/strong><\/td>\r\nb<\/strong><\/td>\r\nf<\/strong>(b)<\/strong><\/td>\r\nc<\/strong>k<\/strong><\/td>\r\nf (c<\/strong>k<\/strong>)<\/strong><\/td>\r\n<\/tr>\r\n
1<\/td>\r\n0<\/td>\r\n-1<\/td>\r\n1<\/td>\r\n1<\/td>\r\n0.5<\/td>\r\n-0.375<\/td>\r\n<\/tr>\r\n
2<\/td>\r\n0.5<\/td>\r\n-0.375<\/td>\r\n1<\/td>\r\n0.17188<\/td>\r\n0.75<\/td>\r\n0.1719<\/td>\r\n<\/tr>\r\n
3<\/td>\r\n0.5<\/td>\r\n-0.375<\/td>\r\n0.75<\/td>\r\n0.17188<\/td>\r\n0.625<\/td>\r\n-0.1309<\/td>\r\n<\/tr>\r\n
4<\/td>\r\n0.625<\/td>\r\n-0.1309<\/td>\r\n0.75<\/td>\r\n0.01245<\/td>\r\n0.6875<\/td>\r\n0.0125<\/td>\r\n<\/tr>\r\n
5<\/td>\r\n0.625<\/td>\r\n-0.1309<\/td>\r\n0.6875<\/td>\r\n0.01245<\/td>\r\n0.65625<\/td>\r\n-0.0611<\/td>\r\n<\/tr>\r\n
6<\/td>\r\n0.65625<\/td>\r\n-0.0611<\/td>\r\n0.6875<\/td>\r\n0.01245<\/td>\r\n0.67188<\/td>\r\n-0.0248<\/td>\r\n<\/tr>\r\n
7<\/td>\r\n0.67188<\/td>\r\n-0.0248<\/td>\r\n0.6875<\/td>\r\n0.01245<\/td>\r\n0.67969<\/td>\r\n-0.0063<\/td>\r\n<\/tr>\r\n
8<\/td>\r\n0.67969<\/td>\r\n-0.0063<\/td>\r\n0.6875<\/td>\r\n0.01245<\/td>\r\n0.6836<\/td>\r\n0.0031<\/td>\r\n<\/tr>\r\n
9<\/td>\r\n0.67969<\/td>\r\n-0.0063<\/td>\r\n0.6836<\/td>\r\n0.00305<\/td>\r\n0.68165<\/td>\r\n-0.0016<\/td>\r\n<\/tr>\r\n
10<\/td>\r\n0.68165<\/td>\r\n-0.0016<\/td>\r\n0.6836<\/td>\r\n0.00305<\/td>\r\n0.68263<\/td>\r\n0.0007<\/td>\r\n<\/tr>\r\n
11<\/td>\r\n0.68165<\/td>\r\n-0.0016<\/td>\r\n0.68263<\/td>\r\n0.00072<\/td>\r\n0.68214<\/td>\r\n-0.0005<\/td>\r\n<\/tr>\r\n
12<\/td>\r\n0.68214<\/td>\r\n-0.0005<\/td>\r\n0.68263<\/td>\r\n0.00072<\/td>\r\n0.68239<\/td>\r\n0.0001<\/td>\r\n<\/tr>\r\n
13<\/td>\r\n0.68214<\/td>\r\n-0.0005<\/td>\r\n0.68239<\/td>\r\n0.00015<\/td>\r\n0.68227<\/td>\r\n-0.0001<\/td>\r\n<\/tr>\r\n
14<\/td>\r\n0.68227<\/td>\r\n-0.0001<\/td>\r\n0.68239<\/td>\r\n0.00015<\/td>\r\n0.68233<\/td>\r\n0<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nEstimated root of<\/span>\r\n\r\nx<\/em>3 + <\/span>x <\/em>-1 = 0 is 0.68233.<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\nObservations:\u00a0<\/strong>\r\n\r\n \r\n

In each of the succeeding iterations, the size of the bracketing interval becomes half of the previous one. Thus, it is always possible to\u00a0 predict the number of iterations required\u00a0 to\u00a0 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<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\nAdvantages:\u00a0<\/strong>\r\n\r\n \r\n\r\n(1)\u00a0 It is very simple.\r\n\r\n(2)\u00a0 Once initial a, b are known, number of iterations needed to be performed to achieve desired accuracy can be predetermined.\r\n\r\n(3)\u00a0 Reliable\r\n\r\n(4)\u00a0 Guarantees Convergence.\r\n\r\n(5)\u00a0 Function needs to be only continuous.\r\n\r\n(6)\u00a0 Only one function evaluation per iteration.\r\n\r\n(7)\u00a0 Calculation for making guess of root for the next iteration is very easy. Simply<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\nc <\/em>= a + b<\/span>\r\n

2<\/p>\r\n\r\n<\/div>\r\n \r\n\r\nDrawbacks<\/strong>:\r\n\r\n \r\n\r\n(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.\r\n\r\n(2) Slowest method\r\n\r\n(3) It does not take into account the nature of function to make next guess of the root.\r\n\r\n\r\n\r\n\r\n
you can view video on Root Finding Problem: (Bisection Method)<\/strong><\/td>\r\n\"\"<\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nSuggested Reading:<\/strong>\r\n
<\/div>\r\n
1. Numerical Methods for Engineers by Steven C Chapra & Raymond P Canale, Fifth Edition, Tata McGraw Hill Publication, Special Indian Edition.<\/div>\r\n
2. A Friendly Introduction to Numerical Analysis by Brian Bradie, Pearson Education.<\/div>\r\n
3. Numerical Mathematics and Computing by Ward Cheney & David Kincaid, fifth Edition, Cengage Learning.<\/div>\r\n
4. Computer Oriented Numerical Methods by Dr. N Datta, Vikas Publication.<\/div>\r\n
5. Numerical Methods with Programs in C by T Veerarajan & T Ramachandran, Second Edition, Tata McGraw<\/div>\r\n
Hill Publication.<\/div>\r\n
6. Numerical Methods by V. Rajaraman, Third Edition, Prentice - Hall India Pvt. Ltd.<\/div>\r\n
7. Numerical Methods with C++ Programming by RM Somasundaram & RM Chandrasekaran, Prentice-Hall India Pvt. Ltd.<\/div>\r\n
8. Applied Numerical Analysis by C F Gerald & P O Wheatley, Seventh Edition, Pearson Education Asia, New Delhi.<\/div>\r\n
9. Numerical Methods by Dr. V. N. Vedamurthy & Dr. N.Ch. S.N. Iyengar, Vikas Publication.<\/div>\r\n
10. Numerical Analysis by Richard L. Burden, J. Douglas Faires, Cengage Publishcation.<\/div>\r\n
11. Numerical Methods with programs in BASIC, FORTRAN, Pascal and C++ by S. Balachandra Rao & C. K. Shantha, Revised Edition, Universities Press.<\/div>\r\n
12. A Textbook of Computer Based Numerical and Statistical Techniques by A. K. Jaiswal & Anju Khandelwal, New Age International (P) Ltd, Publishers.<\/div>\r\n
13. https:\/\/ece.uwaterloo.ca\/~dwharder\/...\/bisection\/examples.html<\/div>\r\n
14. oregonstate.edu\/instruct\/mth251\/cq\/Stage4\/Lesson\/bisection.htm<\/div>\r\n ","rendered":"
\"epgp<\/a>
\n<\/span><\/div>\n
\n

 <\/p>\n

W<\/strong>hy study Root-Finding Problem?<\/strong><\/p>\n

 <\/p>\n

Root finding problem occupies important position amidst different \u00a0scientific \u00a0computing 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:<\/p>\n

 <\/p>\n

When a detective had to find time of death (t) of a person in certain crime, he came across the equation<\/p>\n<\/div>\n

\n

\"\"<\/p>\n<\/div>\n

\n

 <\/p>\n

whose root gives the time of death. Similarly, in Electrical Engineering problem, one needs to determine the value of Voltage V, satisfying the equation<\/p>\n

 <\/p>\n

\"\"<\/p>\n

Introduction\u00a0<\/strong><\/p>\n

 <\/p>\n

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:<\/p>\n<\/div>\n\n\n\n
\n
The Root Finding Problem:<\/strong><\/h5>\n

Given a function f(x), find x = c such that f(c ) = 0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\n

 <\/p>\n

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.<\/p>\n<\/div>\n

\n

\"\"<\/p>\n

 <\/p>\n

Fi<\/strong>gure 1<\/strong><\/p>\n

 <\/p>\n

The simplest case to consider is that\u00a0 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<\/p>\n<\/div>\n

\n

\"\"<\/p>\n<\/div>\n

 <\/p>\n

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.<\/span><\/p>\n

\n

 <\/p>\n

Here, we shall assume that the equation f(x) =\u00a0 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 \u00a0of a root , correct to desired accuracy, which can be very well accepted as a solution of the equation.<\/p>\n<\/div>\n

 <\/p>\n

Where are the roots?\u00a0<\/span><\/strong><\/p>\n

 <\/p>\n

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.<\/span><\/p>\n

<\/div>\n
\n

\"\"<\/p>\n<\/div>\n

\n

 <\/p>\n

Fi<\/strong>gure 2<\/strong><\/p>\n

 <\/p>\n

The only thing is, it may not be always simple to draw the graph of the function.<\/p>\n

 <\/p>\n

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].<\/p>\n

 <\/p>\n

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 :<\/p>\n<\/div>\n

\n

 <\/p>\n

Nature of Iterative Method<\/strong><\/p>\n

 <\/p>\n<\/div>\n

\n

\"\"<\/p>\n

 <\/p>\n

 <\/p>\n

Fi<\/strong>gure 3<\/strong><\/p>\n

 <\/p>\n

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.<\/p>\n<\/div>\n

 <\/p>\n

Iterative Methods used to solve f(x) = 0 can be classified into two types:<\/span><\/p>\n

\n

 <\/p>\n

(i) Closed or bracketing methods. This simply means we choose two points between which we believe the root lies.<\/p>\n

(ii) Open method, where no such constraint is there.<\/p>\n

 <\/p>\n

Let us begin with the simplest of closed iterative methods to find roots of an equation, known as<\/p>\n

 <\/p>\n

B<\/strong>i<\/strong>section Method:<\/strong><\/p>\n

 <\/p>\n

Principle <\/strong>on which Bisection method is based is as follows:<\/p>\n

 <\/p>\n

If \u00a0<\/span>f <\/em>(<\/span>x<\/em>)\u00a0<\/span>is continuous in a closed interval [a, b] and <\/span>f <\/em>(<\/span>a<\/em>),\u00a0<\/span>f <\/em>(<\/span>b<\/em>) are of opposite signs, then the\u00a0<\/span>equation\u00a0<\/span>f <\/em>(<\/span>x<\/em>)= \u00a00 \u00a0will \u00a0have \u00a0at \u00a0least \u00a0one \u00a0real \u00a0root \u00a0between \u00a0a \u00a0and \u00a0b.\u00a0\u00a0 This \u00a0is \u00a0based \u00a0on\u00a0<\/span>intermediate value theorem.\u00a0<\/span><\/p>\n

 <\/p>\n

Let us understand it graphically in lay person terms:\u00a0<\/span><\/p>\n

 <\/p>\n

Since\u00a0<\/span>f <\/em>(<\/span>x<\/em>) is continuous on [a, b], the graph of <\/span>y <\/em>=\u00a0<\/span>f <\/em>(<\/span>x<\/em>) for a \u00a3 x \u00a3 b shall have no break. That\u00a0<\/span>is, it can be drawn from (a, <\/span>f <\/em>(<\/span>a<\/em>)) to (b, <\/span>f <\/em>(<\/span>b<\/em>)) without any jump.<\/span><\/p>\n<\/div>\n

<\/div>\n
\n

\"\"<\/p>\n

Fi<\/strong>gure 4<\/strong><\/p>\n<\/div>\n

 <\/p>\n

No intermediate values can be skipped. Values of f <\/em>(x<\/em>) completely occupy the range from\u00a0f <\/em>(a<\/em>) to\u00a0<\/span>f <\/em>(<\/span>b<\/em>).<\/span><\/p>\n

\n

 <\/p>\n

As \u00a0<\/span>f <\/em>(<\/span>a<\/em>)\u00a0<\/span>and\u00a0<\/span>f <\/em>(<\/span>b<\/em>) are of opposite sign, function has to be zero for some a \u00a3 x \u2264 b. \u00a0Moreover\u00a0<\/span>if <\/span>f <\/em>(<\/span>a<\/em>). <\/span>f <\/em>(<\/span>b<\/em>) < 0 (of opposite signs) then one end of the graph is below X axis and other end is above X axis. \u00a0<\/span>f<\/em>(x) being continuous, the graph of y = <\/span>f<\/em>(x) has to cross X axis in going from one side\u00a0<\/span>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.<\/span><\/p>\n<\/div>\n

 <\/p>\n

Without loss of generality, let\u00a0<\/span>f <\/em>(<\/span>a<\/em>) < 0. Thus\u00a0<\/span>f <\/em>(<\/span>b<\/em>) > 0.<\/span><\/p>\n

\"\"<\/p>\n

Fi<\/strong>gure 5<\/strong><\/div>\n

 <\/p>\n

Explanation of the Method<\/strong><\/p>\n

\n

 <\/p>\n

Bisection method begins with two initial guesses a\u00a0 and b, such that f(a).f(b) <\/em>< 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 ) \u00a0is evaluated \u00a0and \u00a0c will take the role of a or b, according to value of f ( c ), to ensure that root always lies within a and b.<\/p>\n<\/div>\n

\n

\"\"Again the process is repeated. We continue the process, till our interval becomes sufficiently small.<\/span><\/p>\n<\/div>\n

<\/div>\n
<\/div>\n

\"\"Estimate of the root is given by c.<\/span><\/p>\n

\n

\"\"Bisection Method Algorithm:\u00a0<\/span><\/p>\n<\/div>\n

\n\n\n\n\n\n\n\n\n\n\n
<\/td>\nLet f (x) = 0 be a given equation<\/td>\n<\/tr>\n
Step1<\/td>\nDetermine real nos. a and b such that f (a). f (b) < 0<\/td>\n<\/tr>\n
Step2<\/td>\nSet k = 1, c0\u00a0\u00a0 =\u00a0 a<\/td>\n<\/tr>\n
Step3<\/td>\nCompute c \u00a0= \u00a0a <\/em>+ b<\/em><\/p>\n

k<\/p>\n

2<\/td>\n<\/tr>\n

Step4<\/td>\nCalculate f (ck).<\/td>\n<\/tr>\n
Step5<\/td>\nIf f (ck) = 0. Solution is obtained, otherwise:<\/td>\n<\/tr>\n
Step6<\/td>\nIf f(a) . f(ck) > 0,\u00a0\u00a0 set a= ck\u00a0\u00a0 \u00a0Else Set b = ck<\/td>\n<\/tr>\n
Step7<\/p>\n

*<\/td>\n

If | ck – ck-1 | \u00a3 \u00a0e (tolerance) then ck is the required root and Stop. Else set k = k+1 and<\/p>\n

go to step 3.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

* There are other stopping criterions also, which we intend to learn in the next modules.<\/p>\n

 <\/p>\n

Example 1: 3 x \u2013 cos x -1 = 0<\/p>\n

f(0) = -2, f(1) = 1.4597, so root lies between 0 and 1, take a = 0, b=1, c0 = a = 0<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
k<\/strong><\/td>\na<\/strong><\/td>\nf<\/strong>(a)<\/strong><\/td>\nb<\/strong><\/td>\nf<\/strong>(b)<\/strong><\/td>\nc<\/strong>k<\/strong><\/td>\nf (c<\/strong>k<\/strong>)<\/strong><\/td>\n<\/tr>\n
1<\/td>\n0<\/td>\n-2<\/td>\n1<\/td>\n1.4597<\/td>\n0.5<\/td>\n-0.3776<\/td>\n<\/tr>\n
2<\/td>\n0.5<\/td>\n-0.3776<\/td>\n1<\/td>\n1.4597<\/td>\n0.75<\/td>\n0.51831<\/td>\n<\/tr>\n
3<\/td>\n0.5<\/td>\n-0.3776<\/td>\n0.75<\/td>\n0.51831<\/td>\n0.625<\/td>\n0.06404<\/td>\n<\/tr>\n
4<\/td>\n0.5<\/td>\n-0.3776<\/td>\n0.625<\/td>\n0.06404<\/td>\n0.5625<\/td>\n-0.1584<\/td>\n<\/tr>\n
5<\/td>\n0.5625<\/td>\n-0.1584<\/td>\n0.625<\/td>\n0.06404<\/td>\n0.59375<\/td>\n-0.0476<\/td>\n<\/tr>\n
6<\/td>\n0.59375<\/td>\n-0.0476<\/td>\n0.625<\/td>\n0.06404<\/td>\n0.60938<\/td>\n0.00814<\/td>\n<\/tr>\n
7<\/td>\n0.59375<\/td>\n-0.0476<\/td>\n0.60938<\/td>\n0.00814<\/td>\n0.60157<\/td>\n-0.0197<\/td>\n<\/tr>\n
8<\/td>\n0.60157<\/td>\n-0.0197<\/td>\n0.60938<\/td>\n0.00814<\/td>\n0.60548<\/td>\n-0.0058<\/td>\n<\/tr>\n
9<\/td>\n0.60548<\/td>\n-0.0058<\/td>\n0.60938<\/td>\n0.00814<\/td>\n0.60743<\/td>\n0.00117<\/td>\n<\/tr>\n
10<\/td>\n0.60548<\/td>\n-0.0058<\/td>\n0.60743<\/td>\n0.00117<\/td>\n0.60646<\/td>\n-0.0023<\/td>\n<\/tr>\n
11<\/td>\n0.60646<\/td>\n-0.0023<\/td>\n0.60743<\/td>\n0.00117<\/td>\n0.60695<\/td>\n-0.0005<\/td>\n<\/tr>\n
12<\/td>\n0.60695<\/td>\n-0.0005<\/td>\n0.60743<\/td>\n0.00117<\/td>\n0.60719<\/td>\n0.00032<\/td>\n<\/tr>\n
13<\/td>\n0.60695<\/td>\n-0.0005<\/td>\n0.60719<\/td>\n0.00032<\/td>\n0.60707<\/td>\n-0.0001<\/td>\n<\/tr>\n
14<\/td>\n0.60707<\/td>\n-0.0001<\/td>\n0.60719<\/td>\n0.00032<\/td>\n0.60713<\/td>\n0.0001<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

Estimated root of 3x <\/em>– cos x <\/em>-1 is 0.60713.<\/p>\n

 <\/p>\n

Example 2: x3 + x \u2013 1 = 0<\/p>\n

f(0) = -1, f(1) = 1, so root lies between 0 and 1, take a = 0, b=1, c0 = a = 0<\/p>\n

 <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
k<\/strong><\/td>\na<\/strong><\/td>\nf<\/strong>(a)<\/strong><\/td>\nb<\/strong><\/td>\nf<\/strong>(b)<\/strong><\/td>\nc<\/strong>k<\/strong><\/td>\nf (c<\/strong>k<\/strong>)<\/strong><\/td>\n<\/tr>\n
1<\/td>\n0<\/td>\n-1<\/td>\n1<\/td>\n1<\/td>\n0.5<\/td>\n-0.375<\/td>\n<\/tr>\n
2<\/td>\n0.5<\/td>\n-0.375<\/td>\n1<\/td>\n0.17188<\/td>\n0.75<\/td>\n0.1719<\/td>\n<\/tr>\n
3<\/td>\n0.5<\/td>\n-0.375<\/td>\n0.75<\/td>\n0.17188<\/td>\n0.625<\/td>\n-0.1309<\/td>\n<\/tr>\n
4<\/td>\n0.625<\/td>\n-0.1309<\/td>\n0.75<\/td>\n0.01245<\/td>\n0.6875<\/td>\n0.0125<\/td>\n<\/tr>\n
5<\/td>\n0.625<\/td>\n-0.1309<\/td>\n0.6875<\/td>\n0.01245<\/td>\n0.65625<\/td>\n-0.0611<\/td>\n<\/tr>\n
6<\/td>\n0.65625<\/td>\n-0.0611<\/td>\n0.6875<\/td>\n0.01245<\/td>\n0.67188<\/td>\n-0.0248<\/td>\n<\/tr>\n
7<\/td>\n0.67188<\/td>\n-0.0248<\/td>\n0.6875<\/td>\n0.01245<\/td>\n0.67969<\/td>\n-0.0063<\/td>\n<\/tr>\n
8<\/td>\n0.67969<\/td>\n-0.0063<\/td>\n0.6875<\/td>\n0.01245<\/td>\n0.6836<\/td>\n0.0031<\/td>\n<\/tr>\n
9<\/td>\n0.67969<\/td>\n-0.0063<\/td>\n0.6836<\/td>\n0.00305<\/td>\n0.68165<\/td>\n-0.0016<\/td>\n<\/tr>\n
10<\/td>\n0.68165<\/td>\n-0.0016<\/td>\n0.6836<\/td>\n0.00305<\/td>\n0.68263<\/td>\n0.0007<\/td>\n<\/tr>\n
11<\/td>\n0.68165<\/td>\n-0.0016<\/td>\n0.68263<\/td>\n0.00072<\/td>\n0.68214<\/td>\n-0.0005<\/td>\n<\/tr>\n
12<\/td>\n0.68214<\/td>\n-0.0005<\/td>\n0.68263<\/td>\n0.00072<\/td>\n0.68239<\/td>\n0.0001<\/td>\n<\/tr>\n
13<\/td>\n0.68214<\/td>\n-0.0005<\/td>\n0.68239<\/td>\n0.00015<\/td>\n0.68227<\/td>\n-0.0001<\/td>\n<\/tr>\n
14<\/td>\n0.68227<\/td>\n-0.0001<\/td>\n0.68239<\/td>\n0.00015<\/td>\n0.68233<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

Estimated root of<\/span><\/p>\n

x<\/em>3 + <\/span>x <\/em>-1 = 0 is 0.68233.<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

Observations:\u00a0<\/strong><\/p>\n

 <\/p>\n

In each of the succeeding iterations, the size of the bracketing interval becomes half of the previous one. Thus, it is always possible to\u00a0 predict the number of iterations required\u00a0 to\u00a0 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<\/p>\n<\/div>\n

\n

\"\"<\/p>\n

Advantages:\u00a0<\/strong><\/p>\n

 <\/p>\n

(1)\u00a0 It is very simple.<\/p>\n

(2)\u00a0 Once initial a, b are known, number of iterations needed to be performed to achieve desired accuracy can be predetermined.<\/p>\n

(3)\u00a0 Reliable<\/p>\n

(4)\u00a0 Guarantees Convergence.<\/p>\n

(5)\u00a0 Function needs to be only continuous.<\/p>\n

(6)\u00a0 Only one function evaluation per iteration.<\/p>\n

(7)\u00a0 Calculation for making guess of root for the next iteration is very easy. Simply<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

c <\/em>= a + b<\/span><\/p>\n

2<\/p>\n<\/div>\n

 <\/p>\n

Drawbacks<\/strong>:<\/p>\n

 <\/p>\n

(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.<\/p>\n

(2) Slowest method<\/p>\n

(3) It does not take into account the nature of function to make next guess of the root.<\/p>\n\n\n\n
you can view video on Root Finding Problem: (Bisection Method)<\/strong><\/td>\n\"\"<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Suggested Reading:<\/strong><\/p>\n

<\/div>\n
1. Numerical Methods for Engineers by Steven C Chapra & Raymond P Canale, Fifth Edition, Tata McGraw Hill Publication, Special Indian Edition.<\/div>\n
2. A Friendly Introduction to Numerical Analysis by Brian Bradie, Pearson Education.<\/div>\n
3. Numerical Mathematics and Computing by Ward Cheney & David Kincaid, fifth Edition, Cengage Learning.<\/div>\n
4. Computer Oriented Numerical Methods by Dr. N Datta, Vikas Publication.<\/div>\n
5. Numerical Methods with Programs in C by T Veerarajan & T Ramachandran, Second Edition, Tata McGraw<\/div>\n
Hill Publication.<\/div>\n
6. Numerical Methods by V. Rajaraman, Third Edition, Prentice – Hall India Pvt. Ltd.<\/div>\n
7. Numerical Methods with C++ Programming by RM Somasundaram & RM Chandrasekaran, Prentice-Hall India Pvt. Ltd.<\/div>\n
8. Applied Numerical Analysis by C F Gerald & P O Wheatley, Seventh Edition, Pearson Education Asia, New Delhi.<\/div>\n
9. Numerical Methods by Dr. V. N. Vedamurthy & Dr. N.Ch. S.N. Iyengar, Vikas Publication.<\/div>\n
10. Numerical Analysis by Richard L. Burden, J. Douglas Faires, Cengage Publishcation.<\/div>\n
11. Numerical Methods with programs in BASIC, FORTRAN, Pascal and C++ by S. Balachandra Rao & C. K. Shantha, Revised Edition, Universities Press.<\/div>\n
12. A Textbook of Computer Based Numerical and Statistical Techniques by A. K. Jaiswal & Anju Khandelwal, New Age International (P) Ltd, Publishers.<\/div>\n
13. https:\/\/ece.uwaterloo.ca\/~dwharder\/…\/bisection\/examples.html<\/div>\n
14. oregonstate.edu\/instruct\/mth251\/cq\/Stage4\/Lesson\/bisection.htm<\/div>\n

 <\/p>\n","protected":false},"author":4,"menu_order":2,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["prof-savita-r-gandhi"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-39","chapter","type-chapter","status-publish","hentry","contributor-prof-savita-r-gandhi"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/pressbooks\/v2\/chapters\/39","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":8,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/pressbooks\/v2\/chapters\/39\/revisions"}],"predecessor-version":[{"id":580,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/pressbooks\/v2\/chapters\/39\/revisions\/580"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/pressbooks\/v2\/chapters\/39\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/wp\/v2\/media?parent=39"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/pressbooks\/v2\/chapter-type?post=39"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/wp\/v2\/contributor?post=39"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp15\/wp-json\/wp\/v2\/license?post=39"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}