6.00: Introduction to Computer Science and Programming

Problem Set 4: Successive Approximation

Handed out: Tuesday, October 6, 2009
Due date: 11:59pm Tuesday, Oct 13, 2009

Introduction

Successive approximation is a problem-solving method where you try to guess the right answer to a problem and then check your guess. If the guess is good enough, you're done. Otherwise, you keep improving and checking your guess in small increments, getting closer and closer to the right answer, until you determine that the guess is good enough.

In this problem set, we will look at Newton's method, which uses successive approximation to find the roots of a function, and the golden ratio, which is a numerical value that can be found using successive approximation.

Workload
Please let us know how long you spend on each problem. We want to be careful not to overload you by giving out problems that take longer than we anticipated.

Collaboration
Please take note of the policy in the course information handout.

Getting Started

Download and save

  1. ps4.py: the skeleton you'll fill in
  2. ps4test.py: some unit tests for your code

Newton's Method

Newton's method (also known as the Newton-Raphson method) is a successive approximation method for finding the roots of a function. Recall that the roots of a function f(x) are the values of x such that f(x) = 0. You can read more about Newton's method here.

Here is how Newton's method works:

  1. We guess some x0.
  2. We check to see if it's a root or close enough to a root by calculating f(x0). If f(x0) is within some small value epsilon of 0, we say that's good enough and call x0 a root.
  3. If x0 is not good enough, we need to make a better guess, x1. x1 is calculated by the equation: x1 = x0 - f(x0)/f '(x0)
    f '(x) is what's called the derivative of x. We'll explain this in more detail later.
  4. We check to see if x1 is close enough to a root. If it is not, we make a better guess x2 and check that. And so on and so on. For every xn that is not close enough to a root, we replace it with xn+1 = xn - f(xn)/f '(xn) and check if that's close enough to a root. We repeat until we finally find a value close to a root.

For simplicity, we will only be using polynomial functions in this problem set.

Polynomials

For this problem set, we will be representing polynomials as tuples. The index of the tuple represents the power, and the value at that index represents the coefficient for that term. So for example, the polynomial x4 + 3x3 + 17.5x2 - 13.39 would be represented by the tuple (-13.39, 0, 17.5, 3, 1). This is because the tuple represents -13.39x0 + 0x1 + 17.5x2 + 3x3 + 1x4, which is the same as x4 + 3x3 + 17.5x2 - 13.39.

Problem #1
Implement the evaluate_poly function. This function evaluates a polynomial function for the given x value. It takes in a tuple of numbers poly and a number x. By number, we mean that x and each element of poly can be an int or a float. evaluate_poly takes the polynomial represented by poly and computes its value at x. It returns this value as a float.

You may find the Python power operator ** useful.

def evaluate_poly(poly, x):
     """
     Computes the polynomial function for a given value x. Returns that value.

     Example:
     >>> poly = (0, 0, 5, 9.3, 7)     # f(x) = 7x4 + 9.3x3 + 5x2
     >>> x = -13
     >>> print evaluate_poly(poly, x)  # f(-13) = 7(-13)4 + 9.3(-13)3 + 5(-13)2
     180339.9

     poly: tuple of numbers, length > 0
     x: number
     returns: float
     """
      # TO DO ...

Derivatives

As stated before, we will need to find f '(xn). f '(x) is what's known as the derivative of f(x). For those of you who have not taken calculus, the following is all you will need to know about derivatives to do this problem set.

Since we're only dealing with polynomial functions, we only need to know how to calculate the derivative of a polynomial function. Consider a simple polynomial function f(x) = axb. The derivative of f(x) is f '(x) = (a*b)xb-1. In other words, you multiply the coefficient by the power, and then decrement the power by one.

To compute the derivative of a polynomial function with many terms, you just do the same thing to every term individually. For example, consider f(x) = x4 + 3x3 + 17.5x2 - 13.39.

The derivative of x4 is 4x3.
The derivative of 3x3 is 9x2.
The derivative of 17.5x2 is 35x.
The derivative of -13.39 is 0.

We add all those terms up and get f '(x) = 4x3 + 9x2 + 35x.

Problem #2
Implement the compute_deriv function. This function computes the derivative of a polynomial function. It takes in a tuple of numbers poly and returns a tuple of numbers that represents the derivative of the polynomial represented by poly.

def compute_deriv(poly):
     """
     Computes and returns the derivative of a polynomial function. If the derivative is 0, returns (0,).

     Example:
     >>> poly = (-13.39, 0, 17.5, 3, 1)    # x4 + 3x3 + 17.5x2 - 13.39
     >>> print compute_deriv(poly)         # 4x3 + 9x2 + 35x
     (0, 35.0, 9, 4)

     Results such as (0.0, 35.0, 9.0, 4.0) are also acceptable.

     poly: tuple of numbers, length > 0
     returns: tuple of numbers
     """
      # TO DO ...

Implementing Newton's Method

Problem #3
Implement the compute_root function. This function applies Newton's method of successive approximation as described above to find a root of the polynomial function. It takes in a tuple of numbers poly, an initial guess x_0, and a margin of error epsilon. It returns a tuple. The first element is the root of the polynomial represented by poly; the second element is the number of iterations it took to get to that root.

The function starts at x_0. It then applies Newton's method. It ends when it finds a root x such that the absolute value of f(x) is less than epsilon, i.e. f(x) is close enough to zero. It returns the root it found as a float.

def compute_root(poly, x_0, epsilon):
     """
     Uses Newton's method to find and return a root of a polynomial function.
     Returns a tuple containing the root and the number of iterations required to get to the root.

     Example:
     >>> poly = (-13.39, 0, 17.5, 3, 1)     #x4 + 3x3 + 17.5x2 - 13.39
     >>> x_0 = 0.1
     >>> epsilon = .0001
     >>> print compute_root(poly, x_0, epsilon)
     (0.80679075379635201, 8)

     poly: tuple of numbers, length > 1.
           Represents a polynomial function containing at least one real root.
           The derivative of this polynomial function at x_0 is not 0.
     x_0: float
     epsilon: float > 0
     returns: tuple (float, int)
     """
      # TO DO ...

The Golden Ratio

The golden ratio is a special number in mathematics, represented by the Greek letter phi (φ). What's special about it is that the ratio between 1 and φ is the same as the ratio between φ and 1 + φ. In other words,

    φ = (φ + 1)/φ

You can read more about the golden ratio here. While there are straightforward analytical approaches to calculating the value of φ, we'll be taking a look at how to compute φ by successive approximation.

Problem #4
Implement the compute_phi function. This function applies the method of successive approximation to compute the golden ratio phi (φ). It takes in an initial guess phi_0, and it returns an approximation of the golden ratio φ, using the compute_root function defined in Problem #3. Hint: Transform this problem into a problem solvable by compute_root. For epsilon, use 0.000000001.

This problem is primarily meant to get you to think about how you can use previously-defined functions to solve new problems. Your code for this problem should be very short, fewer than four lines of code.

def compute_phi(phi_0):
     """
     Computes and returns an approximation of the golden ratio phi.

     Example:
     >>> print compute_phi(100.0)
     1.61803398898

     phi_0: float > 1.0
     returns: float
     """
      # TO DO ...

This completes the problem set!

Handin Procedure

1. Save
Save your solution as it was provided: ps4.py.
Do not ignore this step or save your file(s) with a different name!

2. Time and collaboration info
At the start of the file, in a comment, write down the number of hours (roughly) you spent on this problem set, and the names of whomever you collaborated with. For example: 

# Problem Set 4
# Name: Jane Lee
# Collaborators (Discussion): John Doe
# Collaborators (Idential Solution): Jane Smith
# Time: 1:30
#
 .... your code goes here ...

3. Submit
Upload the file to your workspace. If there is some error uploading to your workspace, email the file to 6.00-staff [at] mit.edu.

You may upload (or email) new versions of the problem set until the 11:59pm deadline, but anything uploaded after that will be ignored.