WikiPrépaLivrets

Centrale Mathématiques 2 TSI 2022Sujet, corrigé et rapport du jury

Pas encore noté
Logo concours Centrale

Explorer les annales

BanqueCentraleAnnée2022FilièreTSIMatièreMathématiques
Annales Centrale TSI MathématiquesCentrale TSI 2022TSI MathématiquesMathématiques 2022

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Rapport du juryLire en ligneLaTeXWord

Présentation du sujet

Difficulté moyenne
La transformation de Fourier rapide : coefficients de Fourier, matrices circulantes et algorithme de Cooley-Tukey
Afficher ou masquer la section

Le problème étudie en cinq parties largement indépendantes la transformation de Fourier rapide, utilisée notamment pour la compression d'images numériques. Il part de rappels sur les racines de l'unité et les coefficients de Fourier, puis étudie la diagonalisation des matrices circulantes avant de détailler la discrétisation, l'algorithme rapide et une application à la convolution circulaire.

  1. 1Partie I : calculs préliminaires et comportement asymptotique des coefficients de FourierRappels sur les racines de l'unité et étude de propriétés usuelles des coefficients de Fourier.
  2. 2Partie II : diagonalisation des matrices circulantesÉtude du cas N=3 puis généralisation à une matrice circulante de taille quelconque.
  3. 3Partie III : discrétisation et transformée de Fourier discrèteApproximation des coefficients de Fourier par échantillonnage et formule d'inversion.
  4. 4Partie IV : transformée de Fourier rapideÉtude de l'algorithme rapide de calcul et de sa complexité.
  5. 5Partie V : convolution circulaireÉtude d'un opérateur sur les suites périodiques réutilisant les résultats des parties précédentes.

Difficulté moyenne. Le jury qualifie le sujet de longueur raisonnable, accessible aux candidats ayant une bonne connaissance du cours.

L'épreuve en chiffres

Moyenne 8,7 / 20 · écart-type 4,26 · 1 026 présents · où vous situez-vous ?
Afficher ou masquer la section
Moyenne
8,7/ 20
Écart-type
4,26
Présents
1 026
Coefficient
12
Durée
4 h
1er quartile
6
Médiane
8,8
3e quartile
12
moyenne 8,705101520
Deux tiers des copies environ (moyenne ± écart-type)

Votre note sur 20 à ce sujet, en conditions de concours.

Source : document officiel du concours, épreuve du 6 mai 2022. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

5 erreurs relevées
Confusion entre inverse et conjugué · Hypothèses de théorèmes non vérifiées · Diagonalisation mal comprise
Afficher ou masquer la section

Le sujet balayait une large partie du programme d'algèbre et d'analyse des deux années, avec de nombreuses questions proches du cours. Les candidats maîtrisant les théorèmes du cours et sachant les citer précisément ont pu se distinguer.

Les erreurs les plus sanctionnées

  1. 1
    Confusion entre inverse et conjuguéQ3

    Une grande partie des candidats ne différencie pas une puissance inverse et le conjugué d'un nombre complexe.

  2. 2
    Hypothèses de théorèmes non vérifiéesQ9, Q10

    Les hypothèses de continuité pour intégrer sur un segment ou pour utiliser les sommes de Riemann sont souvent oubliées, de même que le caractère C1 lors d'une intégration par parties.

  3. 3
    Diagonalisation mal compriseQ15

    Certains candidats confondent le caractère scindé du polynôme caractéristique et la diagonalisabilité, ou trouvent des espaces propres réduits au vecteur nul.

  4. 4
    Réponses sans justification sur le nombre d'opérationsQ28, Q31, Q41, Q43

    Pour les questions demandant le nombre d'opérations nécessaires à une transformation de Fourier discrète, certains candidats donnent une réponse sans aucune justification.

  5. 5
    Calculs par simple analogie

    Lors de la généralisation à des matrices de taille quelconque, une simple analogie avec le cas particulier n'était pas considérée comme une preuve suffisante.

Ce qui a été bien réussi

  • Le calcul des déterminants pour des matrices de taille 3 a été bien mené.
  • Les dernières parties ont été abordées correctement par les meilleurs candidats.
  • Des efforts appréciables d'expression et de soin ont été remarqués chez de nombreux candidats.

Conseils du jury

  • Lire attentivement l'énoncé et respecter scrupuleusement les notations, en particulier lorsque plusieurs définitions voisines coexistent.
  • Vérifier systématiquement les hypothèses avant d'appliquer un théorème du cours.
  • Justifier les résultats de dénombrement d'opérations plutôt que de les énoncer directement.
  • Préciser clairement si un raisonnement se fait par équivalence ou par simple implication.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

Notations

Si (a, b) ∈ ℤ^2 avec a ⩽ b, [ [a, b] ] désigne l＇ensemble des entiers relatifs compris entre a et b ．
Si z est un nombre complexe， z¯ désigne son conjugué et |z| son module．
Dans tout le problème， N désigne un entier naturel supérieur ou égal à 2 et on note ω = e^(2iπ/N) ．
M_N(𝕂) désigne l＇ensemble des matrices carrées de taille N à coefficients dans 𝕂(𝕂 = ℝ ou ℂ) et I_N désigne la matrice identité d＇ordre N ．
Si A = (a_(i, j))_(1 ⩽ i, j ⩽ N) est une matrice de M_N(ℂ) ，la matrice A¯ = (a¯_(i, j))_(1 ⩽ i, j ⩽ N) désigne la matrice dont les coefficients sont les conjugués de ceux de A ．
On note C_(2π)^0 l＇espace vectoriel des fonctions définies sur ℝ et à valeurs dans ℝ, 2π périodiques et continues sur ℝ ．

Rappels

Pour toute fonction f appartenant à C_(2π)^0 ，les coefficients de Fourier trigonométriques de f sont définis par
a_0(f) = 1/(2π)∫_0^(2π)f(t)dt
et，pour tout entier k dans ℕ^∗ ，
{a_k(f) = 1/π∫_0^(2π)f(t)cos(kt)dt; b_k(f) = 1/π∫_0^(2π)f(t)sin(kt)dt

Structure et objectifs du problème

Ce problème est composé de cinq parties largement indépendantes．
La première partie consiste à établir quelques calculs utiles dans tout le problème et à étudier le comportement asymptotique des coefficients de Fourier d＇une fonction de C_(2π)^0 supposée de classe C^1 ．La partie II traite de questions d＇algèbre linéaire；le résultat de l＇une d＇elles pourra être utilisé dans la partie III．La partie III s＇intéresse à l＇échantillonnage d＇un signal continu et à une application，appelée transformation de Fourier discrète， qui permet le traitement d＇un signal numérique à partir d＇un échantillon．La partie IV est consacrée à l＇étude d＇un algorithme rapide de calcul d＇une transformée de Fourier discrète et au calcul de sa complexité．Enfin， la partie V étudie un opérateur sur l＇ensemble des suites périodiques et fournit une application des résultats obtenus dans les parties précédentes．
L＇algorithme de transformée de Fourier rapide（Cooley et Tukey，1965）est，entre autres，à la base des techniques de compression numérique ayant conduit au format JPEG．

I Première partie

I．A－Calculs préliminaires

Q 1．Résoudre dans ℂ l＇équation z^N = 1 ．On exprimera les solutions à l＇aide du nombre ω ．
Q 2．Déterminer l＇ensemble des entiers relatifs j tels que ω^j = 1 ．
Q 3．Démontrer que，pour tout k ∈ ℕ, 1/(ω^k) = ω¯^k ．
Q 4．Soit q un nombre complexe et N un entier naturel supérieur ou égal à 1．Calculer ∑_(n = 0)^(N − 1)q^n ．On distinguera les cas q = 1 et q ≠ 1 ．
Q 5．En déduire la valeur de ∑_(n = 0)^(N − 1)ω^(rn) ，dans les trois cas
r = 0, r ∈ [ [1, N − 1] ], r ∈ [ [ − (N − 1), − 1] ].

I.B - Comportement asymptotique des coefficients de Fourier

À toute fonction f ∈ C_(2π)^0, on associe la suite (c_k(f))_(k ∈ ℤ^′), à valeur dans ℂ, définie par c_0(f) = a_0(f) et, ∀k ∈ ℕ^∗,
{c_k(f) = 1/2(a_k(f) − ib_k(f)),; c_(− k)(f) = 1/2(a_k(f) + ib_k(f)).
Q 6. Vérifier que
∀k ∈ ℤ, c_k(f) = 1/(2π)∫_0^(2π)f(t)e^(− ikt) dt
La suite (c_k(f))_(k ∈ ℤ) s'appelle la suite des coefficients de Fourier exponentiels de la fonction f. Cette notation est utilisée tout au long du problème.
Q 7. Question de cours : citer le théorème de Parseval pour une fonction f ∈ C_(2π)^0.
Q 8. Pour tout entier naturel k non nul, exprimer |c_k(f)|^2 et |c_(− k)(f)|^2 en fonction de a_k^2(f) et b_k^2(f) et, en utilisant le théorème de Parseval, démontrer que lim_(k → + ∞)c_k(f) = lim_(k → + ∞)c_(− k)(f) = 0.
Dans les trois questions suivantes, f est une fonction 2π périodique, de classe C^1, à valeurs réelles.
Q 9. Pour tout entier naturel k non nul, justifier l'existence de a_k(f^′) et b_k(f^′).
Q 10. À l'aide d'intégrations par parties, démontrer que, pour tout entier naturel k non nul,
{a_k(f^′) = kb_k(f),; b_k(f^′) = − ka_k(f).
En déduire que, pour tout k ∈ ℤ^∗, c_k(f^′) = ikc_k(f).
Q 11. En déduire que |c_k(f)| = _(k → + ∞)o(1/k) et |c_(− k)(f)| = _(k → + ∞)o(1/k).

II Diagonalisation des matrices circulantes

On rappelle que N est un entier naturel supérieur ou égal à 2 .
Pour (a_0, a_1, …, a_(N − 1)) ∈ ℂ^N, on considère la matrice
C(a_0, a_1, …, a_(N − 1)) = (a_0, a_1, a_2, ⋯, a_(N − 1); a_(N − 1), a_0, ⋱, ⋱, ⋮; ⋮, ⋱, ⋱, ⋱, a_2; a_2, ⋱, ⋱, ⋱, a_1; a_1, a_2, ⋯, a_(N − 1), a_0) ∈ M_N(ℂ)

II.A - Étude du cas N = 3

On note G_3 = C(0, 1, 0) = (0, 1, 0; 0, 0, 1; 1, 0, 0) ∈ M_3(ℂ).
Q 12. Montrer que G_3 est une matrice orthogonale de M_3(ℝ). Identifier géométriquement l'isométrie canoniquement associée à la matrice G_3 (on précisera ses éléments caractéristiques).
Q 13. Calculer le polynôme caractéristique de G_3. Montrer que la matrice G_3 est diagonalisable dans M_3(ℂ). Est-elle diagonalisable dans M_3(ℝ) ?
Q 14. Déterminer une matrice P_3 inversible dans M_3(ℂ) et une matrice D_3 ∈ M_3(ℂ) diagonale telles que G_3 = P_3 D_3 P_3^(− 1).
Q 15. Pour tout (a_0, a_1, a_2) ∈ ℂ^3 exprimer C(a_0, a_1, a_2) à l'aide de I_3, G_3 et G_3^2 et en déduire que C(a_0, a_1, a_2) est diagonalisable dans M_3(ℂ).

II.B - Étude du cas général

On note G_N = C(0, 1, 0, …, 0) ∈ M_N(ℂ) et g l'endomorphisme de ℂ^N dont la matrice dans la base canonique (e_1, e_2, …, e_N) de ℂ^N est G_N.
Q 16. Montrer que le polynôme caractéristique de G_N est X^N − 1.
Q 17. G_N est-elle diagonalisable dans M_N(ℂ) ? Justifier.
On note
P_N = (1, 1, ⋯, 1; 1, ω, ⋯, ω^(N − 1); ⋮, ⋮, ⋮; 1, ω^(N − 1), ⋯, ω^((N − 1)(N − 1)))
la matrice de M_N(ℂ) dont, pour tout couple (r, s) ∈ [ [1, N] ], le coefficient situé à la ligne r et à la colonne s est égal à ω^((r − 1)(s − 1)).
On rappelle que ω a été défini dans les notations par ω = e^(2iπ/N).
Pour k ∈ [ [1, N] ], on note C_k la k-ième colonne de la matrice P_N.
Q 18. Calculer le produit matriciel G_N C_k. Démontrer que ω^k est une valeur propre de G_N et donner un vecteur propre associé.
Q 19. En déduire que la famille des vecteurs colonnes (C_1, C_2, …, C_N) est libre, puis que la matrice P_N est inversible.
Q 20. Calculer le produit matriciel P_N P_N^– et en déduire que P_N^(− 1) = 1/NP_N^–.
Q 21. Pour tout j ∈ [ [1, N] ], exprimer g(e_j) en fonction des vecteurs e_1, e_2, …, e_n. On distinguera le cas j = 1.
Q 22. Pour tout k ∈ [ [1, N − 1] ] et tout j ∈ [ [1, N] ], exprimer g^k(e_j) en fonction des vecteurs e_1, e_2, …, e_n. On distinguera les cas j > k et j ⩽ k.
Q 23. En déduire, pour tout k ∈ [ [0, N − 1] ], l'expression de G_N^k comme une matrice C(a_0, a_1, …, a_(N − 1)) particulière. (On rappelle que G_N^0 = I_N ).
Q 24. En exprimant C(a_0, a_1, …, a_(N − 1)) comme combinaison linéaire de G_N^0, G_N^1, …, G_N^(N − 1) et en utilisant les questions précédentes, justifier que C(a_0, a_1, …, a_(N − 1)) est diagonalisable dans M_N(ℂ). Donner sa réduite diagonale et une matrice de passage de la base canonique à une base de vecteurs propres.
Q 25. À l'aide du résultat précédent, calculer le déterminant de la matrice C(a_0, a_1, …, a_(N − 1)).

III Discrétisation et transformée de Fourier discrète

On appelle échantillon de taille N un N-uplet de ℝ^N.
Pour un signal continu variant dans le temps, l'échantillonnage consiste à prélever un nombre fini de valeurs de ce signal, à intervalles fixes, souvent réguliers.

III.A - Approximation des coefficients de Fourier

Soit f une fonction de C_(2π)^0.
Le N-uplet (f((2nπ)/N))_(0 ⩽ n ⩽ N − 1) est un échantillon de ce signal.
On pose a_0^′(N) = c_0^′(N) = 1/N∑_(n = 0)^(N − 1)f((2πn)/N) et, pour tout k ∈ ℕ^∗,
a_k^′(N), = 2/N∑_(n = 0)^(N − 1)f((2nπ)/N)cos(k(2nπ)/N); b_k^′(N), = 2/N∑_(n = 0)^(N − 1)f((2nπ)/N)sin(k(2nπ)/N); c_k^′(N), = 1/2(a_k^′(N) − ib_k^′(N)); c_(− k)^′(N), = 1/2(a_k^′(N) + ib_k^′(N))
Afin d'alléger les notations, on notera respectivement a_k, b_k et c_k les coefficients de Fourier a_k(f), b_k(f) et c_k(f).
Q 26. Justifier, en explicitant le théorème utilisé, que lim_(N → + ∞)a_0^′(N) = a_0, et que, pour tout k ∈ ℕ^∗, lim_(N → + ∞)a_k^′(N) = a_k et lim_(N → + ∞)b_k^′(N) = b_k.
Q27. En déduire que, pour tout entier relatif k, lim_(N → + ∞)c_k^′(N) = c_k.
De ce fait, pour de grandes valeurs de N, on prendra le nombre c_k^′(N) comme une approximation du coefficient de Fourier c_k.

III.B - Formule d'inversion

Si u = (u_n)_(0 ⩽ n ⩽ N − 1) est un échantillon de taille N, on définit u^ = (u^_k)_(0 ⩽ k ⩽ N − 1) par
∀k ∈ [ [0, N − 1] ], u^_k = ∑_(n = 0)^(N − 1)u_n e^(− ik2πn/N).
L'échantillon u^ s'appelle la transformée de Fourier d'ordre N de l'échantillon u.
Q 28. Combien d'opérations (additions et multiplications entre nombres complexes) sont nécessaires pour calculer les N termes de la transformée de Fourier u^, connaissant ceux de l'échantillon u et les nombres e^(− ik2πn/N) ? Parmi les multiplications, on ne comptabilise pas celles dont l'un des facteurs est égal à 1 .
Q 29. Démontrer que
∀k ∈ [ [0, N − 1] ], u_k = 1/N∑_(n = 0)^(N − 1)u^_n e^(ik2πn/N).
On pourra donner une écriture matricielle des N égalités (III.1) et utiliser la question 20.
Les N égalités (III.2), connues sous le nom de formule d'inversion de Fourier, permettent de reconstruire l'échantillon u à partir de sa transformée de Fourier u^.
Q 30. Montrer que, pour tout ℓ ∈ [ [1, N − 1] ], u^^–_ℓ = u^_(N − ℓ).
On suppose dans la question suivante que l'entier naturel N est pair.
Q 31. Combien suffit-il d'opérations (additions, multiplications entre nombres complexes et conjugaison d'un nombre complexe) pour calculer les N termes de la transformée de Fourier u^, connaissant ceux de l'échantillon u de taille N et les nombres e^(− ik2πn/N) ?
Q 32. Donner un équivalent de ce nombre d'opérations lorsque N tend vers + ∞.

IV Transformée de Fourier rapide

La transformée de Fourier rapide est un algorithme dont l'objectif est d'améliorer le temps de calcul des termes de la transformée de Fourier u^, connaissant ceux de l'échantillon u.
Dans cette partie, on suppose que u est un échantillon dont la taille N est une puissance de 2 ; on écrit donc N = 2^j, j ∈ ℕ^∗.
On rappelle que ω = e^(2iπ/N).
Pour tout entier r compris entre 0 et N/2 − 1, on pose y_r = u_(2r) et z_r = u_(2r + 1) ce qui définit deux échantillons y et z de taille N/2.
Q 33. Montrer que u^_(N/2) = y^_0 − z^_0.
Q 34. Montrer que,
∀k ∈ [ [0, N/2 − 1] ], {u^_k = y^_k + ω¯^k z^_k; u^_(k + N/2) = y^_k − ω¯^k z^_k
On note T(N) le nombre d'opérations (additions, multiplications entre nombres complexes) nécessaires pour calculer selon cette méthode les N termes de la transformée de Fourier d'ordre N d'un échantillon u de taille N connaissant les termes de cet échantillon et les ω¯^k.
Q 35. Justifier que T(2) = 3 et démontrer que, pour tout entier j supérieur ou égal à 2 ,
∀r ∈ [ [2, j] ], T(2^r) ⩽ 2T(2^(r − 1)) + 4 × 2^(r − 1).
Q 36. Démontrer que
T(N) ⩽ 2/(ln2)NlnN.
On pourra utiliser la suite auxiliaire (t_k)_(1 ⩽ k ⩽ j), définie par t_k = (T(2^k))/(2^k).
Q 37. Expliquer pourquoi cette méthode est qualifiée de transformée de Fourier «rapide».

V Convolution circulaire

Étant donné un échantillon (u_n)_(0 ⩽ n ⩽ N − 1) ∈ ℝ^n, on appelle suite périodisée, indexée par ℤ, de germe (u_n)_(0 ⩽ n ⩽ N − 1), la suite (u_n)_(n ∈ ℤ) vérifiant, pour tout entier relatif n, u_(n + N) = u_n.
On admet que la donnée d'un germe (u_n)_(0 ⩽ n ⩽ N − 1) permet de définir une unique suite périodisée (u_n)_(n ∈ ℤ).
À titre d'exemple, à partir du germe ( 2, 4, 7, 9 ), on définit, dans ℤ, la suite de période 4(…, 4, 7, 9, 2, 4, 7, 9, 2, 4, 7, 9, 2, …).
Les définitions de somme, produit par un nombre réel et produit de suites définies sur ℕ se prolongent naturellement aux suites définies sur ℤ.
Q 38. Étant donnée une suite (u_n)_(n ∈ ℤ) périodique de période N, démontrer que, pour tout entier relatif p ∈ [ [ − N + 1, 0] ],
∑_(k = p)^(p + N − 1)u_k = ∑_(k = 0)^(N − 1)u_k
À deux suites périodiques de même période N, on associe la suite u∗v, appelée convolée circulaire des suites u et v, définie par ∀n ∈ ℤ, (u∗v)_n = ∑_(k = 0)^(N − 1)u_k v_(n − k).
Q 39. Montrer que la convolée circulaire de deux suites périodiques de période N est une suite périodique de période N.
Q 40. On considère les suites r et s périodiques de période 3 , dont les germes sont r = (1, 2, 3) et s = (6, 5, 4). Donner le germe de r∗s.
Q 41. Combien d'opérations (additions et multiplications) sont à priori nécessaires pour calculer les N termes (u∗v)_0, (u∗v)_1, …, (u∗v)_(N − 1) à partir de la donnée de u_0, …, u_(N − 1) et v_0, …, v_(N − 1) ?
On définit la transformée de Fourier discrète d'une suite u périodique de période N comme la suite périodisée de période N dont le germe est la transformée de Fourier discrète ( u^_0, …, u^_(N − 1) ) du germe ( u_0, …, u_(N − 1) ) de la suite u.
Q 42. Pour deux suites u et v périodiques de période N, montrer que u∗vˆ = u^v^.
Q 43. En utilisant à la fois la transformée de Fourier rapide, le résultat de la question 42 et la formule d'inversion, donner, lorsque N = 2^j, un majorant (dépendant de N ) du nombre d'opérations (additions, multiplications entre nombres complexes, divisions d'un nombre complexe par un entier naturel) utilisées pour calculer efficacement le germe de la convolée circulaire de deux suites périodiques de période N.

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet de mathématiques 2 Centrale TSI 2022 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet de mathématiques 2 Centrale TSI 2022 ?

Il porte sur les séries de Fourier, les nombres complexes, la diagonalisation des matrices et la transformée de Fourier discrète.

Le sujet Centrale maths 2 TSI 2022 est-il difficile ?

Le jury le décrit comme de longueur raisonnable, accessible aux candidats ayant une bonne connaissance du cours des deux années.

Quelles erreurs reviennent le plus dans ce sujet Centrale-Supélec maths 2 TSI 2022 ?

Le jury relève des confusions entre inverse et conjugué, des hypothèses de théorèmes non vérifiées et des réponses de calcul de complexité sans justification.

Ce sujet Centrale TSI 2022 est-il utile pour réviser les séries de Fourier et l'algèbre linéaire ?

Oui, il combine calcul des coefficients de Fourier, diagonalisation de matrices circulantes et une application algorithmique concrète, la transformée de Fourier rapide.

Pas de description pour le moment