Newton’s method (1D)

Newton’s method is a rather popular iterative root finding algorithm. Starting at an initial guess \(x_0\) it tries to find better and better approximations of the root of a function \(f(x)\). For this it uses the first derivative \(f'(x)\) of the function. The process

\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

is repeated until a value \(f(x_n)\) is reached that is within a predefined tolerance to zero. For further information see the Wikipedia page.

The way it is supposed to work is as follows:

>>> def f(x):
...     return x**2 - 2
...
>>> def df_dx(x):
...     return 2*x
...
>>> newtons_method_1d(f, df_dx, x0=4, tol=1e-8)  
1.4142135623730951

Hence, implement a function following the given definition:

newtons_method_1d(f, df_dx, x0, tol)

Return the root of f within tol by using Newton’s method.

Parameters:
  • f (callable[[float], float]) – The function of which the root should be found.
  • df_dx (callable[[float], float]) – The derivative of f.
  • x_0 (float) – The initial guess for the algorithm.
  • tol (float) – The tolerance of the method.
Returns:

The root of f within a tolerance of tol.

Return type:

float

Start by downloading the exercise template and editing this file. You can run tests via

$ python newtons_method_1d.py test

to check whether you got a correct solution. You can also take a look at one possible solution.