Preprint A44/2001
Tangent Graeffe Iteration

Jorge P. Zubelli | Malajovich, Gregorio

**Keywords: **
graeffe | fast-algorithms | root-finding

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.