Project: Newton’s Method

Newton’s method is a powerful technique for numerically computing the zeros of differentiable functions. It is an iterative technique, meaning that instead of applying a formula to directly compute the answer, it repeatedly tries to compute a better approximation until the desired accuracy is reached. Iteration is just a fancy word for repetition, which we know how to do in Python using for loops and while loops.

Newton’s method gives a surprisingly simple algorithm for computing $\sqrt{k}$ .

# To compute sqrt(k)

Begin with an initial guess x.

Repeat until desired accuracy is reached:

 Replace x with the average of x and k/x.

That’s all there is to it. At the end of the loop, x will be approximately equal To $\sqrt{k}$ .

This is an algorithm in pseudocode, but it isn’t yet an executable program. Your task will be to convert this algorithm into a working Python program.

Here are some new bits of Python that may be helpful:

Scientific notation Floats may be specified in Python with an “e” before the exponent. For example, 2.914e6 represents $2.914*{10}^6=\text{2914000}\text{.0}$ .

Absolute value Python provides the built-in function:

The reason absolute value is useful is that it gives an easy measure of how close together two numbers are: the distance between x and y is |x − y|.

One last piece of advice that addresses a question you may have already thought of. How is it possible to know how close x is to $\sqrt{k}$ without knowing the value of $\sqrt{k}$ ahead of time? In other words, how do we know when we are close enough? The answer is to compare x2 with k instead of x to $\sqrt{k}$ . This will not tell you how close x is to the actual root, but it gives you some measurement of accuracy.

Exercises

1. Write a function mysqrt(k) that uses Newton’s method to approximate $\sqrt{k}$ using an accuracy of 10 −10. Do not use the library sqrt() function. Write a program newton.py that uses your function to display the square roots of 2, 3, 4, . . . , 20.
2. Compare the results of your mysqrt(k) function with the sqrt() function in the math module.
3. Experiment with different initial guesses in your program and report the results.
4. Experiment with different values for the required accuracy and report the results.