Conditions for Newton's method to converge.

Question

I would like to know some, easy to use, conditions for Newton's method to converge. I know a condition that states that the method will converge for a function $f(x)$ If for an interval $[a, b]$ it is true that $$f(a)<0<f(b)$$ $$f'(x) >0$$ and $$f''(x) >0$$, but I would like to know how can I find $[a, b]$, should I do this by trial and error? And how can I generally use this method?

Answer 1

In many cases we can prove that $f'(x)>0$ and $f''(x)\geq 0$ for all $x$ without knowing anything about $a$ and $b.$ Then we may be able to prove there exists $a, b$ with $f(a)<0<f(b)$. In this case you can begin the iteration anywhere.

In practice a less restrictive but sufficient set of conditions is

(i). There exists $c$ with $f(c)=0.$

(ii).There exist $a>c$ (the same $c$ as in (i)) such that $f(a)>0$ and such that $f'(x)>0$ for $c<x\leq a.$

(iii). $f'$ is increasing on $(c,a).$ (That is, $c<x<y<a\implies f'(x)\leq f'(y)$ .)

For a non-linear function $f,$ condition (i), (ii) and (iii) imply that $f(x)>0$ for $c<x\leq a$ and that the sequence $a_{n+1}=a_n-f(a_n)/f'(a_n),$ with $a_1=a,$ is strictly decreasing and remains in $(c,a]$ so it has a limit $d,$ and that $f(d)=0$ (so $d=c$).

Example. Let $f(x)=x^4-10.$ We know there exists $c\in (0,2)$ with $f(c)=0$ because $f(0)<0<f(2)$. We have $f'(x)=4x^3 >0$ for $x>0$, hence $f'(x)>0$ for $x>c.$ We have $f''(x)=12x^2\geq 0$ , hence $f'$ is increasing for $x>c.$ So we can begin an iteration with $a=a_1=2.$