My first solution to the root finding homework

Here is my solution to the root finding homework we had last week.

a = 1
b = 2
pa = a**4-3*a**2 + 2*a-1
pb = b**4-3*b**2 + 2*b-1

while b - a > 0.0001:
    c = (a + b)/2
    pc = c**4-3*c**2 + 2*c-1
    if pa > 0 and pc > 0:
        a = c
        pa = pc
    elif pa < 0 and pc < 0:
        a = c
        pa = pc
    else:
        b = c
        pb = pc

print("The root is between ",a," and ",b)

Note that since we had not seen functions at that point in the course I had to compute the values p(a), p(b), and p(c) without using a function.

A more minimal solution

My solution looks very similar to solutions that many of you submitted for the homework.

For any given problem there are likely to be many different solutions that work. Below is an alternative solution that is much shorter. This solution takes advantage of some special characteristics of the problem.

a = 1
b = 2

while b - a > 0.0001:
    c = (a + b)/2
    pc = c**4-3*c**2 + 2*c-1
    if pc < 0:
        a = c
    else:
        b = c

print("The root is between ",a," and ",b)

Here are some observations about what is going on in this problem:

1. We know in advance that p(a) < 0 and p(b) > 0.
2. The goal of the algorithm is move a and b closer together while keeping the signs of p(a) and p(b) unchanged.
3. When we compute c and then p(c), we will move a over to where c if p(a) and p(c) have the same sign. Since we already know that p(a) < 0, we only have to check that p(c) < 0. If it is, we set a equal to c. Likewise, if p(c) > 0 we know that we should set b = c.

Using a function

Now that we know how to write functions in Python, it is natural to rewrite this program to use a function. I am also going to take this opportunity to show yet another strategy for figuring out whether to set a = c or b = c.

def p(x):
    return x**4 - 3*x**2 + 2*x - 1

a = 1
b = 2

while b - a > 0.0001:
    c = (a + b)/2
    if p(a)*p(c) > 0:
        a = c
    else:
        b = c

print("The root is between ",a," and ",b)

The logic in this solution makes use of the observation that if p(a) and p(c) have the same sign then their product will be positive.

Packaging the solution up as a function

Since we have successfully implemented the algorithm for finding a root, the final step is to construct a function that packages this solution up so we can use it in other programs as a way to find a root of a function.

def bisection(f,a,b,tolerance = 0.0001):
    """Finds a root of f(x) for x between a and b. Note that
       a must be less than b, and f(a) and f(b) must have
       opposite signs for this to work correctly."""
    while b - a > tolerance:
        c = (a + b)/2
        if f(a)*f(c) > 0:
            a = c
        else:
            b = c
    return (a+b)/2

def p(x):
    return x**4-3*x**2 + 2*x-1

print("The root is approximately ",bisection(p,1,2))

Here are some things to note about this solution.

1. Python allows you to pass one function as a parameter to another function. The first parameter in the bisection function is the function we are trying to find the root of. When we call the bisection function we pass the polynomial function p to bisection in the first parameter.
2. The fourth parameter in the bisection function is an example of a default parameter. When we call the function we get to choose whether or not we want to pass a fourth parameter to the bisection function. If we don't pass in a fourth parameter, bisection will use the value 0.0001 for tolerance by default.