Equidistant Nodes and The Discrete Fourier Transform
The special case in which the points xk are equally spaced is especially important. In this case, we have
The transformation that maps the data points yk to the coefficients am, bm 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).
Read more about this topic: Trigonometric Interpolation
Famous quotes containing the words nodes, discrete and/or transform:
“There are characters which are continually creating collisions and nodes for themselves in dramas which nobody is prepared to act with them. Their susceptibilities will clash against objects that remain innocently quiet.”
—George Eliot [Mary Ann (or Marian)
“The mastery of one’s phonemes may be compared to the violinist’s mastery of fingering. The violin string lends itself to a continuous gradation of tones, but the musician learns the discrete intervals at which to stop the string in order to play the conventional notes. We sound our phonemes like poor violinists, approximating each time to a fancied norm, and we receive our neighbor’s renderings indulgently, mentally rectifying the more glaring inaccuracies.”
—W.V. Quine (b. 1908)
“Americans, unhappily, have the most remarkable ability to alchemize all bitter truths into an innocuous but piquant confection and to transform their moral contradictions, or public discussion of such contradictions, into a proud decoration, such as are given for heroism on the battle field.”
—James Baldwin (1924–1987)