Newton\u2019s method is well known as a root finder locally near the roots. It is often \u201cnot recommended\u201d as a global root finder because of its \u201cchaotic\u201d properties. We give a very efficient theoretical upper bound on its speed of convergence: all roots of a degree d polynomial can be found with accuracy eps in O(d^2 log^4 d + d log\\log eps) Newton iterations in the expected case \u2014 very close to the theoretical upper bound of O(d^2) for this method. In practice, all roots of polynomials of degree more than a million are found routinely and in (4log 2) d^2 iterations \u2014 in practice, this means less than a day for degree a million on standard laptops. A modified method, for which we do not yet have a complete theory, brings this down to 3 d log^2 d iterations, which in practice for certain polynomials finds all roots of degree a million in a matter of minutes. <\/p>\n","protected":false},"excerpt":{"rendered":"
Newton\u2019s method is well known as a root finder locally near the roots. It is often \u201cnot recommended\u201d as a global root finder because of its \u201cchaotic\u201d properties. We give a very efficient theoretical upper bound on its speed of convergence: all roots…<\/p>\n