356
9 Polynˆ omes orthogonaux en th´ eorie de l’approximation
En effet, en utilisant (9.55) et (9.57) dans (9.56), on a
Π
F
N f(x j ) =
N−1
k=0
f k e
ikjh e
−ijh
N
2 =
N−1
l=0
f(x l )
1
N
N−1
k=0
e
−ik(j−l)h
= f(x j ).
La premi` ere et la derni` ere ´ egalit´ es donnent donc
f(x j ) =
N−1
k=0
f k e
ik(j−
N
2 )h =
N−1
k=0
f k W
−(j−
N
2 )k
N
,
j = 0, . . ., N − 1. (9.58)
L’application {f(x j )} → {
f k } d´ efinie en (9.55) est appel´ ee transform´ ee de
Fourier discr` ete (DFT pour discrete Fourier transform), et l’application (9.58)
qui `
a {
f k } associe {f(x j )} est appel´ ee transform´ ee inverse (IDFT). DFT et
IDFT peuvent s’´ ecrire sous forme matricielle {
f k } = T{f(x j )} et {f(x j )} =
C{
f k } o` u T ∈ C
N×N , C est l’inverse de T et
T kj =
1
N
W
(k−
N
2 )j
N
, k,j = 0, . . . , N − 1,
C jk = W
−(j−
N
2 )k
N
, j,k = 0, . . ., N − 1.
Une impl´ ementation na¨ ıve du produit matrice vecteur de DFT et IDFT n´ ecessiterait N
2 op´ erations. Nous verrons `
a la Section 9.9.1 qu’en utilisant l’algorithme de transformation de Fourier rapide (FFT pour Fast Fourier Transform) le calcul ne n´ ecessite plus que O(N log 2 N ) flops, `
a condition que N
soit une puissance de 2.
La fonction Π
F
N f ∈ S N introduite en (9.56) est la solution du probl` eme de
minimisation f − Π
F
N f N ≤ ≤f − g N , ∀g ∈ S N , o` u · · N = (·, ·)
1/2
N est une
norme discr` ete sur S N . Dans le cas o` u f est p´ eriodique ainsi que ses d´ eriv´ ees
jusqu’` a l’ordre s (s ≥ 1), on a une estimation d’erreur analogue `
a celle des
interpolations de Chebyshev et Legendre, i.e.
− Π
F
N f L 2 (0,2π) ≤ CN
−s
f s
et
max
0≤x≤2π
|f(x) − Π
F
N f(x)| ≤ CN
1/2−s
f s .
De mani` ere analogue, on a ´ egalement
|(f, v N ) − (f, v N ) N | ≤ CN
−s
f s v N L 2 (0,2π)
pour tout v N ∈ S N , et en particulier, en posant v N = 1, on a l’estimation
d’erreur suivante pour la formule de quadrature (9.54)
2π
0
f(x)dx − h
N−1
j=0
f(x j )
≤ CN
−s
f s
9 Polynˆ omes orthogonaux en th´ eorie de l’approximation
En effet, en utilisant (9.55) et (9.57) dans (9.56), on a
Π
F
N f(x j ) =
N−1
k=0
f k e
ikjh e
−ijh
N
2 =
N−1
l=0
f(x l )
1
N
N−1
k=0
e
−ik(j−l)h
= f(x j ).
La premi` ere et la derni` ere ´ egalit´ es donnent donc
f(x j ) =
N−1
k=0
f k e
ik(j−
N
2 )h =
N−1
k=0
f k W
−(j−
N
2 )k
N
,
j = 0, . . ., N − 1. (9.58)
L’application {f(x j )} → {
f k } d´ efinie en (9.55) est appel´ ee transform´ ee de
Fourier discr` ete (DFT pour discrete Fourier transform), et l’application (9.58)
qui `
a {
f k } associe {f(x j )} est appel´ ee transform´ ee inverse (IDFT). DFT et
IDFT peuvent s’´ ecrire sous forme matricielle {
f k } = T{f(x j )} et {f(x j )} =
C{
f k } o` u T ∈ C
N×N , C est l’inverse de T et
T kj =
1
N
W
(k−
N
2 )j
N
, k,j = 0, . . . , N − 1,
C jk = W
−(j−
N
2 )k
N
, j,k = 0, . . ., N − 1.
Une impl´ ementation na¨ ıve du produit matrice vecteur de DFT et IDFT n´ ecessiterait N
2 op´ erations. Nous verrons `
a la Section 9.9.1 qu’en utilisant l’algorithme de transformation de Fourier rapide (FFT pour Fast Fourier Transform) le calcul ne n´ ecessite plus que O(N log 2 N ) flops, `
a condition que N
soit une puissance de 2.
La fonction Π
F
N f ∈ S N introduite en (9.56) est la solution du probl` eme de
minimisation f − Π
F
N f N ≤ ≤f − g N , ∀g ∈ S N , o` u · · N = (·, ·)
1/2
N est une
norme discr` ete sur S N . Dans le cas o` u f est p´ eriodique ainsi que ses d´ eriv´ ees
jusqu’` a l’ordre s (s ≥ 1), on a une estimation d’erreur analogue `
a celle des
interpolations de Chebyshev et Legendre, i.e.
− Π
F
N f L 2 (0,2π) ≤ CN
−s
f s
et
max
0≤x≤2π
|f(x) − Π
F
N f(x)| ≤ CN
1/2−s
f s .
De mani` ere analogue, on a ´ egalement
|(f, v N ) − (f, v N ) N | ≤ CN
−s
f s v N L 2 (0,2π)
pour tout v N ∈ S N , et en particulier, en posant v N = 1, on a l’estimation
d’erreur suivante pour la formule de quadrature (9.54)
2π
0
f(x)dx − h
N−1
j=0
f(x j )
≤ CN
−s
f s