Convergence of Newton's Method

In [4]:
import numpy as np
import matplotlib.pyplot as pt
In [5]:
def f(x):
    return np.exp(x) - 2

def df(x):
    return np.exp(x)
In [8]:
xgrid = np.linspace(-2, 3, 1000)
pt.grid()
pt.plot(xgrid, f(xgrid))
Out[8]:
[<matplotlib.lines.Line2D at 0x7fec13f69048>]

What's the true solution of $f(x)=0$?

In [9]:
xtrue = np.log(2)
print(xtrue)
print(f(xtrue))
0.69314718056
0.0

Now let's run Newton's method and keep track of the errors:

In [18]:
errors = []
x = 2

At each iteration, print the current guess and the error.

In [24]:
x = x - f(x)/df(x)
print(x)
errors.append(abs(x-xtrue))
print(errors[-1])
0.69314718056
0.0
In [25]:
for err in errors:
    print(err)
0.577523385913
0.13881012318
0.00920340345722
4.22216905669e-05
8.91323015395e-10
0.0
  • Do you have a hypothesis about the order of convergence?
In [27]:
# Doubles number of digits each iteration: probably quadratic.

Let's check:

In [26]:
for i in range(len(errors)-1):
    print(errors[i+1]/errors[i]**2)
0.416180751055
0.47764604026
0.498469622214
0.499992953401
0.0
In [ ]: