TOPICS
Search

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 f(x) 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 f(x) a polynomial, Newton's method is essentially the same as Horner's method.

The Taylor series of f(x) about the point x=x_0+epsilon is given by

 f(x_0+epsilon)=f(x_0)+f^'(x_0)epsilon+1/2f^('')(x_0)epsilon^2+....
(1)

Keeping terms only to first order,

 f(x_0+epsilon) approx f(x_0)+f^'(x_0)epsilon.
(2)

Equation (2) is the equation of the tangent line to the curve at (x_0,f(x_0)), so (x_1,0) is the place where that tangent line intersects the x-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 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=epsilon_0 gives

 epsilon_0=-(f(x_0))/(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 fixed point (which is precisely a root) using

 epsilon_n=-(f(x_n))/(f^'(x_n)).
(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

 x_(n+1)=x_n-(f(x_n))/(f^'(x_n))
(5)

for n=1, 2, 3, .... An initial point x_0 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 x_(k+1) converges toward x^* with f^'(x^*)!=0, and define the error after the kth step by

 x_k=x^*+epsilon_k.
(6)

Expanding f(x_k) about x^* gives

f(x_k)=f(x^*)+f^'(x^*)epsilon_k+1/2f^('')(x^*)epsilon_k^2+...
(7)
=f^'(x^*)epsilon_k+1/2f^('')(x^*)epsilon_k^2+...
(8)
f^'(x_k)=f^'(x^*)+f^('')(x^*)epsilon_k+....
(9)

But

epsilon_(k+1)=epsilon_k+(x_(k+1)-x_k)
(10)
=epsilon_k-(f(x_k))/(f^'(x_k))
(11)
 approx epsilon_k-(f^'(x^*)epsilon_k+1/2f^('')(x^*)epsilon_k^2)/(f^'(x^*)+f^('')(x^*)epsilon_k).
(12)

Taking the second-order expansion

 (aepsilon+1/2bepsilon^2+cepsilon^3)/(a+bepsilon+depsilon^2) approx epsilon-b/(2a)epsilon^2
(13)

gives

 epsilon_(k+1) approx (f^('')(x^*))/(2f^'(x^*))epsilon_k^2.
(14)

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

NewtonsMethodBasins

Applying Newton's method to the roots of any polynomial of degree two or higher yields a rational map of C, 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 z^n-1=0 with starting point z_0 gives

 z_(i+1)=z_i-(z_i^n-1)/(nz_i^(n-1))
(15)

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

NewtonsMethodCross

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 z^2-2^z (D. Cross, pers. comm., Jan. 10, 2005) and z^3-3^z.


See also

Alpha-Test, Approximate Zero, Fixed Point, Halley's Irrational Formula, Halley's Method, Horner's Method, Householder's Method, Laguerre's Method, Newton's Iteration, Newtonian Vector Field, Root-Finding Algorithm Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. 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.Boyer, C. B. and Merzbacher, U. C. A History of Mathematics, 2nd ed. New York: Wiley, 1991.Dickau, R. M. "Basins of Attraction for z^5=1 Using Newton's Method in the Complex Plane." http://mathforum.org/advanced/robertd/newtons.html.Dickau, R. M. "Variations on Newton's Method." http://mathforum.org/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 p. 114) and p. 220, 1988.Gourdon, X. and Sebah, P. "Newton's Iteration." http://numbers.computation.free.fr/Constants/Algorithms/newton.html.Householder, A. S. Principles of Numerical Analysis. New York: McGraw-Hill, pp. 135-138, 1953.Mandelbrot, B. B. The Fractal Geometry of Nature. San Francisco, CA: W. H. Freeman, 1983.Newton, I. Methodus fluxionum et serierum infinitarum. 1664-1671.Ortega, J. M. and Rheinboldt, W. C. Iterative Solution of Nonlinear Equations in Several Variables. Philadelphia, PA: SIAM, 2000.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.Raphson, J. Analysis aequationum universalis. London, 1690.Smale, S. "On the Efficiency of Algorithms of Analysis." Bull. Amer. Math. Soc. 13, 87-121, 1985.Varona, J. L. "Graphic and Numerical Comparison Between Iterative Methods." Math. Intell. 24, 37-46, 2002.Whittaker, E. T. and Robinson, G. "The Newton-Raphson Method." §44 in The Calculus of Observations: A Treatise on Numerical Mathematics, 4th ed. New York: Dover, pp. 84-87, 1967.

Referenced on Wolfram|Alpha

Newton's Method

Cite this as:

Weisstein, Eric W. "Newton's Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NewtonsMethod.html

Subject classifications