Trigonometric interpolation

Trigonometric interpolation

In mathematics, trigonometric interpolation is interpolation with trigonometric polynomials. Interpolation is the process of finding a function which goes through some given data points. For trigonometric interpolation, this function has to be a trigonometric polynomial, that is, a sum of sines and cosines of given periods. This form is especially suited for interpolation of periodic functions.

An important special case is when the given data points are equally spaced, in which case the solution is given by the discrete Fourier transform.

Formulation of the interpolation problem

A trigonometric polynomial of degree "n" has the form: p(x) = a_0 + sum_{m=1}^n a_m cos(mx) + sum_{m=1}^n b_m sin(mx). , This expression contains 2"n" + 1 coefficients, "a"0, "a"1, … "a""n", "b"1, …, "b""n", and we wish to compute those coefficients so that the function passes through "N" points:: p(x_k) = y_k, quad k=1,ldots,N. , Since the trigonometric polynomial is periodic with period 2π, it makes sense to assume that: 0 le x_1 < x_2 < cdots < x_{N} < 2pi. , (Note that we do "not" in general require these points to be equally spaced.) The interpolation problem is now to find coefficients such that the trigonometric polynomial "p" satisfies the interpolation conditions.

olution of the problem

Under the above conditions, there exists a solution to the problem for "any" given set of data points {"x""k", "p"("x""k")} as long as the number of data points is not larger than the number of coefficients in the polynomial, i.e., "N" ≤ 2"n"+1 (a solution may or may not exist if "N">2"n"+1 depending upon the particular set of data points). Moreover, the interpolating polynomial is unique if and only if the number of adjustable coefficients is equal to the number of data points, i.e., "N"=2"n"+1. In the remainder of this article, we will assume this condition to hold true.

The solution can be written in a form similar to the Lagrange formula for polynomial interpolation:: p(x) = sum_{k=1}^{2n+1} y_k prod_{m=1,m e k}^{2n+1} frac{sinfrac12(x-x_m)}{sinfrac12(x_k-x_m)}. , This can be shown to be a trigonometric polynomial by employing the multiple-angle formula and other identities for sin ½("x" − "x""m").

Formulation in the complex plane

The problem becomes more natural if we formulate it in the complex plane. We can rewrite the formula for a trigonometric polynomial as: p(x) = sum_{m=-n}^n c_m e^{imx}, , where "i" is the imaginary unit. If we set "z" = "e""ix", then this becomes: p(z) = sum_{m=-n}^n c_m z^{m}. , This reduces the problem of trigonometric interpolation to that of polynomial interpolation on the unit circle. Existence and uniqueness for trigonometric interpolation now follows immediately from the corresponding results for polynomial interpolation.

For more information on formulation of trigonometric interpolating polynomials in the complex plane see [http://www.physics.arizona.edu/~restrepo/475A/Notes/sourcea.pdf , p128 Interpolation using Fourier Polynomials] .

Equidistant nodes and the discrete Fourier transform

The special case in which the points "x""k" are equally spaced is especially important. In this case, we have: x_k = frac{2kpi}{2n+1}. The transformation that maps the data points "y""k" to the coefficients "a""m", "b""m" is known as the discrete Fourier transform (DFT) of order 2n+1.

(Because of the way the problem was formulated above, we have restricted ourselves to odd numbers of points. This is not strictly necessary; for even numbers of points, one includes another cosine term corresponding to the Nyquist frequency.)

The case of the cosine-only interpolation for equally spaced points, corresponding to a trigonometric interpolation when the points have even symmetry, was treated by Alexis Clairaut in 1754. In this case the solution is equivalent to a discrete cosine transform. The sine-only expansion for equally spaced points, corresponding to odd symmetry, was solved by Joseph Louis Lagrange in 1762, for which the solution is a discrete sine transform. The full cosine and sine interpolating polynomial, which gives rise to the DFT, was solved by Carl Friedrich Gauss in unpublished work around 1805, at which point he also derived a fast Fourier transform algorithm to evaluate it rapidly. Clairaut, Lagrange, and Gauss were all concerned with studying the problem of inferring the orbit of planets, asteroids, etc., from a finite set of observation points; since the orbits are periodic, a trigonometric interpolation was a natural choice. See also Heideman "et al." (1984).

References

* Kendall E. Atkinson, "An Introduction to Numerical Analysis" (2nd edition), Section 3.8. John Wiley & Sons, New York, 1988. ISBN 0-471-50023-2.
* M. T. Heideman, D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform," "IEEE ASSP Magazine" 1 (4), 14&ndash;21 (1984).


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Interpolation — In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points. In engineering and science one often has a number of data points, as obtained… …   Wikipedia

  • Trigonometric polynomial — In the mathematical subfields of numerical analysis and mathematical analysis, a trigonometric polynomial is a finite linear combination of functions sin(nx) and cos(nx) with n a natural number. The coefficients may be taken as real numbers, for… …   Wikipedia

  • Polynomial interpolation — In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. In other words, given some data points (such as obtained by sampling), the aim is to find a polynomial which… …   Wikipedia

  • Generating trigonometric tables — In mathematics, tables of trigonometric functions are useful in a number of areas. Before the existence of pocket calculators, trigonometric tables were essential for navigation, science and engineering. The calculation of mathematical tables was …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • List of trigonometry topics — This is a list of trigonometry topics, by Wikipedia page.*Angle *Angle excess *Brahmagupta interpolation formula *Chebyshev polynomials *Conway triangle notation *De Moivre s formula *Dirichlet kernel *Euler s formula *Exact trigonometric… …   Wikipedia

  • Clenshaw–Curtis quadrature — and Fejér quadrature are methods for numerical integration, or quadrature , that are based on an expansion of the integrand in terms of Chebyshev polynomials. Equivalently, they employ a change of variables x = cos θ and use a discrete… …   Wikipedia

  • Mathematics Subject Classification — The Mathematics Subject Classification (MSC) is an alphanumerical classification scheme collaboratively produced by staff of and based on the coverage of the two major mathematical reviewing databases, Mathematical Reviews and Zentralblatt MATH.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”