A note on Newbery's algorithm for discrete least-squares approximation by trigonometric polynomials
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.
- Discrete Least Squares Approximation by Trigonometric Polynomials
- scientific article; zbMATH DE number 741186
- On numerical methods for discrete least-squares approximation by trigonometric polynomials
- Vector Orthogonal Polynomials and Least Squares Approximation
- Orthonormal polynomial vectors and least squares approximation for a discrete inner product
- Approximation of scattered data by trigonometric polynomials on the torus and the 2-sphere
- Downdating of Szegö polynomials and data-fitting applications
- A parallel algorithm for discrete least squares rational approximation
- A method to compute recurrence relation coefficients for bivariate orthogonal polynomials by unitary matrix transformations
- On polynomial approximation in the uniform norm by the discrete least squares method
This page was built for publication: A note on Newbery's algorithm for discrete least-squares approximation by trigonometric polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920185)
