Volume 4, pp. 64-74, 1996.

A note on Newbery's algorithm for discrete least-squares approximation by trigonometric polynomials

Heike Faßbender

Abstract

Recently fast, efficient and reliable algorithms for discrete least-squares approximation of a real-valued function given at arbitrary distinct nodes in [0,2π) by trigonometric polynomials were presented in different papers. These algorithms are based on schemes for the solution of inverse unitary eigenproblems and require only O(mn) arithmetic operations as compared to O(mn2) operations needed for algorithms that ignore the structure of the problem. In 1970 Newbery already presented a O(mn) algorithm for solving the discrete least-squares approximation by trigonometric polynomials. In this paper the connection between the different algorithms is illustrated.

Full Text (PDF) [177 KB], BibTeX

Key words

trigonometric approximation.

AMS subject classifications

65D10, 42A10, 65F99.