Newton's method converges quadratically from sufficiently close to a root of multiplicity one

Statement

Suppose $f$ is a function of one variable that is at least two times continuously differentiable around a point $x^{*}$ in its domain, and further, $f^{\prime }(x^{*})\ne 0$. Then, there exists $\epsilon >0$ such that for any $x^{(0)}\in (x^{*}-\epsilon ,x^{*}+\epsilon )$, the sequence obtained by applying Newton's method for root-finding for a function of one variable starting from $x^{(0)}$ either reaches the root in finitely many steps or has quadratic convergence (or higher-order convergence) to the root $x^{*}$.

Case that the second derivative is nonzero

In the case that $f^{″}(x^{*})\ne 0$, we get precisely quadratic convergence from sufficiently close to the root, with convergence rate $\frac{1}{2}\left|\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}\right|$.

General case of an infinitely differentiable function with finite order of zero

Suppose that, of the integers greater than or equal to 2, $r$ is the smallest integer such that $f^{(r)}(x^{*})\ne 0$. Then, we get convergence of order $r$, with convergence rate:

$\frac{r-1}{r!}\left|\frac{f^{(r)}(x^{*})}{f^{\prime }(x^{*})}\right|$

Corresponding statement for optimization

The preceding statements are in the context of Newton's method for root-finding for a function of one variable. They also imply corresponding statements for Newton's method for optimization of a function of one variable, but all the derivative orders increase by one. Explicitly, for a function $F$, the statements for finding the minimum of $F$ correspond to statements for funding the zeros of $F^{\prime }$ (i.e., set $f=F^{\prime }$ to easily translate statements back and forth).

Suppose we have that $x^{*}$ is a point of local minimum. Suppose $F$ is at least three times continuously differentiable at $x^{*}$, and $F^{″}(x^{*})\ne 0$. Then, there exists a value $\epsilon >0$ such that for all $x^{(0)}\in (x^{*}-\epsilon ,x^{*}+\epsilon )$, Newton's method for optimization, starting at $x^{(0)}$, converges to $x^{*}$, and the convergence is quadratic or of higher order.

Case that the third derivative is nonzero

In the case that $F^{‴}(x^{*})\ne 0$, the convergence is precisely quadratic convergence and the convergence rate is:

$\frac{1}{2}\left|\frac{F^{‴}(x^{*})}{F^{″}(x^{*})}\right|$

General case of an infinitely differentiable function with finite order of zero

Suppose that, of the integers greater than or equal to 2, $r$ is the smallest integer such that $F^{(r+1)}(x^{*})\ne 0$. Then, we get convergence of order $r$, with convergence rate:

$\frac{r-1}{r!}\left|\frac{F^{(r+1)}(x^{*})}{F^{″}(x^{*})}\right|$

Related facts

• Newton's method converges linearly from sufficiently close to a root of multiplicity greater than one

Proof

Proof for the case that the second derivative is nonzero

Since the function is twice continuously differentiable around $x^{*}$, we have a value $\delta$ such that $f$ has a partial Taylor expansion around $x^{*}$ (going up to degree two) for $x\in (x^{*}-\delta ,x^{*}+\delta )$. Explicitly, if $h=x-x^{*}$, we should be able to write:

$f(x)=f(x^{*}+h)=f(x^{*})+h{f}^{\prime }(x^{*})+\frac{h^2}{2}{f}^{″}(x^{*})+o(h^2)$

where the $o(h^2)$ formally means that:

$\underset{h\to 0}{lim}\frac{f(x^{*}+h)-f(x^{*})-h{f}^{\prime }(x^{*})-\frac{h^2}{2}{f}^{″}(x^{*})}{h^2}=0$

Note that in case the function is three or more times differentiable, that term is actually $O(h^3)$.

Suppose $x^{(k)}$, the $k^{th}$ iterate of Newton's method, is in the interval $(x^{*}-\delta ,x^{*}+\delta )$. Define:

$h^{(k)}=x^{(k)}-x^{*}$

We thus obtain:

$f(x^{(k)})=f(x^{*})+h^{(k)}{f}^{\prime }(x^{*})+\frac{(h^{(k)}{)}^2}{2}{f}^{″}(x^{*})+o((h^{(k)}{)}^2)$

Since $f(x^{*})=0$, this simplifies to:

$f(x^{(k)})=h^{(k)}(f^{\prime }(x^{*})+\frac{h^{(k)}}{2}{f}^{″}(x^{*})+o(h^{(k)}))$

We also have:

$f^{\prime }(x^{(k)})=f^{\prime }(x^{*})+h^{(k)}{f}^{″}(x^{*})+o(h^{(k)})$

We therefore obtain:

$\frac{f(x^{(k)})}{f^{\prime }(x^{(k)})}=h^{(k)}\frac{(1+\frac{h^{(k)}}{2}\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}+o(h^{(k)}))}{(1+h^{(k)}\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}+o(h^{(k)}))}$

Taylor-expanding the reciprocal of the denominator and simplifying, we obtain:

$\frac{f(x^{(k)})}{f^{\prime }(x^{(k)})}=h^{(k)}(1-\frac{h^{(k)}}{2}\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}+o(h^{(k)}))$

We have:

$x^{(k+1)}=x^{(k)}-\frac{f(x^{(k)})}{f^{\prime }(x^{(k)})}$

Recall that $h^{(k)}=x^{(k)}-x^{*}$. Similarly, $h^{(k+1)}=x^{(k+1)}-x^{*}$. Thus:

$h^{(k+1)}=h^{(k)}-h^{(k)}(1-\frac{h^{(k)}}{2}\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}+o(h^{(k)}))$

This simplifies to:

$h^{(k+1)}=\frac{{(h^{(k)})}^2}{2}\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}+o((h^{(k)})2)$

Notice that if $h^{(k)}$ is sufficiently small, then we are guaranteed that $\left|h^{(k+1)}\right|<\left|h^{(k)}\right|$, so that the corresponding statement holds for $h^{(k+1)}$. In particular, we obtain convergence, and moreover, we obtain that:

$\underset{k\to \mathrm{\infty }}{lim}\frac{|x^{(k+1)}-x^{*}|}{|x^{(k)}-x^{*}{|}^2}=\underset{k\to \mathrm{\infty }}{lim}\frac{\left|h^{(k+1)}\right|}{|h^{(k)}{|}^2}=\frac{1}{2}\left|\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}\right|$

Proof for the case that a higher finite order derivative is nonzero

Consider the case that $f^{\prime }(x^{*})\ne 0$, and of the integers that are at least 2, $r$ is the smallest one such that $f^{(r)}(x^{*})\ne 0$. The proof remains very similar to the above, with the following changes.

We get:

$f(x^{(k)})=h^{(k)}(f^{\prime }(x^{*})+\frac{{(h^{(k)})}^{r-1}}{r!}{f}^{(r)}(x^{*})+o({(h^{(k)})}^{r-1}))$

and:

$f^{\prime }(x^{(k)})=f^{\prime }(x^{*})+\frac{{(h^{(k)})}^{r-1}}{(r-1)!}{f}^{(r)}(x^{*})+o({(h^{(k)})}^{r-1})$

Dividing and Taylor-expanding, we get:

$\frac{f(x^{(k)})}{f^{\prime }(x^{(k)})}=h^{(k)}(1+(\frac{1}{r!}-\frac{1}{(r-1)!}){(h^{(k)})}^{r-1}\frac{f^{(r-1)}(x^{*})}{f^{\prime }(x^{*})}+o({(h^{(k)})}^{r-1}))$

Thus, we get:

$h^{(k+1)}=h^{(k)}-\frac{f(x^{(k)})}{f^{\prime }(x^{(k)})}=\frac{r-1}{r!}{(h^{(k)})}^r\frac{f^{(r)}(x^{*})}{f^{\prime }(x^{*})}+o({(h^{(k)})}^r)$

Thus, we get:

$\left|\frac{h^{(k+1)}}{{(h^{(k)})}^r}\right|=|\frac{r-1}{r!}\frac{f^{(r)}(x^{*})}{f^{\prime }(x^{*})}+o(1)|$

So that, if we start from sufficiently close, the limit is:

$\frac{r-1}{r!}\left|\frac{f^{(r)}(x^{*})}{f^{\prime }(x^{*})}\right|$