[Math] Newton’s method — for which initial guesses does it converge

basins-of-attractiondynamical systemsnewton raphsonnumerical methodsreal-analysis

We've got a function: $ f : \Bbb R \to \Bbb R$ defined by $f(x) = x^3 – 9$.
Let $x^* $ be its root, which means $ f(x^*) = 0$. We want to find approximation for $x^*$ using a Newton's method.
There are two questions I don't know how to answer:

  1. We choose an initial guess: $x_0 = 2,5$. Does it lineary converge for such $x_0$? And quadratically? And, most of all, I'm interested how to find range of $x_0 $ for which this method converges. How to do it?

  2. Can we show that $|x_3 – x^*| < 2^{-15}$? Is there a posiibility to do it without computing $x_3$, which is not that easy without a calculator?

Best Answer

I'm not an expert on Newton's Method, but I spent some time thinking about it last year while teaching an honors calculus course. As I understand it, the basic philosophy behind convergence of Newton's method is:

  1. Although one can find counterexamples to convergence by "making trouble", under reasonably mild hypotheses one can show there is $\delta > 0$ such that if $x_0 \in [c-\delta,c+\delta]$, then the sequence of Newton iterates converges to the true root $c$ "quadratically". One can certainly work out an explicit value of $\delta$: see below.

  2. On the other hand, if one starts with an $x_0$ which is "too far away" from $c$, then the question of whether the Newton's method iterates converge to $c$ can become arbitrarily complicated and delicate. (As in some sense it must: e.g. maybe there are other roots!) For instance if you look at $z \mapsto z^3-1$ (in the complex plane, which is not our setup), you get fractal basins of convergence.

Here is a result from my honors calculus notes which gives you an explicit value of $\delta$. $\newcommand{\ra}{\rightarrow}$ $\newcommand{\N}{\mathbb{N}}$ $\renewcommand{\R}{\mathbb{R}}$

Theorem Let $f: I \ra \R$ be twice differentiable, and let $x^* \in I^{\circ}$ be a root of $f$.
a) Suppose there are real numbers $\delta ,A ,B > 0$ such that for all $x \in [x^*-\delta,x^*+\delta]$, $|f'(x)| \geq A$ and $|f''(x)| \leq B$. For any $x_0 \in [x^*-\delta,x^*+\delta]$, let $\{x_n\}$ be the Newton's Method sequence with initial value $x_0$. Then for all $n \in \N$, $$ |x_{n+1} - x^*| \leq \frac{B}{A} |x_n - x^*|^2. $$ b) If $f''$ is continuous on $I$ and $f'(x^*) \neq 0$, then there are indeed $\delta,A,B > 0$ as in the statement of part a), so that the above inequality holds for all $x_0 \in [x^*-\delta,x^*+\delta]$.

You can try computing a $\delta$ this in your situation and check whether the $\delta$ you get is small enough so that $|3^{\frac{2}{3}}-2| \leq \delta$: I haven't tried this myself.

Related Question