Fourier series
Let f be a periodic function of period 2
, such that
f (
xk) =
yk,
xk =
![$\displaystyle {\frac{{2k\pi}}{{N}}}$](img217.png)
,
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:
cnexp(
inx)
Hence we want a numeric approximation of
cn =
![$\displaystyle {\frac{{1}}{{2\pi}}}$](img219.png)
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 cn obtained by the
trapezoidal rule, then
Indeed, since
xk = 2k
/N and
f (xk) = yk:
f (xk)exp(- inxk) |
= |
ykexp(- 2i ), |
|
f (0)exp(0) = f (2 )exp(- 2i ) |
= |
y0 = yN |
|
Hence :
[
![$\displaystyle \tilde{{c}}_{0}^{}$](img229.png)
,..
![$\displaystyle \tilde{{c}}_{{\frac{N}{2}-1}}^{}$](img230.png)
,
![$\displaystyle \tilde{{c}}_{{\frac{-N}{2}}}^{}$](img231.png)
,..
c-1] =
FN([
y0,
y1...
y(N-1)])
since
- if n
0,
= yn
- if n < 0
= yn+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) =
ckexp(2
ik
t)
the trigonometric polynomial that interpolate f = P is P, the numeric
approximation of the coefficients are in fact exact (
= cn).
- More generally, we can compute
- cn.
Suppose that f is equal to it's Fourier serie, i.e. that :
f (
t) =
cmexp(2
i
mt),
![$\displaystyle \sum_{{m=-\infty}}^{{+\infty}}$](img239.png)
|
cm| <
Then :
f (
xk) =
f (
![$\displaystyle {\frac{{2k\pi}}{{N}}}$](img217.png)
) =
yk =
cm![$\displaystyle \omega_{N}^{{km}}$](img240.png)
,
![$\displaystyle \tilde{{c_n}}$](img223.png)
=
![$\displaystyle {\frac{{1}}{{N}}}$](img153.png)
yk
Replace yk by it's value in
:
If
m
n(mod N),
is a N-th root of unity different
from 1, hence:
Therefore, if m - n is a multiple of N (
m = n + l . N) then
![$ \sum_{{k=0}}^{{N-1}}$](img245.png)
= N, otherwise
![$ \sum_{{k=0}}^{{N-1}}$](img245.png)
= 0.
By reversing the two sums, we get
![$\displaystyle \tilde{{c_n}}$](img223.png) |
= |
![$\displaystyle {\frac{{1}}{{N}}}$](img153.png) cm![$\displaystyle \sum_{{k=0}}^{{N-1}}$](img225.png) ![$\displaystyle \omega_{N}^{{k(m-n)}}$](img247.png) |
|
|
= |
c(n+l . N) |
|
|
= |
...cn-2 . N + cn-N + cn + cn+N + cn+2 . N + ..... |
|
Conclusion: if | n| < N/2,
- cn is a sum of cj 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
c0 = 0, c1 = 4.0/8, c2 = 4.0/2, c3 = 0.0,
c-4 = 0, c-3 = 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.