Advanced

On the speed of convergence of Newton's method for complex polynomials

Bilarev, Todor; Aspenberg, Magnus LU and Schleicher, Dierk (2016) In Mathematics of Computation 85(298). p.693-705
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 S-d 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 S-d 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 1-2/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 S-d 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 S-d 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 1-2/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 well-separated (so-called delta-separated) 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:
author
organization
publishing date
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
1088-6842
DOI
10.1090/mcom/2985
language
English
LU publication?
yes
id
22457e12-6989-4301-95cc-71d52d7245aa (old id 8728531)
date added to LUP
2016-02-26 11:01:28
date last changed
2017-06-18 03:27:48
@article{22457e12-6989-4301-95cc-71d52d7245aa,
  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 S-d 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 S-d 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 1-2/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 well-separated (so-called delta-separated) 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         = {1088-6842},
  language     = {eng},
  number       = {298},
  pages        = {693--705},
  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},
}