Epita 1999 epreuve commune classe prepa mp epreuve commune 1999 classe prepa mp

E.P.I.T.A. Mathématiques (Obligatoire : durée 3h) Ce problème a pour objectif l'étude de la transformation de Fourier discrète et son application à un algorithme rapide de multiplication des polynômes. Dans tout la suite, on désigne par N un nombre entier naturel non nul et on convient de noter n le nombre entier 2N et a le nombre complexe exp(2idn) = cos(2dn)+isin(2n/n). On appellera : ~~ polynôme associé à un n-uplet a = (ao, al, ... , a,!) de C" le polynôme A appartenant à C,,-l[Xl et défini par : n-1 A( X) = a, + al X + . . + an-l X"-' = zu,Xr r=O transformation de Fourier discrète l'application linéaire F, associant à tout n-uplet a de C" le n-uplet de C" défini à l'aide du polynôme A associé au n-uplet a par : &(a) = (A(1),A(Un),4U3, *-- ,A(u;-'N. L'espace C" est muni de sa norme usuelle, défini pour un Clément a = (ao, al, . . , a=l) par : 1 O) Etude du cas particulier n = 4. a) Expliciter l'image d'un quadruplet a = (ao, al, a2, al) de C4 par l'application F4. b) la matrice M4 de l'endomorphisme F4 dans la base canonique de C4, définie par : eo=(1,0,0,0), el=(0,1,0,0), - - e2=(0,0,1,0), e3=(0,0,0,1). c) Calculer le produit matriciel M, M4 où M, désigne la matrice d'ordre 4 dont les Cléments sont les Conjugués de ceux de la matrice M4. En déduire que F4 est inversible; préciser F4-I. d) Calculer enfin Mt et M44. 2") Etude du cas général. a) Etablir que l'application F, est bijective de C" dans C". b) Expliciter la matrice M, de ...