Newton's method: Difference between revisions

Revision as of 23:53, 20 May 2007

Revision as of 03:32, 25 May 2007

Line 4:

==Description of the method==

The idea of the method is as follows: one starts with an initial estimateguess which is reasonably close to the true root, then replaces the function is approximated by its [[tangent line]] (which can be computed using the tools of [[calculus]]), and one computes the ''x''-intercept of this tangent line (which is easily done with elementary algebra). This ''x''-intercept will typically be a better approximation to the function's root than the original guess, and the method can be [[iterative method|iterated]].

Suppose ''f'' : [''a'', ''b''] → '''R''' is a [[derivative|differentiable]] function defined on the [[interval (mathematics)|interval]] [''a'', ''b''] with values in the [[real number]]s '''R'''. The formula for converging on the root can be easily derived. Suppose we have some current approximation ''x''_n. Then we can derive the formula for a better approximation, ''x''_n+1 by referring to the diagram below.

The formula for converging on the root can be easily derived. Suppose we have some current approximation ''x''_n. Then we can derive the formula for a better approximation, ''x''_n+1 by referring to the diagram below.

We know from the definition of the derivative at a given point that it is the slope of a tangent at that point.

[[Image:newton_iteration.png|alt Illustration of Newton's method|thumb|right|300px|An illustration of one iteration of Newton's method (the function ''f'' is shown in blue and the tangent line is in red). We see that <math>x_{n+1}</math> is a better approximation than <math>x_n</math> for the zeroroot <math>x</math> of the function <math>f</math>.]]

That is

:<math>f'(x_{n}) = \frac{ \mathrm{rise} }{ \mathrm{run} } = \frac{ f( x_{n} ) - 0 }{ x_{n} - x_{n+1} } = \frac{0 - f(x_{n})}{(x_{n+1} - x_{n})}\,\!</math>.