La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.
Aucun document n'est autorisé. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.
Ce problème étudie la transformée de Fourier discrète des vecteurs de où l'entier est une puissance de 2. Dans la première partie, on découvre la matrice de Fourier-Vandermonde. Dans la seconde, on utilise les résultats obtenus pour les matrices circulantes et, dans la troisième partie, on s'intéresse à un algorithme d'obtention de la transformée de Fourier discrète que l'on applique ensuite au calcul d'un produit de convolution.
Dans tout le problème :
désigne un entier supérieur ou égal à 1 et .
On note le nombre complexe .
Si est un nombre complexe, on note son conjugué . Ainsi, .
est la base canonique de et est le vecteur .
Si , on pourra identifier et la matrice colonne de ses coordonnées dans la base .
, on note .
Si , on note la matrice .
On utilisera sans démonstration la formule .
Si , on remarquera que :
où est la matrice ligne .
Si est une valeur propre d'un endomorphisme de , on note l'espace propre associé à la valeur propre .
Un sous-espace vectoriel de est dit stable par un endomorphisme de si, pour tout .
On note alors . On utilisera sans démonstration le fait que est un endomorphisme de .
Cet endomorphisme est appelé endomorphisme de induit par .
On s'intéresse, dans ce problème, à l'étude de l'application :
On acceptera sans le démontrer que est un endomorphisme de .
On notera la matrice de dans la base ; on a donc .
(on prendra bien garde que dans tout le problème, les indexations des coefficients de vecteurs et de matrices sont réalisées à l'aide de l'ensemble d'entiers )
Partie I = Premières propriétés de l'application
Préliminaires :
(a) Que vaut ? Et plus généralement, que vaut pour ?
Montrer que : .
Justifier alors la factorisation dans .
(b) Soit ; montrer que .
2. Cas particulier :
(a) Expliciter la matrice . Est-elle inversible? Si oui, calculer son inverse.
(b) est-elle diagonalisable? Si oui, déterminer ses valeurs propres et une base de vecteurs propres.
3. Cas particulier :
(a) Expliciter la matrice et calculer la matrice . En déduire que est inversible et donner son inverse.
(b) Calculer la matrice puis . En déduire un polynôme annulateur non nul de .
(c) Quelles sont les valeurs propres possibles de ?
(d) On note ; montrer que est stable par .
Écrire la matrice de l'endomorphisme induit dans la base ( ) de .
Déterminer les valeurs propres de ainsi qu'une base de vecteurs propres de .
En déduire que 2 et -2 sont valeurs propres de et déterminer des vecteurs propres de associés à ces deux valeurs propres.
(e) Calculer ainsi que .
En déduire le spectre de ainsi que ses espaces propres. est-il diagonalisable?
4. Exemples de transformées de Fourier discrètes :
Soient et .
(a) Déterminer dans les trois cas suivants:
i. .
ii. où tel que .
iii. .
(b) On suppose que pour tout .
Montrer que pour tout .
5. Inversibilité de dans le cas général et formule de Parseval :
(a) Calculer la matrice .
Justifier alors que est inversible et préciser .
(b) Justifier que est inversible et préciser .
(c) Montrer que pour tout .
(d) En déduire la formule de Parseval : pour tout .
6. Valeurs propres de :
(a) Soit , une valeur propre de ; montrer que (on pourra utiliser la question 5. (c)).
(b) Montrer que la matrice est la matrice de terme général où tel que :
Autrement dit, .
(c) Préciser alors .
En déduire un polynôme annulateur non nul de et les valeurs propres possibles de .
7. Construction de vecteurs propres de :
on suppose dans cette question que .
On note et .
(a) Calculer et en fonction des vecteurs et .
(b) On note l'endomorphisme canoniquement associé à .
Préciser et et en déduire que :
(c) On note .
Vérifier que est de dimension 2 et montrer que est stable par .
Quelle est la matrice de l'endomorphisme induit dans la base ( ) de ?
Déterminer les valeurs propres ainsi qu'une base de vecteurs propres de cette matrice.
En déduire que et sont valeurs propres de et déterminer des vecteurs propres de associés à ces deux valeurs propres.
(d) Procéder de la même façon avec .
(e) En déduire les valeurs propres de .
Partie II - Lien avec les matrices circulantes
Soit ; on appelle matrice circulante associée à et on note la matrice :
On note en particulier,
(c' est-à-dire et si ).
On note l'endomorphisme de dont la matrice dans la base est . Enfin, on note l'ensemble des matrices circulantes de .
8. Puissances successives de :
(a) Pour tout , déterminer , puis et en déduire la matrice .
(b) Soit . Montrer que :
(c) Enfin, pour tout , calculer .
Que vaut ?
(d) Déduire de ce qui précède l'expression des matrices pour .
9. Réduction de :
(a) Déduire de la question 8 ., les valeurs propres possibles de .
(b) Montrer que pour tout est vecteur propre de pour la valeur propre .
(c) Donner alors tous les sous-espaces propres de .
En déduire que est diagonalisable dans et que où est la matrice diagonale de taille dont les coefficients diagonaux sont les complexes où .
10. Structure de :
(a) Justifier que est un sous-espace vectoriel de .
En donner une base et la dimension.
(b) Montrer que est stable pour la multiplication.
11. Réduction des matrices circulantes:
Soit et la matrice circulante associée.
(a) Vérifier que .
(b) Montrer alors que est diagonalisable dans et préciser ses valeurs propres.
(c) Exemple : soit , c'est-à-dire :
On note .
Quelles sont les valeurs propres de ?
La matrice est-elle inversible?
12. Caractérisation des matrices circulantes:
On se propose dans cette question, de montrer que est l'ensemble des matrices qui commutent avec . On note .
(a) Vérifier que .
Dans la suite de cette question, on considère une matrice vérifiant et on note l'endomorphisme de dont la matrice dans la base canonique de est .
(b) Montrer que pour tout , il existe tel que .
(c) En déduire une explicitation simple de .
(d) Démontrer que est un sous-espace vectoriel de de dimension , et que est égal à .
Partie III - Construction algorithmique
Algorithme de calcul de :
algorithme de Cooley-Tukey ou algorithme «papillon».
On rappelle que l'entier est égal à avec entier supérieur ou égal à 1.
On se propose dans cette question, de construire un algorithme de calcul de , pour un vecteur de .
Pour tout , on note la composante d'indice de dans la base . À , on associe les vecteurs et tels que pour tout et .
Ainsi, pour , pour , on a et .
(a) Vérifier que pour tout :
(b) On suppose déjà calculés et et on considère l'algorithme suivant:
A prend la valeur 1
pour \(k\) allant de 0 à \(\frac{n}{2}-1\) faire
\(B\) prend la valeur \(A \times\left[F_{n / 2}(z)\right]_{k}\)
\(\alpha_{k}\) prend la valeur \(\left[F_{n / 2}(y)\right]_{k}+B\)
\(\alpha_{k+n / 2}\) prend la valeur \(\left[F_{n / 2}(y)\right]_{k}-B\)
\(A\) prend la valeur \(\omega_{n} \times A\)
fin
Comparer le vecteur obtenu après exécution de cet algorithme au vecteur .
(c) On s'intéresse, dans cette question, à l'efficacité de l'algorithme précédent en terme de rapidité de calcul. Pour ceci, la procédure habituelle consiste à évaluer le nombre d'opérations arithmétiques (additions, soustractions, multiplications et divisions de deux nombres complexes) nécessaires à l'obtention du résultat final.
L'implémentation de ce type d'algorithmes, dits récursifs (pour calculer des images par la fonction , on commence par calculer des images par la fonction ), nécessite une gestion particulière dans la mémoire de la machine, du stockage des variables et de l'adressage des instructions exécutées, gestion dont nous ne tiendrons pas compte dans ce sujet.
On note le nombre d'opérations nécessaires au calcul de avec .
Les calculs de et de nécessitent donc chacun opérations.
On convient que .
Justifier alors que la suite ( ) vérifie la relation de récurrence .
(d) En déduire pour tout , la valeur de en fonction de , puis de .
(on pourra d'abord s'intéresser à la suite définie par: )
14. Produit de convolution de deux vecteurs de :
Soient et ; on pose, pour tout ;
on construit ainsi deux vecteurs notés et . On pose alors tel que pour tout , .
Le vecteur est appelé produit de convolution des vecteurs et .
(a) Vérifier que pour tout .
(b) On calcule le produit de convolution en calculant successivement:
les transformées de Fourier discrètes et par l'algorithme étudié dans la question 13.
les produits : pour tout , donc ,
la transformée de Fourier discrète inverse .
Déterminer le nombre d'opérations nécessaires à la réalisation de chacune de ces trois étapes, et en déduire en fonction de un équivalent du nombre d'opérations nécessaires au calcul du produit de convolution par cette méthode.
(c) Comparer, du point de vue du nombre d'opérations effectuées, cette méthode à la méthode du calcul du produit par la définition : pour tout .
