Trigonometric interpolation

The trigonometric interpolation is a term from the mathematical branch of numerics . A trigonometric polynomial (a sum of sine and cosine of given period lengths) is sought for given points , which goes through all these points. It is therefore a special interpolation method that is particularly suitable for interpolating periodic functions .

If the distances between the given points are the same, then there is an important special case. In this case, the solution can be calculated using the discrete Fourier transform .

Formulation of the interpolation problem

A trigonometric polynomial of degree has the form ${\ displaystyle n}$

{\ displaystyle p (x) = a_ {0} + \ sum _ {j = 1} ^ {n} a_ {j} \ cos (jx) + \ sum _ {j = 1} ^ {n} b_ {j } \ sin (jx). \,}

This expression has coefficients , so we assume interpolation conditions: ${\ displaystyle 2n + 1}$ ${\ displaystyle a_ {0}, a_ {1}, \ dots a_ {n}, b_ {1}, \ dots b_ {n}}$ ${\ displaystyle 2n + 1}$

{\ displaystyle p (x_ {k}) = y_ {k}, \ quad k = 1, \ ldots, 2n + 1. \,}

Since the trigonometric polynomial is periodic with the period , one can without loss of generality ${\ displaystyle 2 \ pi}$

{\ displaystyle 0 \ leq x_ {0} <x_ {1} <\ cdots <x_ {2n} <2 \ pi \,}

presuppose. In general, it is not necessary that these points be equidistant. The interpolation problem now is to find coefficients such that the trigonometric polynomial meets the interpolation conditions. ${\ displaystyle p}$

the solution of the problem

There is a clear solution to the problem under the above conditions. This solution can be given in a form similar to Lagrange's interpolation formula :

{\ displaystyle p (x) = \ sum _ {k = 1} ^ {2n + 1} y_ {k} \ prod _ {j = 1, j \ neq k} ^ {2n + 1} {\ frac {\ sin {\ frac {1} {2}} (x-x_ {j})} {\ sin {\ frac {1} {2}} (x_ {k} -x_ {j})}}. \,}

It can be shown to be a trigonometric polynomial by applying the formula for multiples of angles and other identities for . ${\ displaystyle \ sin {\ frac {1} {2}} (x-x_ {j})}$

Formulation in the complex plane

The problem becomes easier when we describe it in the complex plane . We can rewrite the formula for a trigonometric polynomial as follows

{\ displaystyle p (x) = \ sum _ {j = -n} ^ {n} c_ {j} e ^ {ijx}, \,}

where is the imaginary unit . If we set , then it becomes ${\ displaystyle i}$ ${\ displaystyle z = e ^ {ix}}$

{\ displaystyle q (z) = \ sum _ {j = -n} ^ {n} c_ {j} z ^ {j}. \,}

whereby . This reduces the problem of trigonometric interpolation to one of polynomial interpolations on the unit circle. The existence and uniqueness of the trigonometric interpolation follow directly from the corresponding results for the polynomial interpolation. ${\ displaystyle q (e ^ {ix}) = p (x)}$

Equidistant support points and the discrete Fourier transform

The special case when the points are equidistantly distributed is particularly important. In this case ${\ displaystyle x_ {k}}$

{\ displaystyle x_ {k} = {\ frac {2k \ pi} {2n + 1}}}

The transformation that maps the interpolation points to the coefficients and is called the discrete Fourier transformation (DFT) of the order . ${\ displaystyle y_ {k}}$ ${\ displaystyle a_ {j}}$ ${\ displaystyle b_ {j}}$ ${\ displaystyle 2n + 1}$

The case of a purely cosine-based interpolation for equidistantly distributed interpolation points, which leads to a trigonometric polynomial when the interpolation points are oddly symmetrical , was treated by Alexis Clairaut in 1754 . In this case the solution is equivalent to a discrete cosine transform . The purely sine-based interpolation for equidistantly distributed interpolation points, that of a discrete sine transformation . The complete cosine and sine interpolation polynomial that led to the DFT was solved by Carl Friedrich Gauß around 1805 in an unpublished paper in which he also derived a fast Fourier transform algorithm to calculate the polynomials. Clairaut, Lagrange and Gauss were all concerned with the problem of deriving the orbit of planets , asteroids , etc. from a finite set of observation points. Since the orbits themselves are periodic, a trigonometric polynomial was the natural choice.

literature

MT Heideman, DH Johnson, and CS Burrus: Gauss and the history of the fast Fourier transform. In: IEEE ASSP Magazine 1 (4), 14/21/1984
Josef Stoer: Numerical Mathematics 1. 9. Edition. Springer, Berlin 2005, ISBN 3-540-21395-3

Web links

LP - Trigonometric Interpolation