Convergence of Newton's method

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
3
down vote

favorite












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 $bf C$ 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 $bf 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.










share|cite|improve this question



























    up vote
    3
    down vote

    favorite












    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 $bf C$ 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 $bf 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.










    share|cite|improve this question

























      up vote
      3
      down vote

      favorite









      up vote
      3
      down vote

      favorite











      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 $bf C$ 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 $bf 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.










      share|cite|improve this question















      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 $bf C$ 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 $bf 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.







      reference-request complex-dynamics






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 1 hour ago

























      asked 2 hours ago









      coudy

      11.5k14591




      11.5k14591




















          3 Answers
          3






          active

          oldest

          votes

















          up vote
          2
          down vote













          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.






          share|cite|improve this answer




















          • Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
            – coudy
            1 hour ago










          • This answer does not address the question.
            – Alexandre Eremenko
            36 mins ago










          • @AlexandreEremenko this post most certainly addresses the question as originally stated.
            – Mark McClure
            8 mins ago










          • @Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
            – Alexandre Eremenko
            5 mins ago


















          up vote
          2
          down vote













          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."






          share|cite|improve this answer



























            up vote
            1
            down vote













            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.






            share|cite|improve this answer




















            • 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?
              – Mark McClure
              9 mins ago










            • @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.
              – Alexandre Eremenko
              1 min ago










            Your Answer




            StackExchange.ifUsing("editor", function ()
            return StackExchange.using("mathjaxEditing", function ()
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            );
            );
            , "mathjax-editing");

            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "504"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            convertImagesToLinks: true,
            noModals: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );













             

            draft saved


            draft discarded


















            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f313781%2fconvergence-of-newtons-method%23new-answer', 'question_page');

            );

            Post as a guest






























            3 Answers
            3






            active

            oldest

            votes








            3 Answers
            3






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            2
            down vote













            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.






            share|cite|improve this answer




















            • Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
              – coudy
              1 hour ago










            • This answer does not address the question.
              – Alexandre Eremenko
              36 mins ago










            • @AlexandreEremenko this post most certainly addresses the question as originally stated.
              – Mark McClure
              8 mins ago










            • @Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
              – Alexandre Eremenko
              5 mins ago















            up vote
            2
            down vote













            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.






            share|cite|improve this answer




















            • Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
              – coudy
              1 hour ago










            • This answer does not address the question.
              – Alexandre Eremenko
              36 mins ago










            • @AlexandreEremenko this post most certainly addresses the question as originally stated.
              – Mark McClure
              8 mins ago










            • @Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
              – Alexandre Eremenko
              5 mins ago













            up vote
            2
            down vote










            up vote
            2
            down vote









            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.






            share|cite|improve this answer












            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.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered 1 hour ago









            Mark McClure

            1,438613




            1,438613











            • Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
              – coudy
              1 hour ago










            • This answer does not address the question.
              – Alexandre Eremenko
              36 mins ago










            • @AlexandreEremenko this post most certainly addresses the question as originally stated.
              – Mark McClure
              8 mins ago










            • @Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
              – Alexandre Eremenko
              5 mins ago

















            • Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
              – coudy
              1 hour ago










            • This answer does not address the question.
              – Alexandre Eremenko
              36 mins ago










            • @AlexandreEremenko this post most certainly addresses the question as originally stated.
              – Mark McClure
              8 mins ago










            • @Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
              – Alexandre Eremenko
              5 mins ago
















            Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
            – coudy
            1 hour ago




            Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
            – coudy
            1 hour ago












            This answer does not address the question.
            – Alexandre Eremenko
            36 mins ago




            This answer does not address the question.
            – Alexandre Eremenko
            36 mins ago












            @AlexandreEremenko this post most certainly addresses the question as originally stated.
            – Mark McClure
            8 mins ago




            @AlexandreEremenko this post most certainly addresses the question as originally stated.
            – Mark McClure
            8 mins ago












            @Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
            – Alexandre Eremenko
            5 mins ago





            @Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
            – Alexandre Eremenko
            5 mins ago











            up vote
            2
            down vote













            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."






            share|cite|improve this answer
























              up vote
              2
              down vote













              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."






              share|cite|improve this answer






















                up vote
                2
                down vote










                up vote
                2
                down vote









                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."






                share|cite|improve this answer












                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."







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered 1 hour ago









                Joe Silverman

                29.8k178156




                29.8k178156




















                    up vote
                    1
                    down vote













                    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.






                    share|cite|improve this answer




















                    • 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?
                      – Mark McClure
                      9 mins ago










                    • @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.
                      – Alexandre Eremenko
                      1 min ago














                    up vote
                    1
                    down vote













                    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.






                    share|cite|improve this answer




















                    • 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?
                      – Mark McClure
                      9 mins ago










                    • @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.
                      – Alexandre Eremenko
                      1 min ago












                    up vote
                    1
                    down vote










                    up vote
                    1
                    down vote









                    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.






                    share|cite|improve this answer












                    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.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered 20 mins ago









                    Alexandre Eremenko

                    47.6k6130245




                    47.6k6130245











                    • 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?
                      – Mark McClure
                      9 mins ago










                    • @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.
                      – Alexandre Eremenko
                      1 min ago
















                    • 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?
                      – Mark McClure
                      9 mins ago










                    • @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.
                      – Alexandre Eremenko
                      1 min ago















                    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?
                    – Mark McClure
                    9 mins ago




                    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?
                    – Mark McClure
                    9 mins ago












                    @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.
                    – Alexandre Eremenko
                    1 min ago




                    @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.
                    – Alexandre Eremenko
                    1 min ago

















                     

                    draft saved


                    draft discarded















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f313781%2fconvergence-of-newtons-method%23new-answer', 'question_page');

                    );

                    Post as a guest













































































                    Comments

                    Popular posts from this blog

                    What does second last employer means? [closed]

                    Installing NextGIS Connect into QGIS 3?

                    One-line joke