Accurate Goertzel Algorithm: Error Analysis, Validations and Applications

Chuanying Li, Peibing Du, Kuan Li, Yu Liu, Hao Jiang and Zhe Quan
Additional contact information
Chuanying Li: College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
Peibing Du: Northwest Institute of Nuclear Technology, Xi’an 710024, China
Kuan Li: School of Cyberspace Security, Dongguan University of Technology, Dongguan 523106, China
Yu Liu: Northwest Institute of Nuclear Technology, Xi’an 710024, China
Hao Jiang: College of Computer, National University of Defense Technology, Changsha 410073, China
Zhe Quan: College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China

Mathematics, 2022, vol. 10, issue 11, 1-19

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 10 16 . 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 10 15 to 10 17 , and that of the fft was from 10 12 to 10 15 .

Keywords: polynomial evaluation; goertzel algorithm; round-off error; error-free transformation; compensated algorithm; numerical stability (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/11/1788/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/11/1788/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:11:p:1788-:d:822463

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().