0 like 0 dislike
98 views
Suppose that
$f(x)= \begin{cases}e^{-1 / x^{2}} & \text { if } x \neq 0 \\ 0 & \text { if } x=0\end{cases}$
The function $f$ is continuous everywhere, in fact differentiable arbitrarily often everywhere, and 0 is the only solution of $f(x)=0$. Show that if $x_{0}=0.0001$, it takes more than one hundred million iterations of the Newton Method to get below $0.00005$.
| 98 views

0 like 0 dislike
The differentiation (for $x \neq 0$ ) is straightforward. (Showing that $f^{\prime}(0)=0$ is more delicate, but we don't need that here.) By the Chain Rule,
$f^{\prime}(x)=\frac{2 e^{-1 / x^{2}}}{x^{3}} .$
Write down the standard Newton Method iteration. The $e^{-1 / x_{n}^{2}}$ terms cancel, and we get
$x_{n+1}=x_{n}-\frac{x_{n}^{3}}{2} \quad \text { or equivalently } \quad x_{n}-x_{n+1}=\frac{x_{n}^{3}}{2} .$
Now the analysis is somewhat delicate. It hinges on the fact that if $x_{n}$ is close to 0 , then $x_{n+1}$ is very near to $x_{n}$, meaning that each iteration gains us very little additional accuracy.
Start with $x_{0}=0.0001$. It is fairly easy to see that $x_{n}>0$ for all $n$. For $x_{1}=x_{0}\left(1-x_{0}^{2} / 2\right)$, and in particular $0<x_{1}<x_{0}$. The same idea shows that $0<x_{2}<x_{1}$, but then $0<x_{3}<x_{2}$, and so on forever.

Thus if we start with $x_{0}=0.0001$, the difference $x_{n}-x_{n+1}$ will always be positive and equal to $x_{n}^{3} / 2$, and in particular less than or equal to $(0.0001)^{3} / 2$. So with each iteration there is a shrinkage of at most $5 \times 10^{-13}$. But to get from $0.0001$ to $0.00005$ we must shrink by more than $5 \times 10^{-5}$. Thus we will need more than $\left(5 \times 10^{-5}\right) /\left(5 \times 10^{-13}\right)$, that is, $10^{8}$ iterations. (More, because as we get closer to $0.00005$, the shrinkage per iteration is less than what we estimated.)
by Platinum (130,878 points)

0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
1 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike