Predictive Hacks

Newton-Raphson Method in Python

newton raphson method

The Newton-Raphson Method is a simple algorithm to find an approximate solution for the root of a real-valued function \(f(x)=0\). If the function \(f\) satisfies sufficient assumptions then after repeative steps the \(x_{n+1}\):

\(x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)}\)

will be a good approximation to the root.

Newton-Raphson Method in Python 1

Failure of the method to converge to the root

It is important to review the proof of quadratic convergence of Newton’s method before implementing it. Specifically, one should review the assumptions made in the proof. For situations where the method fails to converge, it is because the assumptions made in this proof are not met.


Calculate Derivatives in Python

The Newton-Raphson Method requires to calculate the first derivative of the function \(f\). This can be done with the SymPy library. Let’s provide an example by funding the first derivative of the function \(f(x) = x^2-4 \times x-5\)


import numpy as np
from sympy import *

# define what is the variable
x = symbols('x')

# define the function
f = x**2-4*x-5

# find the first derivative
fderivative = f.diff(x)
fderivative
 
2x-4
# get a valua of the derivate for a specific x
# let's say f'(0)

fderivative.evalf(subs= {x:0})
 
-4

Newton-Raphson Method

Since we calculate defined the function \(f(x)\) and the derivative \(f'(x)\) we are in a position to apply the simple Newton-Raphson Method.

We will start with \(x_0=1\):

xn = 1
for i in range(10):
    xn = xn - np.float(f.evalf(subs= {x:xn})) / np.float(fderivative.evalf(subs= {x:xn}))
    print(f'The {i+1} iteration xn is {xn:.2} and f(xn) is {np.float(f.evalf(subs= {x:xn})):.2}')
  
The 1 iteration xn is -3.0 and f(xn) is 1.6e+01
The 2 iteration xn is -1.4 and f(xn) is 2.6
The 3 iteration xn is -1.0 and f(xn) is 0.14
The 4 iteration xn is -1.0 and f(xn) is 0.00055
The 5 iteration xn is -1.0 and f(xn) is 8.4e-09
The 6 iteration xn is -1.0 and f(xn) is 9.5e-125
The 7 iteration xn is -1.0 and f(xn) is 9.5e-125
The 8 iteration xn is -1.0 and f(xn) is 9.5e-125
The 9 iteration xn is -1.0 and f(xn) is 9.5e-125
The 10 iteration xn is -1.0 and f(xn) is 9.5e-125

As we can see at the third iteration it found an approximate solution which is correct since \(f(-1) = 0\).


Issues with the Newton-Raphson Solutions

The algorithm found a solution but it does not mean that this solution is unique. Actually it found the closest one. Let’s see what we would get if we had chosen as a starting point the \(x_0=10\)

xn = 10
for i in range(10):
    xn = xn - np.float(f.evalf(subs= {x:xn})) / np.float(fderivative.evalf(subs= {x:xn}))
    print(f'The {i+1} iteration xn is {xn:.2} and f(xn) is {np.float(f.evalf(subs= {x:xn})):.2}')
  

The 1 iteration xn is 6.6 and f(xn) is 1.2e+01
The 2 iteration xn is 5.3 and f(xn) is 1.7
The 3 iteration xn is 5.0 and f(xn) is 0.066
The 4 iteration xn is 5.0 and f(xn) is 0.00012
The 5 iteration xn is 5.0 and f(xn) is 4e-10
The 6 iteration xn is 5.0 and f(xn) is 3.8e-124
The 7 iteration xn is 5.0 and f(xn) is 3.8e-124
The 8 iteration xn is 5.0 and f(xn) is 3.8e-124
The 9 iteration xn is 5.0 and f(xn) is 3.8e-124
The 10 iteration xn is 5.0 and f(xn) is 3.8e-124

As we can see at the third iteration it found the other approximate solution which is correct since \(f(5) = 0\).

Share This Post

Share on facebook
Share on linkedin
Share on twitter
Share on email

Leave a Comment

Subscribe To Our Newsletter

Get updates and learn from the best

More To Explore

data science journey
Miscellaneous

My Journey as a Data Science Blogger

Μy Background My Studies Back in 2001, I entered university to study Statistics. During my first year, I ran my