Newton’s method works for convex real functions
Theorem 1.
Let f:I→R be a convex differentiable function
on an interval I⊆R, with at least one root.
Then the following sequence {xn}
obtained from Newton’s method,
xn+1=xn-f(xn)f′(xn), |
will converge to a root of f, provided that
f′(x0)≠0 and x1∈I for the given starting point x0∈I.
The proof will proceed in several steps. First, a simple converse result:
Theorem 2.
Let f:I→R be a differentiable convex function,
and {xn} be the sequence in Theorem 1.
If it is convergent to a number a∈I,
then a is necessarily a root of f.
Proof.
We have
0=lim |
(The first limit is zero by local boundedness of at ,
which follows from being finite and monotone11
Actually, a differentiable convex function must necessarily have a continuous
derivative
,
for the derivative is increasing, and it cannot have any jump discontinuities by
Darboux’s Theorem (http://planetmath.org/DarbouxsTheorem)..)
∎
Proof of Theorem 1
Case A: when , , and
We claim that whenever , then too.
Recall that the graph of a convex function always lies
above any of its tangent lines.
So in particular, the point is higher than the point
, which is on the tangent line by definition.
By induction
, we have for all .
We also have for all .
By hypothesis the slope of the tangent line is positive,
and lies above the horizontal axis.
Then the intersection
point of the tangent line and the horizontal axis,
which is , must be to the left of .
So the sequence is decreasing. It converges to a real number or diverges to . If the limit is a real number, by Theorem 2 that number is a root of , and we are done.
If the limit is , then we must have for all . Hence for all , as is monotone and can be arbitrarily large negative. In other words, has no root to begin with.
Case B: when , , and
This situation is the (left-right) mirror of Case A, except that because the slope of the curve is negative, the sequence is increasing this time. We still have , so the sequence either converges to a root of , or diverges to (in which case has no root).
Case C: when , , and
To begin, note that the first part of Case A, asserting that for all , still goes through only assuming — in which case the sequence would not be defined after the point . We show that, in fact, for all , so the rest of Case A goes through.
Suppose is the smallest integer for which . Also assume , otherwise we would be done anyway. The reasoning in Case A shows .
The function is strictly positive on , for the graph of lies above the tangent line segment extending from to , which in turn lies strictly above the horizontal axis. Since is decreasing to the left of and increasing to the right, never touches the horizontal axis anywhere. This contradicts our hypothesis that has roots.
Case D: when , , and
This situation is the (left-right) mirror
of Case C. The same argument shows that
for all (or for some ), and the
argument of Case B applies.
Case E: for general intervals
The only concern is that the iteration might go outside the interval . We show that it does not.
Suppose . Then as we have proved, for all . Suppose but . Then has no root, because the graph of lies above the tangent line from to which lies above the horizontal axis.
The limit of could conceivably go just outside
the interval .
But this case is similar to the case
already considered in Case A:
possesses no root then.
Finally, suppose , the case we have ignored all along. Our hypotheses assume that is defined. We immediately have , since the graph of lies above the tangent line from to . But this just brings us back to the other cases.
Examples
Newton’s method for finding square roots of positive numbers (which reduces to the ancient divide-and-average method) always converges, for the target function is convex.
References
- 1 Michael Spivak. Calculus, third edition. Publish or Perish, 1994.
Title | Newton’s method works for convex real functions |
---|---|
Canonical name | NewtonsMethodWorksForConvexRealFunctions |
Date of creation | 2013-03-22 15:41:28 |
Last modified on | 2013-03-22 15:41:28 |
Owner | stevecheng (10074) |
Last modified by | stevecheng (10074) |
Numerical id | 7 |
Author | stevecheng (10074) |
Entry type | Theorem |
Classification | msc 49M15 |
Classification | msc 65H05 |
Classification | msc 26A06 |
Synonym | Newton’s method works for concave real functions |