Easy conditions that guarantee the convergence of Newton's method I know that Newton's method was discussed often at this forum, but I am still looking for an easy sufficient condition for the convergence of Newton's method without things like "initial guess close enough".
The idea of Newton's method is to use the iteration
$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ to get a root of the function
$f(x)$

What are sufficient conditions to guarantee the convergence of this method ?

Wikipedia shows several issues that can occur.
I found some conditions here on the forum and I noticed Kantorovich's theorem. But it is not easy to understand what this means in practice.
I only want to have conditions for the one-dimensional case, and the convergence need not to be quadratic. And it does not matter to which root the method converges (I only want to be sure that it converges at all).
It can also be assumed that $f(x)$ is defined on an interval $[a,b]$ and that this interval contains at least one root of $f(x)$
Some special cases :


*

*Is it enough that $f'(x)\ne 0$ for all $x\in [a,b]$ and either $f''(x)>0$ for all $x\in [a,b]$ or $f''(x)<0$ for all $x\in [a,b]$ to guarantee the convergence for every starting point in $[a,b]$ ?

*Is it enough that either $f'(x)>0$ for all $x\in [a,b]$ or $f'(x)<0$ for all $x\in [a,b]$ , and that $f'(x)$ is bounded in $[a,b]$ to guarantee the convergence for every starting point in $[a,b]$ ?
If no, how can I modify these conditions so that they become sufficient ?
 A: Partial answer : Neither condition is sufficient. Let $f:R \to R$ be twice differentiable . Let $a\in (0,\pi /6)$ and $b=\pi /4.$ Let $f(x)=-\sqrt 3 /2+\cos x$ for $x\in [a,b].$ If $a$ is close enough to $0$ and the starting point $x_1$ is close enough to $a$ then the slope $f'(x_1)=-\sin x_1$ will be so close  to $0$ that $x_2=x_1-f(x_1)/f'(x_1) >b.$ The behavior of $f$ on $(b,\infty)$ is indeterminate (except that $f$ is twice differentiable on $R$). For example we could have $f'(x_2)=0\ne f(x_2),$ and then the next iterate $x_3$ doesn't exist. If some iterate $x_n$ can fail to lie in $[a,b]$ then conditions on $f(x),f'(x),$ and  $f''(x)$ for $x'\in [a,b]$ will not suffice.
For differentiable $f$:
One well-known sufficient set of conditions is  (i) $f(a)<0<f(b),$ (ii) $f'(a)>0$ and $f'$ is increasing (not necessarily strictly increasing ) on $[a,b],$ (iii) $a-f(a)/f'(a)\leq b.$.... Then there is a unique $x_0\in (a,b)$ such that $f(x_0)=0.$ Let $x^*=x-f(x)/f'(x).$ If $x\in [a,x_0)$ then $x^*\in [x_0,b].$ If $x\in (x_0,b]$ then $x^*\in [x_0,x).$
Another well-known sufficient set of conditions is (i) $f(a)<0<f(b),$ (ii) $f$ is monotonic on $[a,b],$ (iii) $f$ is  concave  on $[a,x_0),$ and $f$ is convex  on $(x'_0,b],$ where $x_0=\min \{x\in [a,b]: f(x)=0\}$ and $x'_0=\max \{x\in [a,b]:f(x)=0\}.$... If $x\in [a,x_0)$ then $x^*\in (x,x_0].$ If $x\in (x'_0,b]$ then $x^*\in [x'_0,x).$ (With $x^*$ as in the previous paragraph.) 
Proof for the 1st set of conditions: 


*

*$f'>0$ on $[a,b]$ so $f$ is strictly increasing and continuous  on $[a,b]$ with $f(a)<0<f(b).$ This implies the existence and uniqueness of $x_0.$

*If $x\in (a,x_0)$ then $f(a)<f(x)<0$ and $f'(x)\geq f'(a)>0.$ So the line thru the point $(x,f(x))$ with slope $f'(x)$ will intersect the $x$-axis at $(x^*,0) ,$  while the line thru $(a,f(a))$ with slope $f(a)$ will intersect the $x$-axis at $(a^*,0),$  where $x<x^*<a^*\leq b.$

*To show that $x\in [a,x_0)\implies f(x^*)\geq 0$ :Observe that $(f(x^*)-f(x))/(x^*-x)=f'(y)$ for some $y\in (x,x^*).$ And $x<x^*$ so $f(x)<f(x^*)$. And we have  $$f(x)<f(x^*)<0\implies 0<\frac {f(x^*)-f(x)}{-f(x)}<1 . $$ But then we have  $y>x$ and$$f(x^*)<0\implies \ f'(y)=
\frac {f(x^*)-f(x)}{x^*-x}=$$ $$=\frac {f(x^*)-f(x)}{-f(x)/f'(x)}= \frac {f(x^*)-f(x)}{-f(x)} \cdot f'(x)<f'(x),$$ contradicting the fact that $f'$ is increasing on $[a,b].$

*To show that $x\in (x_0,b]\implies f(x^*)\in [x_0,x)$: The slope $S$ of the line joining $(x_0,f(x_0)=(x_0,0)$ to $(x,f(x))$ is equal to $f'(y)$ for some $y\in (x_0,x),$ so $0<S\leq f'(x).$ So the line thru $(x,f(x))$ with  slope $f'(x)$ will intersect the $x$-axis at $(x^*,0),$ with $x_0\leq x^*<x.$

*Finally if $x_1\in [a,b]$ and $x_{n+1}=x^*_n,$ then $x_0\leq x_{n+1}\leq x_n\leq b$ for $n\geq 2.$ So $(x_n)_{n\in N}$ converges to a limit $y\in [a,b].$ And since $f'(x)\geq f'(a)>0$ for all $x\in [a,b]$ we have $$0=\lim_{n\to \infty} |f(x_{n+1})-f(x_n)|= \lim_{n\to \infty}|f(x_n)/f'(x_n)|\geq \lim_{n\to \infty}|f(x_n)|/f'(a)=|f(y)|/f'(a).$$ So $f(y)=0.$

A: The main issue is to look back at the Banach fixed point theorem. Newton's method tries to find a fixed point of $g(x)=x-\frac{f(x)}{f'(x)}$. The Banach fixed point theorem gives you the existence and a recipe for computing the fixed point provided that $g$ maps some compact set into itself and is contractive on that compact set. Assuming $f$ has two continuous derivatives, contractivity means that $\left | \frac{f(x) f''(x)}{f'(x)^2} \right |$ is less than $1$ on that compact set. It is OK for this to exclude the actual root itself, which is of course important for the case when $f'$ vanishes at the root. But that's about the only condition that you can easily relax.
In my experience the more difficult condition to check is actually to find a compact set that $g$ maps into itself. This can be easy under some assumptions about signs of various quantities but it is often quite hard.
Also, you can get a feel for that contractivity condition by taking leading order approximations of each term. You find that to leading order, assuming $f'(x^*) \neq 0$, the condition says
$$\left | \frac{f'(x^*)f''(x^*)}{f'(x^*)^2} \right |<\frac{1}{|x-x^*|}$$
and this is nearly correct provided $|f''(y)(x-x^*)| \ll |f'(x^*)|$ and $|f'''(y)(x-x^*)| \ll |f''(x^*)|$ for $y$ between $x$ and $x^*$.
