1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark McClure Feb 1 '18 at 15:03
  • $\begingroup$ 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? $\endgroup$ – syn3449 Feb 1 '18 at 15:11
  • $\begingroup$ Hmm... That function maps $\mathbb R \to \mathbb R$ and the attractive three cycle is real. Sorry if the $z$ misled you. $\endgroup$ – Mark McClure Feb 1 '18 at 15:16
  • $\begingroup$ 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. $\endgroup$ – syn3449 Feb 1 '18 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.