Mathématiques approfondies HEC-ESSEC ECS 2021 : la transformée de Fourier discrète et les matrices circulantes
Afficher ou masquer la section
Le sujet étudie la transformée de Fourier discrète des vecteurs de C^n, n étant une puissance de 2, via la matrice de Fourier-Vandermonde A_n. La partie I établit les premières propriétés de l'endomorphisme F_n associé (cas n=2 et n=4, inversibilité, formule de Parseval, valeurs et vecteurs propres). La partie II relie F_n aux matrices circulantes, qui commutent exactement avec le décalage cyclique J_n, et montre qu'elles sont diagonalisables dans la base de Fourier. La partie III construit l'algorithme de Cooley-Tukey et l'applique au calcul rapide d'un produit de convolution.
1Partie I : premières propriétés de l'application F_nOn étudie les cas particuliers n=2 et n=4, l'inversibilité de A_n, la formule de Parseval, et on construit explicitement les valeurs propres et vecteurs propres de F_n dans le cas général.
2Partie II : lien avec les matrices circulantesOn étudie les puissances de la matrice de décalage cyclique J_n, sa diagonalisation dans la base de Fourier, puis on montre que les matrices circulantes sont exactement celles qui commutent avec J_n.
3Partie III : construction algorithmiqueOn construit l'algorithme de Cooley-Tukey (transformée de Fourier rapide) par récursion, on évalue sa complexité, puis on l'applique au calcul rapide d'un produit de convolution.
Description
Annale de maths approfondies BCE HEC/ESSEC pour la filiere ECS, session 2021.
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 ℂ^n où l'entier n 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 :
N désigne un entier supérieur ou égal à 1 et n = 2^N.
On note ω_n le nombre complexe e^((2iπ)/n) = cos((2π)/n) + isin((2π)/n).
Si z = Re(z) + iIm(z) est un nombre complexe, on note son conjugué z¯ = Re(z) − iIm(z). Ainsi, ω_n^– = e^(− (2iπ)/n).
ℬ_n = (e_0, e_1, …, e_(n − 1)) est la base canonique de ℂ^n et e_Σ est le vecteur e_Σ = ∑_(k = 0)^(n − 1)e_k.
Si x = (x_0, x_1, …, x_(n − 1)) = ∑_(k = 0)^(n − 1)x_k e_k ∈ ℂ^n, on pourra identifier x et la matrice colonne X = (x_0; x_1; ⋮; x_(n − 1)) de ses coordonnées dans la base ℬ_n.
SiX = (x_0; x_1; ⋮; x_(n − 1)), on note X¯ = (x_0^–; x_1^–; ⋮; x_(n − 1)^–).
Si M = (m_(i, j))_((i, j) ∈ [ [0, n − 1] ]^2) ∈ ℳ_n(ℂ), on note M¯ la matrice M¯ = (m_(i, j)^–)_((i, j) ∈ [ [0, n − 1] ]^2) ∈ ℳ_n(ℂ).
On utilisera sans démonstration la formule MX^– = M¯X¯.
Si x = ∑_(k = 0)^(n − 1)x_k e_k, on remarquera que :
∑_(k = 0)^(n − 1)|x_k|^2 = (^t X¯)X
où ^t X¯ est la matrice ligne (x_0^–, x_1^–, ⋯, x_(n − 1)^–).
Si λ est une valeur propre d'un endomorphisme g de ℂ^n, on note E_λ(g) = Ker(g − λid_(ℂ^n)) l'espace propre associé à la valeur propre λ.
Un sous-espace vectoriel G de ℂ^n est dit stable par un endomorphisme g de ℂ^n si, pour tout x ∈ G, g(x) ∈ G.
On note alors g_(|G) : {G → G; x ↦ g(x). On utilisera sans démonstration le fait que g_(|G) est un endomorphisme de G.
Cet endomorphisme g_(|G) est appelé endomorphisme de G induit par g.
On s'intéresse, dans ce problème, à l'étude de l'application :
On acceptera sans le démontrer que F_n est un endomorphisme de ℂ^n.
On notera A_n la matrice de F_n dans la base ℬ_n; on a donc A_n = (ω_n^(kj))_((k, j) ∈ [ [0, n − 1] ]^2) ∈ ℳ_n(ℂ).
(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 [ [0, n − 1] ] )
Partie I = Premières propriétés de l'application F_n
Préliminaires :
(a) Que vaut ω_n^n ? Et plus généralement, que vaut (ω_n^k)^n pour k ∈ ℤ ?
Montrer que : ∀(k, k^′) ∈ [ [0, n − 1] ]^2, k ≠ k^′ ⟹ ω_n^k ≠ ω_n^(k^′).
Justifier alors la factorisation dans ℂ[X] : X^n − 1 = ∏_(k = 0)^(n − 1)(X − ω_n^k).
(b) Soit s ∈ ℤ; montrer que ∑_(q = 0)^(n − 1)ω_n^(sq) = {n, si s est un multiple de n; 0, sinon.
2. Cas particulier n = 2 :
(a) Expliciter la matrice A_2. Est-elle inversible? Si oui, calculer son inverse.
(b) A_2 est-elle diagonalisable? Si oui, déterminer ses valeurs propres et une base de vecteurs propres.
3. Cas particulier n = 4 :
(a) Expliciter la matrice A_4 et calculer la matrice A_4 A_4^–. En déduire que A_4 est inversible et donner son inverse.
(b) Calculer la matrice A_4^2 puis A_4^4. En déduire un polynôme annulateur non nul de A_4.
(c) Quelles sont les valeurs propres possibles de A_4 ?
(d) On note P = vect(e_0, e_Σ); montrer que P est stable par F_4.
Écrire la matrice C_4 de l'endomorphisme induit F_(4|P) dans la base ( e_0, e_Σ ) de P.
Déterminer les valeurs propres de C_4 ainsi qu'une base de vecteurs propres de C_4.
En déduire que 2 et -2 sont valeurs propres de F_4 et déterminer des vecteurs propres de F_4 associés à ces deux valeurs propres.
(e) Calculer F_4(e_0 + e_2) ainsi que F_4(e_1 − e_3).
En déduire le spectre de F_4 ainsi que ses espaces propres. F_4 est-il diagonalisable?
4. Exemples de transformées de Fourier discrètes :
Soient x = ∑_(k = 0)^(n − 1)x_k e_k ∈ ℂ^n et y = F_n(x) = ∑_(k = 0)^(n − 1)y_k e_k.
(a) Déterminer y dans les trois cas suivants:
i. x = e_Σ = ∑_(k = 0)^(n − 1)e_k.
ii. x = ∑_(k = 0)^(n − 1)a^k e_k où a ∈ ℂ tel que |a| ≠ 1.
iii. x = ∑_(k = 0)^(n − 1)((n − 1)/k)e_k.
(b) On suppose que pour tout k ∈ [ [0, n − 1] ], x_k ∈ ℝ.
Montrer que pour tout k ∈ [ [1, n − 1] ], y_k = y_(n − k)^–.
5. Inversibilité de A_n dans le cas général et formule de Parseval :
(a) Calculer la matrice A_n A_n^–.
Justifier alors que A_n est inversible et préciser A_n^(− 1).
(b) Justifier que F_n est inversible et préciser F_n^(− 1).
(c) Montrer que pour tout X ∈ ℳ_(n, 1)(ℂ), n(^t X¯)X = ^t(A_n X^–)A_n X.
(d) En déduire la formule de Parseval : pour tout x = ∑_(k = 0)^(n − 1)x_k e_k, ∑_(k = 0)^(n − 1)|∑_(j = 0)^(n − 1)ω_n^(kj)x_j|^2 = n∑_(k = 0)^(n − 1)|x_k|^2.
6. Valeurs propres de A_n :
(a) Soit λ ∈ ℂ, une valeur propre de A_n; montrer que |λ| = √n (on pourra utiliser la question 5. (c)).
(b) Montrer que la matrice A_n^2 est la matrice de terme général b_(k, j) où (k, j) ∈ [ [0, n − 1] ]^2 tel que :
b_(0, 0) = n b_(k, n − k) = n pour k ∈ [ [1, n − 1] ] et b_(k, j) = 0 sinon
En déduire un polynôme annulateur non nul de A_n et les valeurs propres possibles de A_n.
7. Construction de vecteurs propres de F_n :
on suppose dans cette question que n ≥ 8.
On note e_(cos) = ∑_(k = 0)^(n − 1)cos((2kπ)/n)e_k et e_(sin) = ∑_(k = 0)^(n − 1)sin((2kπ)/n)e_k.
(a) Calculer F_n(e_1 + e_(n − 1)) et F_n(e_1 − e_(n − 1)) en fonction des vecteurs e_(cos) et e_(sin).
(b) On note G_n l'endomorphisme canoniquement associé à A_n^2.
Préciser G_n(e_1 + e_(n − 1)) et G_n(e_1 − e_(n − 1)) et en déduire que :
Vérifier que Q est de dimension 2 et montrer que Q est stable par F_n.
Quelle est la matrice de l'endomorphisme induit F_(n|Q) dans la base ( e_1 + e_(n − 1), e_(cos) ) de Q ?
Déterminer les valeurs propres ainsi qu'une base de vecteurs propres de cette matrice.
En déduire que √n et − √n sont valeurs propres de F_n et déterminer des vecteurs propres de F_n associés à ces deux valeurs propres.
(d) Procéder de la même façon avec R = vect(e_1 − e_(n − 1), e_(sin)).
(e) En déduire les valeurs propres de F_n.
Partie II - Lien avec les matrices circulantes
Soit a = (a_0, a_1, …, a_(n − 1)) ∈ ℂ^n; on appelle matrice circulante associée à a et on note C(a) la matrice :
On note en particulier, J_n = C(0, 1, 0, 0, …, 0) = (0, 1, 0, ⋯, 0; 0, 0, 1, ⋱, ⋮; ⋮, 0, ⋱, ⋱, 0; 0, ⋮, ⋱, ⋱, 1; 1, 0, ⋯, 0, 0)
(c' est-à-dire a_1 = 1 et a_j = 0 si j ≠ 1 ).
On note φ_n l'endomorphisme de ℂ^n dont la matrice dans la base ℬ_n est J_n. Enfin, on note Circ_n(ℂ) l'ensemble des matrices circulantes de ℳ_n(ℂ).
8. Puissances successives de J_n :
(a) Pour tout j ∈ [ [0, n − 1] ], déterminer φ_n(e_j), puis φ_n^2(e_j) et en déduire la matrice J_n^2.
(b) Soit k ∈ [ [1, n − 1] ]. Montrer que :
∀j ∈ [ [k, n − 1] ] φ_n^k(e_j) = e_(j − k) et ∀j ∈ [ [0, k − 1] ] φ_n^k(e_j) = e_(n − k + j)
(c) Enfin, pour tout j ∈ [ [0, n − 1] ], calculer φ_n^n(e_j).
Que vaut φ_n^n ?
(d) Déduire de ce qui précède l'expression des matrices J_n^k pour k ∈ [ [1, n] ].
9. Réduction de J_n :
(a) Déduire de la question 8 ., les valeurs propres possibles de J_n.
(b) Montrer que pour tout k ∈ [ [0, n − 1] ], F_n(e_k) est vecteur propre de φ_n pour la valeur propre ω_n^k.
(c) Donner alors tous les sous-espaces propres de φ_n.
En déduire que J_n est diagonalisable dans ℳ_n(ℂ) et que J_n = 1/nA_n D_n A_n^– où D_n est la matrice diagonale de taille n dont les coefficients diagonaux sont les complexes ω_n^k où k ∈ [ [0, n − 1] ].
10. Structure de Circ_n(ℂ) :
(a) Justifier que Circ_n(ℂ) est un sous-espace vectoriel de ℳ_n(ℂ).
En donner une base et la dimension.
(b) Montrer que Circ_n(ℂ) est stable pour la multiplication.
11. Réduction des matrices circulantes:
Soit a = (a_0, a_1, …, a_(n − 1)) ∈ ℂ^n et C(a) la matrice circulante associée.
(a) Vérifier que C(a) = ∑_(k = 0)^(n − 1)a_k J_n^k.
(b) Montrer alors que C(a) est diagonalisable dans ℳ_n(ℂ) et préciser ses valeurs propres.
(c) Exemple : soit α = (0, 1, 0, 0, …, 0, 1) ∈ ℂ^n, c'est-à-dire :
α_1 = α_(n − 1) = 1 et α_i = 0 si i ≠ 1 et i ≠ n − 1
On note S_n = C(α).
Quelles sont les valeurs propres de S_n ?
La matrice S_n est-elle inversible?
12. Caractérisation des matrices circulantes:
On se propose dans cette question, de montrer que Circ_n(ℂ) est l'ensemble des matrices qui commutent avec J_n. On note Ω = {M ∈ ℳ_n(ℂ)|J_n M = MJ_n}.
(a) Vérifier que Circ_n(ℂ) ⊂ Ω.
Dans la suite de cette question, on considère une matrice M ∈ ℳ_n(ℂ) vérifiant J_n M = MJ_n et on note g l'endomorphisme de ℂ^n dont la matrice dans la base canonique de ℂ^n est M.
(b) Montrer que pour tout k ∈ [ [0, n − 1] ], il existe λ_k ∈ ℂ tel que g(F_n(e_k)) = λ_k F_n(e_k).
(c) En déduire une explicitation simple de 1/nA_n^–MA_n.
(d) Démontrer que Ω est un sous-espace vectoriel de ℳ_n(ℂ) de dimension n, et que Ω est égal à Circ_n(ℂ).
Partie III - Construction algorithmique
Algorithme de calcul de F_n(x) :
algorithme de Cooley-Tukey ou algorithme «papillon».
On rappelle que l'entier n est égal à 2^N avec N entier supérieur ou égal à 1.
On se propose dans cette question, de construire un algorithme de calcul de F_n(x), pour un vecteur x = ∑_(k = 0)^(n − 1)x_k e_k = (x_0, x_1, …, x_(n − 1)) de ℂ^n.
Pour tout k ∈ [0, n − 1], on note [F_n(x)]_k la composante d'indice k de F_n(x) dans la base ℬ_n. À x, on associe les vecteurs y = (y_0, y_1, …, y_(n/2 − 1)) ∈ ℂ^(n/2) et z = (z_0, z_1, …, z_(n/2 − 1)) ∈ ℂ^(n/2) tels que pour tout k ∈ [ [0, n/2 − 1] ], y_k = x_(2k) et z_k = x_(2k + 1).
Ainsi, pour n = 8, pour x = (x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7) ∈ ℂ^8, on a y = (x_0, x_2, x_4, x_6) ∈ ℂ^4 et z = (x_1, x_3, x_5, x_7) ∈ ℂ^4.
(a) Vérifier que pour tout k ∈ [ [0, n/2 − 1] ] :
(b) On suppose déjà calculés F_(n/2)(y) et F_(n/2)(z) 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 (α_0, α_1, …, α_(n − 1)) obtenu après exécution de cet algorithme au vecteur F_n(x).
(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 F_n, on commence par calculer des images par la fonction F_(n/2) ), 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 u_N le nombre d'opérations nécessaires au calcul de F_n(x) avec n = 2^N.
Les calculs de F_(n/2)(y) et de F_(n/2)(z) nécessitent donc chacun u_(N − 1) opérations.
On convient que u_0 = 0.
Justifier alors que la suite ( u_N ) vérifie la relation de récurrence u_N = 2u_(N − 1) + 2^(N + 1).
(d) En déduire pour tout N ∈ ℕ, la valeur de u_N en fonction de N, puis de n.
(on pourra d'abord s'intéresser à la suite (v_N) définie par: ∀N ∈ ℕ, v_N = (u_N)/(2^N) )
14. Produit de convolution de deux vecteurs de ℂ^(n/2) :
Soient y = (y_0, y_1, …, y_(n/2 − 1)) ∈ ℂ^(n/2) et z = (z_0, z_1, …, z_(n/2 − 1)) ∈ ℂ^(n/2); on pose, pour tout k ∈ [ [n/2, n − 1] ], y_k = z_k = 0;
on construit ainsi deux vecteurs notés y~ = (y_0, y_1, …, y_(n − 1)) ∈ ℂ^n et z~ = (z_0, z_1, …, z_(n − 1)) ∈ ℂ^n. On pose alors x = y∗z = (x_0, x_1, …, x_(n − 1)) ∈ ℂ^n tel que pour tout k ∈ [ [0, n − 1] ], x_k = ∑_(j = 0)^k y_j z_(k − j).
Le vecteur x est appelé produit de convolution des vecteurs y et z.
(a) Vérifier que pour tout k ∈ [ [0, n − 1] ], [F_n(x)]_k = [F_n(y~)]_k ⋅ [F_n(z~)]_k.
(b) On calcule le produit de convolution x = y∗z en calculant successivement:
les transformées de Fourier discrètes F_n(y˜) et F_n(z˜) par l'algorithme étudié dans la question 13.
les produits : pour tout k ∈ [ [0, n − 1] ], [F_n(x)]_k = [F_n(y˜)]_k ⋅ [F_n(z˜)]_k, donc F_n(y∗z),
la transformée de Fourier discrète inverse F_n^(− 1)(F_n(y∗z)).
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 n un équivalent du nombre d'opérations nécessaires au calcul du produit de convolution x = y∗z 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 x = y∗z par la définition : pour tout k ∈ [ [0, n − 1] ], x_k = ∑_(j = 0)^k y_j z_(k − j).
Questions fréquentes
4 questions
Sur quels chapitres porte le sujet de mathématiques approfondies HEC-ESSEC ECS 2021 ?
Afficher ou masquer la section
Sur quels chapitres porte le sujet de mathématiques approfondies HEC-ESSEC ECS 2021 ?
+
Il porte sur la réduction des endomorphismes, les nombres complexes et les racines de l'unité, le produit scalaire hermitien, et l'algorithmique récursive appliquée à la transformée de Fourier rapide.
Les trois parties sont-elles indépendantes ?
+
Non, la partie II utilise les résultats de la partie I sur les valeurs propres de F_n, et la partie III utilise la transformée de Fourier discrète étudiée dans les deux parties précédentes.
Qu'est-ce que l'algorithme de Cooley-Tukey construit en partie III ?
+
C'est un algorithme récursif, dit de transformée de Fourier rapide, qui calcule la transformée de Fourier discrète d'un vecteur de taille n = 2^N en O(n log n) opérations au lieu de O(n^2).
Ce sujet est-il faisable en première année ?
+
Non, il mobilise la réduction des endomorphismes en dimension complexe et l'algorithmique récursive avancée, notions de deuxième année ECS.
Même chapitre : Suites et séries de fonctions (+4)BCE Maths approfondies emlyon ECS 2021BCE · 2021Corrigé
Même année, EcricomeEcricome Maths approfondies ECS 2021Ecricome · 2021Corrigé
Même sessionBCE Maths approfondies EDHEC ECS 2021BCE · 2021Corrigé
Même sessionBCE Maths approfondies HEC/ESCP ECS 2021, épreuve 2BCE · 2021Corrigé