Lesson6 Individual Assignment

Individual means that you do it yourself. You won't learn to code if you don't struggle for yourself and write your own code. Remember that while you can discuss the general (algorithmic) way to solve a problem, you should not even be looking at anyone else's code or showing anyone else your code for an individual assignment. Ask an instructor if you are really stuck and having very specific code problems.
Review the Group Work guidelines on Cavas and/or ask an instructor if you have any questions.

Programming Practice

Instructions (best to read them carefully)

In this assignment you will create a number of functions that will be used together to implement Newton's method to solve for the roots of a function.

You'll be using a modular approach again (combining several functions) and it is easiest to make the whole thing work together if the final versions of all those separate pieces are in the same code cell so that when you run that cell, all of the functions are defined together. You might have figured this out in the last Individual Assignment, but if you didn't try it there, it will probably save you some hassle. If you have some or all of the pieces and parts that got you there lying around, that's fine, but make sure your final versions are all together, tidy, doc stringed (doc strung?), commented, functional, spelled correctly, etc. (not doing any of these things will result in lost honor and points, but hopefully not lost hope)

In this assignment, the final versions of all your functions should appear in a code cell after Part I and after Part L.

Make sure that you are running test cases for everything and commenting on the results in markdown.

Get after it...

A. First, define a function called equation2, which should take a single parameter $x_{0}$ and returns $f(x_{0})$ as defined by Equation 2 in the Pre-Activity. This function is the one you will be solving numerically using Newton's method.

Test your function by calling it in a Jupyter code cell to make sure the results are consistent with your answers from the Pre-Activity. Also comment on the results in a markdown cell.


In [ ]:

B. Define a function called equation2prime, which should take a single parameter $x_{0}$ and returns $f'(x_{0})$.

Test your function by calling it in a Jupyter code cell to make sure the results are consistent with your answers from the Pre-Activity. Also comment on the results in a markdown cell.


In [ ]:

C. Define a function called function, which takes one parameter, calls equation2 with that parameter, and returns the return value from equation2. Briefly comment on the output.


In [ ]:

D. Define a function called fprime, which takes one parameter, calls equation2prime with that parameter, and returns the return value from equation2prime. Briefly comment on the output.


In [ ]:

E. Define a function called newton, which should take two parameters and return a single value. For now, have your function return its first parameter:

def newton(x0,maxError):
    return x0

This is known as a stub function. It is syntactically correct, so your code will run, but it is deliberately incomplete. The purpose of a stub is to temporarily stand in place of the correct implementation during the early part of developing a program. By using a stub, you are concentrating on getting the rest of your program working, before tackling this part of the program. Eventually, the newton function will implement Newton's method.

Run a single, simple test case through this function and comment on the results.


In [ ]:

F. Define a function called newton_ui, which takes no parameters and returns no values. Instead, it will be used to create a friendly user-interface (UI) for calling the newton function.

Your newton_ui function should print a message, explaining that you are using Newton's method to find a root for the function: $f(x)=x^2-sin(x)-1$ (note: this eq is formatted using LaTeX here and you won't be able to do that in a function).

Then your function should prompt the user for an initial estimate and the maximum acceptable error.

Then it should call the newton function, passing it the two parameters.

Finally, it should print out the return value from the newton function.

After writing your newton_ui function, add a call to the newton_ui function as a test case in a separate Jupyter code cell and comment on the results in a markdown cell.


In [ ]:

G. After the newton_ui user interface program works with the stub function, it’s time to go back and fill in the stub function newton. But you will still program in steps.

First, modify your newton function so it only completes one iteration of Newton's method (ignoring the maximum error acceptable for now). Don't forget to call function and fprime, instead of equation2 and equation2prime. Remember that you should be running this entire collection of functions as a single code cell at the end of Part I. (Each time you want the whole collection of code to run, you need to call newton_ui which calls newton which calls...)

Thanks to your newton_ui function, you should be prompted for your initial guess. This time, the root found should differ from your initial estimate. Make sure the result is consistent with your answer to the Pre-Activity by running test cases and commenting on the results in markdown.


In [ ]:

H. Once your newton function successfully calculates one iteration of Newton's method, you're ready to add a loop to your function (finally!).

But first, answer the three questions that you should always answer before writing a loop:

  • what condition must be true for the loop to repeat?
  • what needs to be initialized before the start of the loop?
  • what will change inside the body of the loop so that the loop will eventually end?

Replace with answers to three questions

The three answers should help you determine what code should be repeated multiple times – that code will be the body of your while loop. Hint: the condition of the while loop will be based on comparing $f(x_{1})$ to the maximum error, because if your function found the exact solution $x_{1}$, then $f(x_{1})=0$.

For debugging purposes, add a print statement to the body of your while loop. Print the current root estimate and its error.

Before you run your while loop for the first time (or anytime you suspect that it will "hang" since you have produced an infinite loop) save your notebook! If you have produced an infinite loop, the safest way out is to use the I,I keyboard shortcut, and fastest way back to productivity is the Kernel -> Restart & Clear Output menu option (this will also end the infinte loop) as this will safely restart the kernel and flush any obnoxiously long output from an infinite print.

Run your collection of code in the single cell (which you will also have to do after Part I) and debug it if necessary. Thanks to the print statement, you should be able to see Newton's method work in steps.


In [ ]:

I. Now modify your new newton function so it keeps count of the number of iterations necessary to find the root. Your function should print out the number of iterations just before returning the root.

test the function with values that you are familiar with from the Pre-Activity. Double-check that your newton function returns the final guess for the root.


In [ ]:

Replace this with a single code cell with the final version of all your functions, including:

  • newton_ui
  • newton
  • function
  • function_prime
  • equation2
  • equation2prime

Comparison of bisection and Newton's method

Let's have some (nerdy) fun and look at which method performs better, which we'll define as gets an approximation of the root of $f(x) = x^2 - sin(x)-1$ to within the maximum error, $\varepsilon$, in fewer iterations.

J. First, you need to clean up your bisection function from Lesson5.

Feel free to copy (the scandal, I know) from your previous work into new Jupyter code cells here for the bisection function.

Make sure you use the version that uses equation3 from Lesson5 which is the same as equation2 from Lesson6! Don't get confused, the math and code should be the same: $f(x) = x^2 - sin(x)-1$

bisection should take 2 parameters:

  • a list that has 2 values - a and b - that define the initial interval
  • the maximum amount of error tolerated - maxError so it should look like this:
bisection([a,b], maxError)

You should already have a version that takes [a,b] but you'll need to modify what you have so that it takes maxError as a parameter and uses a while loop and comparison to determine the number of iterations and keeps track of the number of iterations (good thing you just did this for newton_ui).

bisection should not print anything but should return the root approximation and iteration number, like this:

     return approximation, iterations

e.g. 1.4140625, 7.

test the bisection function with values that you are familiar with to make sure it works!


In [ ]:

K. Now you need to clean up your and your newton and associated functions so that they have similar parameters and returns as bisection. Luckily, there is less work to do here.

You should again copy (gasp!) from your previous work on these functions into new cells here to make a new module.

Modify your newton_ui function to be called newton_args (args stands for arguments) and comment out all of the print and input business.

Make newton_args take 2 parameters:

  • an initial value for the root approximation - x0,
  • the maximum amount of error tolerated - maxError

newton_args should not print anything and should return the root approximation and iteration number, like this (approximation, iterations) e.g. (1.4140625, 7).

test this code with values that you are familiar with to make sure it works!


In [ ]:

L. Once you are sure that bisection and newton functions work, you can compare them.

Run through a set of test cases for finding the root of equation3 from Lesson5/equation2 from Lesson6 (both functions use $f(x) = x^2 - sin(x)-1$, you checked, right) and illustrate how many iterations each method takes to find a root to:

  • within $\varepsilon = 0.1$?
  • within $\varepsilon = 0.01$?
  • within $\varepsilon = 0.001$?
  • within $\varepsilon = 0.000001$?

Illustrate your answers with code, and collect your data in a markdown cell(s) including a table that compares methods and an explanation of the results. (hint: Newton's method is the winner by a lot)


In [ ]:

Replace this cell with a code cell with the final version of your functions, including:

  • newton
  • bisection
  • equation3

Notice that your newton function will rely on the some functions that you developed for Part I.