9.10 Approximation des d´ eriv´ ees
359
else
a1 = f(1:2:N); b1 = f(2:2:N);
a2 = fftrec(a1,NN); b2 = fftrec(b1,NN);
for k=-NN/2:NN-1-NN/2
fftv(k+1+NN/2) = a2(k+1+NN/2) + b2(k+1+NN/2)*wˆk;
end
end
return
Remarque 9.4 On peut aussi d´ efinir un proc´ ed´ e de FFT quand N n’est pas
une puissance de 2. L’approche la plus simple consiste `
a ajouter des z´ eros ` a
la suite originale {f i } de fa¸ con `
a obtenir un nombre total de valeurs ´ egal ` a
˜
N = 2
p , pour un certain p. Cette technique ne conduit n´ eanmoins pas toujours
` a un r´ esultat correct. Une alternative efficace consiste ` a effectuer une partition
de la matrice de Fourier C en sous-blocs de taille plus petite. En pratique, les
impl´ ementations de la FFT peuvent adopter les deux strat´ egies (voir, par
exemple, le package fft disponible dans MATLAB).
9.10 Approximation des d´ eriv´ ees
Un probl` eme qu’on rencontre souvent en analyse num´ erique est l’approximation de la d´ eriv´ ee d’une fonction f sur un intervalle donn´ e [a, b]. Une approche
naturelle consiste ` a introduire n + 1 noeuds {x k , k = 0, . . ., n} de [a, b], avec
x 0 = a, x n = b et x k+1 = x k + h, k = 0, . . ., n − 1 o` u h = (b − a)/n. On
approche alors f
(x i ) en utilisant les valeurs nodales f(x k ) :
h
m
k=−m
α k u i−k =
m
k=−m
β k f(x i−k ),
(9.59)
o` u {α k }, {β k } ∈ R sont m + m
+ 1 coefficients ` a d´ eterminer et u k est l’approximation recherch´ ee de f
(x k ).
Le coˆ ut du calcul est un crit` ere important dans le choix du sch´ ema (9.59).
Il faut par exemple noter que si m = 0, la d´ etermination des quantit´ es {u i }
requiert la r´ esolution d’un syst` eme lin´ eaire.
L’ensemble des noeuds impliqu´ es dans la construction de la d´ eriv´ ee de y en
un noeud donn´ e est appel´ e stencil. La bande de la matrice associ´ ee au syst` eme
(9.59) augmente avec la taille du stencil.
9.10.1 M´ ethodes des diff´ erences finies classiques
Le moyen le plus simple pour construire une formule du type (9.59) consiste
` a revenir `
a la d´ efinition de la d´ eriv´ ee. Si f
(x i ) existe, alors
f
(x i ) = lim
h→0 +
f(x i + h) − f(x i )
h
.
(9.60)
359
else
a1 = f(1:2:N); b1 = f(2:2:N);
a2 = fftrec(a1,NN); b2 = fftrec(b1,NN);
for k=-NN/2:NN-1-NN/2
fftv(k+1+NN/2) = a2(k+1+NN/2) + b2(k+1+NN/2)*wˆk;
end
end
return
Remarque 9.4 On peut aussi d´ efinir un proc´ ed´ e de FFT quand N n’est pas
une puissance de 2. L’approche la plus simple consiste `
a ajouter des z´ eros ` a
la suite originale {f i } de fa¸ con `
a obtenir un nombre total de valeurs ´ egal ` a
˜
N = 2
p , pour un certain p. Cette technique ne conduit n´ eanmoins pas toujours
` a un r´ esultat correct. Une alternative efficace consiste ` a effectuer une partition
de la matrice de Fourier C en sous-blocs de taille plus petite. En pratique, les
impl´ ementations de la FFT peuvent adopter les deux strat´ egies (voir, par
exemple, le package fft disponible dans MATLAB).
9.10 Approximation des d´ eriv´ ees
Un probl` eme qu’on rencontre souvent en analyse num´ erique est l’approximation de la d´ eriv´ ee d’une fonction f sur un intervalle donn´ e [a, b]. Une approche
naturelle consiste ` a introduire n + 1 noeuds {x k , k = 0, . . ., n} de [a, b], avec
x 0 = a, x n = b et x k+1 = x k + h, k = 0, . . ., n − 1 o` u h = (b − a)/n. On
approche alors f
(x i ) en utilisant les valeurs nodales f(x k ) :
h
m
k=−m
α k u i−k =
m
k=−m
β k f(x i−k ),
(9.59)
o` u {α k }, {β k } ∈ R sont m + m
+ 1 coefficients ` a d´ eterminer et u k est l’approximation recherch´ ee de f
(x k ).
Le coˆ ut du calcul est un crit` ere important dans le choix du sch´ ema (9.59).
Il faut par exemple noter que si m = 0, la d´ etermination des quantit´ es {u i }
requiert la r´ esolution d’un syst` eme lin´ eaire.
L’ensemble des noeuds impliqu´ es dans la construction de la d´ eriv´ ee de y en
un noeud donn´ e est appel´ e stencil. La bande de la matrice associ´ ee au syst` eme
(9.59) augmente avec la taille du stencil.
9.10.1 M´ ethodes des diff´ erences finies classiques
Le moyen le plus simple pour construire une formule du type (9.59) consiste
` a revenir `
a la d´ efinition de la d´ eriv´ ee. Si f
(x i ) existe, alors
f
(x i ) = lim
h→0 +
f(x i + h) − f(x i )
h
.
(9.60)