Skip to Main content Skip to Navigation
Reports

On Approximating Complex Polynomial Zeros: Modified Quadtree (Weyl's) Construction and Improved Newton's Iteration

Victor Y. Pan 1
1 SAFIR - Algebraic Formal Systems for Industry and Research
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The known record complexity estimates for approximating polynomial zeros rely on geometric constructions on the complex plane, which achieve initial approximation to the zeros and/or their clusters as well as their isolation from each other, and on the subsequent fast analytic refinement of the initial approximations. We modify Weyl's classical geometric construction for approximating all the $n$ polynomial zeros in order to more rapidly achieve their strong isolation. For approximating the isolated zeros or clusters of zeros, we propose a new extension of Newton's iteration to yield quadratic global convergence (right from the start), under substantially weaker requirements to their initial isolation than one needs in the known algorithms.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00073796
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 1:46:16 PM
Last modification on : Saturday, January 27, 2018 - 1:31:32 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:58:30 PM

Identifiers

  • HAL Id : inria-00073796, version 1

Collections

Citation

Victor Y. Pan. On Approximating Complex Polynomial Zeros: Modified Quadtree (Weyl's) Construction and Improved Newton's Iteration. RR-2894, INRIA. 1996. ⟨inria-00073796⟩

Share

Metrics

Record views

119

Files downloads

219