Exercise: Evaluate the cells below to define the Bisection and MakeTestFunction functions. Then create a root-finding function with the same inputs as the Bisection function which is at least somewhat faster than the bisection function. A bonus (maximum 1/2 of a lab) will be given for the fastest version.

You should not use any information about the test function apart from the fact that they will have roots between -1 and 2.

You can use bisection, Regula Falsi, the secant method, Newton's method, or other methods in combination but you must implement them yourself.

In [1]:

def Bisection(f, a, b, tol=10^(-14 ), max_iterations=10^6 , verbose=False):

 '''

 Implements the Bisection Method to find a zero of f, given points a and b with f(a)f(b)<0.

 '''

 assert(f(x=a)*f(x=b)<0 ) #Checks assumption that f(a) and f(b) are different signs

 c = float((a+b)/2)

 iterates = 0

 while (abs(f(x=c)) > tol or (b-a) > tol) and iterates < max_iterations:

 iterates += 1

 if sgn(f(x=c))==sgn(f(x=a)):

 a = c

 else:

 b = c

 c = (a+b)/2.0

 if abs(f(x=c)) < tol or (b-a) < tol:

 if verbose:

 print(iterates, 'iterates')

 return c

 else:

 print('Did not converge')

 return NaN 

In [5]:

def MakeTestFunction(c,m):

 var('x')

 temp = random()

 if temp > 0.5:

 return (x - c*sin(x) - m) 

 else:

 return (x - c*sin(x + x^3) - m)*sgn(0.5-random())

In [6]:

%%timeit -n 1 -r 2

lower = -1.0

upper = 2.0

for i in range(100):

 ftest = MakeTestFunction(random(),random())

 ans = Newton(ftest,lower,upper, verbose=False)

 assert(ans>lower and ans 
 assert(abs(ftest(x=ans))<10^(-14))