7.2 Newton’s Method
183
With x 0 = 1000, we get x 1 ≈ 500, which is in accordance with the graph in Fig. 7.1.
Repeating the process, we get
x 2 = x 1 −
f (x 1 )
f (x 1 )
≈ 250 .
The general scheme 2 of Newton’s method may be written as
x n+1 = x n −
f (x n )
f (x n )
, n = 0, 1, 2, . . .
(7.1)
The computation in (7.1) is repeated until f (x n ) is close enough to zero. More
precisely, we test if |f (x n )| < <, with being a small number.
We moved from 1000 to 250 in two iterations, so it is exciting to see how
fast we can approach the solution x = 3. A computer program can automate
the calculations. Our first try at implementing Newton’s method is in a function
naive_Newton (found in naive_Newton.py):
def naive_Newton(f, dfdx, x, eps):
while abs(f(x)) > eps:
x = x - (f(x))/dfdx(x)
return x
The argument x is the starting value, called x 0 in our previous mathematical
description.
To solve the problem x 2 = 9 we also need to implement
def f(x):
return x**2 - 9
def dfdx(x):
return 2*x
print(naive_Newton(f, dfdx, 1000, 0.001))
which in naive_Newton.py is included by use of an extra function and a test block.
2 The term scheme is often used as a synonym for method or computational recipe.