You should create both a program and a document that describes parts of your program.

Newtons method is a way of getting successively better approximations to a root of a function, f. The process is to compute a sequence of approximations to the root, x_i. The initial value, a guess at the root, is given as x₀. Then, subsequent x_i are found by the formula:

a)Begin by creating a function, F, that takes in some value, x, and returns the value of some function f at that value, x. Your function F can be an arbitrary function it may be a polynomial, trigonometric, exponential/logarithmic, etc. function, or any combination. Initially, please choose a function that is very simple, for which you can easily compute the roots and derivatives by hand, e.g. x²-1. Write in the document what function you used.

b)We will next look at turning the numerical derivative calculations that we computed in lab 6 into a function. Recall that a derivative of a function at any value, x, could be approximated by computing a difference: or or , for a sufficiently small value of a.

a.Write a function, deriv, that computes an approximate derivative of the function F at a particular value. The function deriv should take in a value x, and return the (approximate) derivative of f, i.e. f(x), at that value.

c)Next, create a function named newton_step that performs one step of Newtons method. Using the functions F and deriv, newton_step should take as input a guess at a root, x_i, and should return a new guess for the root, x_i+1.

d)Next, create a function newton that will take an initial guess for a root, x₀, and will compute a sequence of root approximations. The function should create and return a list of successive approximations to a root. It can stop when the difference between successive approximations is no more than 10^-6.

e)Finally, create a complete program that asks a user for an initial guess of a root, and prints the set of root approximations that Newtons method computes from that initial guess.

Once you have the program working, try the following. You should write the answers to the following questions in the document that accompanies your program.

f)Change the function F to one that does not have any real roots (e.g. x²+1). Record this function in your document. What happens to your program? You may want to print out the values computed inside the function newton to see this better.

g)Change the function F to one that is more complex, where you do not know the derivative/roots ahead of time. Write in the document what the function is, as well as the answer to the following questions.

a.Test out several different starting guesses for the root. Do all of your guesses converge to the same root?

b.Of several guesses, about how many successive values of x_i are computed before the program has converged to a root?

c.From your memory of the bisection approach for finding a root more accurately, which do you think converges to the root faster (i.e. which takes fewer iterations) Bisection or Newtons method?

d.Compare the number of evaluations of the function F between the Bisection method and Newtons method when we must approximate the derivative numerically.

i.For each iteration of the Bisection method, how many times is the function F evaluated?

ii.For each iteration of Newtons method, how many times is the function F evaluated?

iii.Does this change your thoughts about your answer in (c), above (comparing which converges faster between Bisection and Newtons method)? Why or why not?

Turn in your program generated in part g with the document you put together.

Challenges: One interesting thing we can do in Python is to easily pass a function as an argument to another function! That is, we could call a function dosomething(myfunc) where myfunc is a function. Then, inside of the body of dosomething, we could have code such as myfunc(x).

a)See if you can rewrite the Newtons Method program so that the newton routine takes in both a function and an initial guess (instead of assuming the function is F). Test with multiple functions.

b) See if you can modify the Newton routine so that it will detect when it seems there are no real roots and output a message accordingly.