7.2 Newton’s Method
185
functions and import the naive_Newton function from naive_Newton.py). With
|x 0 | ≤ 1.08 everything works fine. For example, x 0 = 1.08 leads to six iterations if
= 0.001:
-1.05895313436
0.989404207298
-0.784566773086
0.36399816111
-0.0330146961372
2.3995252668e-05
Adjusting x 0 slightly to 1.09 gives division by zero! The approximations computed
by Newton’s method become
-1.09331618202
1.10490354324
-1.14615550788
1.30303261823
-2.06492300238
13.4731428006
-1.26055913647e+11
The division by zero is caused by x 7 = −1.26055913647 × 10 11 , because tanh(x 7 )
is 1.0 to machine precision, and then f (x) = 1 − tanh(x) 2 becomes zero in the
denominator in Newton’s method.
The underlying problem, leading to the division by zero in the above example,
is that Newton’s method diverges: the approximations move further and further
away from x = 0. If it had not been for the division by zero, the condition in
the while loop would always be true and the loop would run forever. Divergence
of Newton’s method occasionally happens, and the remedy is to abort the method
when a maximum number of iterations is reached.
Another disadvantage of the naive_Newton function is that it calls the f (x)
function twice as many times as necessary. This extra work is of no concern when
f (x) is fast to evaluate, but in large-scale industrial software, one call to f (x) might
take hours or days, and then removing unnecessary calls is important. The solution
in our function is to store the call f(x) in a variable (f_value) and reuse the value
instead of making a new call f(x).
To summarize, we want to write an improved function for implementing
Newton’s method where we
• handle division by zero properly
• allow a maximum number of iterations
• avoid the extra evaluation of f (x)
A more robust and efficient version of the function, inserted in a complete program
(Newtons_method.py) for solving x 2 − 9 = 0, is listed below.
import sys
def Newton(f, dfdx, x, eps):
f_value = f(x)
185
functions and import the naive_Newton function from naive_Newton.py). With
|x 0 | ≤ 1.08 everything works fine. For example, x 0 = 1.08 leads to six iterations if
= 0.001:
-1.05895313436
0.989404207298
-0.784566773086
0.36399816111
-0.0330146961372
2.3995252668e-05
Adjusting x 0 slightly to 1.09 gives division by zero! The approximations computed
by Newton’s method become
-1.09331618202
1.10490354324
-1.14615550788
1.30303261823
-2.06492300238
13.4731428006
-1.26055913647e+11
The division by zero is caused by x 7 = −1.26055913647 × 10 11 , because tanh(x 7 )
is 1.0 to machine precision, and then f (x) = 1 − tanh(x) 2 becomes zero in the
denominator in Newton’s method.
The underlying problem, leading to the division by zero in the above example,
is that Newton’s method diverges: the approximations move further and further
away from x = 0. If it had not been for the division by zero, the condition in
the while loop would always be true and the loop would run forever. Divergence
of Newton’s method occasionally happens, and the remedy is to abort the method
when a maximum number of iterations is reached.
Another disadvantage of the naive_Newton function is that it calls the f (x)
function twice as many times as necessary. This extra work is of no concern when
f (x) is fast to evaluate, but in large-scale industrial software, one call to f (x) might
take hours or days, and then removing unnecessary calls is important. The solution
in our function is to store the call f(x) in a variable (f_value) and reuse the value
instead of making a new call f(x).
To summarize, we want to write an improved function for implementing
Newton’s method where we
• handle division by zero properly
• allow a maximum number of iterations
• avoid the extra evaluation of f (x)
A more robust and efficient version of the function, inserted in a complete program
(Newtons_method.py) for solving x 2 − 9 = 0, is listed below.
import sys
def Newton(f, dfdx, x, eps):
f_value = f(x)