ON NUMERICAL-METHODS FOR DISCRETE LEAST-SQUARES APPROXIMATION BY TRIGONOMETRIC POLYNOMIALS

Fast, efficient and reliable algorithms for discrete least-squares app roximation of a real-valued function given at arbitrary distinct nodes in [0; 2 pi) by trigonometric polynomials are presented. The algorith ms are based on schemes for the solution of inverse unitary eigenprobl ems and require only O(mn) arithmetic operations as compared to O(mn(2 )) operations needed for algorithms that ignore the structure of the p roblem. An algorithm which solves this problem with real-valued data a nd real-valued solution using only real arithmetic is given. Numerical examples are presented that show that the proposed algorithms produce consistently accurate results that are often better than those obtain ed by general QR decomposition methods for the least-squares problem.