Fourier series
Let f be a periodic function of period 2π, such that
Suppose that the Fourier series 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:
Hence we want a numeric approximation of
The numeric value of the integral ∫02π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 development
has its coefficients equal to zero, since the integrated function is
periodic, hence all its derivatives have the same value at 0 and at 2π).
If c_n is the numeric value of cn obtained by the
trapezoidal rule, then
Indeed, since xk=2kπ/N and f(xk)=yk:
Hence :
[c0,..c | | ,c | | ,..cN−1]=
| | FN([y0,y1...y(N−1)]) |
since
-
if n≥0, cn=yn
- if n<0 cn=yn+N
- ωN=exp(2iπ/N),
then ωNn=ωNn+N
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≤ N/2,
then
the trigonometric polynomial that interpolate f=P is P, the numeric
approximation of the coefficients are in fact exact (cn=cn).
- More generally, we can compute cn−cn.
Suppose that f is equal to its Fourier series, i.e. that :
f(t)= | | cmexp(2iπ mt),
| | |cm|<∞ |
Then :
f(xk)=f( | | )=yk= | | cmωNkm,
c_n= | | | ykωN−kn |
Replace yk by its value in c_n:
If m≠ n (mod N ), ωNm−n is an N-th root of unity different
from 1, hence:
Therefore, if m−n is a multiple of N (m=n+l· N) then
∑k=0N−1ωNk(m−n)=N, otherwise
∑k=0N−1ωNk(m−n)=0.
By reversing the two sums, we get
c_n | = | |
| = | |
| = | ...cn−2· N+cn−N+cn+cn+N+cn+2·
N+.....
|
|
Conclusion: if |n|<N/2, c_n−cn is a sum of cj of large indexes
(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)
Then :
x={2,sqrt(2)/2,-1,(-sqrt(2)/2,0,(-sqrt(2))/2,-1,sqrt(2)/2}
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
c0=0,c1=4.0/8,c2=4.0/8,c3=0.0,
c−4=0.0,c−3=0.0,c−2=4.0/8,=c−1=4.0/8
Hence bk=0 and ak=c−k+ck is equal to 1 if k=1,2 and 0 otherwise.