3
$\begingroup$

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 ?

$\endgroup$
1
  • 1
    $\begingroup$ $1 > f'(x) > 0 $ on $[a,b]$ if the starting point and the solution lie inside of $[a,b]$. Also there is only one zero in the interval. But it's fairly strong conditions so maybe there are ones that are softer out there. $\endgroup$ Aug 14, 2016 at 16:36

2 Answers 2

2
$\begingroup$

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:

  1. $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.$
  2. 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.$
  3. 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].$
  4. 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.$
  5. 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.$
$\endgroup$
6
  • $\begingroup$ I have added a couple of sufficient conditions in my A. $\endgroup$ Aug 14, 2016 at 22:52
  • $\begingroup$ If you add a proof that the first set of conditions is sufficient, I will accept the answer. I already upvoted it. $\endgroup$
    – Peter
    Aug 15, 2016 at 8:24
  • $\begingroup$ I have added a proof for the 1st set of conditions. I have broken it into small parts which should help to see how each condition is used. $\endgroup$ Aug 16, 2016 at 2:10
  • $\begingroup$ Isaac Newton, (who, to quote Stephen Hawking , "was not a nice man.") would likely tell you to draw a graph to see that it's obvious. $\endgroup$ Aug 16, 2016 at 2:17
  • $\begingroup$ I did not find the "well known" sufficient condition online. Neither did I find it for the fixpoint iteration. $\endgroup$
    – Peter
    Aug 17, 2016 at 19:02
1
$\begingroup$

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^*$.

$\endgroup$
1
  • $\begingroup$ Why do we need the second derivative of $f$ to be continuous? $\endgroup$
    – J. C.
    Mar 30, 2020 at 18:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .