Newton's method, also known as the Newton-Raphson method, uses an iterative procedure to solve for a root using information about the derivative of a function. The derivative is treated as a linear problem to be solved. The first-order derivation of the function represents the tangent line. The approximation to the next value of , given as , is as follows:
Here, the tangent line intersects the axis at , which produces . This also represents the first-order Taylor expansion about such that that the new point solves the following equation:
This process is repeated with taking the value of until the maximum number of iterations is reached, or the absolute difference between and is within an acceptable accuracy level.
An initial guess value is required to compute the values of and . The rate of convergence is quadratic, which is considered to be extremely fast in obtaining the solution with high levels of accuracy.
The drawback to Newton's method is that it does not guarantee global convergence to the solution. Such a situation arises when the function contains more than one root, or when the algorithm arrives at a local extremum and is unable to compute the next step. As this method requires knowledge of the derivative of its input function, it is required that the input function be differentiable. However, in certain circumstances, it is impossible for the derivative of a function to be known, or otherwise be mathematically easy to compute.
A graphical representation of Newton's method is shown in the following screenshot. is the initial value. The derivative of is evaluated, which is a tangent line crossing the axis at . The iteration is repeated, evaluating the derivative at points , , , and so on.
The implementation of Newton's method in Python is as follows:
""" The Newton-Raphson method """ def newton(f, df, x, tol=0.001, maxiter=100): """ :param f: The function to solve :param df: The derivative function of f :param x: Initial guess value of x :param tol: The precision of the solution :param maxiter: Maximum number of iterations :return: The x-axis value of the root, number of iterations used """ n = 1 while n <= maxiter: x1 = x - f(x)/df(x) if abs(x1 - x) < tol: # Root is very close return x1, n else: x = x1 n += 1 return None, n
We will use the same function used in the bisection example and take a look at the results from Newton's method:
>>> y = lambda x: x**3 + 2*x**2 - 5 >>> dy = lambda x: 3*x**2 + 4*x >>> root, iterations = newton(y, dy, 5.0, 0.00001, 100) >>> print "Root is:", root >>> print "Iterations:", iterations Root is: 1.24189656303 Iterations: 7
With Newton's method, we obtained a really close solution with less iteration over the bisection method.