Newton’s method works for convex real functions

Theorem 1.

Let $f\mathrm{:}I\mathrm{\to }\mathrm{R}$ be a convex differentiable functionon an interval $I\mathrm{\subseteq }\mathrm{R}$, with at least one root.Then the following sequence $\mathrm{\{}{x}_n\mathrm{\}}$obtained from Newton’s method,

$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)},$$

will converge to a root of $f$, provided that$f^{\mathrm{\prime }}\mathit{}\mathrm{(}{x}_{\mathrm{0}}\mathrm{)}\mathrm{\ne }\mathrm{0}$ and $x_{\mathrm{1}}\mathrm{\in }I$ for the given starting point $x_{\mathrm{0}}\mathrm{\in }I$.

Obviously, “convex” can be replaced by “concave” in Theorem 1.

The proof will proceed in several steps. First, a simple converse result:

Theorem 2.

Let $f\mathrm{:}I\mathrm{\to }\mathrm{R}$ be a differentiable convex function,and $\mathrm{\{}{x}_n\mathrm{\}}$ be the sequence in Theorem 1.If it is convergent to a number $a\mathrm{\in }I$,then $a$ is necessarily a root of $f$.

Proof.

We have

$$0=\underset{n\to \mathrm{\infty }}{lim}{f}^{\prime }(x_n)\cdot (x_n-x_{n+1})=\underset{n\to \mathrm{\infty }}{lim}f(x_n)=f(a).$$

(The first limit is zero by local boundedness of $f^{\prime }$ at $a$,which follows from $f^{\prime }$ being finite and monotone.)∎

Proof of Theorem 1

Case A: when $I=ℝ$, $f^{\prime }>0$, and $f(x_0)\ge 0$

We claim that whenever $f(x_n)\ge 0$, then $f(x_{n+1})\ge 0$ too.Recall that the graph of a convex function $f$ always liesabove any of its tangent lines.So in particular, the point $(x_{n+1},f(x_{n+1}))$ is higher than the point$(x_{n+1},0)$, which is on the tangent line by definition.By induction, we have $f(x_n)\ge 0$ for all $n$.

We also have $x_{n+1}\le x_n$ for all $n$.By hypothesis the slope $f^{\prime }(x_n)$ of the tangent line is positive,and $(x_n,f(x_n))$ lies above the horizontal axis.Then the intersection point of the tangent line and the horizontal axis,which is $(x_{n+1},0)$, must be to the left of $(x_n,0)$.

So the sequence $\{x_n\}$ is decreasing. It converges to a real number ordiverges to $-\mathrm{\infty }$.If the limit is a real number, by Theorem 2 that numberis a root of $f$, and we are done.

If the limit is $-\mathrm{\infty }$, then we must have $f(x_n)>0$for all $x_n$. Hence $f(x)>0$ for all $x$, as $f$ is monotoneand $x_n$ can be arbitrarily large negative.In other words, $f$ has no root to begin with.

Figure 1: Case A: $\{x_n\}$ is monotonically decreasing

Case B: when $I=ℝ$, , and $f(x_0)\ge 0$

This situation is the (left-right) mirror of Case A,except that because the slope of the curve is negative,the sequence $\{x_n\}$ is increasing this time. We still have $x_n\ge 0$,so the sequence either converges to a root of $f$, or diverges to $+\mathrm{\infty }$ (in which case $f$ has no root).

Figure 2: Case B: $\{x_n\}$ is monotonically increasing

Case C: when $I=ℝ$, $f^{\prime }(x_0)>0$, and $f(x_0)\ge 0$

To begin, note that the first part of Case A, asserting that $f(x_n)\ge 0$for all $n$, still goes through only assuming $f^{\prime }(x_n)\ne 0$— in which case the sequence would not be defined after the point $x_n$.We show that, in fact, $f^{\prime }(x_n)>0$ for all $n$,so the rest of Case A goes through.

Suppose $n$ is the smallest integerfor which $f^{\prime }(x_{n+1})\le 0$.Also assume $f(x_n),f(x_{n+1})\ne 0$, otherwise we would be done anyway.The reasoning in Case A shows .

Figure 3: Case C: a tangent line separates $f$ from the horizontal axis

The function $f$ is strictly positive on $[x_{n+1},x_n]$,for the graph of $f$ lies above the tangent line segment extendingfrom $(x_{n+1},0)$ to $(x_n,f(x_n))$, which in turn liesstrictly above the horizontal axis.Since $f$ is decreasing to the left of $[x_{n+1},x_n]$and increasing to the right,$f$ never touches the horizontal axis anywhere.This contradicts our hypothesis that $f$ has roots.

Case D: when $I=ℝ$, , and $f(x_0)\ge 0$

This situation is the (left-right) mirrorof Case C. The same argument shows that for all $n$ (or $f(x_n)=0$ for some $n$), and theargument of Case B applies.

Case E: for general intervals $I$

The only concern is that the iteration $\{x_n\}$might go outside the interval $I$. We show that it does not.

Suppose $f(x_0)\ge 0$.Then as we have proved, $f(x_n)\ge 0$ for all $n$.Suppose $x_n\in I$ but $x_{n+1}\notin I$.Then $f$ has no root, because the graph of $f$ lies abovethe tangent line from $(x_n,f(x_n))$ to $(x_{n+1},0)$which lies above the horizontal axis.

The limit of $x_n$ could conceivably go just outsidethe interval $I$.But this case is similar to the case $x_n\to \pm \mathrm{\infty }$already considered in Case A:$f$ possesses no root then.

Finally, suppose , the case we have ignored all along.Our hypotheses assume that $f(x_1)$ is defined.We immediately have $f(x_1)\ge 0$,since the graph of $f$ lies above the tangent linefrom $(x_0,f(x_0))$ to $(x_1,0)$.But this just brings us back to the other cases.

Figure 4: Case E: $f(x_1)$ is always $\ge 0$

Examples

Newton’s method for finding square roots of positive numbers $\alpha$(which reduces to the ancient divide-and-average method) alwaysconverges, for the target function $f(x)=x^2-\alpha$ is convex.