Newton Convergence

In this post, we establish that Newton’s method works under sufficiently mild conditions.

Let $f : [-1, 1] \to \mathbb R$ have a continuous first derivative $f' > 0$ and suppose

$f(-1) < 0 < f(1).$

Problem 1. Show that there exists a unique $c \in (-1, 1)$ such that $f(c) = 0$ .

(Click for Solution)

Solution. By the intermediate value theorem, there exists $c \in (-1, 1)$ such that $f(c)$ . For uniqueness, fix any root $c' \in (-1,1)$ . If $c' \neq c$ , then by Rolle’s theorem, there exists $c''$ between $c, c'$ such that $0 < f'(c') = 0$ , a contradiction. Hence, $c = c'$ , establishing uniqueness.

Problem 2. For any $t \in (c, 1)$ , denote the $x$ -intercept of the tangent to $y = f(x)$ at $(t, f(t))$ by $t_0$ . Show that $t_0 < t$ .

(Click for Solution)

Solution. Firstly, if $f(t) \leq 0$ , then the intermediate value theorem gives us a second root $c' \in [t, 1)$ , contradicting the uniqueness of $c$ in Problem 1. Therefore, $f(t) > 0$ .

The tangent to $y = f(x)$ at $(t, f(t))$ has equation

$y = f(t) + f'(t) \cdot (x-t).$

Therefore, $0 = f(t) + f'(t) \cdot (t_0-t)$ . Doing some algebruh,

$\displaystyle t_0 = t- \frac{ f(t) }{ f'(t) } < t,$

since $f(t) > 0$ and $f'(t) > 0$ .

Now furthermore suppose that $f'$ is non-decreasing.

Problem 3. Show that $t_0 > c$ , as defined in Problems 1 and 2.

(Click for Solution)

Solution. We observe that if $t_0 < c$ , then $f(t_0) < 0$ . Taking the contrapositive, it suffices to check that $f(t_0) > 0$ . To that end, define the function

$g(x) := f(x) - (f(t) + f'(t) \cdot (x-t)).$

By definition, $f(t_0) = g(t_0)$ , so it suffices to prove that $g \geq 0$ . To that end, we use the mean value theorem to furnish $\xi$ between $t$ and $x$ such that

$f(x) = f(t) + f'(\xi) \cdot (x-t).$

Substituting and subtracting,

$g(x) = (f'(\xi) - f'(t)) \cdot (x-t).$

If $x < t$ , then $\xi < t$ so that $f'(\xi) \leq f'(t)$ . Hence, $g(x) \geq 0$ . In particular, $g(t_0) \geq 0$ , so that $f(t_0) \geq 0$ . Since $f(t_0) \neq 0$ , we must have $f(t_0) > 0$ . Therefore, $t_0 > c$ .

Now furthermore suppose that $f$ has a second derivative such that $f'' > 0$ . Define the sequence $\{x_n\}$ by

$\displaystyle x_0 := 1,\quad x_{n+1} := x_n - \frac{ f(x_n) }{ f'(x_n) }.$

Problem 4. Show that $x_n \to c$ .

(Click for Solution)

Solution. By Problem 2, $x_{n+1} < x_n$ . By Problem 3, $x_{n+1} > c$ . Therefore, $\{x_n\}$ is decreasing and bounded below. By the monotone convergence theorem, $x_n \to \xi$ for some $\xi \in [-1, 1]$ . Thanks to convergence and continuity,

$\begin{aligned} \xi = \lim_{n \to \infty}(x_{n+1}) &= \lim_{n \to \infty} \left( x_n - \frac{ f(x_n) }{ f'(x_n) } \right) = \xi - \frac{ f(\xi) }{ f'(\xi) }. \end{aligned}$