Accurate Goertzel Algorithm: Error Analysis, Validations and Applications

Mathematics

Chuanying Li¹  Zhe Quan¹  Hao Jiang²  Peibing Du³  Yu Liu³  Kuan Li⁴ 

[1] College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China;College of Computer, National University of Defense Technology, Changsha 410073, China;Northwest Institute of Nuclear Technology, Xi’an 710024, China;School of Cyberspace Security, Dongguan University of Technology, Dongguan 523106, China;

关键词: polynomial evaluation;    goertzel algorithm;    round-off error;    error-free transformation;    compensated algorithm;    numerical stability;   

DOI  :  10.3390/math10111788

来源: DOAJ

【 摘 要 】

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 ${10}^{16}$. An application is given to illustrate that our algorithm is more accurate than MATLAB’s $\mathtt{fft}$ function. The results show that the relative error of our algorithm is from ${10}^{15}$ to ${10}^{17}$, and that of the $\mathtt{fft}$ was from ${10}^{12}$ to ${10}^{15}$.

【 授权许可】

Unknown