A Post-Fitting Algorithm for High Precision Complex Polynomial Root Finding
Peter Strobach · 2014
A noniterative algorithm for root refinement of univariate p olynomials with real or complex coefficients is introduced. The method uses a convolutional mode l which is fitted onto the coefficient sequence of a given polynomial. If initialized with root est imates from a conventional polynomial root finding algorithm like POLZEROS, the algorithm can double the number of accurate digits of these root estimates. Simulation results are shown for several types of polynomials which typically occur in signal and array processing. For instance, r andom coefficient polynomials up to degree n = 64000, where we reduced the absolute root errors of the POLZEROS root-finder by a factor of approximately 1000, or the roots of a complex chirp polynomial of degree n = 2000, where we reduced the absolute root errors by a factor of 10000 using the new method. Fortran subroutines of this high precision root refinement algorith m for real or complex polynomials are available upon request.