Seite - 200 - in Programming for Computations – Python - A Gentle Introduction to Numerical Simulations with Python

200 6 SolvingNonlinearAlgebraicEquations if return_x_list: x_list = [] while abs(f_M) > eps: if f_L*f_M > 0: # i.e. same sign x_L = x_M f_L = f_M else: x_R = x_M x_M = float(x_L + x_R)/2 f_M = f(x_M) iteration_counter += 1 if return_x_list: x_list.append(x_M) if return_x_list: return x_list, iteration_counter else: return x_M, iteration_counter def f(x): return x**2 - 9 a = 0; b = 1000 solution, no_iterations = bisection(f, a, b, eps=1.0e-6) print "Number of function calls: %d" % (1 + 2*no_iterations) print "A solution is: %f" % (solution) Note thatwefirstcheck iff changessign in Œa;b ,because that isa requirement for thealgorithmtowork.Thealgorithmalso reliesonacontinuousf.x/ function, but this isverychallenging foracomputercode tocheck. Weget thefollowingprintoutto thescreenwhenbisection_method.pyisrun: Number of function calls: 61 A solution is: 3.000000 Wenoticethat thenumberoffunctioncalls ismuchhigherthanwiththeprevious methods. Requiredworkinthebisectionmethod If the starting interval of the bisectionmethod is boundedbya and b, and the solutionat stepn is taken tobe themiddlevalue, theerror is boundedas jb aj 2n ; (6.4) because the initial interval has beenhalvedn times. Therefore, tomeet a toler- ance , we needn iterations such that the length of the current interval equals : jb aj 2n D ) nD ln..b a/= / ln2 :