15
$\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.

Improve this question
$\endgroup$
3
  • $\begingroup$ In the result of Lyubich, the starting point $z_0$ is also real. $\endgroup$
    – Alexandre Eremenko
    Commented Oct 26, 2018 at 0:11
  • 1
    $\begingroup$ It's $z_{n+1} = z_n - {P(z_n) \over P'(z_n)}$, not + $\endgroup$
    – smci
    Commented Oct 26, 2018 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
    Commented Oct 26, 2018 at 10:28

3 Answers 3

Reset to default
13
$\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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks. $\endgroup$
    – coudy
    Commented Oct 25, 2018 at 22:36
  • $\begingroup$ This answer does not address the question. $\endgroup$
    – Alexandre Eremenko
    Commented Oct 25, 2018 at 23:22
  • 3
    $\begingroup$ @AlexandreEremenko this post most certainly addresses the question as originally stated. $\endgroup$
    – Mark McClure
    Commented Oct 25, 2018 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
    Commented Oct 26, 2018 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
    Commented Oct 26, 2018 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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Oct 25, 2018 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
    Commented Oct 25, 2018 at 23:56
  • $\begingroup$ Yes, you're right. Perhaps I was thinking non-empty interior. $\endgroup$
    – Mark McClure
    Commented Oct 26, 2018 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."

Improve this answer
$\endgroup$

You must log in to answer this question.

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