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 ⪇ j ⪇ 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).