On numerical methods for discrete least-squares approximation by trigonometric polynomials

Faßbender, Heike

doi:10.1090/S0025-5718-97-00845-4

On numerical methods for discrete least-squares approximation by trigonometric polynomials
HTML articles powered by AMS MathViewer

by Heike Faßbender PDF

Math. Comp. 66 (1997), 719-741 Request permission

Abstract:

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 are presented. The 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. An algorithm which solves this problem with real-valued data and 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 obtained by general QR decomposition methods for the least-squares problem.

References

G. S. Ammar, W. B. Gragg, and L. Reichel, On the Eigenproblem for Orthogonal Matrices, Proc. 25th IEEE Conference on Decision and Control, 1986, pp. 1963 – 1966.
Gregory Ammar, William Gragg, and Lothar Reichel, Constructing a unitary Hessenberg matrix from spectral data, Numerical linear algebra, digital signal processing and parallel algorithms (Leuven, 1988) NATO Adv. Sci. Inst. Ser. F: Comput. Systems Sci., vol. 70, Springer, Berlin, 1991, pp. 385–395. MR 1150072
M. Van Barel and A. Bultheel, Discrete linearized least squares rational approximation on the unit circle, Report TW179, Department of Computer Science, K.U. Leuven, Belgium, 1992.
David F. Griffiths (ed.), The mathematical basis of finite element methods, The Institute of Mathematics and its Applications Conference Series. New Series, vol. 2, The Clarendon Press, Oxford University Press, New York, 1984. With applications to partial differential equations; Papers from the expository conference held at Imperial College, University of London, London, January 5–7, 1983. MR 807005
Åke Björck and Victor Pereyra, Solution of Vandermonde systems of equations, Math. Comp. 24 (1970), 893–903. MR 290541, DOI 10.1090/S0025-5718-1970-0290541-1
A. Bultheel and M. Van Barel, Vector orthogonal polynomials and least squares approximation, Report TW184, Department of Computer Science, K.U. Leuven, Belgium, 1992.
Angelika Bunse-Gerstner and Ludwig Elsner, Schur parameter pencils for the solution of the unitary eigenproblem, Linear Algebra Appl. 154/156 (1991), 741–778. MR 1113168, DOI 10.1016/0024-3795(91)90402-I
Tony F. Chan, Rank revealing $QR$ factorizations, Linear Algebra Appl. 88/89 (1987), 67–82. MR 882441, DOI 10.1016/0024-3795(87)90103-0
Cédric J. Demeure, Fast $QR$ factorization of Vandermonde matrices, Linear Algebra Appl. 122/123/124 (1989), 165–194. MR 1019987, DOI 10.1016/0024-3795(89)90652-6
J. Dongarra, J.R. Bunch, C. Moler, and G.W. Stewart, Linpack user’s guide, SIAM, Philadelphia, PA, 1979.
H. Faßbender, Numerische Verfahren zur diskreten trigonometrischen Polynomapproximation, Dissertation Universität Bremen, 1993.
—, Inverse unitary eigenproblems and related orthogonal functions, to appear in Numerische Mathematik.
—, A note on Newbery’s algorithm for computing discrete least-squares approximation by trigonometric polynomials, Electron. Trans. Numer. Anal. 4 (1996), 64–74.
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Peter Henrici, Applied and computational complex analysis. Vol. 3, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1986. Discrete Fourier analysis—Cauchy integrals—construction of conformal maps—univalent functions; A Wiley-Interscience Publication. MR 822470
A. C. R. Newbery, Trigonometric interpolation and curve-fitting, Math. Comp. 24 (1970), 869–876. MR 279966, DOI 10.1090/S0025-5718-1970-0279966-8
L. Reichel, G. S. Ammar, and W. B. Gragg, Discrete least squares approximation by trigonometric polynomials, Math. Comp. 57 (1991), no. 195, 273–289. MR 1079030, DOI 10.1090/S0025-5718-1991-1079030-8