Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB

icon

28

pages

icon

English

icon

Documents

Écrit par

Publié par

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

icon

28

pages

icon

English

icon

Ebook

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Modélisation et résolutions numérique et symboliquede problèmes via les logiciels Maple et MATLAB(MODEL)oCours n 9 : Transformée de Fourier discrèteStef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 1 / 28Résumé du cours précédentCalcul matricielManipulations des matrices :1 Stockage des : ligne ou colonne2 Les BLASLes décompositions utiles et leurs applications :1 LU2 QR3 Réduction (diagonalisation, etc.)4 SVDS. Graillat (Univ. Paris 6) MODEL (cours n˚9) 2 / 28ObjectifsPrésenter l’algorithme de « Transformée de Fourier Rapide » (Fast FourierTransform ou FFT)Un des algorithmes les plus utilisés dans le monde avec des applications entraitement du signal d’imagecalcul formel (multiplication de polynômes, de grands entiers, etc)S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 3 / 28Plan du cours1 Multiplication de polynômes et choix de représentation2 Évaluation et interpolation3 Racine n-ième de l’unité4 Version matricielle de la FFTS. Graillat (Univ. Paris 6) MODEL (cours n˚9) 4 / 28BibliographieAlgorithms, S. Dasgupta, C.H. Papadimitriou et U.V. Vazirani,McGraw Hill, 2006Introduction à l’algorithmique, Thomas Cormen, Charles Leiserson,Ronald Rivest et Clifford Stein, 2nd édition, Dunod, 2002The Art of Computer Programming, Volume 2 : SeminumericalAlgorithms, Donald E. Knuth, 3e édition, Addison-Wesley, 1997Modern Computer Algebra, Joachim von zur Gathen et JürgenGerhard, 2nd edition, ...
Voir Alternate Text

Publié par

Nombre de lectures

52

Langue

English

Modélisation et résolutions numérique et symbolique
de problèmes via les logiciels Maple et MATLAB
(MODEL)
oCours n 9 : Transformée de Fourier discrète
Stef Graillat
Université Pierre et Marie Curie (Paris 6)
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 1 / 28Résumé du cours précédent
Calcul matriciel
Manipulations des matrices :
1 Stockage des : ligne ou colonne
2 Les BLAS
Les décompositions utiles et leurs applications :
1 LU
2 QR
3 Réduction (diagonalisation, etc.)
4 SVD
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 2 / 28Objectifs
Présenter l’algorithme de « Transformée de Fourier Rapide » (Fast Fourier
Transform ou FFT)
Un des algorithmes les plus utilisés dans le monde avec des applications en
traitement du signal d’image
calcul formel (multiplication de polynômes, de grands entiers, etc)
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 3 / 28Plan du cours
1 Multiplication de polynômes et choix de représentation
2 Évaluation et interpolation
3 Racine n-ième de l’unité
4 Version matricielle de la FFT
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 4 / 28Bibliographie
Algorithms, S. Dasgupta, C.H. Papadimitriou et U.V. Vazirani,
McGraw Hill, 2006
Introduction à l’algorithmique, Thomas Cormen, Charles Leiserson,
Ronald Rivest et Clifford Stein, 2nd édition, Dunod, 2002
The Art of Computer Programming, Volume 2 : Seminumerical
Algorithms, Donald E. Knuth, 3e édition, Addison-Wesley, 1997
Modern Computer Algebra, Joachim von zur Gathen et Jürgen
Gerhard, 2nd edition, Cambridge University Press, 2003
Numerical Recipes. The Art of Scientific Computing, William Press,
Saul Teukolsky, William Vetterling et Brian Flannery, 3e édition,
Cambridge University Press, 2007
Computational Frameworks for the Fast Fourier Transform, Charles
Van Loan, SIAM, 1987
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 5 / 28Multiplication de polynômes
Le produit de 2 polynômes de degré n est un polynôme de degré au plus 2n
2 2 2 3 4
(1+2x +3x )(2+x +4x ) = 2+5x +12x +11x +12x
Plus généralement, si
n nP(x) = a +a x ++a x et Q(x) = b +b x ++b x0 1 n 0 1 n
2nalors R(x) = P(x)Q(x) = c +c x ++c x avec0 1 2n
kX
c = a b +a b ++a b = a bk 0 k 1 k 1 k 0 i k i
i=0
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 6 / 28Multiplication de polynômes (suite)
Algorithme 1 (Multiplication naïve)
function R = mult(P,Q)
n = length(P);
R = zeros(1,2n 1);
for i=1:n
for j=1:n
R( i+j 1) = R( i+j 1) + P( i )Q( j );
end
end
2Coût :O(n )
2Peut-on faire mieux queO(n )?
log 3 1:58
2! algorithme de Karatsuba :O(n )O(n )
Peut-on encore faire mieux?
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 7 / 28Changement de représentation (suite)
On représente généralement le polynôme
nP(x) = a +a x ++a x0 1 n
par le vecteur de ses coefficients a = (a ;a ;:::;a )0 1 n 1
Question : y-a-t’il d’autres représentations des polynômes?
Définition 1
Un nombre complexe z est une racine de P(x) si P(z) = 0
Théorème 1 (Théorème de d’Alembert-Gauss)
Tout polynôme P(x) de degré n à coefficients dans C admet n racines
z ;:::;z (comptées avec leurs multiplicités). On a alors1 n
P(x) = a (x z )(x z )n 1 n
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 8 / 28Changement de représentation (suite)
On peut donc représenter le polynôme P(x) par a et ses racines z ;:::;z .n 1 n
Évaluation : P étant donné par a et z ;:::;z , on peut évaluer P en x enn 1 n
O(n)
Multiplication : P étant donné par a et z ;:::;z et Q étant donné par bn 1 n n
0 0 0 0et z ;:::;z , PQ est donné par a b , z ;:::;z ;z ;:::;zn n 1 n1 n 1 n
Addition : difficile!
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 9 / 28Changement de représentation (suite)
Théorème 2
Un polynôme de degré n est uniquement déterminé par ses valeurs sur
n +1 points distincts.
Fixons n +1 points distincts x ;:::;x . On peut spécifier un polynôme0 n
nP(x) = a +a x ++a x de degré n par l’une des façons suivantes :0 1 n
1 ses coefficients a ;a ;:::;a0 1 n
2 les valeurs P(x );P(x );:::;P(x )0 1 n
Il est facile de multiplier deux polynômes dont on connaît les valeurs. Le
produit R(z) en un point z est le produit de P(z) par Q(z)!
Facile aussi pour l’addition!
S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 10 / 28

Voir Alternate Text
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents
Alternate Text