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\pi)$ 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($mn^2$) 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.