Newton's Method

Newton's method, also called the Newton-Raphson method, is a root-finding algorithm that uses the first few terms of the Taylor series of a function in the vicinity of a suspected root. Newton's method is sometimes also known as Newton's iteration, although in this work the latter term is reserved to the application of Newton's method for computing square roots.

For a polynomial, Newton's method is essentially the same as Horner's method.

The Taylor series of about the point is given by

(1)

Keeping terms only to first order,

(2)

Equation (2) is the equation of the tangent line to the curve at , so is the place where that tangent line intersects the -axis. A graph can therefore give a good intuitive idea of why Newton's method works at a well-chosen starting point and why it might diverge with a poorly-chosen starting point.

This expression above can be used to estimate the amount of offset needed to land closer to the root starting from an initial guess . Setting and solving (2) for gives

(3)

which is the first-order adjustment to the root's position. By letting , calculating a new , and so on, the process can be repeated until it converges to a fixed point (which is precisely a root) using

(4)

Unfortunately, this procedure can be unstable near a horizontal asymptote or a local extremum. However, with a good initial choice of the root's position, the algorithm can be applied iteratively to obtain

(5)

for , 2, 3, .... An initial point that provides safe convergence of Newton's method is called an approximate zero.

Newton's method can be implemented in the Wolfram Language as

  NewtonsMethodList[f_, {x_, x0_}, n_] :=
    NestList[# - Function[x, f][#]/
      Derivative[1][Function[x, f]][#]& , x0, n]

Assume that Newton's iteration converges toward with , and define the error after the th step by

(6)

Expanding about gives

			(7)
			(8)
			(9)

But

			(10)
			(11)
			(12)

Taking the second-order expansion

(13)

gives

(14)

Therefore, when the method converges, it does so quadratically.

Applying Newton's method to the roots of any polynomial of degree two or higher yields a rational map of , and the Julia set of this map is a fractal whenever there are three or more distinct roots. Iterating the method for the roots of with starting point gives

(15)

(Mandelbrot 1983, Gleick 1988, Peitgen and Saupe 1988, Press et al. 1992, Dickau 1997). Since this is an th order polynomial, there are roots to which the algorithm can converge. Coloring the basin of attraction (the set of initial points that converge to the same root) for each root a different color then gives the above plots.

Fractals typically arise from non-polynomial maps as well. The plot above shows the number of iterations needed for Newton's method to converge for the function (D. Cross, pers. comm., Jan. 10, 2005) and .