Fourier series
Let f be a periodic function of period 2, such that
f (
x_{k}) =
y_{k},
x_{k} =
,
k = 0..
N  1
Suppose that the Fourier serie of f converges to f (this will
be the case if for example f is continuous). If N is large,
a good approximation of f will be given by:
c_{n}exp(
inx)
Hence we want a numeric approximation of
c_{n} =
f (
t)exp(
int)
dt
The numeric value of the integral
f (t)exp( int)dt may be
computed by the trapezoidal rule
(note that the Romberg algorithm would not work here,
because the Euler Mac Laurin developpement
has it's coefficients equal to zero, since the integrated function is
periodic, hence all it's derivatives have the same value at 0 and at 2).
If
is the numeric value of c_{n} obtained by the
trapezoidal rule, then
Indeed, since
x_{k} = 2k/N and
f (x_{k}) = y_{k}:
f (x_{k})exp( inx_{k}) 
= 
y_{k}exp( 2i), 

f (0)exp(0) = f (2)exp( 2i) 
= 
y_{0} = y_{N} 

Hence :
[
,..
,
,..
c_{1}] =
F_{N}([
y_{0},
y_{1}...
y_{(N1)}])
since
 if n 0,
= y_{n}
 if n < 0
= y_{n+N}

= exp(),
then
=
Properties
 The coefficients of the trigonometric polynomial that interpolates f
at x = 2k/N are
 If f is a trigonometric polynomial P of degree
m ,
then
f (
t) =
P(
t) =
c_{k}exp(2
ikt)
the trigonometric polynomial that interpolate f = P is P, the numeric
approximation of the coefficients are in fact exact (
= c_{n}).
 More generally, we can compute
 c_{n}.
Suppose that f is equal to it's Fourier serie, i.e. that :
f (
t) =
c_{m}exp(2
imt),

c_{m} <
Then :
f (
x_{k}) =
f (
) =
y_{k} =
c_{m},
=
y_{k}
Replace y_{k} by it's value in
:
If
m n(mod N),
is a Nth root of unity different
from 1, hence:
Therefore, if m  n is a multiple of N (
m = n + l^{ . }N) then
= N, otherwise
= 0.
By reversing the two sums, we get

= 
c_{m} 


= 
c_{(n+l . N)} 


= 
...c_{n2 . N} + c_{nN} + c_{n} + c_{n+N} + c_{n+2 . N} + ..... 

Conclusion: if  n < N/2,
 c_{n} is a sum of c_{j} of large indices
(at least N/2 in absolute value), hence is small (depending on the
rate of convergence of the Fourier series).
Example, input
f(t):=cos(t)+cos(2*t)
x:=f(2*k*pi/8)$(k=0..7)
Output :
fft(x)=[0.0,4.0,4.0,0.0,0.0,0.0,4.0,4.0]
After a division by N = 8, we get
c_{0} = 0, c_{1} = 4.0/8, c_{2} = 4.0/2, c_{3} = 0.0,
c_{4} = 0, c_{3} = 0, c_{2} = 4.0/8, = c_{1} = 4.0/8
Hence b_{k} = 0 and
a_{k} = c_{k} + c_{k} is equal to 1 if k = 1, 2 and 0 otherwise.