Editing Newton's method (section)

== Description ==

The purpose of Newton's method is to find a root of a function. The idea is to start with an initial guess at 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 [[iterative method|iterated]].

[[Image:newton iteration.svg|alt=Illustration of Newton's method|thumb|right|upright=1.4|{{math|{{var|x}}{{sub|{{var|n}}+1}}}} is a better approximation than {{math|{{var|x}}{{sub|{{var|n}}}}}} for the root {{mvar|x}} of the function {{mvar|f}} (blue curve)]]

The best [[linear approximation]] to an arbitrary [[differentiable function]] <math>f(x)</math> near the point <math>x = x_{n}</math> is the tangent line to the curve, with equation

<math display="block">
f(x) \approx f(x_{n}) + f'(x_{n})(x - x_{n}).
</math>

The root of this linear function, the place where it intercepts the {{tmath|x}}-axis, can be taken as a closer approximate root {{tmath|x_{n+1} }}:

<math display="block">
x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.
</math>

[[Image:NewtonIteration Ani.gif|alt=Illustration of Newton's method|thumb|right|upright=1.4|Iteration typically improves the approximation]]

The process can be started with any arbitrary initial guess {{tmath|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 {{tmath|f'(x_0) \neq 0}}. Furthermore, for a root of [[Multiplicity (mathematics)|multiplicity]]&nbsp;1, the convergence is at least quadratic (see ''[[Rate of convergence]]'') in some sufficiently small [[neighbourhood (mathematics)|neighbourhood]] of the root: the number of correct digits of the approximation roughly doubles with each additional step. More details can be found in ''{{section link|#Analysis}}'' below.

[[Householder's method]]s 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 {{tmath|f}} or its derivatives are computationally expensive to evaluate.