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

192 7 SolvingNonlinearAlgebraicEquations RequiredWorkin theBisection Method If thestarting intervalof the bisectionmethod is boundedbya andb, and the solutionat stepn is taken tobe the middlevalue, theerror isboundedas |b−a| 2n , (7.4) because the initial interval has been halved n times. Therefore, to meet a tolerance , we needn iterations such that the length of the current interval equals : |b−a| 2n = ⇒ n= ln((b−a)/ ) ln2 . This is a great advantage of the bisection method: we know beforehandhow manyiterationsn it takes tomeeta certainaccuracy in thesolution. 7.5 RateofConvergence With the methodsabove, we noticed that the number of iterations or function calls coulddifferquitesubstantially.Thenumberof iterationsneededtofindasolution is closelyrelatedtotherateofconvergence,whichdictatesthespeedoferrorreduction as we approach the root. More precisely, we introduce the error in iteration n as en=|x−xn|, anddefine the convergencerateq as en+1 =Ceqn, (7.5) whereC is a constant.The exponentq measureshowfast the error is reducedfrom one iteration to the next. The larger q is, the faster the error goes to zero (when en<1),and thefewer iterationsweneed tomeet thestoppingcriterion |f(x)|< . ConvergenceRateand Iterations When we previously addressed numerical integration (Chap.6), the approx- imation error E was related to the size h of the sub-intervals and the convergencerate r asE=Khr,K beingsomeconstant. Observe that (7.5) gives a different definition of convergence rate. This makes sense, since numerical integration is based on a partitioning of the original integration interval inton sub-intervals,which is verydifferent from the iterativeproceduresusedhere for solvingnonlinearalgebraicequations.