In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valued function. The most basic version starts with a real-valued function f, its derivative f′, and an initial guess x0 for a root of f. If f satisfies certain assumptions and the initial guess is close, then
x 1 = x 0 − f ( x 0 ) f ′ ( x 0 ) {\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}}
is a better approximation of the root than x0. Geometrically, (x1, 0) is the x-intercept of the tangent to the graph of f at (x0, f(x0)): that is, the improved guess, x1, is the unique root of the linear approximation of f at the initial guess, x0. The process is repeated as
x n + 1 = x n − f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}
until a sufficiently precise value is reached. The number of correct digits roughly doubles with each step. This algorithm is first in the class of Householder's methods, and was succeeded by Halley's method. The method can also be extended to complex functions and to systems of equations.
Description The purpose of Newton's method is to find a root of a function. The idea is to start with an initial guess near a root, approximate the function by its tangent line near the guess, and then take the root of the linear approximation as a next guess at the function's root. This will typically be closer to the function's root than the previous guess, and the method can be iterated.
The best linear approximation to an arbitrary differentiable function f ( x ) {\displaystyle f(x)} near the point x = x n {\displaystyle x=x_{n}} is the tangent line to the curve, with equation
f ( x ) ≈ f ( x n ) + f ′ ( x n ) ( x − x n ) . {\displaystyle f(x)\approx f(x_{n})+f'(x_{n})(x-x_{n}).}
The root of this linear function, the place where it intercepts the x {\displaystyle x} -axis, can be taken as a closer approximate root x n + 1 {\displaystyle x_{n+1}} if f ′ ( x n ) ≠ 0 {\displaystyle f'(x_{n})\neq 0} :
x n + 1 = x n − f ( x n ) f ′ ( x n ) . {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.}
The process can be started with any arbitrary initial guess x 0 {\displaystyle x_{0}} , though it will generally require fewer iterations to converge if the guess is close to one of the function's roots. The method will usually converge if f ′ ( x 0 ) ≠ 0 {\displaystyle f'(x_{0})\neq 0} . Furthermore, for a root of multiplicity 1, the convergence is at least quadratic (see Rate of convergence) in some sufficiently small neighbourhood of the root: the number of correct digits of the approximation roughly doubles with each additional step. More details can be found in § Analysis below. Householder's methods are similar but have higher order for even faster convergence. However, the extra computations required for each step can slow down the overall performance relative to Newton's method, particularly if f {\displaystyle f} or its derivatives are computationally expensive to evaluate.
… excerpt ends here. Continue reading the full article.
