Newton’s method works for convex real functions
The proof will proceed in several steps. First, a simple converse result:
(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 .
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.
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.
- 1 Michael Spivak. Calculus, third edition. Publish or Perish, 1994.
|Title||Newton’s method works for convex real functions|
|Date of creation||2013-03-22 15:41:28|
|Last modified on||2013-03-22 15:41:28|
|Last modified by||stevecheng (10074)|
|Synonym||Newton’s method works for concave real functions|