Q: When can we say that the starting value is near the root in Newton Raphson method?

Question

I would like to know when can I use the Newton Raphson methos to find an approximation of a root. We know that it can be used or that it is possible to work when the starting value is near of the root; but what is near? I mean, if for example if I've got $f(x)=(x-3)^{1/2}$ I know that the root would be $3$, so can I start from the point $p_0=4$? Is $4$ near $3$???

Answer 1

In principle it may be possible to determine the immediate basin of attraction of a root $r$ of your function $f$, i.e. the largest interval $(a,b)$ containing $r$ such that Newton's method starting at any point in $(a,b)$ converges to $r$. Namely, $a$ and $b$ (if finite) are the closest points to left and right of $r$ which are either roots of $f'$, or points where $f$ is not differentiable, or they form a $2$-cycle for Newton's method.

However, in practice the simplest thing to do, to tell whether a point is "sufficiently close", is usually just to try it and see what happens to the iterations.

Your example $f(x) = (x-3)^{1/2}$ is not a good candidate for Newton's method, because (if you stick to real numbers) the function is not defined for $x < 3$ and (even if you allow complex numbers) is not differentiable at $x=3$. If you start at any $x_0 > 3$, the very first iteration will take you to numbers $< 3$. Perhaps you mean $(x-3)^2$.

Answer 2

It is possible to characterize a symmetric open interval $I = (r-\delta,r+\delta)$ around the root $r$ such that Newton's method converges to $r$ for all $x_0 \in I$.

Newton's method is a special case of the functional iteration $x_{n+1} = g(x_n)$. It corresponds to the choice of $$g(x) = x - \frac{f(x)}{f'(x)}.$$

Now if $J$ is a closed interval and $h : J \rightarrow J$ is a contractive mapping, then $h$ has exactly one fixed point $\xi \in J$ and the functional iteration $x_{n+1} = h(x_n)$ will converge to $\xi$ for all $x_0 \in J$. This is the celebrated contractive mapping theorem. The condition that $J$ be closed is necessary. A contractive mapping $h : J \rightarrow \mathbb{R}$ is a function such that $$\exists L \in [0,1) \: \forall x, y \in J \: : \: |h(x) - h(y)| \leq L |x-y|.$$ If $h$ is differentiable and $|h'(t)| \leq L < 1$ for all $t \in J$, then the mean value theorem of differentiation implies that $h$ is a contractive mapping.

Now in terms of Newton's method we have $$g'(x) = \frac{f(x) f''(x)}{f'(x)}.$$ Clearly, $g'(r) = 0$, because $f(r) = 0$. Now let $I \subseteq \mathbb{R}$ be an open interval of the form $I = (r-\delta, r+\delta)$ such that $$\forall x \in I \: : \: |g'(x)| < 1.$$ I will now show that Newton's method will converge to $r$ for all $x_0 \in I$. I cannot immediately deploy the contractive mapping theorem, because $I$ is an open interval. However, if $\rho = |r-x_0|$, then $$J = [r-\rho,r+\rho]$$ is a closed interval and $x_0 \in J$ and $J \subset I$. I will now show that $g$ maps $J$ into itself. If $x \in J$, then there exist at least one $t$ between $r$ and $x$ such $$|g(x) - r| = |g(x)-g(r)| = |g'(t)||x-r|.$$ Since $t \in J \subset I$ we have $|g'(t)| < 1$. It follows that $$|g(x)-r)| < \rho.$$ This shows that $g$ maps $J$ into itself. By the contractive mapping theorem, we can now conclude that Newton's method converges to $r$. Since $x_0 \in I$ was arbitrary, the proof is complete.

Now for some illustrative examples.

1. The equation $f(x) = x^2 - 2 = 0$ can be used to compute $\sqrt{2}$. We have $$g'(x) = \frac{f(x)f''(x)}{f'(x)} = \frac{x^2-2}{2x^2}.$$ We have $|g'(x)| < 1$ if and only if $|x^2-2| < 2 |x|$. It follows that $x<-\sqrt{\frac{2}{3}}$ or $\sqrt{\frac{2}{3}} < x$. By the previous analysis we can choose $\delta = \sqrt{2} - \sqrt{\frac{2}{3}}$ and Newton's method will converge to $\sqrt{2}$ for any $x_0 \in I = (\sqrt{2} - \delta, \sqrt{2} + \delta)$. Note: Far more is true for this specific function $f$.
2. The equation $f(x) = (x-3)^2$ was suggested by @RobertIsrael. Then $$g(x) = x - \frac{f(x)}{f'(x)} = x - \frac{(x-3)^2}{2(x-3)} = x - \frac{1}{2}(x-3).$$ We find that $g'(x) = \frac{1}{2}$ and Newton's method converges linearly for all $x_0 \in \mathbb{R}$. Note: This is readily seen from $$3-g(x) = -\frac{1}{2}(3-x).$$