0 like 0 dislike
303 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$$.
| 303 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 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 (108k points)

0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
2 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike