Newton's method
Newton's method provides a way for finding the real zeros of a function. This algorithm is sometimes called the Newton–Raphson method, named after Sir Isaac Newton and Joseph Raphson.
The method uses the derivative of the function in order to find its roots. An initial "guess value" for the location of the zero must be made. From this value, a new guess is calculated by this formula:
[math]\displaystyle{ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} }[/math]
Here xn is the initial guess and xn+1 is the next guess. The function f (whose zero is being solved for) has the derivative f'.
By repeatedly applying this formula to the generated guesses (that is by setting the value of xn to the formula's output and recomputing), the value of the guesses will approach a zero of the function.
Newton's method can be explained graphically by looking at intersections of tangent lines with the x-axis. First, a line tangent to the f at xn is calculated. Next, the intersection between this tangent line and the x-axis is found. Finally, the x-position of this intersection is recorded as the next guess, xn+1.
Problems with Newton's Method
Newton's method can find a solution quickly if the guess value begins sufficiently near the desired root. However, when the initial guess value is not close, and depending on the function, Newton's method may find the answer slowly or not at all.
Further reading
- Fernández, J. A. E., & Verón, M. Á. H. (2017). Newton’s method: An updated approach of Kantorovich’s theory. Birkhäuser.
- Peter Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms, Second printed edition. Series Computational Mathematics 35, Springer (2006)
- Yamamoto, T. (2001). "Historical Developments in Convergence Analysis for Newton's and Newton-like Methods". In Brezinski, C.; Wuytack, L. (eds.). Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241–263.
Newton's Method Media
x'n+1 is a better approximation than x'n for the root x of the function f (blue curve)
The tangent lines of x3 − 2x + 2 at 0 and 1 intersect the x-axis at 1 and 0 respectively, illustrating why Newton's method oscillates between these values for some starting points.
Basins of attraction for x5 − 1 = 0; darker means more iterations to converge.
Related pages
- Kantorovich theorem (Statement about the convergence of Newton's method, found by Leonid Kantorovich)