Page - 201 - in Programming for Computations – Python - A Gentle Introduction to Numerical Simulations with Python

6.5 RateofConvergence 201 This is a great advantage of the bisectionmethod: we know beforehand how many iterationsn it takes tomeet acertainaccuracy in thesolution. Aswith the twopreviousmethods, the functionbisection is placed in thefile nonlinear_solvers.pyforeasy importanduse. 6.5 RateofConvergence With themethodsabove,wenoticed that thenumberof iterationsor functioncalls coulddiffer quite substantially. Thenumberof iterations needed tofinda solution is closely related to the rate of convergence, which dictates the speed of error re- ductionasweapproach the root.Moreprecisely,we introduce theerror in iteration nasen Djx xnj, anddefine theconvergencerateq as enC1 DCeqn; (6.5) whereC is aconstant. Theexponentqmeasureshowfast theerror is reducedfrom one iteration to the next. The largerq is, the faster the error goes to zero, and the fewer iterationsweneed tomeet thestoppingcriterion jf.x/j< . A singleq in (6.5) is defined in the limitn ! 1. For finiten, and especially smallern,qwill varywithn. To estimateq,we can compute all the errors en and set up (6.5) for threeconsecutiveexperimentsn 1,n, andnC1: en DCeqn 1; enC1 DCeqn : Dividing these twoequationsbyeachotherandsolvingwith respect toqgives qD ln.enC1=en/ ln.en=en 1/ : Since this qwill vary somewhatwithn, we call it qn. Asn grows,we expect qn to approach a limit (qn ! q). To compute all the qn values, we need all the xn approximations. However, our previous implementationsofNewton’smethod, the secantmethod,and thebisectionmethodreturned just thefinal approximation. Therefore, we have extended the implementations in the module file nonlinear_solvers.py such that the user can choose whether the final value or the whole history of solutions is to be returned. Each of the extended im- plementations now takes an extra parameter return_x_list. This parameter is a boolean, set toTrue if the function is supposed to return all the root approxima- tions, orFalse, if the function should only return the final approximation. As an example, let us takeacloser lookatNewton: def Newton(f, dfdx, x, eps, return_x_list=False): f_value = f(x) iteration_counter = 0 if return_x_list: x_list = []