{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:36:14Z","timestamp":1776800174483,"version":"3.51.2"},"reference-count":7,"publisher":"American Mathematical Society (AMS)","issue":"298","license":[{"start":{"date-parts":[[2016,6,18]],"date-time":"2016-06-18T00:00:00Z","timestamp":1466208000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We investigate Newton\u2019s method for complex polynomials of arbitrary degree\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , normalized so that all their roots are in the unit disk. For each degree\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , we give an explicit set\n \n \n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msub>\n \\mathcal {S}_d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n of\n \n \n \n \n 3.33<\/mml:mn>\n d<\/mml:mi>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n d<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n 3.33d\\log ^2 d(1 + o(1))<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n points with the following universal property: for every normalized polynomial of degree\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n there are\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n starting points in\n \n \n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msub>\n \\mathcal {S}_d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n whose Newton iterations find all the roots with a low number of iterations: if the roots are uniformly and independently distributed, we show that with probability at least\n \n \n \n \n 1<\/mml:mn>\n \n \u2212\n \n <\/mml:mo>\n 2<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:mrow>\n 1-2\/d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n the number of iterations for these\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n starting points to reach all roots with precision\n \n \n \n \n \u03b5\n \n <\/mml:mi>\n \\varepsilon<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n d<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n log<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n d<\/mml:mi>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n O(d^2\\log ^4 d + d\\log |\\log \\varepsilon |)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . This is an improvement of an earlier result by Schleicher, where the number of iterations is shown to be\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n d<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msup>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n \n d<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n d<\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n O(d^4\\log ^2 d + d^3\\log ^2d|\\log \\varepsilon |)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in the worst case (allowing multiple roots) and\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n d<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n d<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n \u03b4\n \n <\/mml:mi>\n )<\/mml:mo>\n +<\/mml:mo>\n d<\/mml:mi>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n O(d^3\\log ^2 d(\\log d + \\log \\delta ) + d\\log |\\log \\varepsilon |)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for well-separated (so-called\n \n \n \n \n \u03b4\n \n <\/mml:mi>\n \\delta<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -separated) roots.\n <\/p>\n

\n Our result is almost optimal for this kind of starting points in the sense that the number of iterations can never be smaller than\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n d<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(d^2)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for fixed\n \n \n \n \n \u03b5\n \n <\/mml:mi>\n \\varepsilon<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . It provides theoretical support for an empirical study, by Schleicher and Stoll, in which all roots of polynomials of degree\n \n \n \n \n 10<\/mml:mn>\n 6<\/mml:mn>\n <\/mml:msup>\n 10^6<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and more were found efficiently.\n <\/p>","DOI":"10.1090\/mcom\/2985","type":"journal-article","created":{"date-parts":[[2015,6,18]],"date-time":"2015-06-18T14:37:28Z","timestamp":1434638248000},"page":"693-705","source":"Crossref","is-referenced-by-count":11,"title":["On the speed of convergence of Newton\u2019s method for complex polynomials"],"prefix":"10.1090","volume":"85","author":[{"given":"Todor","family":"Bilarev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magnus","family":"Aspenberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dierk","family":"Schleicher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,6,18]]},"reference":[{"issue":"281","key":"1","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1090\/S0025-5718-2012-02640-8","article-title":"A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton\u2019s method","volume":"82","author":"Bollob\u00e1s, B\u00e9la","year":"2013","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s002220100149","article-title":"How to find all roots of complex polynomials by Newton\u2019s method","volume":"146","author":"Hubbard, John","year":"2001","journal-title":"Invent. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-9910","issn-type":"print"},{"issue":"4","key":"3","first-page":"78","article-title":"The measure of maximal entropy of a rational endomorphism of a Riemann sphere","volume":"16","author":"Lyubich, M. Yu.","year":"1982","journal-title":"Funktsional. Anal. i Prilozhen.","ISSN":"https:\/\/id.crossref.org\/issn\/0374-1990","issn-type":"print"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1090\/fic\/053\/09","article-title":"Rational and transcendental Newton maps","author":"R\u00fcckert, Johannes","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9780821842751"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1090\/fic\/053\/10","article-title":"Newton\u2019s method as a dynamical system: efficient root finding of polynomials and the Riemann \ud835\udf01 function","author":"Schleicher, Dierk","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9780821842751"},{"key":"6","unstructured":"[S2] D. Schleicher, On the efficient global dynamics of Newton\u2019s method for complex polynomials. Manuscript, submitted (2011). arXiv:1108.5773."},{"key":"7","unstructured":"[SSt] D. Schleicher and R. Stoll, Newton\u2019s method in practice: finding all roots of polynomials of degree one million efficiently. Manuscript, submitted (2015)."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-298\/S0025-5718-2015-02985-8\/S0025-5718-2015-02985-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-298\/S0025-5718-2015-02985-8\/S0025-5718-2015-02985-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:41:57Z","timestamp":1776796917000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-298\/S0025-5718-2015-02985-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,18]]},"references-count":7,"journal-issue":{"issue":"298","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["S0025-5718-2015-02985-8"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/2985","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2015,6,18]]}}}