Page - 190 - in Programming for Computations – Python - A Gentle Introduction to Numerical Simulations with Python 3.6, Volume Second Edition

190 7 SolvingNonlinearAlgebraicEquations print(’Number of function calls: {:d}’.format(2+no_iterations)) print(’A solution is: {:f}’.format(solution)) else: print(’Solution not found!’) The number of function calls is now related to no_iterations, i.e., the number of iterations, as 2 + no_iterations, since we need two function calls before entering the while loop, and then one function call per loop iteration. Note that, even though we need two points on the graph to compute each updated estimate, only a single function call (f(x1)) is required in each it- eration since f(x0) becomes the “old” f(x1) and may simply be copied as f_x0 = f_x1 (the exception is the very first iteration where two function evalu- ationsareneeded). Runningsecant_method.py, gives the followingprintouton thescreen: Number of function calls: 19 A solution is: 3.000000 7.4 TheBisectionMethod Neither Newton’s method nor the secant method can guarantee that an existing solution will be found(see Exercises 7.1 and 7.2). The bisection method,however, does that. However, if there are several solutionspresent, it finds onlyone of them, just as Newton’s method and the secant method. The bisection method is slower thantheother twomethods,so reliabilitycomeswithacostofspeed(but,again, for a singleequation that is rarelyan issue with laptopsof today). To solve x2 −9 = 0, x ∈ [0,1000], with the bisection method, we reason as follows.Thefirstkey idea is that iff(x)=x2−9 iscontinuouson the intervaland the function values for the interval endpoints (xL = 0, xR = 1000) have opposite signs, f(x) must cross the x axis at least once on the interval. That is, we know there is at least onesolution. The second key idea comes from dividing the interval in two equal parts, one to the left and one to the right of the midpointxM = 500. By evaluating the sign off(xM), we will immediately know whether a solution must exist to the left or right ofxM. This is so, since iff(xM)≥ 0, we know thatf(x)has to cross thex axis betweenxL andxM at least once (using the same argument as for the original interval).Likewise, if insteadf(xM)≤0,weknowthatf(x)has tocross thex axis betweenxM andxR at least once. In any case, we may proceed with half the interval only. The exception is if f(xM) ≈ 0, in which case a solution is found. Such interval halving can be continued until a solution is found. A “solution” in this case, is when |f(xM)| is sufficiently close to zero, more precisely (as before): |f(xM)| < , where is a smallnumberspecifiedby theuser.