Algorithm 493: Zeros of a Real Polynomial [C2]
Michael A. Jenkins · ACM Transactions on Mathematical Software · 1975
The subroutine RPOLY is a Fortran program to find all the zeros of a real polynomial.The parameters are: OP double precision vector of coefficients in order of decreasing powers of the variable D E G R E E integer degree of the polynomial ZEROR, double precision vectors of real and imaginary parts of the zeros found ZEROI by the algorithm FAIL logical parameter which is true only if the leading coefficient is zero or if R P O L Y has found fewer than degree zeros; in the latter case the degree is reset to the number of zeros found.The routine as written solves polynomials of degree up to 100; however, this can be modified by systematic changing of the declarations in the routines.The program is based on the three-stage algorithm described in Jenkins and Traub [1].The algorithm generates a sequence of polynomials of degree one less than the degree of the given polynomial from which an approximation to a zero or a quadratic factor can be extracted.The first stage is linearly convergent and involves no shift of origin.It is used primarily to bias the decision making process in the second stage in favor of the zeros of small magnitude.The second stage is also linearly convergent and involves a double shift to a complex point and its conjugate.The shift point is chosen arbitrarily on a circle whose radius is less than the magnitude of all the zeros.In most cases, either the shift is closest to a real zero, or the pair of shift points are equidistant and closest to a pair of zeros.In the former case the second stage yields an approximation to the real zero and in the latter case