Consider the function $$ f(x) = x^2 - a $$ The roots are $\pm \sqrt{a}$. The Newton method is $$ x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right) $$
from math import sqrt
a = 2.0
r = sqrt(a)
Define the function and its derivative.
def f(x):
return x**2 - a
def df(x):
return 2.0*x
Now implement Newton method as a function.
def newton(f,df,x0,M=100,eps=1.0e-15):
x = x0
for i in range(M):
dx = - f(x)/df(x)
x = x + dx
print('%3d %20.14f %20.14e %20.14e'%(i,x,x-r,abs(f(x))))
if abs(dx) < eps * abs(x):
return x
print('No convergence, current root = %e' % x)
We call Newton method with a complex initial guess for the root.
x0 = 2.0
x = newton(f,df,x0)
0 1.50000000000000 8.57864376269049e-02 2.50000000000000e-01 1 1.41666666666667 2.45310429357160e-03 6.94444444444464e-03 2 1.41421568627451 2.12390141474117e-06 6.00730488287127e-06 3 1.41421356237469 1.59472435257157e-12 4.51061410444709e-12 4 1.41421356237310 0.00000000000000e+00 4.44089209850063e-16 5 1.41421356237309 -2.22044604925031e-16 4.44089209850063e-16
From the last column, we observe that in each iteration, the number of correct decimal places doubles.