Calculus/Newton's Method

 ← Extrema and Points of Inflection Calculus Related Rates → Newton's Method

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.

 Newton's Method Let ${\displaystyle f(x)}$ be a differentiable function. Select a point ${\displaystyle x_{0}}$ based on a first approximation to the root, arbitrarily close to the function's root. To approximate the root you then recursively calculate using: ${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}$ As you recursively calculate, the ${\displaystyle x_{n+1}}$'s often become increasingly better approximations of the function's root.

In order to explain Newton's method, imagine that ${\displaystyle x_{0}}$ is already very close to a 0 of ${\displaystyle f(x)}$ . We know that if we only look at points very close to ${\displaystyle x_{0}}$ then ${\displaystyle f(x)}$ looks like its tangent line. If ${\displaystyle x_{0}}$ was already close to the place where ${\displaystyle f(x)}$ was 0, and near ${\displaystyle x_{0}}$ we know that ${\displaystyle f(x)}$ looks like its tangent line, then we hope the 0 of the tangent line at ${\displaystyle x_{0}}$ is a better approximation then ${\displaystyle x_{0}}$ itself.

The equation for the tangent line to ${\displaystyle f(x)}$ at ${\displaystyle x_{0}}$ is given by

${\displaystyle y=f'(x_{0})\cdot (x-x_{0})+f(x_{0})}$

Now we set ${\displaystyle y=0}$ and solve for ${\displaystyle x}$ .

${\displaystyle 0=f'(x_{0})\cdot (x-x_{0})+f(x_{0})}$
${\displaystyle -f(x_{0})=f'(x_{0})\cdot (x-x_{0})}$
${\displaystyle {\frac {-f(x_{0})}{f'(x_{0})}}=(x-x_{0})}$
${\displaystyle x={\frac {-f(x_{0})}{f'(x_{0})}}+x_{0}}$

This value of ${\displaystyle x}$ we feel should be a better guess for the value of ${\displaystyle x}$ where ${\displaystyle f(x)=0}$ . We choose to call this value of ${\displaystyle x_{1}}$ , and a little algebra we have

${\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}}$

If our intuition was correct and ${\displaystyle x_{1}}$ is in fact a better approximation for the root of ${\displaystyle f(x)}$ , then our logic should apply equally well at ${\displaystyle x_{1}}$ . We could look to the place where the tangent line at ${\displaystyle x_{1}}$ is zero. We call ${\displaystyle x_{2}}$ , following the algebra above we arrive at the formula

${\displaystyle x_{2}=x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}}$

And we can continue in this way as long as we wish. At each step, if your current approximation is ${\displaystyle x_{n}}$ our new approximation will be ${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}$ .

Examples

Find the root of the function ${\displaystyle f(x)=x^{2}}$ .

Figure 1: A few iterations of Newton's method applied to ${\displaystyle y=x^{2}}$ starting with ${\displaystyle x_{0}=4}$ . The blue curve is ${\displaystyle f(x)}$ . The other solid lines are the tangents at the various iteration points.

{\displaystyle {\begin{aligned}x_{0}&=&4\\x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}=4-{\frac {16}{8}}=2\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}=2-{\frac {4}{4}}=1\\x_{3}&=&x_{2}-{\frac {f(x_{2})}{f'(x_{2})}}=1-{\frac {1}{2}}={\frac {1}{2}}\\x_{4}&=&x_{3}-{\frac {f(x_{3})}{f'(x_{3})}}={\frac {1}{2}}-{\frac {\frac {1}{4}}{1}}={\frac {1}{4}}\\x_{5}&=&x_{4}-{\frac {f(x_{4})}{f'(x_{4})}}={\frac {1}{4}}-{\frac {\frac {1}{16}}{\frac {1}{2}}}={\frac {1}{8}}\\x_{6}&=&x_{5}-{\frac {f(x_{5})}{f'(x_{5})}}={\frac {1}{8}}-{\frac {\frac {1}{64}}{\frac {1}{4}}}={\frac {1}{16}}\\x_{7}&=&x_{6}-{\frac {f(x_{6})}{f'(x_{6})}}={\frac {\frac {1}{256}}{\frac {1}{8}}}={\frac {1}{32}}\end{aligned}}}

As you can see ${\displaystyle x_{n}}$ is gradually approaching 0 (which we know is the root of ${\displaystyle f(x)}$) . One can approach the function's root with arbitrary accuracy.

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


Notes

Figure 2: Newton's method applied to the function
${\displaystyle f(x)={\begin{cases}{\sqrt {x-4}},&{\text{for }}x\geq 4\\-{\sqrt {4-x}},&{\text{for }}x<4\end{cases}}}$
starting with ${\displaystyle x_{0}=2}$ .

This method fails when ${\displaystyle f'(x)=0}$ . In that case, one should choose a new starting place. Occasionally it may happen that ${\displaystyle f(x)=0}$ and ${\displaystyle f'(x)=0}$ have a common root. To detect whether this is true, we should first find the solutions of ${\displaystyle f'(x)=0}$ , and then check the value of ${\displaystyle f(x)}$ at these places.

Newton's method also may not converge for every function, take as an example:

${\displaystyle f(x)={\begin{cases}{\sqrt {x-r}},&{\text{for }}x\geq r\\-{\sqrt {r-x}},&{\text{for }},x

For this function choosing any ${\displaystyle x_{1}=r-h}$ then ${\displaystyle 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.

Figure 3: Newton's method, when applied to the function ${\displaystyle f(x)=x^{5}-x+1}$ with initial guess ${\displaystyle x_{0}=0}$ , eventually iterates between the three points shown above.

Newton's method may also fail to converge on a root if the function has a local maximum or minimum that does not cross the x-axis. As an example, consider ${\displaystyle f(x)=x^{5}-x+1}$ with initial guess ${\displaystyle x_{0}=0}$ . In this case, Newton's method will be fooled by the function, which dips toward the x-axis but never crosses it in the vicinity of the initial guess.