Calculus/Newton's Method
From Wikibooks, the open-content textbooks collection
Newton's Method (also called the Newton-Raphson method) is a recursive algorithm for approximating the root of a differentiable function. We know simple formulas for finding the roots of linear and quadratic equations, and there are also more complicated formulae for cubic and quartic equations. At one time it was hoped that there would be formulas found for equations of quintic and higher-degree, though it was later shown by Neils Henrik Abel that no such equations exist. The Newton-Raphson method is a method for approximating the roots of polynomial equations of any order. In fact the method works for any equation, polynomial or not, as long as the function is differentiable in a desired interval.
|
Let f(x) be a differentiable function. Select a point x1 based on a first approximation to the root, arbitrarily close to the function's root. To approximate the root you then recursively calculate using: As you recursively calculate, the xn's become increasingly better approximations of the function's root. For n number of approximations, |
In order to explain Newton's method, imagine that x0 is already very close to a zero of f(x). We know that if we only look at points very close to x0 then f(x) looks like it's tangent line. If x0 was already close to the place where f(x) was zero, and near x0 we know that f(x) looks like its tangent line, then we hope the zero of the tangent line at x0 is a better approximation then x0 itself.
The equation for the tangent line to f(x) at x0 is given by
- y = f'(x0)(x − x0) + f(x0).
Now we set y = 0 and solve for x.
- 0 = f'(x0)(x − x0) + f(x0)
- − f(x0) = f'(x0)(x − x0)
This value of x we feel should be a better guess for the value of x where f(x) = 0. We choose to call this value of x1, and a little algebra we have
If our intuition was correct and x1 is in fact a better approximation for the root of f(x), then our logic should apply equally well at x1. We could look to the place where the tangent line at x1 is zero. We call x2, following the algebra above we arrive at the formula
And we can continue in this way as long as we wish. At each step, if your current approximation is xn our new approximation will be 
[edit] Examples
Find the root of the function.
As you can see xn is gradually approaching zero (which we know is the root of f(x)). One can approach the function's root with arbitrary accuracy.
Answer:.
[edit] Notes
This method fails when f'(x) = 0. In that case, one should choose a new starting place. Occasionally it may happen that f(x) = 0 and f'(x) = 0 have a common root. To detect whether this is true, we should first find the solutions of f'(x) = 0, and then check the value of f(x) at these places.
Newton's method also may not converge for every function, take as an example:
For this function choosing any x1 = r − h then x2 = r + h would cause successive approximations to alternate back and forth, so no amount of iteration would get us any closer to the root than our first guess.
