Modèle de concours : CNC 2011 Mathématiques II (MP) — Concours National Commun

Ce sujet est l'épreuve de Mathématiques II de la filière MP du Concours National Commun (CNC) 2011 d'admission aux grandes écoles d'ingénieurs marocaines. Il compte 4 pages et la calculatrice est interdite (la page de garde, avec la durée, ne figure pas dans le scan). Il est formé de deux problèmes indépendants. Le premier porte sur la transformation de Fourier discrète et son algorithme rapide (FFT), comparé à Horner. Le second établit le théorème de Courant-Fischer et étudie la continuité et la dérivabilité des valeurs propres d'une application matricielle. Voici une correction méthodologique proposée.

💡 Avant de commencer : les deux problèmes sont indépendants. Commencez par celui que vous maîtrisez le mieux. Dans le premier, tout repose sur deux faits : Σ_k w_p^mk vaut p ou 0, et P_a(X) = P_b(X²) + X P_c(X²). Dans le second, retenez que le quotient de Rayleigh R_A est « linéaire en A » et que la formule min-max permet de comparer les valeurs propres de deux matrices. L'énoncé contient deux coquilles : en I.3(b), lire R_A(w) ; en II.2(a), lire A(t) − A(t₀). Signalez-les sur la copie.

Premier problème — Transformation de Fourier discrète

Notation : w = w_p = e^2iπ/p, y_k = P_x(w^k).

I.1. (a) et (b)

• (a) Φ_p(x) = 0 ⇔ P_x(w^k) = 0 pour k = 0, …, p−1. Les w^k sont p racines p-ièmes de l'unité distinctes, et deg P_x ≤ p − 1. Un polynôme de degré ≤ p − 1 ayant p racines est nul : Φ_p(x) = 0 ⇔ P_x = 0 (la réciproque est immédiate).
• (b) Φ_p est linéaire (x ↦ P_x et l'évaluation le sont). Son noyau vaut {x ; P_x = 0} = {0}. Un endomorphisme injectif en dimension finie est bijectif : Φ_p est un automorphisme.

I.2. Matrice de Φ_p

• (a) Φ_p(e_j) = (w^kj)_{0≤k≤p−1}, donc m_i,j = w_p^ij.
• (b) M est la matrice de Vandermonde de (1, w, …, w^p−1). Son déterminant vaut Π_i<j(w^j − wⁱ) ≠ 0 car les wⁱ sont distincts : M est inversible, donc Φ_p est un automorphisme.

I.3. Sommes et égalité de Parseval

• (a) S = Σ_k=0^p−1 w^(i−j)k. Si i = j (plus généralement si p divise i − j) : S = p. Sinon w^i−j ≠ 1 et la somme géométrique vaut (w^(i−j)p − 1)/(w^i−j − 1) = 0, car w^p = 1.
• (b) Σ_k|y_k|² = Σ_k Σ_i,j x_i x̄_j w^(i−j)k = Σ_i,j x_i x̄_j S_i,j = p Σ_i|x_i|². D'où Σ|y_k|² = p Σ|x_k|².

I.4. Inverse de M

• (a) (M̄M)_i,j = Σ_k w^−ik w^kj = Σ_k w^(j−i)k = p δ_i,j, donc M̄M = pI_p.
• (b) M⁻¹ = (1/p) M̄, c'est-à-dire (M⁻¹)_i,j = w_p^−ij/p. Φ_p⁻¹ est donc, au facteur 1/p près, la même transformation avec w̄_p.

Premier problème — 2^ème partie : algorithmique (p = 2ⁿ)

II.1. L'étape « papillon »

• (a) À l'entrée de l'étape k, E = w_p^k (initialisé à 1 et multiplié par w_p à chaque tour). Donc F_k = w_p^kγ_k, α_k = β_k + w_p^kγ_k, α_k+p/2 = β_k − w_p^kγ_k.
• (b) En séparant les indices pairs et impairs : P_a(X) = P_b(X²) + X P_c(X²). On utilise w_p² = w_p/2 et w_p^p/2 = e^iπ = −1. Pour 0 ≤ k ≤ p/2 − 1 :
  P_a(w_p^k) = P_b(w_p/2^k) + w_p^kP_c(w_p/2^k) = β_k + w_p^kγ_k = α_k ;
  w_p^k+p/2 = −w_p^k et (w_p^k+p/2)² = w_p/2^k, donc P_a(w_p^k+p/2) = β_k − w_p^kγ_k = α_k+p/2.
  D'où Φ_p(a) = (α₀, …, α_p−1).

II.2. Coût de l'algorithme récursif

• (a) Pour n = 1 : a₀ + a₁ et a₀ − a₁ (une soustraction compte comme une addition), donc s₁ = 2, r₁ = 0. Au rang n, il y a deux transformées de taille 2ⁿ⁻¹, puis la boucle de 2ⁿ⁻¹ tours. Chaque tour compte 2 additions et 2 multiplications (E*γ_k et w_p*E). D'où s_n = 2s_n−1 + 2ⁿ et r_n = 2r_n−1 + 2ⁿ.
• (b) En divisant par 2ⁿ : s_n/2ⁿ = s_n−1/2ⁿ⁻¹ + 1, donc s_n = n·2ⁿ. De même r_n = (n−1)·2ⁿ. Total : s_n + r_n = (2n − 1)2ⁿ = p(2 log₂p − 1).
  Variante : si l'on considère les puissances w_p^k comme connues (on ne compte pas la mise à jour de E), r_n = 2r_n−1 + 2ⁿ⁻¹, donc r_n = (n−1)2ⁿ⁻¹. Le total vaut alors (3n−1)2ⁿ⁻¹ = p(3 log₂p − 1)/2. Dans les deux cas, O(p log₂ p). Précisez sur la copie la convention choisie.

II.3. Horner

• (a) P_a(λ) = (…((a_p−1λ + a_p−2)λ + a_p−3)… + a₁)λ + a₀ : p − 1 multiplications et p − 1 additions, soit 2(p − 1) opérations.
• (b) Pour les p points w_p^k : 2p(p − 1) opérations, auxquelles s'ajoutent au plus p − 2 multiplications pour les puissances w_p^k, si on ne les suppose pas connues.

II.4. Comparaison

Algorithme récursif (FFT) : O(p log₂ p). Horner : O(p²). Pour p assez grand, l'algorithme récursif est le plus rapide. Exemple : pour p = 2¹⁰ = 1024, environ 2·10·1024 ≈ 2·10⁴ opérations contre 2·1024·1023 ≈ 2·10⁶, soit un rapport de l'ordre de 100.

Deuxième problème — 1^ère partie : théorème de Courant-Fischer

1. Base orthonormée de vecteurs propres

A est symétrique réelle, donc f_A est autoadjoint pour le produit scalaire canonique : (Au|v) = ^tu^tAv = (u|Av). Par le théorème spectral, il existe une base orthonormée de vecteurs propres de f_A.

2. Quotient de Rayleigh sur V_k

• (a) R_A(e_k) = λ_k, car (λ_ke_k|e_k)/(e_k|e_k) = λ_k.
• (b) Pour v = Σ_i≤k x_ie_i ≠ 0 : (Av|v) = Σ_i≤k λ_ix_i² ≤ λ_k Σ x_i² = λ_k(v|v), donc R_A(v) ≤ λ_k. L'égalité a lieu en e_k ∈ V_k, donc λ_k = max_u∈Vk\{0} R_A(u).

3. Minoration sur tout F de dimension k

• (a) Soit W_k = Vect(e_k, …, e_n), de dimension n − k + 1. Par la formule de Grassmann, dim(F ∩ W_k) = dim F + dim W_k − dim(F + W_k) ≥ k + (n−k+1) − n = 1.
• (b) Pour w = Σ_i≥k x_ie_i ≠ 0 : (Aw|w) = Σ_i≥k λ_ix_i² ≥ λ_k(w|w), donc R_A(w) ≥ λ_k (l'énoncé écrit R_A(v) : coquille).

4. Formule min-max

R_A(tv) = R_A(v) pour t ≠ 0, donc sup_F\{0} R_A = sup sur la sphère unité de F. C'est un compact et R_A y est continue, donc ce sup est un max. Pour tout F ∈ ℱ_k, par 3(b), max_F\{0} R_A ≥ λ_k. Pour F = V_k, ce max vaut λ_k (2(b)). Donc λ_k = min_F∈ℱk max_v∈F\{0} R_A(v).

Deuxième problème — 2^ème partie : continuité et dérivabilité des valeurs propres

1.

Par Cauchy-Schwarz, |(Cv|v)| ≤ ||Cv||₂||v||₂ ≤ |||C|||₂||v||₂². En divisant par (v|v) = ||v||₂² : |(Cv|v)/(v|v)| ≤ |||C|||₂.

2. Continuité des λ_k

• (a) R_M(v) est linéaire en M, donc R_A(t)(v) = R_A(t0)(v) + R_A(t)−A(t0)(v). Pour v ∈ V_k(t₀)\{0}, R_A(t0)(v) ≤ λ_k(t₀) (I.2(b)). Par Courant-Fischer appliqué à A(t) avec F = V_k(t₀) ∈ ℱ_k :
  λ_k(t) ≤ max_{v∈Vk(t0)\{0}} R_A(t)(v) ≤ λ_k(t₀) + sup{R_A(t)−A(t0)(v) ; v ∈ V_k(t₀)\{0}}.
• (b) Par II.1, ce sup est ≤ |||A(t) − A(t₀)|||₂. Donc λ_k(t) − λ_k(t₀) ≤ |||A(t) − A(t₀)|||₂, puis, en échangeant t et t₀ : |λ_k(t) − λ_k(t₀)| ≤ |||A(t) − A(t₀)|||₂. Ce majorant tend vers 0 quand t → t₀ (A est continue, et toutes les normes sont équivalentes en dimension finie) : λ_k est continue.

3. Un contre-exemple pour les vecteurs propres

• (a) Sur ℝ*, a et b sont C^∞. En 0 : |a(t)/t| ≤ e^−1/t2/|t| → 0, donc a'(0) = 0. Pour t ≠ 0 :
  a'(t) = e^−1/t2[(2/t³)cos(1/t) + (1/t²)sin(1/t)], d'où |a'(t)| ≤ (2/|t|³ + 1/t²)e^−1/t2 → 0, par croissances comparées (u^me^−u2 → 0).
  Donc a est C¹, de même b, et A est de classe C¹.
• (b) t = 0 : A(0) = 0, seule valeur propre 0, tout vecteur non nul est propre. Pour t ≠ 0, on pose r = e^−1/t2 et θ = 1/t. Alors A(t) = r(cos θ, sin θ ; sin θ, −cos θ), c'est-à-dire r fois une symétrie orthogonale. Son polynôme caractéristique est X² − r² : valeurs propres ±e^−1/t2.
  Sous-espaces propres : E_r = ℝ(cos(1/(2t)), sin(1/(2t))) et E_−r = ℝ(−sin(1/(2t)), cos(1/(2t))) (vérification directe par les formules d'addition).
• (c) Supposons e continue avec e(t) propre (donc non nul) pour tout t. Sur ]0, +∞[, la fonction t ↦ R_A(t)(e(t))/r(t) est continue et ne prend que les valeurs ±1. Elle est donc constante sur cet intervalle (connexe) : disons que e(t) ∈ E_r(t) pour tout t > 0 (l'autre cas est identique).
  Avec u(t) = (cos(1/(2t)), sin(1/(2t))), on a e(t) = ρ(t)u(t), où ρ(t) = (e(t)|u(t)) est continue et ne s'annule pas, donc de signe constant ε. Alors u(t) = ε e(t)/||e(t)|| → ε e(0)/||e(0)|| quand t → 0⁺.
  Or u(t) n'a pas de limite : pour t = 1/(4mπ), u = (1, 0) ; pour t = 1/((4m+2)π), u = (−1, 0). Contradiction : aucune telle application e n'existe.

4. Valeurs propres C¹ en dimension 2

Posons M(t) = (α, β ; β, δ), avec α, β, δ de classe C¹. Alors χ = X² − (α+δ)X + (αδ − β²), de discriminant Δ = (α − δ)² + 4β² = f² + g² avec f = α − δ et g = 2β de classe C¹. Par le résultat admis, il existe h de classe C¹ avec h² = Δ. Posons λ₁ = (α + δ − h)/2, λ₂ = (α + δ + h)/2, de classe C¹. On a λ₁ + λ₂ = α + δ et λ₁λ₂ = ((α+δ)² − h²)/4 = αδ − β², donc χ_M(t) = (X − λ₁(t))(X − λ₂(t)) pour tout t ∈ I (l'énoncé écrit « t ∈ ℝ », lire t ∈ I).

5. Contre-exemple sans symétrie

• (a) B(0) = 0 est diagonale. Pour t ≠ 0, χ = X² − t b(t) = X² − t⁴(2 + sin(1/t))², avec t⁴(2 + sin(1/t))² > 0 car 2 + sin ≥ 1. On obtient deux valeurs propres réelles distinctes ±φ(t), où φ(t) = t²(2 + sin(1/t)). Donc B(t) est diagonalisable pour tout t.
• (b) b est C^∞ sur ℝ*. En 0, b(t)/t = t²(2 + sin(1/t))² → 0, donc b'(0) = 0. Pour t ≠ 0, b'(t) = 3t²(2 + sin(1/t))² − 2t(2 + sin(1/t))cos(1/t) → 0. Donc b est C¹ et B est de classe C¹.
  Supposons λ₁, λ₂ de classe C¹ avec χ_B(t) = (X − λ₁)(X − λ₂). Sur ]0, +∞[, λ₁(t) ∈ {±φ(t)} et λ₁ − λ₂ est continue et ne s'annule pas. Donc λ₁ = εφ avec ε = ±1 fixe. Alors λ₁'(t) = ε(2t(2 + sin(1/t)) − cos(1/t)) pour t > 0, qui n'a pas de limite en 0⁺ (à cause de cos(1/t)). λ₁' n'est donc pas continue en 0 : contradiction.
  Le résultat de la question 4 tombe parce que B(t) n'est pas symétrique : le discriminant 4t b(t) n'est plus de la forme (α − δ)² + 4β², et ses racines carrées ±2φ ne sont pas de classe C¹.

💡 À réviser pour le CNC MP (Maths II) : racines de l'unité et sommes géométriques ; polynômes (nombre de racines, Vandermonde) ; matrice de Fourier et son inverse ; principe « diviser pour régner » et récurrences du type u_n = 2u_n−1 + 2ⁿ (diviser par 2ⁿ) ; complexité O(p log p) contre O(p²). Côté algèbre bilinéaire : théorème spectral, quotient de Rayleigh, formule de Grassmann, norme subordonnée et Cauchy-Schwarz. Côté analyse : dérivabilité en un point par le taux d'accroissement, fonctions du type e^−1/t2, argument de connexité (fonction continue à valeurs dans {−1, 1}). Pensez à signaler explicitement les coquilles de l'énoncé.