PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (237)
Orphanage
Unclass'd
Unproven (550)
Corrections (54)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Copyright
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] Newton's method works for convex real functions (Theorem)
Theorem 1   Let $ f\colon I \to \mathbb{R}$ be a convex differentiable function on an interval $ I \subseteq \mathbb{R}$, with at least one root. Then the following sequence $ \{ x_n \}$ obtained from Newton's method,

$\displaystyle x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\,, $
will converge to a root of $ f$, provided that $ f'(x_0) \neq 0$ and $ x_1 \in I$ for the given starting point $ x_0 \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\colon I \to \mathbb{R}$ be a differentiable convex function, and $ \{x_n\}$ be the sequence in Theorem 1. If it is convergent to a number $ a \in I$, then $ a$ is necessarily a root of $ f$.
Proof. We have

$\displaystyle 0 = \lim_{n \to \infty} f'(x_n) \cdot (x_n - x_{n+1}) = \lim_{n \to \infty} f(x_n) = f(a)\,. $
(The first limit is zero by local boundedness of $ f'$ at $ a$, which follows from $ f'$ being finite and monotone 1.) $ \qedsymbol$

Proof of Theorem 1

Case A: when $ I = \mathbb{R}$, $ f' > 0$, and $ f(x_0) \geq 0$

We claim that whenever $ f(x_n) \geq 0$, then $ f(x_{n+1}) \geq 0$ too. Recall that the graph of a convex function $ f$ always lies above 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) \geq 0$ for all $ n$.

We also have $ x_{n+1} \leq x_n$ for all $ n$. By hypothesis the slope $ f'(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 or diverges to $ -\infty$. If the limit is a real number, by Theorem 2 that number is a root of $ f$, and we are done.

If the limit is $ -\infty$, then we must have $ f(x_n) > 0$ for all $ x_n$. Hence $ f(x) > 0$ for all $ x$, as $ f$ is monotone and $ 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
\includegraphics{convex-newton.1.eps}

Case B: when $ I = \mathbb{R}$, $ f' < 0$, and $ f(x_0) \geq 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 \geq 0$, so the sequence either converges to a root of $ f$, or diverges to $ +\infty$ (in which case $ f$ has no root).
Figure 2: Case B: $ \{ x_n \}$ is monotonically increasing
\includegraphics{convex-newton.2.eps}

Case C: when $ I = \mathbb{R}$, $ f'(x_0) > 0$, and $ f(x_0) \geq 0$

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

Suppose $ n$ is the smallest integer for which $ f'(x_{n+1}) \leq 0$. Also assume $ f(x_n), f(x_{n+1}) \neq 0$, otherwise we would be done anyway. The reasoning in Case A shows $ x_{n+1} < x_n$.

Figure 3: Case C: a tangent line separates $ f$ from the horizontal axis
\includegraphics{convex-newton.3.eps}

The function $ f$ is strictly positive on $ [x_{n+1}, x_n]$, for the graph of $ f$ lies above the tangent line segment extending from $ (x_{n+1}, 0)$ to $ (x_n, f(x_n))$, which in turn lies strictly 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 = \mathbb{R}$, $ f'(x_0) < 0$, and $ f(x_0) \geq 0$

This situation is the (left-right) mirror of Case C. The same argument shows that $ f'(x_n) < 0$ for all $ n$ (or $ f(x_n) = 0$ for some $ n$), and the argument 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) \geq 0$. Then as we have proved, $ f(x_n) \geq 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 above the 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 outside the interval $ I$. But this case is similar to the case $ x_n \to \pm \infty$ already considered in Case A: $ f$ possesses no root then.

Finally, suppose $ f(x_0) < 0$, the case we have ignored all along. Our hypotheses assume that $ f(x_1)$ is defined. We immediately have $ f(x_1) \geq 0$, since the graph of $ f$ lies above the tangent line from $ (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 $ \geq 0$
\includegraphics{convex-newton.4.eps} \includegraphics{convex-newton.5.eps}

Examples

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

Bibliography

1
Michael Spivak. Calculus, third edition. Publish or Perish, 1994.


Footnotes

...http://planetmath.org/encyclopedia/WeaklyMonotone.html 1
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.


"Newton's method works for convex real functions" is owned by stevecheng.
(view preamble | get metadata)

View style:

Other names:  Newton's method works for concave real functions
Keywords:  Newton's method, Newton-Raphson method

This object's parent.

Attachments:
nth root by Newton's method (Example) by pahio
Log in to rate this entry.
(view current ratings)

Cross-references: square roots, similar, iteration, right, segment, strictly, function, integer, curve, negative, diverges, real number, decreasing, intersection, axis, positive, slope, hypothesis, induction, tangent lines, graph, jump discontinuities, increasing, derivative, continuous, monotone, finite, limit, number, convergent, convex function, differentiable, converse, proof, theorem, point, converge, Newton's method, sequence, root, interval, differentiable function, convex

This is version 4 of Newton's method works for convex real functions, born on 2006-02-18, modified 2006-04-11.
Object id is 7634, canonical name is NewtonsMethodWorksForConvexRealFunctions.
Accessed 4016 times total.

Classification:
AMS MSC: 26A06 (Real functions :: Functions of one variable :: One-variable calculus)
 65H05 (Numerical analysis :: Nonlinear algebraic or transcendental equations :: Single equations)
 49M15 (Calculus of variations and optimal control; optimization :: Methods of successive approximations :: Methods of Newton-Raphson, Galerkin and Ritz types)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)