<jupyter_start><jupyter_text>Bisection search<jupyter_code>%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt<jupyter_output><empty_output><jupyter_text>Define a function to calculate the function value for a given x<jupyter_code>def eval_function(x): 
    a = 1.01
    b = -3.04
    c = 2.07
    return a*x**2 + b*x +c<jupyter_output><empty_output><jupyter_text>Validate our intial values for x; check if one of them are roots and if they bracket a root<jupyter_code>def check_initial_values(f, x_min, x_max, tol):
    #check our initial guesses
    y_min = f(x_min)
    y_max = f(x_max)
    
    #check that xmin and xmas bracket a root
    if (y_min*y_max > 0.0):
        print("no zero crossing found in the range",x_min, x_max)
        s = "f(%f) = %f, f(%f) = %f" % {x_min,y_min,x_max,y_max}
        print(s)
        return 0
   
    #if x_min is a root , then return flag ==1
    if(np.fabs(y_min) < tol):
        return 1
   
    #if x_max is a root, then return flag == 2
    if(np.fabs(y_max) < tol):
        return 2
  
    #if we reach this point, the bracket is valid
    #and we will return 3
    return 3<jupyter_output><empty_output><jupyter_text>main work function<jupyter_code>def bisection_root_finding(f, x_min_start, x_max_start, tol):
    #this function uses bisection search to find a root of f
    x_min = x_min_start
    x_max = x_max_start
    x_mid = 0.0
    
    imax = 1000 #max number of iterations
    i = 0
    
    #check the initial values
    flag = check_initial_values(f,x_min,x_max,tol)
    if(flag == 0):
        print("error in bisection_root_finding")
        raise ValueError("Initial values invalid", x_min, x_max)
    
    elif(flag ==1):
        #got lucky
        return x_min
    
    elif(flag == 2):
        return x_max
    #if we reach here,then conduct the search
    
    #set a flag
    flag = 1
    
    while (flag):
        #set mid point
        x_mid = 0.5*(x_min+x_max)
        y_mid = f(x_mid) #function at mid point
        
        #check if x_mid is a root
        if(np.fabs(y_mid) < tol):
            flag = 0
        else:
            #x_mid is not a root
        
            #if the product of the fuction at the mid point
            #and at one of the end points is greater than zero, 
            #replace this end point
            if(f(x_min) * f(x_mid) > 0):
                x_min = x_mid
            else:
                #replace x_max with x_mid
                x_max = x_mid
        
          #print out the iteration 
        #print the labels only for iteration 1
        if (i == 0):
            print("x_min   y_min   x_max    x_max")
        
        print(x_min, f(x_min), x_max, f(x_max))
    
        #count the iterations
        i +=1
    
        #if we have exceeded the max number
            #of iterations, exit
        if (i >= imax):
            print("Exceeded max number of iterations", i)
            s = "min bracket f(%f) = %f" % (x_min, f(x_min))
            print(s)
            s = "max bracket f(%f) = %f" % (x_max, f(x_max))
            print(s)
            raise StopIteration("stop iterations after ", i)
        #inside the while loop
        #end of wile loop
    
    #outside of the while loop

    #we are done, return the root and iterations
    return x_mid, i<jupyter_output><empty_output><jupyter_text>perform search<jupyter_code>x_min = 0.25
x_max = 1.8
y_min = eval_function(x_min)
y_max = eval_function(x_max)
tolerance = 1.0e-6
#print the initial guesses
print ("initial guesses are: [%f, %f], [%f, %f]", x_min,y_min,x_max,y_max)


#call the bisection root finding function
x_root, iterations = bisection_root_finding(eval_function, x_min, x_max, tolerance)
y_root = eval_function(x_root)
print()
s = "root found with y(%f) = %f, after %d number of iterations " % (x_root,y_root, iterations)
print(s)

#Plot f(x) and x
x = np.linspace(0,3,1000)
y = eval_function(x)

plt.xlabel(r'$x$')
plt.ylabel(r'$y(x)')
plt.xlim([0,3])
plt.ylim([-0.5,2.1])
plt.plot(x,y)

#draw a line at y =0 
#points are x=0, y = 0 and x=3 and y =0
x_values = [0,3];
v_values =[0,0];
plt.plot(x_values, v_values)

#draw bracketing points
plt.plot(x_min, y_min, marker='o', color="green")
plt.annotate("%.4f,%.4f" %(x_min,y_min), (x_min,y_min))
plt.plot(x_max,y_max, marker='o', color="green")
plt.annotate("%.4f,%.4f" %(x_max,y_max), (x_max,y_max))

#draw the root
plt.plot(x_root,y_root, marker='o', color ="red")
plt.annotate("%.4f,%.4f" %(x_root,y_root), (x_root,y_root))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1173345140580031, 'fraction_numerical': 0.01593978304184193, 'mean_word_length': 2.574367088607595, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '566938', 'license': 'MIT', 'n_tokens_mistral': 1769, 'n_tokens_neox': 1695, 'n_words': 473, 'path': 'astr-119-hw-4/hw-4.ipynb', 'repo_name': 'amunnangi/astr-119', 'size': '4517'}