# Almost sure convergence of Newton's method

Background:

Let $f$ be a function on the real line. In numerical analysis, Newton's method for finding roots of the equation $f(x) = 0$ uses iteration $x_{n+1} = x_n - \frac{f(x_n)}{f^{'}(x_n)}$. According to Wikipedia, if $\alpha$ is a solution of $f(x) = 0$, then our $\{x_n\}$ satisfies the relation

$|\alpha - x_{n+1}| = \frac{|f^{''}(\zeta_n)|}{2|f^{'}(x_n)|} \cdot |\alpha - x_n|^2$,

where $\zeta_n$ is between $\alpha$ and $x_n$. This relation ensures quadratic convergence of Newton's method under suitable conditions.

https://en.wikipedia.org/wiki/Newton%27s_method

What I want to prove:

I want to prove that if $f$ is a polynomial having a real root, then ${x_n}$ converges to a root of $f$ for almost every choice of the initial point $x_0$. In other words, except for few (hopefully at most countable) pathological choices of $x_0$, for example unless $\{x_n\}$ enters a cycle or $f^{'}(x_n) = 0$ for some $n$, $x_n$ converges to one of the roots of $f$.

What I have found:

There are at most countably many $x_0$ for which $f'(x_n) = 0$ for some $n$, because $f'$ has finitely many roots. Also, unless $f^{'}(x_n) = 0$, $\{x_n\}$ does not diverge to $\pm \infty$. I inferred this from the shape of the graph of $y = f(x)$ when $x$ is large.

Can you help me to prove the whole assertion? Thanks!

• The statement is false. Try experimenting with $f(z)=z^5-z-1$. You should be able to find an attracting three cycle for the corresponding Newton's method iteration function. – Mark McClure Feb 1 '18 at 15:03
• Thanks for the answer! Well, I should have said I am dealing with functions on the real line. Then, are there still counterexamples like the one you suggested? – syn3449 Feb 1 '18 at 15:11
• Hmm... That function maps $\mathbb R \to \mathbb R$ and the attractive three cycle is real. Sorry if the $z$ misled you. – Mark McClure Feb 1 '18 at 15:16
• Thanks a lot. For those who might be interested, I found this paper ac.els-cdn.com/S0377042711000215/… , which describes a method of constructing polynomials with attracting cycles. – syn3449 Feb 1 '18 at 15:26