MANUEL
DE
CALCUL
NUMÉ RIQUE
APPLIQUÉ
expressions cn utilisant les relations (16.22) :
Si à prkcnt nous revenons à l’expression de F dans laquelle IIOIIS séparons les partics
constituées par les indices pairs et les indices impairs, nous pouvons écrire :
N/2-1
N/a-1
NFk z c QV$" + c ujT/liN"+-l)k'.
,y=0
")=Cl
Il n’y a plus qu’à substituer les expressions de U et V, ce qui donne :
2Fk = U, + VjW;.
(16.23)
Cette expression ne permet de calculer que la moiti6 de la transforrnée de Fourier, et il faut
une autre relation pour obtenir l’autre moitie. Polir cela, il suffit de remarquer que les fonctions
U et V sont pkriodiques de @iode N/2, par conséquent 11011s po~lvons dire que :
Comme par ailleurs nous avons :
Wk+N/2
N
nous obtenons la relation (16.24) :
~FA+N/~ = uk- - vjw;.
(16.24)
À présent on comprend l’int6rCt d’avoir choisi pour N une puissance dc deux, puisqu’il va de
soi que l’on va calculer chacune des transformées U et V par le même procédé.
9.4. Mise en œuvre de l’algorithme
Il y a plusieurs réalisations pratiques possibles pour utiliser cet, algorithme.
a. Si l’on dispose d’un langage récursif, c’est le cas du Pascal, du C, du PLl... ~ ct dans la
mesure où lc temps de calcul n’est pas prohibitif
il n‘y awra pas dc difficultks particulières
pour réaliser un programme car le tri des données initiales se fera par appel récursif.
b. Si l’on nc dispose pas d’un langage récursif c’ktait le cas du FORTRAN ct du BASIC ~
il est indispensable de procéder à, un tri prkalable des données initiales afin de commencer
les calculs de transforrnées par les fonctions contenant deux ~lkncnts, puis cn poursuivant
par les fonctions à quatre ékmentsT
puis à huit, seize... Donc le problème qui se pose est
celui de la disposition convcnablc des khantillons au départ, lesquels ont été pris dans l’ordre
séquentiel. Autrernent dit, il s’agit de savoir à quelle place (indice) il convient de mettre la
donnk d’indice k. Il y a deux rnéthodes usuelles qui permettent dc rkaliscr Ckgamment
cette
tâche à savoir le tri direct et le tri par inversion de bit.
264
DE
CALCUL
NUMÉ RIQUE
APPLIQUÉ
expressions cn utilisant les relations (16.22) :
Si à prkcnt nous revenons à l’expression de F dans laquelle IIOIIS séparons les partics
constituées par les indices pairs et les indices impairs, nous pouvons écrire :
N/2-1
N/a-1
NFk z c QV$" + c ujT/liN"+-l)k'.
,y=0
")=Cl
Il n’y a plus qu’à substituer les expressions de U et V, ce qui donne :
2Fk = U, + VjW;.
(16.23)
Cette expression ne permet de calculer que la moiti6 de la transforrnée de Fourier, et il faut
une autre relation pour obtenir l’autre moitie. Polir cela, il suffit de remarquer que les fonctions
U et V sont pkriodiques de @iode N/2, par conséquent 11011s po~lvons dire que :
Comme par ailleurs nous avons :
Wk+N/2
N
nous obtenons la relation (16.24) :
~FA+N/~ = uk- - vjw;.
(16.24)
À présent on comprend l’int6rCt d’avoir choisi pour N une puissance dc deux, puisqu’il va de
soi que l’on va calculer chacune des transformées U et V par le même procédé.
9.4. Mise en œuvre de l’algorithme
Il y a plusieurs réalisations pratiques possibles pour utiliser cet, algorithme.
a. Si l’on dispose d’un langage récursif, c’est le cas du Pascal, du C, du PLl... ~ ct dans la
mesure où lc temps de calcul n’est pas prohibitif
il n‘y awra pas dc difficultks particulières
pour réaliser un programme car le tri des données initiales se fera par appel récursif.
b. Si l’on nc dispose pas d’un langage récursif c’ktait le cas du FORTRAN ct du BASIC ~
il est indispensable de procéder à, un tri prkalable des données initiales afin de commencer
les calculs de transforrnées par les fonctions contenant deux ~lkncnts, puis cn poursuivant
par les fonctions à quatre ékmentsT
puis à huit, seize... Donc le problème qui se pose est
celui de la disposition convcnablc des khantillons au départ, lesquels ont été pris dans l’ordre
séquentiel. Autrernent dit, il s’agit de savoir à quelle place (indice) il convient de mettre la
donnk d’indice k. Il y a deux rnéthodes usuelles qui permettent dc rkaliscr Ckgamment
cette
tâche à savoir le tri direct et le tri par inversion de bit.
264