# The Newton's method

Newton's Method

Newton's method generates a sequence ${\displaystyle \displaystyle x_{k}}$ to find the root ${\displaystyle \displaystyle \alpha }$ of a function ${\displaystyle \displaystyle f}$ starting from an initial guess ${\displaystyle \displaystyle x_{0}}$. This initial guess ${\displaystyle x_{0}}$ should be close enough to the root ${\displaystyle \alpha }$ for the convergence to be guaranteed. We construct the tangent of ${\displaystyle \displaystyle f}$ at ${\displaystyle \displaystyle x_{0}}$ and we find an approximation of ${\displaystyle \alpha }$ by computing the root of the tangent. Repeating this iterative process we obtain the sequence ${\displaystyle \displaystyle x_{k}}$.

## Derivation of Newton's Method

Approximating ${\displaystyle \displaystyle f(x)}$ with a second order Taylor expansion around ${\displaystyle \displaystyle x_{k}}$,

${\displaystyle f(x)=f(x_{k})+f'(x_{k})(x-x_{k})+{\frac {f''(\eta _{k})}{2}}(x-x_{k})^{2},}$

with ${\displaystyle \displaystyle \eta _{k}}$ between ${\displaystyle \displaystyle x}$ and ${\displaystyle \displaystyle x_{k}}$. Imposing ${\displaystyle x=\alpha }$ and recalling that ${\displaystyle f(\alpha )=0}$, with a little rearranging we obtain

${\displaystyle \alpha =x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}-{\frac {(\alpha -x_{k})^{2}}{2}}{\frac {f''(\eta _{k})}{f'(x_{k})}}.}$

Neglecting the last term, we find an approximation of ${\displaystyle \displaystyle \alpha }$ which we shall call ${\displaystyle \displaystyle x_{k+1}}$. We now have an iteration which can be used to find successively more precise approximations of ${\displaystyle \displaystyle \alpha }$:

Newton's method :

${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}.}$

## Convergence Analysis

It's clear from the derivation that the error of Newton's method is given by

Newton's method error formula:

${\displaystyle \alpha -x_{k+1}=-{\frac {f''(\eta _{k})}{2f'(x_{k})}}(\alpha -x_{k})^{2}.}$

From this we note that if the method converges, then the order of convergence is 2. On the other hand, the convergence of Newton's method depends on the initial guess ${\displaystyle \displaystyle x_{0}}$.

The following theorem holds

Theorem

Assume that ${\displaystyle f(x),\,f'(x),}$ and ${\displaystyle \displaystyle f''(x)}$ are continuous in neighborhood of the root ${\displaystyle \displaystyle \alpha }$ and that ${\displaystyle \displaystyle f'(\alpha )\neq 0}$. Then, taken ${\displaystyle \displaystyle x_{0}}$ close enough to ${\displaystyle \displaystyle \alpha }$, the sequence ${\displaystyle \displaystyle x_{k}}$, with ${\displaystyle k\geq 0}$, defined by the Newton's method converges to ${\displaystyle \alpha }$. Moreover the order of convergence is ${\displaystyle \displaystyle p=2}$, as

${\displaystyle \lim _{k\to \infty }{\frac {\alpha -x_{k+1}}{(\alpha -x_{k})^{2}}}=-{\frac {f''(\alpha )}{2f'(\alpha )}}.}$

The disadvantages of using this method are numerous. First of all, it is not guaranteed that Newton's method will converge if we select an ${\displaystyle \displaystyle x_{0}}$ that is too far from the exact root. Likewise, if our tangent line becomes parallel or almost parallel to the x-axis, we are not guaranteed convergence with the use of this method. Also, because we have two functions to evaluate with each iteration (${\displaystyle f(x_{k})}$ and ${\displaystyle f'(x_{k})}$, this method is computationally expensive. Another disadvantage is that we must have a functional representation of the derivative of our function, which is not always possible if we working only from given data.