Exercise 25: Suppose $f$ is twice differentiable on $[a,b]$, $f(a) 0$, $f'(x)\ge\delta>0$, and $0\le f'(x)\le M$ for all $x\in[a,b]$. Let $\xi$ be the unique point in $(a,b)$ at which $f(\xi)=0$. (a) Choose $x_1\in(\xi,b)$, and define $\{x_n\}$ by $x_{n+1}=x_n-f(x_n)/f'(x_n)$. Interpret this geometrically, in terms of a tangent to the graph of $f$. (b) Prove that $x_{n+1}<x_n$ and that $\lim_{x\rightarrow\infty}x_n=\xi$. (c) Use Taylor's theorem to show that $$x_{n+1}-\xi=\frac{f''(t_n)}{2f'(x_n)}(x_n-\xi)^2$$ for some $t_n\in(\xi,x_n)$. (d) if $A=M/2\delta$, deduce that $$0\le x_{n+1}-\xi\le\frac{1}{A}\bigl(A(x_1-\xi)\bigr)^{2^n}.$$ Compare with Exercises 3.16 and 3.18. (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'(x)}.$$ How does $g'(x)$ behave for $x$ near $\xi$? (f) Put $f(x)=x^{1/3}$ on $(-\infty,\infty)$ and try Newton's method. What happens?

\def\eps{\varepsilon} (a) The tangent to the graph of $f$ at the point $\bigl(x_n,f(x_n)\bigr)$ has the equation $$y-f(x_n)=f'(x_n)(x-x_n).$$ Letting $y=0$ and solving for $x$, we see that this line intersects the $x$-axis at the point $(x_{n+1},0)$. (b) Note that if $x_n>\xi$ then $f(x_n)>0$ so that $x_{n+1}=x_n-f(x_n)/f'(x_n)<x_n$. By Theorem 5.10, there is a $t\in(\xi,x_n)$ such that $$f(x_n)=f(x_n)-f(\xi)=f'(t)(x_n-\xi) \quad\hbox{or}\quad \xi=x_n-\frac{f(x_n)}{f'(t)}\le x_n-\frac{f(x_n)}{f'(x_n)}=x_{n+1}$$ since $f''\ge0$ implies $f'(t)\le f'(x_n)$. If for some $m$ $x_{m}=\xi$ then $x_{m+1}= x_{m+2}=\cdots=\xi$ and so the infinite sequence converges to $\xi$. Otherwise, it is a monotonically decreasing sequence with lower bound $\xi$ and so by Theorem 3.14 converges to a limit $y\ge\xi$. To see that $y=\xi$, let $g$ be the continuous function defined in part (e), $g(x)=x-f(x)/f'(x)$. Assume that $y>\xi$. Then $f(y)>0$, so $g(y) 0$ be small enough so that $g(y)+\varepsilon 0$ such that $\big|g(x)-g(y)\big|<\varepsilon$ if $|x-y|<\delta$. Let $N$ be large enough so that $|x_N-y|<\delta$. Then $g(x_N)<g(y)+\varepsilon<y$, but this contradicts $g(x_N)=x_{N+1}\ge y$. Hence $y=\xi$. (c) Letting $\alpha=x_n$ and $\beta=\xi$ in Theorem 5.15, and using $f(x_n)=f'(x_n)(x_n-x_{n+1})$, there is some $t_n\in(\xi,x_n)$ such that \begin{align*} f(\xi) &= f(x_n)+f'(x_n)(\xi-x_n)+\frac{f''(t_n)}{2}(\xi-x_n)^2 \\ 0 &= f'(x_n)(x_n-x_{n+1})+f'(x_n)(\xi-x_n)+\frac{f''(t_n)}{2}(\xi-x_n)^2 \\ 0 &= f'(x_n)(\xi-x_{n+1})+\frac{f''(t_n)}{2}(\xi-x_n)^2 \\ x_{n+1}-\xi &= \frac{f''(t_n)}{2f'(x_n)}(x_n-\xi)^2 \end{align*} (d) Part (c) gives us \begin{align*} (x_{n+1}-\xi) &\le A(x_n-\xi)^2 \\ &\le A\cdot A^2(x_{n-1}-\xi)^{2^2} \\ &\le A\cdot A^2\cdot A^{2^2}(x_{n-2}-\xi)^{2^3} \\ &\le\cdots \\ &\le A^{1+2+2^2+\cdots+2^{n-1}}(x_1-\xi)^{2^n} = A^{2^n-1}(x_1-\xi)^{2^n} = \frac{1}{A}\bigl(A(x_1-\xi)\bigr)^{2^n}. \end{align*} The algorithm described in Exercises 3.16 and 3.18 is Newton's method applied to the functions $x^2-\alpha$ and $x^p-\alpha$, respectively. (e) We have $g(\xi)=\xi$ if and only if $f(\xi)=0$. Since $$g'(x)=1-\frac{f'(x)^2-f(x)f''(x)}{f'(x)^2}=\frac{f(x)f''(x)}{f'(x)^2}\le f(x)\frac{M}{\delta^2},$$ $g'(x)$ tends to 0 as $x$ approaches $\xi$. (f) For $f(x)=x^{1/3}$, note that $$x_{n+1}=x_1-\frac{x_n^{1/3}}{(1/3)x_n^{-2/3}}=-2x_n$$ so that $x_n=(-2)^{n-1}x_1$. That is, $\{x_n\}$ is an alternating sequence such that $|x_n|\rightarrow\infty$ as $x\rightarrow\infty$.

Homepage › Solution manuals › Walter Rudin › Principles of Mathematical Analysis › Exercise 5.25

Principles of Mathematical Analysis

Exercise 5.25

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

(a) Choose $x_{1} \in (ξ, b)$ , and define ${x_{n}}$ by $x_{n + 1} = x_{n} - f (x_{n}) ∕ f^{'} (x_{n})$ . Interpret this geometrically, in terms of a tangent to the graph of $f$ .

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

x_{n + 1} - ξ = \frac{f^{″} (t_{n})}{2 f^{'} (x_{n})} {(x_{n} - ξ)}^{2}

for some $t_{n} \in (ξ, x_{n})$ .

(d) if $A = M ∕ 2 δ$ , deduce that

0 \leq x_{n + 1} - ξ \leq \frac{1}{A} {(A (x_{1} - ξ))}^{2^{n}} .

Compare with Exercises 3.16 and 3.18.

(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^{'} (x)} .

How does $g^{'} (x)$ behave for $x$ near $ξ$ ?

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

Answers

(a) The tangent to the graph of $f$ at the point $(x_{n}, f (x_{n}))$ has the equation

y - f (x_{n}) = f^{'} (x_{n}) (x - x_{n}) .

Letting $y = 0$ and solving for $x$ , we see that this line intersects the $x$ -axis at the point $(x_{n + 1}, 0)$ .

(b) Note that if $x_{n} > ξ$ then $f (x_{n}) > 0$ so that $x_{n + 1} = x_{n} - f (x_{n}) ∕ f^{'} (x_{n}) < x_{n}$ . By Theorem 5.10, there is a $t \in (ξ, x_{n})$ such that

f (x_{n}) = f (x_{n}) - f (ξ) = f^{'} (t) (x_{n} - ξ) or ξ = x_{n} - \frac{f (x_{n})}{f^{'} (t)} \leq x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})} = x_{n + 1}

since $f^{″} \geq 0$ implies $f^{'} (t) \leq f^{'} (x_{n})$ . If for some $m$ $x_{m} = ξ$ then $x_{m + 1} = x_{m + 2} = \dots = ξ$ and so the infinite sequence converges to $ξ$ . Otherwise, it is a monotonically decreasing sequence with lower bound $ξ$ and so by Theorem 3.14 converges to a limit $y \geq ξ$ .

To see that $y = ξ$ , let $g$ be the continuous function defined in part (e), $g (x) = x - f (x) ∕ f^{'} (x)$ . Assume that $y > ξ$ . Then $f (y) > 0$ , so $g (y) < y$ . Let $𝜀 > 0$ be small enough so that $g (y) + 𝜀 < y$ . Then there is a $δ > 0$ such that $| g (x) - g (y) | < 𝜀$ if $| x - y | < δ$ . Let $N$ be large enough so that $| x_{N} - y | < δ$ . Then $g (x_{N}) < g (y) + 𝜀 < y$ , but this contradicts $g (x_{N}) = x_{N + 1} \geq y$ . Hence $y = ξ$ .

(c) Letting $α = x_{n}$ and $β = ξ$ in Theorem 5.15, and using $f (x_{n}) = f^{'} (x_{n}) (x_{n} - x_{n + 1})$ , there is some $t_{n} \in (ξ, x_{n})$ such that

\begin{array}{l} f (ξ) & = f (x_{n}) + f^{'} (x_{n}) (ξ - x_{n}) + \frac{f^{″} (t_{n})}{2} {(ξ - x_{n})}^{2} \\ 0 & = f^{'} (x_{n}) (x_{n} - x_{n + 1}) + f^{'} (x_{n}) (ξ - x_{n}) + \frac{f^{″} (t_{n})}{2} {(ξ - x_{n})}^{2} \\ 0 & = f^{'} (x_{n}) (ξ - x_{n + 1}) + \frac{f^{″} (t_{n})}{2} {(ξ - x_{n})}^{2} \\ x_{n + 1} - ξ & = \frac{f^{″} (t_{n})}{2 f^{'} (x_{n})} {(x_{n} - ξ)}^{2} \end{array}

(d) Part (c) gives us

\begin{array}{l} (x_{n + 1} - ξ) & \leq A {(x_{n} - ξ)}^{2} \\ \leq A \cdot A^{2} {(x_{n - 1} - ξ)}^{2^{2}} \\ \leq A \cdot A^{2} \cdot A^{2^{2}} {(x_{n - 2} - ξ)}^{2^{3}} \\ \leq \dots \\ \leq A^{1 + 2 + 2^{2} + \dots + 2^{n - 1}} {(x_{1} - ξ)}^{2^{n}} = A^{2^{n} - 1} {(x_{1} - ξ)}^{2^{n}} = \frac{1}{A} {(A (x_{1} - ξ))}^{2^{n}} . \end{array}

The algorithm described in Exercises 3.16 and 3.18 is Newton’s method applied to the functions $x^{2} - α$ and $x^{p} - α$ , respectively.

(e) We have $g (ξ) = ξ$ if and only if $f (ξ) = 0$ . Since

g^{'} (x) = 1 - \frac{f^{'} {(x)}^{2} - f (x) f^{″} (x)}{f^{'} {(x)}^{2}} = \frac{f (x) f^{″} (x)}{f^{'} {(x)}^{2}} \leq f (x) \frac{M}{δ^{2}},

$g^{'} (x)$ tends to 0 as $x$ approaches $ξ$ .

(f) For $f (x) = x^{1 ∕ 3}$ , note that

x_{n + 1} = x_{1} - \frac{x_{n}^{1 ∕ 3}}{(1 ∕ 3) x_{n}^{- 2 ∕ 3}} = - 2 x_{n}

so that $x_{n} = {(- 2)}^{n - 1} x_{1}$ . That is, ${x_{n}}$ is an alternating sequence such that $| x_{n} | \to \infty$ as $x \to \infty$ .

analambanomenos

2023-08-07 00:00

Exercise 5.25

Answers

Comments

Add answer