Newton-Raphson method is a recursive algorithm for approximating the root of a differentiable function. We know simple formulas for finding the roots of linear and quadratic equations, and there are also more complicated formulae for cubic and quartic equations. The Newton-Raphson method is a method for approximating the roots of polynomial equations of any order. In fact the method works for any equation, polynomial or not, as long as the function is differentiable in a desired interval.
The idea of the method is as follows: one starts with an initial guess which is reasonably close to the true root, then the function is approximated by its tangent line , and one computes the x-intercept of this tangent line . This x-intercept will typically be a better approximation to the function’s root than the original guess, and the method can be iterated. (Show in formulas below)
Suppose ƒ : [a, b] → R is a differentiable function defined on the interval [a, b] with values in the real numbers R. The formula for converging on the root can be easily derived. Suppose we have some current approximation xn. Then we can derive the formula for a better approximation, xn+1. The equation of the tangent line to the curve y = ƒ(x) at the point x=xn : y = f’(xn) (x- xn) + f(xn) where, ƒ’ denotes the derivative of the function ƒ. The x-intercept of this line (the value of x such that y=0) is then used as the next approximation to the root, xn+1.
In other words, setting y to zero and x to xn+1 gives 0 = f’(xn) (x- xn) + f(xn)
Solving for xn+1 gives, xn+1 = xn – f(xn) / f’(xn)
Proof of quadratic convergence for Newton’s iterative method:
According to Taylor’s theorem, any function f(x) which has a continuous second derivative can be represented by an expansion about a point that is close to a root of f(x). Suppose this root is Then the expansion of f(α) about xn is
where ξn is in between xn and a. Since is the root, (1) becomes:
Generalizations - Newton Fractal: When dealing with complex functions, Newton’s method can be directly applied to find their zeroes. Each zero has a basin of attraction in the complex plane, the set of all starting values that cause the method to converge to that particular zero. These sets can be mapped as in the image shown. For many complex functions, the boundaries of the basins of attraction are fractals.
- Newton fractal for three degree-3 roots P(z) = z^3 - 1, coloured by root reached. (A Julia set for the rational function associated to Newton’s method for f : z→z3−1. Coloring of Fatou set according to attractor, the roots of f)
- Newton fractal for P(z) = z^3 +2z +2 . Points in the red basins do not reach a root.
- Newton fractal for P(z) = z^5 - 3iz^3 -(5+2i)z^2, coloured by root reached, shaded by number of iterations required.
Image: Fractal de Newton