On the speed of convergence of Newton's method for complex polynomials
(2016) In Mathematics of Computation 85(298). p.693705 Abstract
 We investigate Newton's method for complex polynomials of arbitrary degree d, normalized so that all their roots are in the unit disk. For each degree d, we give an explicit set Sd of 3.33d log(2) d(1 + o(1)) points with the following universal property: for every normalized polynomial of degree d there are d starting points in Sd 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 12/d the number of iterations for these d starting points to reach all roots with precision epsilon is O(d(2) log(4) d + d log vertical bar log epsilon vertical bar). This is an improvement of an earlier result by Schleicher, where the... (More)
 We investigate Newton's method for complex polynomials of arbitrary degree d, normalized so that all their roots are in the unit disk. For each degree d, we give an explicit set Sd of 3.33d log(2) d(1 + o(1)) points with the following universal property: for every normalized polynomial of degree d there are d starting points in Sd 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 12/d the number of iterations for these d starting points to reach all roots with precision epsilon is O(d(2) log(4) d + d log vertical bar log epsilon vertical bar). This is an improvement of an earlier result by Schleicher, where the number of iterations is shown to be O(d(4) log(2) d + d(3) log(2) d vertical bar log epsilon vertical bar) in the worst case (allowing multiple roots) and O(d(3) log(2) d(log d + log delta) + d log vertical bar log epsilon vertical bar) for wellseparated (socalled deltaseparated) roots. Our result is almost optimal for this kind of starting points in the sense that the number of iterations can never be smaller than O(d(2)) for fixed e. It provides theoretical support for an empirical study, by Schleicher and Stoll, in which all roots of polynomials of degree 10(6) and more were found efficiently. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/8728531
 author
 Bilarev, Todor; Aspenberg, Magnus ^{LU} and Schleicher, Dierk
 organization
 publishing date
 2016
 type
 Contribution to journal
 publication status
 published
 subject
 in
 Mathematics of Computation
 volume
 85
 issue
 298
 pages
 693  705
 publisher
 American Mathematical Society (AMS)
 external identifiers

 wos:000369093400007
 scopus:85000799269
 ISSN
 10886842
 DOI
 10.1090/mcom/2985
 language
 English
 LU publication?
 yes
 id
 22457e126989430195cc71d52d7245aa (old id 8728531)
 date added to LUP
 20160226 11:01:28
 date last changed
 20180204 03:19:28
@article{22457e126989430195cc71d52d7245aa, abstract = {We investigate Newton's method for complex polynomials of arbitrary degree d, normalized so that all their roots are in the unit disk. For each degree d, we give an explicit set Sd of 3.33d log(2) d(1 + o(1)) points with the following universal property: for every normalized polynomial of degree d there are d starting points in Sd 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 12/d the number of iterations for these d starting points to reach all roots with precision epsilon is O(d(2) log(4) d + d log vertical bar log epsilon vertical bar). This is an improvement of an earlier result by Schleicher, where the number of iterations is shown to be O(d(4) log(2) d + d(3) log(2) d vertical bar log epsilon vertical bar) in the worst case (allowing multiple roots) and O(d(3) log(2) d(log d + log delta) + d log vertical bar log epsilon vertical bar) for wellseparated (socalled deltaseparated) roots. Our result is almost optimal for this kind of starting points in the sense that the number of iterations can never be smaller than O(d(2)) for fixed e. It provides theoretical support for an empirical study, by Schleicher and Stoll, in which all roots of polynomials of degree 10(6) and more were found efficiently.}, author = {Bilarev, Todor and Aspenberg, Magnus and Schleicher, Dierk}, issn = {10886842}, language = {eng}, number = {298}, pages = {693705}, publisher = {American Mathematical Society (AMS)}, series = {Mathematics of Computation}, title = {On the speed of convergence of Newton's method for complex polynomials}, url = {http://dx.doi.org/10.1090/mcom/2985}, volume = {85}, year = {2016}, }