A small probabilistic universal set of starting points for finding roots\n of complex polynomials by Newton's method

2010/09/09 by Béla Bollobás, Bollobás, Béla, Malte Lackmann +3
Computer Science · Mathematics · #37F10 #49M15 #Dynamical Systems (math.DS) #FOS: Mathematics #Iterative Methods for Nonlinear Equations #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1009.1843

openalex publication_date 2010/09/09 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

We specify a small set, consisting of O(d(\log\log d)²) points, that\nintersects the basins under Newton's method of \all roots of \all\n(suitably normalized) complex polynomials of fixed degrees d, with\narbitrarily high probability. This set is an efficient and universal\n\probabilistic set of starting points to find all roots of polynomials of\ndegree d using Newton's method; the best known \deterministic set of\nstarting points consists of lceil 1.1d(\log d)² rceil points.\n

Related

• On the Efficient Global Dynamics of Newton's Method for Complex Polynomials
• A review of some recent results on random polynomials over R and over C
• Fast real and complex root-finding methods for well-conditioned polynomials
• A Globally Convergent Newton Method for Polynomials
• Certified counting of roots of random univariate polynomials