14
$\begingroup$

For a polynomial $P$ of degree $n$ with real coefficients and with $n$ distinct real roots, the Newton's method $z_{n+1} = z_n - {P(z_n) \over P'(z_n)}$ converges for almost all initial values $z_0$ in $\mathbb R$ (or almost all $z_0$ in $\bf C$ with respect to the area measure) to a root of $P$. This is a result due to M. Lyubich (~ 1984).

I think I remember that for a polynomial with complex coefficients, almost all initial values $z_0$ has an orbit that converges to a periodic orbit in ${\mathbb C} \cup \{\infty\}$, but there are examples where that orbit is not a root of $P$.

Unfortunately, I can't remember who is the author of that result and I would like to find a reference.

EDIT: the result is actually false. There are polynomials whose Newton's method has a periodic Siegel disk, see e.g. this answer. In that case, there is an open set of points whose orbit's $\omega$-limit set is a circle.

$\endgroup$
  • $\begingroup$ In the result of Lyubich, the starting point $z_0$ is also real. $\endgroup$ – Alexandre Eremenko Oct 26 '18 at 0:11
  • 1
    $\begingroup$ It's $z_{n+1} = z_n - {P(z_n) \over P'(z_n)}$, not + $\endgroup$ – smci Oct 26 '18 at 9:21
  • $\begingroup$ @eremenko. It also works with $z_0$ complex (in which case the measure is the area). See Lyubich, Th 1.27 p92 of his 1986 survey, "the dynamics of rational transform: the topological picture". $\endgroup$ – coudy Oct 26 '18 at 10:28
12
$\begingroup$

I don't think your initial assertion is accurate. Consider, for example, $f(z)=z^5-z-1$. If you iterate the Newton's method function $N(z) = z-f(z)/f'(z)$ from $z_0=0$, you'll quickly find an attractive orbit of period 3. The basin of attraction of that orbit is a positive measure set with no point converging to a root of $f$. The standard Newton method picture looks like so:

enter image description here

Those black regions are exactly where your assertion fails. Notice, also, the five regions converging to five simple roots.

$\endgroup$
  • 1
    $\begingroup$ Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks. $\endgroup$ – coudy Oct 25 '18 at 22:36
  • $\begingroup$ This answer does not address the question. $\endgroup$ – Alexandre Eremenko Oct 25 '18 at 23:22
  • 3
    $\begingroup$ @AlexandreEremenko this post most certainly addresses the question as originally stated. $\endgroup$ – Mark McClure Oct 25 '18 at 23:49
  • 3
    $\begingroup$ @AlexandreEremenko In the first paragraph of his original post he stated that almost every initial seed converged to a root of the polynomial. I was simply pointing out that is not correct at the level of generality that he originally stated. I'm not claiming it's profound. :) $\endgroup$ – Mark McClure Oct 26 '18 at 0:01
  • 1
    $\begingroup$ @AlexandreEremenko Hmm... perhaps I neglected to mention that my post was written in response to his post as originally stated because the all real root thing is exactly the part he left out. Here's a link to the original post, if you're not sure what I'm talking about. Regardless, we should stop discussing this trivial matter. $\endgroup$ – Mark McClure Oct 26 '18 at 0:24
7
$\begingroup$

Your statement that iterates of the Newton method converge to a cycle almost everywhere is equivalent to the statement that for every polynomial $f$ the Julia set of the rational function $z-f(z)/f'(z)$ has zero area. This is unlikely to be true, but I do not know a published counterexample.

For the state of the art on Newton Method for polynomials, I recommend these papers:

MR1859017 J. Hubbard, D. Schleicher, S. Sutherland, How to find all roots of complex polynomials by Newton's method. Invent. Math. 146 (2001), no. 1, 1–33.

MR3659421 D. Schleicher, R. Stoll, Newton's method in practice: Finding all roots of polynomials of degree one million efficiently. Theoret. Comput. Sci. 681 (2017), 146–166.

$\endgroup$
  • $\begingroup$ I'm tempted to say that this doesn't address the question, but .. +1 instead. :) Isn't it true, though, that the Julia set of a rational function either has zero area or is the whole Riemann sphere? $\endgroup$ – Mark McClure Oct 25 '18 at 23:48
  • 1
    $\begingroup$ @Mark McClure: No, this is not true in general. Function $z^2+c$ can have the Julia set of positive measure, according to a result of Buff and Cheritat. However this function is not a Newton method of a polynomial. $\endgroup$ – Alexandre Eremenko Oct 25 '18 at 23:56
  • $\begingroup$ Yes, you're right. Perhaps I was thinking non-empty interior. $\endgroup$ – Mark McClure Oct 26 '18 at 0:06
6
$\begingroup$

For Newton's method (and more general iterative methods) for finding roots of complex polynomials, you may want to look at Curt McMullen's paper:

Families of Rational Maps and Iterative Root-Finding Algorithms, Curt McMullen, Annals of Mathematics, Second Series, Vol. 125, No. 3 (May, 1987), pp. 467-493

From the abstract: "In this paper we develop a rigidity theorem for algebraic families of rational maps and apply it to the study of iterative root-finding algorithms. We answer a question of Smale's by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree 4 or more. We settle the case of degree 3 by exhibiting a generally convergent algorithm for cubics; and we give a classification of all such algorithms."

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.