Question

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\).

Answer 1

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.)