Prob. 25, Chap. 5 in Baby Rudin: Newton's Method

Here is Prob. 25, Chap. 5 in the book Principles of Mathematical Analysis by Walter Rudin, 3rd edition:

Suppose $f$ is twice differentiable on $[a, b]$, $f(a) < 0$, $f(b) > 0$, $f^\prime(x) \geq \delta > 0$, and $0 \leq f^{\prime\prime}(x) \leq M$ for all $x \in [a, b]$. Let $\xi$ be the unique point in $[a, b]$ at which $f(\xi) = 0$.

Complete the details in the following outline of Newton's method for computing $\xi$.

(a) Choose $x_1 \in (\xi, b)$, and define $\left\{ x_n \right\}$ by $$x_{n+1} = x_n - \frac{ f\left(x_n \right)}{f^\prime\left(x_n\right)}.$$ Interpret this geometrically, in terms of a tangent to the graph of $f$.

(b) Prove that $x_{n+1} < x_n$ and that $$\lim_{n \to \infty} x_n =\xi.$$

(c) Use Taylor's theorem to show that $$x_{n+1} - \xi = \frac{ f^{\prime\prime}\left( t_n \right) }{ 2 f^\prime \left( x_n \right) } \left( x_n - \xi \right)^2$$ for some $t_n \in \left( \xi, x_n \right)$.

(d) If $A = M / 2\delta$, deduce that $$0 \leq x_{n+1} - \xi \leq \frac{1}{A} \left[ A \left( x_1 - \xi \right) \right]^{2^n}.$$ (Compare with Exercises 16 and 18, Chapter 3.)

(e) Show that Newton's method amounts to finding a fixed point of the function $g$ defined by $$g(x) = x - \frac{ f(x) }{ f^\prime(x) }.$$ How does $g^\prime(x)$ behave for $x$ near $\xi$?

(f) Put $f(x) = x^{1/3}$ on $( - \infty, \infty)$ and try Newton's method. What happens?

Solutions:

Part (a);

The tangent to the graph of $f$ at the point $\left( x_n, f \left( x_n \right) \right)$ has the equation $$y = f\left( x_n \right) + f^\prime \left( x_n \right) \left( x - x_n \right).$$ Let $x_{n+1}$ be the abscissa of the point at which this line intersects the $x$-axis. Then we have $$0 = f\left( x_n \right) + f^\prime \left( x_n \right) \left( x_{n+1} - x_n \right).$$ Solving the last equation for $x_{n+1}$, we obtain $$x_{n+1} = = x_n - \frac{ f\left(x_n \right)}{f^\prime\left(x_n\right)}.$$

Part (b):

As $f^\prime(x) > 0$, so $f$ is strictly increasing on $[a, b]$, and as $\xi < x_1 < b$, so $f ( \xi) = 0 < f \left( x_1 \right) < f(b)$; thus $f \left( x_1 \right) > 0$, and so $$x_2 = x_1 - f \left( x_1 \right)/f^\prime \left( x_1 \right) < x_1.$$ As $f^{\prime\prime} \geq 0$, so $f^\prime$ is monotonically increasing.

By the mean-value theorem we can find a point $c_1 \in \left( x_2, x_1 \right)$ such that \begin{align} f\left( x_2 \right) &= f\left( x_1 \right) + f^\prime\left( c_1 \right) \left( x_2 - x_1 \right) \\ &= f\left( x_1 \right) - f^\prime\left( c_1 \right) \left( x_1 - x_2 \right) \\ & \geq f\left( x_1 \right) - f^\prime\left( x_1 \right) \left( x_1 - x_2 \right) \\ & \qquad \mbox{[ as x_2 < c_1 < x_1 and as f^\prime is monotonically increasing, } \\ & \qquad \mbox{ so f^\prime \left( x_2 \right) \leq f^\prime \left( c_1 \right) \leq f^\prime \left(x_1 \right).]} \\ &= f^\prime\left( x_1 \right) \left[ \frac{ f\left( x_1 \right) }{ f^\prime\left( x_1 \right) } - x_1 + x_2 \right] \\ &= f^\prime\left( x_1 \right) \left( -x_2 + x_2 \right) \\ &= 0 \\ &= f \left( \xi \right), \end{align} and as $f$ is strictly increasing, so we can conclude that $x_2 \geq \xi$. Now if $x_2 = \xi$, then we see that $$x_3 = x_2 - \frac{ f\left(x_2 \right)}{f^\prime\left(x_2\right)} = \xi - \frac{ f\left(\xi \right)}{f^\prime\left(\xi\right)} = \xi,.$$ and hence $$x_4 = x_3 - \frac{ f\left(x_3 \right)}{f^\prime\left(x_3 \right)} = \xi - \frac{ f\left(\xi \right)}{f^\prime\left(\xi\right)} = \xi,.$$ and so on. Thus $x_n = \xi$ for all $n \geq 2$ and so $x_n \to \xi$ as $n \to \infty$. So we suppose that $x_2 > \xi$.

Now suppose that $x_n$, where $n \geq 2$, has been found so that $\xi < x_n$. Then $0 = f(\xi) < f\left(x_n \right)$, and so $$x_{n+1} = x_n - \frac{ f\left( x_n \right) }{ f^\prime \left( x_n \right) } < x_n,$$ and there exists a point $c \in \left( x_{n+1}, x_n \right)$ such that \begin{align} f\left( x_{n+1} \right) &= f\left( x_n \right) + f^\prime\left( c \right) \left( x_{n+1} - x_n \right) \\ &= f\left( x_n \right) - f^\prime\left( c \right) \left( x_n - x_{n+1} \right) \\ & \geq f\left( x_n \right) - f^\prime\left( x_n \right) \left( x_n - x_{n+1} \right) \\ & \qquad \mbox{[ as x_{n+1} < c < x_n and as f^\prime is monotonically increasing, } \\ & \qquad \mbox{ so f^\prime \left( x_{n+1} \right) \leq f^\prime\left( c \right) \leq f^\prime \left( x_n \right).]} \\ &= f^\prime\left( x_n \right) \left[ \frac{ f\left( x_n \right) }{ f^\prime\left( x_n \right) } - x_n + x_{n+1} \right] \\ &= f^\prime\left( x_n \right) \left( -x_{n+1} + x_{n+1} \right) \\ &= 0 \\ &= f \left( \xi \right); \end{align} that is, $f \left( x_{n+1} \right) \geq f \left(\xi \right)$, which implies that $x_{n+1} \geq \xi$, because $f$ is strictly increasing. If $x_{n+1} = \xi$, then, as above, $x_m = \xi$ for all $m \geq n+1$, and so $x_m \to \xi$ as $m \to \infty$. So we suppose that $x_{n+1} > \xi$, and proceed.

Thus, for each $n \in \mathbb{N}$, we have $x_n > x_{n+1} \geq \xi$. That is, the sequence $\left\{ x_n \right\}$ is monotonically decreasing and bounded from below by $\xi$; so this sequence converges, with $\lim x_n \geq \xi$.

Put $$\eta \colon= \lim_{n \to \infty} \xi_n.$$ Then $\eta \geq \xi$.

Now as $f$ and $f^\prime$ are differentiable on $[a, b]$, so these two functions are also continuous on $[a, b]$, which implies that both of the sequences $\left\{ f \left( x_n \right) \right\}$ and $\left\{ f^\prime \left( x_n \right) \right\}$ are convergent, with $$\lim_{n \to \infty} f \left( x_n \right) = f\left( \eta \right), \qquad \lim_{n \to \infty} f^\prime \left( x_n \right) = f^\prime \left( \eta \right),$$ and, for each $n \in \mathbb{N}$, as $$x_{n+1} = x_n - \frac{ f\left( x_n \right) }{ f^\prime \left( x_n \right) },$$ so upon taking the limit on both sides as $n \to \infty$, we have the equation $$\eta = \eta - \frac{ f(\eta) }{ f^\prime ( \eta ) },$$ which implies that $$\frac{ f(\eta) }{ f^\prime ( \eta ) } = 0,$$ which in turn implies that $$f(\eta) = 0,$$ and so $\eta = \xi$. Thus $x_n \to \xi$ as $n \to \infty$, as required.

Part (c):

By Taylor's theorem we can find a point $t_n \in \left( \xi, x_n \right)$ such that $$0 = f\left( \xi \right) = f \left( x_n \right) + f^\prime \left( x_n \right) \left( \xi - x_n \right) + \frac{ f^{\prime\prime} \left( t_n \right) }{ 2 } \left( \xi - x_n \right)^2,$$ which implies that $$\frac{ f \left( x_n \right) }{ f^\prime \left( x_n \right) } + \xi - x_n + \frac{ f^{\prime\prime} \left( t_n \right) }{ 2 f^\prime \left( x_n \right) } \left( \xi - x_n \right)^2 = 0,$$ that is, $$\xi - x_{n+1} + \frac{ f^{\prime\prime} \left( t_n \right) }{ 2 f^\prime \left( x_n \right) } \left( \xi - x_n \right)^2 = 0,$$ and so $$x_{n+1} - \xi = \frac{ f^{\prime\prime} \left( t_n \right) }{ 2 f^\prime \left( x_n \right) } \left( x_n - \xi \right)^2,$$ as required.

Part (d):

Using what is given about $f^\prime$ and $f^{\prime\prime}$ and using what we have shown in Parts (a) and (c), we obtain $$0 \leq x_{n+1} - \xi = \frac{ f^{\prime\prime} \left( t_n \right) }{ 2 f^\prime \left( x_n \right) } \left( x_n - \xi \right)^2 \leq \frac{ M }{ 2\delta } \left( x_n - \xi \right)^2 = A \left( x_n - \xi \right)^2 \tag{1}$$ for each $n \in \mathbb{N}$. So $$0 \leq x_2 - \xi \leq A \left( x_1 - \xi \right)^2 = { 1 \over A } \left[ A \left( x_1 - \xi \right)\right]^2 = { 1 \over A } \left[ A \left( x_1 - \xi \right)\right]^{2^1}.$$ Suppose the required result holds for $k = 1, \ldots, n$, where $n \geq 1$. Then from (1) we see that $$0 \leq x_{n+2} - \xi \leq A \left( x_{n+1} - \xi \right)^2 \leq A \left[ { 1 \over A } \left[ A \left( x_1 - \xi \right) \right]^{2^n} \right]^2 = { 1 \over A } \left[ A \left( x_1 - \xi \right) \right]^{2^{n+1}}.$$ So by induction, the required inequality holds for all natural numbers $n$.

Here are the links to my posts here on Math SE on Probs. 16 and 18, Chap. 3, in Baby Rudin, 3rd edition:

Prob. 16, Chap. 3 in Baby Rudin: $x_{n+1} = (x_n + \alpha/x_n)/2$, with $x_1 > \sqrt{\alpha}$, $\alpha > 0$

Prob. 18, Chap. 3 in Baby Rudin: Behaviour of $x_{n+1}=\frac{p-1}{p} x_n+\frac{\alpha}{p} x_n^{1-p}$ with $\alpha>0$ and $p$ a positive integer

Now Prob. 18, is when we put $f(x) = x^p - \alpha$, but what are our $a$ and $b$ so that all the conditions given above are satisfied by $f$ and its first and second derivatives? Of course, Prob. 16 is the special case of Prob. 18 when $p = 2$.

Part (e):

As $f(\xi) = 0$, so $$g(\xi) = \xi - \frac{ f(\xi) }{ f^\prime(\xi) } = \xi.$$ Thus $\xi$ is a fixed point of $g$.

Conversely, if $x \in [a, b]$ is a fixed point of $g$, then $g(x) = x$; that is, $$x - \frac{ f(x) }{ f^\prime(x) } = x,$$ which implies that $f(x) = 0$ and so $x = \xi$.

Now $$g^\prime(x) = 1 - \frac{ f^\prime(x) f^\prime(x) - f(x) f^{\prime\prime}(x) }{ \left[ f^\prime(x) \right]^2 } = \frac{ f(x) f^{\prime\prime}(x)}{ \left[ f^\prime(x) \right]^2 }$$ so that $g^\prime(x) \to 0$ as $x \to \xi$.

Thus by taking $a$ and $b$ sufficiently close to $\xi$, we can make $\left| g^\prime \right| \leq { 1 \over 2 }$, and then we can apply the recursion $x_1 \in (\xi, b)$ arbitrary, and $$x_{n+1} = g \left( x_n \right)$$ to converge to the fixed point of $g$, as has been established in Prob. 22 (c), Chap. 3, in Baby Rudin.

Here is the link to a post of mine here on Math SE on Prob. 22, Chap. 3, in Baby Rudin, 3rd edition.

Prob. 22, Chap. 5 in Baby Rudin: Fixed Points of Real Functions

Part (f):

For $f(x) = x^{1/3}$, we have $\xi = 0$.

But $f^\prime(x) = {1\over 3} x^{-2/3}$ provided $x \neq 0$, while $f^\prime(0)$ does not exist; moreover $f^\prime(x) \to \infty$ as $x \to 0$, and $f^\prime(x) \to 0$ as $x \to \pm \infty$.

And, for $x \neq 0$, we have $$f^{\prime\prime}(x) = - {2 \over 9} x^{-5/3}.$$ So $f^{\prime\prime}(x) \to +\infty$ as $x \to 0-$, $f^{\prime\prime}(x) \to -\infty$ as $x \to 0+$, and $f^{\prime\prime}(x) \to 0$ as $x \to \pm \infty$.

And, the Newton method recursion formula becomes $$x_{n+1} = x_n - \frac{ x_n^{1/3} }{ {1 \over 3} x_n^{-2/3} } = x_n - 3 x_n = -2 x_n.$$ Thus, for arbitrary $x_1$, we have $x_2 = -2 x_1$, $x_3 = -2x_2 = (-2)^2 x_1$, and so on $$x_n = (-2)^{n-1} x_1.$$

Thus, if $x_1 \neq 0$, then $$\lim_{n\to\infty} \sup x_n = +\infty, \qquad \lim_{n\to\infty} \inf x_n = -\infty.$$

Are all the parts of my solution correct and as required by Rudin? If not, then where have I erred?

• With $e\in (a,b)$ and $f(e)=0,$ in case you ask how, when applying this practically, we can choose $x_1\in (e,b]$ without knowing what $e$ is, observe that we can take $x_1$ to be any $x\in (a,b]$ such that $f(x)>0.$. For example in practice we can choose $x_1=b.$ Jun 10 '17 at 2:54
• @DanielWainfleet indeed!! Jun 10 '17 at 10:54