Tangent Graeffe iteration

Gregorio Malajovich, Jorge P. Zubelli

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

Graeffe iteration was the choice algorithm for solving univariate polynomials 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 modern digital computers. We prove that under a certain generic assumption the proposed algorithm converges. We also estimate the error after N iterations and the running cost. The main ideas from which this algorithm is built are: classical Graeffe iteration and Newton Diagrams, changes of scale (renormalization), and replacement of a difference technique by a differentiation one. The algorithm was implemented successfully and a number of numerical experiments are displayed.

Original languageBritish English
Pages (from-to)749-782
Number of pages34
JournalNumerische Mathematik
Volume89
Issue number4
DOIs
StatePublished - Oct 2001

Fingerprint

Dive into the research topics of 'Tangent Graeffe iteration'. Together they form a unique fingerprint.

Cite this