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

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 \textit{L. Reichel}, \textit{G. S. Ammar} and \textit{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. \textit{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.