Editing Trigonometric interpolation (section)

===Relation with the discrete Fourier transform===
The special case in which the points ''x''<sub>''n''</sub> are equally spaced is especially important. In this case, we have
:<math> x_n = 2 \pi \frac{n}{N}, \qquad 0 \leq n < N.</math>

The transformation that maps the data points ''y''<sub>''n''</sub> to the coefficients ''a''<sub>''k''</sub>, ''b''<sub>''k''</sub> is obtained from the [[discrete Fourier transform]] (DFT) of order&nbsp;N.

:<math> Y_k = \sum_{n=0}^{N-1} y_n \ e^{-i 2 \pi nk/N} \, </math>

:<math> y_n = p(x_n) = \frac{1}{N} \sum_{k=0}^{N-1} Y_k \ e^{i 2 \pi nk/N} \, </math>

(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 and odd functions|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 [[Cooley–Tukey FFT algorithm|fast Fourier transform]] algorithm to evaluate it rapidly. Clairaut, Lagrange, and Gauss were all concerned with studying the problem of inferring the [[orbit]] of [[planet]]s, [[asteroid]]s, 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).