Newton's Method

A Root-finding Algorithm which uses the first few terms of the Taylor Series in the vicinity of a suspected Root to zero in on the root. The Taylor Series of a function $f(x)$ about the point $x+\epsilon$ is given by

$$f(x+\epsilon)=f(x)+f'(x)\epsilon+{\textstyle{1\over 2}}f''(x)\epsilon^2+\ldots.$$ (1)

Keeping terms only to first order,

$$f(x+\epsilon)\approx f(x)+f'(x)\epsilon.$$ (2)

This expression can be used to estimate the amount of offset $\epsilon$ needed to land closer to the root starting from an initial guess $x_0$. Setting $f(x_0+\epsilon)=0$ and solving (2) for $\epsilon$ gives

$$\epsilon_0=-{f(x_0)\over f'(x_0)},$$ (3)

which is the first-order adjustment to the Root's position. By letting $x_1=x_0+\epsilon_0$, calculating a new $\epsilon_1$, and so on, the process can be repeated until it converges to a root.

Unfortunately, this procedure can be unstable near a horizontal Asymptote or a Local Minimum. However, with a good initial choice of the Root's position, the algorithm can by applied iteratively to obtain

$$x_{n+1} = x_n - {f(x_n)\over f'(x_n)}$$ (4)

for $n = 1$, 2, 3, ....

The error $\epsilon_{n+1}$ after the $(n+1)$st iteration is given by

$$\epsilon_{n+1} = \epsilon_n+(x_{n+1}-x_n)$$

$$= \epsilon_n-{f(x_n)\over f'(x_n)}.$$ (5)

But

$$f(x_n) = f(x)+f'(x)\epsilon_n+{\textstyle{1\over 2}}f''(x){\epsilon_n}^2+\ldots$$

$$= f'(x)\epsilon_n+{\textstyle{1\over 2}}f''(x){\epsilon_n}^2+\ldots$$ (6)

$$f'(x_n) = f'(x)+f''(x)\epsilon_n+\ldots,$$ (7)

so

$${f(x_n)\over f'(x_x)} = {f'(x)\epsilon_n+{\textstyle{1\over 2}}f''(x){\epsilon_n}^2+\ldots \over f'(x)+f''(x)\epsilon_n+\ldots}$$

$$\approx {f'(x)\epsilon+{\textstyle{1\over 2}}f''(x){\epsilon_n}^2\over f'(x)+f''(x)\epsilon_n} = \epsilon_n+{f''(x)\over 2f'(x)} {\epsilon_n}^2,$$ (8)

and (5) becomes

$$\epsilon_{n+1}=\epsilon_n-\left[{\epsilon_n+{f''(x)\over 2f'... ... {\epsilon_n}^2}\right]= -{f''(x)\over 2f'(x)} {\epsilon_n}^2.$$ (9)

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

A Fractal is obtained by applying Newton's method to finding a Root of $z^n-1=0$ (Mandelbrot 1983, Gleick 1988, Peitgen and Saupe 1988, Press et al. 1992, Dickau 1997). Iterating for a starting point $z_0$ gives

$$z_{i+1}=z_i-{{z_i}^n-1\over n {z_i}^{n-1}}.$$ (10)

Since this is an $n$th order Polynomial, there are $n$ Roots to which the algorithm can converge.

Coloring the Basin of Attraction (the set of initial points $z_0$ which converge to the same Root) for each Root a different color then gives the above plots, corresponding to $n=2$, 3, 4, and 5.

See also Halley's Irrational Formula, Halley's Method, Householder's Method, Laguerre's Method

References

Abramowitz, M. and Stegun, C. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 18, 1972.

Acton, F. S. Ch. 2 in Numerical Methods That Work. Washington, DC: Math. Assoc. Amer., 1990.

Arfken, G. Mathematical Methods for Physicists, 3rd ed. Orlando, FL: Academic Press, pp. 963-964, 1985.

Dickau, R. M. ``Basins of Attraction for $z^5=1$ Using Newton's Method in the Complex Plane.'' http://forum.swarthmore.edu/advanced/robertd/newtons.html.

Dickau, R. M. ``Variations on Newton's Method.'' http://forum.swarthmore.edu/advanced/robertd/newnewton.html.

Dickau, R. M. ``Compilation of Iterative and List Operations.'' Mathematica J. 7, 14-15, 1997.

Gleick, J. Chaos: Making a New Science. New York: Penguin Books, plate 6 (following pp. 114) and p. 220, 1988.

Householder, A. S. Principles of Numerical Analysis.ew York: McGraw-Hill, pp. 135-138, 1953.

Mandelbrot, B. B. The Fractal Geometry of Nature. San Francisco, CA: W. H. Freeman, 1983.

Ortega, J. M. and Rheinboldt, W. C. Iterative Solution of Nonlinear Equations in Several Variables. New York: Academic Press, 1970.

Peitgen, H.-O. and Saupe, D. The Science of Fractal Images. New York: Springer-Verlag, 1988.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Newton-Raphson Method Using Derivatives'' and ``Newton-Raphson Methods for Nonlinear Systems of Equations.'' §9.4 and 9.6 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 355-362 and 372-375, 1992.

Ralston, A. and Rabinowitz, P. §8.4 in A First Course in Numerical Analysis, 2nd ed. New York: McGraw-Hill, 1978.