Calculus/Newton's Method

Newton's Method

In Calculus, 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 the function is differentiable in a desired interval.

Newton's Method Let $f(x)$ be a differentiable function. Select a point $x_1$ based on a first approximation to the root, arbitrarily close to the function's root. To approximate the root you then recursively calculate using: $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$ As you recursively calculate, the $x_n$'s become increasingly better approximations of the functions root. For n number of approximations, $x_n=x_0-\sum _{i=0}^n\frac{f(x_i)}{f^{\prime }(x_i)}$

Examples

Find the root of the function $f(x)=x^2$.

$x_1=f(2)=4$

$x_2=x_1-\frac{f(x_1)}{f^{\prime }(x_1)}=2$

$x_3=x_2-\frac{f(x_2)}{f^{\prime }(x_2)}=1$

$x_4=x_3-\frac{f(x_3)}{f^{\prime }(x_3)}=\frac{1}{2}$

$x_5=x_4-\frac{f(x_4)}{f^{\prime }(x_4)}=\frac{1}{4}$

$x_6=x_5-\frac{f(x_5)}{f^{\prime }(x_5)}=\frac{1}{8}$

$x_7=x_6-\frac{f(x_6)}{f^{\prime }(x_6)}=\frac{1}{16}$

$x_8=x_7-\frac{f(x_7)}{f^{\prime }(x_7)}=\frac{1}{32}$

As you can see $x_n$ is gradually approaching zero (which we know is the root of f(x)). One can approach the function's root with arbitrary accuracy.

Answer: $f(x)=x^2$ has a root at $x=0$.

Notes

This method fails when $f^{\prime }(x)=0$. In that case, one should choose a new starting place. Occasionally it may happen that $f(x)=0$ and $f^{\prime }(x)=0$ have a common root. To detect whether this is true, we should first find the solutions of $f^{\prime }(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:

$f(x)=\{\begin{array}{cc}\sqrt{x-r},& \text{for}x\ge r\\ -\sqrt{r-x},& \text{for}x\le r\end{array}$

For this function choosing any $x_1=r-h$ then $x_2=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.

See Also

• Wikipedia:Newton-raphson method
• Wikipedia:Abel-Ruffini theorem