A note on Newbery’s algorithm for discrete least-squares approximation by trigonometric polynomials. (English) Zbl 0862.65095

This paper compares several methods for discrete least squares trigonometric polynomial approximation, i.e. minimizing \(\sum^m_{k=1}|f(\theta_k)-t(\theta_k)|^2\omega^2_k\) where \(\omega_k\) are real positive weights, the \(\theta_k\) are distinct nodes in the interval \([0,2\pi)\) and \(t(\theta)\) is a trigonometric polynomial of degree \(n\), \(f(\theta_k)\) are given function values. The algorithm of L. Reichel, G. S. Ammar and W. B. Gragg [Math. Comput. 57, No. 195, 273-289 (1991; Zbl 0733.65102)] solves this problem as an inverse eigenvalue problem for a unitary Hessenberg matrix. The algorithm is based on the Szegö recursion for polynomials orthogonal on the unit circle. This algorithm requires \(O(mn+n^2)\) arithmetic operations and relies on complex arithmetic. A version of this algorithm for computations in real arithmetic also exists.
In earlier work, the author has described an algorithm which computes the solution of the real problem using only real arithmetic using \(O(mn+n^2)\) operations. A. C. R. Newbery [Math. Comput. 24 (1970), 869-876 (1971; Zbl 0224.65003)] gives an alternative algorithm which constructs an orthogonal basis for the space spanned by \(\{\sin k\phi,\cos k\phi:k=0,1,\dots,n\}\). In the paper under review, the relation between the Newbery and the Reichel-Ammar-Gragg algorithm is made explicit. Some concluding remarks about numerical experiments of the different algorithms are included. Although they are theoretically equivalent, efficiency and accuracy are different when implemented.


65T40 Numerical methods for trigonometric approximation and interpolation
65F99 Numerical linear algebra
42A10 Trigonometric approximation
65D10 Numerical smoothing, curve fitting
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
Full Text: EuDML EMIS