bisection-performance.ipynb

Kernel: Unknown Kernel

Task 3

This homework is an activity intended to explore the bisection method and compare its computational performance and convergence with a modification called trisection.

Due to: May 24

Bisection, Trisection and Quadsection

As mentioned in class, bisection is a very simple and basic algorithm that finds roots of functions and exploits the intermediate value theorem.

The error of this method is obtained by means of a geometric analysis. Considering that successives iterations bisect the previous interval into two new ones, where one of them will be chose as the interval for the next iteration, the convergence of the method is given by:

$$p_n = p + \left(\frac{1}{2^n}\right)$$

Following this reasoning from a pure mathematical point of view, modifying this scheme, such that three or even more intervals are taken in each iteration instead of two, would produce a convergence as:

$$p'_n = p + \left(\frac{1}{N^n}\right)$$

where $N$ is the number of intervals to be considered. It is clear, then, that the greater is the value $N$ the faster the convergence is reached.

Nevertheless, a greater number of subintervals will imply a harder computational implementation per iteration. In other words, the number of iterations for a given precision is lower, but the computing time per iteration is higher. This push-and-pull situation is very interesting to analyse as there is not a clear answer about which scenario is more favorable, and it even depends on the number of subintervals $N$.

1. Modify the Bisection function provided in class and write two new routines, Trisection and Quadsection. These new routines should have to find roots like Bisection does, but using three and four subintervals per iteration respectively.

Test your routines using the next function

$$f(x) = x^2-5$$

Be aware this function has analytic roots, so you can compare directly your results.

#Defining Bisection function
def Bisection( f, a, b, Nmax, printer=False ):
    #verifying the STEP1, a and b with different signs
    if f(a)*f(b)>0:
        print "Error, f(a) and f(b) should have opposite signs"
        return False
    #Assigning the current extreme values, STEP2
    ai = a
    bi = b
    #Iterations
    n = 1
    while n<=Nmax:
        #Bisection, STEP3
        pi = (ai+bi)/2.0
        #Evaluating function in pi, STEP4 and STEP5
        if printer:
            print "Value for %d iterations:"%(n),pi
        #Condition A
        if f(pi)*f(ai)>0:
            ai = pi
        #Condition B
        elif f(pi)*f(ai)<0:
            bi = pi
        #Condition C: repeat the cycle
        n+=1
    #Final result
    return pi

2. Make a plot and illustrate the behaviour of Bisection, Trisection and Quadsection in terms of the number of iterations.

3. For a float32 precision, how long does each method take?

4. Compare all the previous routines with the function offered by Scipy (scipy.optimize.bisect)

Question:

If you were going to use one of these routines for a professional usage, which one would you choose and why?