Newton’s Method¶

Loops are often used in programs that compute numerical results by starting with an approximate answer and iteratively improving it.

For example, one way of computing square roots is Newton’s method.
Suppose that you want to know the square root of n.
If you start with almost any approximation, you can compute a better approximation with the following formula:

better =  1/2 * (approx + n/approx)

The following implementation of Newton’s method requires two parameters.

The first is the value whose square root will be approximated.
The second is the number of times to iterate the calculation yielding a better result.

def newtonSqrt(n, howmany):
    approx = 0.5 * n
    for i in range(howmany):
        betterapprox = 0.5 * (approx + n/approx)
        approx = betterapprox
    return betterapprox

print(newtonSqrt(10, 3))
print(newtonSqrt(10, 5))
print(newtonSqrt(10, 10))

(chp07_newtonsdef)

The second and third calls to newtonSqrt in the previous example both returned the same value for the square root of 10.
Using 10 iterations instead of 5 did not improve the the value.
In general, Newton’s algorithm will eventually reach a point where the new approximation is no better than the previous.
At that point, we could simply stop.

This implementation, shown in codelens, uses a while condition to execute until the approximation is no longer changing. Each time through the loop we compute a “better” approximation using the formula described earlier. As long as the “better” is different, we try again. Step through the program and watch the approximations get closer and closer.

(chp07_newtonswhile)

Note

The while statement shown above uses comparison of two floating point numbers in the condition. Since floating point numbers are themselves approximation of real numbers in mathematics, it is often better to compare for a result that is within some small threshold of the value you are looking for.