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'(x^{*})\neq 0$. Then, there exists $\varepsilon >0$ such that for any $x^{(0)}\in (x^{*}-\varepsilon ,x^{*}+\varepsilon )$, 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^{*})\neq 0$, we get precisely quadratic convergence from sufficiently close to the root, with convergence rate ${\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)}(x^{*})\neq 0$. Then, we get convergence of order $r$, with convergence rate:

${\frac {r-1}{r!}}\left|{\frac {f^{(r)}(x^{*})}{f'(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'$ (i.e., set $f=F'$ 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^{*})\neq 0$. Then, there exists a value $\varepsilon >0$ such that for all $x^{(0)}\in (x^{*}-\varepsilon ,x^{*}+\varepsilon )$, 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^{*})\neq 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^{*})\neq 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^{*})+hf'(x^{*})+{\frac {h^{2}}{2}}f''(x^{*})+o(h^{2})$

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

$\lim _{h\to 0}{\frac {f(x^{*}+h)-f(x^{*})-hf'(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'(x^{*})+{\frac {(h^{(k)})^{2}}{2}}f''(x^{*})+o((h^{(k)})^{2})$

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

$f(x^{(k)})=h^{(k)}\left(f'(x^{*})+{\frac {h^{(k)}}{2}}f''(x^{*})+o(h^{(k)})\right)$

We also have:

$f'(x^{(k)})=f'(x^{*})+h^{(k)}f''(x^{*})+o(h^{(k)})$

We therefore obtain:

${\frac {f(x^{(k)})}{f'(x^{(k)})}}=h^{(k)}{\frac {\left(1+{\frac {h^{(k)}}{2}}{\frac {f''(x^{*})}{f'(x^{*})}}+o(h^{(k)})\right)}{\left(1+h^{(k)}{\frac {f''(x^{*})}{f'(x^{*})}}+o(h^{(k)})\right)}}$

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

${\frac {f(x^{(k)})}{f'(x^{(k)})}}=h^{(k)}\left(1-{\frac {h^{(k)}}{2}}{\frac {f''(x^{*})}{f'(x^{*})}}+o(h^{(k)})\right)$

We have:

$x^{(k+1)}=x^{(k)}-{\frac {f(x^{(k)})}{f'(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)}\left(1-{\frac {h^{(k)}}{2}}{\frac {f''(x^{*})}{f'(x^{*})}}+o(h^{(k)})\right)$

This simplifies to:

$h^{(k+1)}={\frac {\left(h^{(k)}\right)^{2}}{2}}{\frac {f''(x^{*})}{f'(x^{*})}}+o(\left(h^{(k)}\right)2)$

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

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

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

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

We get:

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

and:

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

Dividing and Taylor-expanding, we get:

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

Thus, we get:

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

Thus, we get:

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

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

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