Accurate Goertzel Algorithm: Error Analysis, Validations and Applications

Abstract

The Horner and Goertzel algorithms are frequently used in polynomial evaluation. Each of them can be less expensive than the other in special cases. In this paper, we present a new compensated algorithm to improve the accuracy of the Goertzel algorithm by using error-free transformations. We derive the forward round-off error bound for our algorithm, which implies that our algorithm yields a full precision accuracy for polynomials that are not too ill-conditioned. A dynamic error estimate in our algorithm is also presented by running round-off error analysis. Moreover, we show the cases in which our algorithms are less expensive than the compensated Horner algorithm for evaluating polynomials. Numerical experiments indicate that our algorithms run faster than the compensated Horner algorithm in those cases while producing the same accurate results, and our algorithm is absolutely stable when the condition number is smaller than 1016. An application is given to illustrate that our algorithm is more accurate than MATLAB’s fft function. The results show that the relative error of our algorithm is from 1015 to 1017, and that of the fft was from 1012 to 1015.

Keywords

• polynomial evaluation
• goertzel algorithm
• round-off error
• error-free transformation
• compensated algorithm
• numerical stability