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.
Type de document :
Rapport
RR-2894, INRIA. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00073796
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:46:16
Dernière modification le : samedi 27 janvier 2018 - 01:31:32
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:58:30

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

95

Téléchargements de fichiers

173