a generalized graeffe's iteration for evaluating polynomials and rational functions
In this paper we present a suitable generalization of the classical Graeffe's iteration by showing that it provides effective algorithms for the fast evaluation of polynomials and residues of rational and meromorphic functions. In particular, if g ( z ) = q ( z )/ p ( z ) is a rational function with n finite poles &xgr; 1 ,,&xgr; n and &xgr; is an initial approximation of &xgr; k such that &xgr; - &xgr; k  < &xgr; - &xgr; j  for any j ? k , 1 &lne; j &lne; n , then an extrapolation method is found for computing the residue of g ( z ) at &xgr; k by means of successive evaluations of the derivatives of q ( z ) and p ( z ) at the point z = &xgr;. In the case where q ( z ) = zp ?( z ) we thus obtain a set of iterations for the refinement of polynomial zeros. Moreover, by setting q ( z ) = r ( z ) p ?( z ), the same approach can also be used for the fast approximate evaluation of r ( z ) on the zeros of p ( z ).
graeffe's iteration meromorphic functions polynomial zeros fast approximate polynomial evaluation residue computation