Tangent Graeffe iteration

Citation
G. Malajovich et Jp. Zubelli, Tangent Graeffe iteration, NUMER MATH, 89(4), 2001, pp. 749-782
Citations number
42
Categorie Soggetti
Mathematics
Journal title
NUMERISCHE MATHEMATIK
ISSN journal
0029599X → ACNP
Volume
89
Issue
4
Year of publication
2001
Pages
749 - 782
Database
ISI
SICI code
0029-599X(200110)89:4<749:TGI>2.0.ZU;2-A
Abstract
Graeffe iteration was the choice algorithm for solving univariate polynomia ls in the XIX-th and early XX-th century. In this paper, a new variation of Graeffe iteration is given, suitable to IEEE floating-point arithmetics of modem digital computers. We prove that under a certain generic assumption the proposed algorithm converges. We also estimate the error after N iterat ions and the running cost. The main ideas from which this algorithm is buil t are: classical Graeffe iteration and Newton Diagrams, changes of scale (r enormalization), and replacement of a difference technique by a differentia tion one. The algorithm was implemented successfully and a number of numeri cal experiments are displayed.