X ENS Mathématiques PC 2013Sujet, corrigé et rapport du jury

Q: Sur quels chapitres porte la composition de mathématiques X-ENS-ESPCI PC 2013 ?

Elle porte sur les matrices de rotation, la réduction des matrices symétriques, le polynôme caractéristique et les algorithmes numériques de diagonalisation, à travers l'étude de l'algorithme de Jacobi.

Q: Quelles erreurs le jury a-t-il le plus relevées à l'X-ENS mathématiques PC 2013 ?

Une confusion entre matrices semblables et matrices équivalentes, l'oubli des relations coefficients-racines, une exploitation trigonométrique manquée, et une continuité du polynôme caractéristique non justifiée.

Q: La composition de mathématiques X-ENS-ESPCI PC 2013 est-elle difficile ?

Oui, la moyenne s'établit à 8,04 sur 20 avec un écart-type de 3,46, et le rapport signale que les résultats ont été très moyens, plusieurs questions n'ayant été traitées que par une infime minorité de candidats.

Pas encore noté

Explorer les annales

BanqueX-ENS Année2013 FilièrePC MatièreMathématiques

Annales X-ENS PC Mathématiques X-ENS PC 2013 PC Mathématiques Mathématiques 2013

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Difficile

Composition de mathématiques X-ENS-ESPCI PC : l'algorithme de Jacobi pour la diagonalisation des matrices symétriques

Le sujet étudie l'algorithme de Jacobi, une méthode itérative de diagonalisation d'une matrice symétrique par conjugaisons successives par des matrices de rotation. Après un préliminaire sur les matrices de rotation, il étudie l'effet d'une conjugaison, la convergence d'une version incomplète puis optimale de l'algorithme, en lien avec le polynôme caractéristique.

1Partie I : préliminairePropriétés des matrices de rotation, notion de matrices semblables et inégalité triangulaire.
2Partie II : conjugaison par matrice de rotationEffet d'une conjugaison par une matrice de rotation sur les coefficients d'une matrice symétrique, expressions en fonction de tangente, cosinus et sinus.
3Partie III : algorithme de Jacobi incompletÉtude de la convergence d'une version incomplète de l'algorithme par des critères de suites télescopiques.
4Partie IV : convergence et polynôme caractéristiqueContinuité des coefficients du polynôme caractéristique et multiplicité des valeurs propres.
5Partie V : algorithme de Jacobi, version optimaleChoix optimal du couple d'indices à chaque étape et vitesse de convergence de l'algorithme.

Difficile. La moyenne s'établit à 8,04 sur 20 avec un écart-type de 3,46 sur 1389 copies, et le rapport indique que les résultats ont été très moyens, certaines questions n'ayant été traitées que par moins de 1% des candidats.

L'épreuve en chiffres

Moyenne 8,04 / 20 · écart-type 3,46 · 1 389 copies · où vous situez-vous ?

Moyenne: 8,04/ 20
Écart-type: 3,46
Copies: 1 389

Deux tiers des copies environ (moyenne ± écart-type)

Où je me situe ?

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

Source : rapport du jury. 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

Matrices semblables confondues avec matrices équivalentes · Relations coefficients-racines non utilisées · Expression trigonométrique non exploitée

Le sujet ne demandait pas forcément de connaissances très élaborées mais était parfois technique et calculatoire, avec des calculs longs importants à ne pas manquer. Le jury insiste sur la nécessité de vérifier ses calculs plutôt que de les tenir pour acquis, et déplore une explosion du nombre de copies mal écrites ou illisibles.

Les erreurs les plus sanctionnées

1
Matrices semblables confondues avec matrices équivalentesquestion 3
La notion de matrices semblables est souvent confondue avec celle de matrices équivalentes.
2
Relations coefficients-racines non utiliséesquestion 8b
Plus de la moitié des candidats n'ont pas le réflexe d'utiliser les relations coefficients-racines et s'embarquent dans des calculs compliqués alors qu'il suffisait de dire que le produit des racines valait -1.
3
Expression trigonométrique non exploitéequestion 9
La plupart des candidats ayant traité la question 9 ont simplement exprimé les coefficients sans se soucier des coefficients trigonométriques, alors qu'il fallait exprimer cosinus et sinus en fonction de la tangente.
4
Continuité du polynôme caractéristique non justifiéequestion 17
Il est important de bien justifier la continuité des coefficients du polynôme caractéristique par rapport aux coefficients du polynôme, ce qui a le plus manqué pour une question qui pouvait rapporter beaucoup.
5
Résultat non vérifié après un calcul long
Lorsqu'on aboutit après un calcul long et fastidieux à un résultat, il n'y a aucune raison de croire qu'il soit exact et d'enchaîner sans le vérifier, même en cas de contradiction avec des résultats suivants.

Ce qui a été bien réussi

La plupart des candidats ont bien reconnu une rotation à la première question du préliminaire.
La question 6 a été correctement traitée par la plupart des candidats.
La question 8a a été bien traitée lorsque la question précédente l'avait été avec précision.

Conseils du jury

Vérifier systématiquement les résultats obtenus après un calcul long, par exemple par une vérification numérique sur un exemple.
Privilégier deux ou trois questions plus difficiles et bien traitées plutôt que de survoler toutes les questions faciles.
Quantifier précisément les affirmations, en particulier lors des passages cruciaux des démonstrations.

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.

Sujet en PDF

COMPOSITION DE MATHÉMATIQUES (XEULC)

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

Dans ce problème,

n ⩾ 2

est un entier et

M_n

désigne l'espace vectoriel des matrices de taille

n \times n

à coefficients réels. La transposée d'une matrice

A \in M_n

est notée

^t A

. Le sous-espace vectoriel des matrices symétriques est noté

S_n

. Enfin, le groupe orthogonal est noté

O_n

. On utilisera la notation de Kronecker

δ_i^j = {1, si, i = j; 0, si, i ≠ j

On munit l'espace

M_n

de la norme euclidienne

‖A‖ = \sqrt(\sum_(1 ⩽ i, j ⩽ n)(a_(ij))^2)

où les

a_(ij)

sont les coefficients de

A

. On pourra utiliser la formule

‖A‖^2 = Tr(^t AA)

.
Si

θ \in ℝ

et si

p < q

sont des entiers entre 1 et

n

, on désigne par

R_(p, q)(θ)

la matrice

n \times n

dont les coefficients

r_(ij)

sont donnés, pour

1 ⩽ i, j ⩽ n

, par

r_(ij) = {δ_i^j, si, j ≠ p, q; δ_i^j, si, i ≠ p, q; cosθ, si, i = j = p ou q; sinθ, si, i = q et j = p; − sinθ, si, i = p et j = q

Par exemple,

R_(1, 2)(θ) = (cosθ, - sinθ, 0, \dots, \dots, 0; sinθ, cosθ, 0, \dots, \dots, 0; 0, 0, 1, ⋱, ⋮; ⋮, ⋮, ⋱, ⋱, ⋱, ⋮; ⋮, ⋮, ⋱, ⋱, 0; 0, 0, \dots, \dots, 0, 1) = (cosθ, - sinθ; sinθ, cosθ, O_(2 \times (n - 2)); O_((n - 2) \times 2), I_(n - 2))

Soit

(A^((m)))_(m \in ℕ)

une suite quelconque de matrices dans

M_n

. On dit que

A^((m))

converge vers

A

A \in M_n

lim_(m \to + \infty)‖A^((m)) - A‖ = 0

Il revient au même de dire que pour tout

1 ⩽ i, j ⩽ n

, la suite des coefficients

a_(ij)^((m))

A^((m))

converge vers

a_(ij)

, le coefficient de

A

correspondant.

1 Préliminaires

On suppose dans cette question que $n = 3$ . Quelle interprétation géométrique peut-on donner de $R_(p, q)(θ)$ ?
Calculer le produit $^t(R_(p, q)(θ))R_(p, q)(θ)$ . Quelle propriété de $R_(p, q)(θ)$ reconnaît-on ?
On se donne $S \in S_n$ et $R \in O_n$ . Vérifier que $^t RSR$ est symétrique et qu'elle est semblable à $S$ .
Soit $A \in M_n$ et $U, V \in O_n$ . Montrer que $‖UAV‖ = ‖A‖$ .
On se donne quatre nombres réels $a ⩽ b ⩽ c ⩽ d$ tels que $a + d = b + c$ . Étudier les variations de la fonction $x \mapsto |x - a| - |x - b| - |x - c| + |x - d|$ ; montrer qu'elle est à valeurs positives. Un raisonnement étayé par une représentation graphique sera le bienvenu.

2 Conjugaison par une matrice de rotation

On se donne une matrice

S \in S_n

, un angle

θ \in ] - π/2, π/2[

et des entiers

1 ⩽ p < q ⩽ n

tels que

s_(pq) \neq 0

. On définit

S^' = ^t R_(p, q)(θ)SR_(p, q)(θ)

et on note

s_(ij)^'

ses coefficients.
6. Montrer que

s_(qq)^' + s_(pp)^' = s_(qq) + s_(pp)

.
7. Exprimer les coefficients

s_(ij)^'

S^'

en fonction de ceux de

S

.
8. On cherche un angle

θ \in ] - π/2, π/2[

pour lequel on ait

s_(pq)^' = 0

.
(a) Montrer que

s_(pq)^' = 0

si et seulement si

t = tanθ

satisfait l'équation

t^2 + (s_(pp) - s_(qq))/(s_(pq))t - 1 = 0

(b) Montrer que cette équation admet une solution

t_0 \in ] - 1, 1]

et une autre

t_1 \notin ] - 1, 1]

. Quelle est la relation entre les angles

θ_0

θ_1

qui correspondent à ces racines ?
(c) Dans toute la suite, on choisit l'une des deux racines

t

de l'équation (1). On a donc

s_(pq)^' = 0

. Un choix plus précis sera fait à partir de la question 12.
Vérifier que

s_(pp)^' - s_(pp) = ts_(pq)

; établir une formule analogue pour

s_(qq)^' - s_(qq)

.
(d) On décompose

S

sous la forme

S = D + E

avec

D

diagonale et

E

à diagonale nulle. On décompose de même

S^' = D^' + E^'

. Calculer

‖E^'‖^2

en fonction de

‖E‖^2

et de

(s_(pq))^2

.
(e) En justifiant que

‖S^'‖ = ‖S‖

, en déduire une expression de

‖D^'‖^2

au moyen de

‖D‖^2

et de

(s_(pq))^2

.
9. Montrer que les coefficients de

S^'

s'expriment uniquement en fonction de ceux de

S

et de la racine (

t_0

t_1

) qu'on a choisie.
10. On suppose dans cette question que

s_(pq)

est le coefficient de plus grande valeur absolue de

E

.
(a) Montrer que

‖E^'‖ ⩽ ρ‖E‖

où

ρ < 1

est une constante que l'on explicitera.
(b) Si on choisit la racine

t_0

, montrer en outre que

‖D^' - D‖ ⩽ ‖E‖

.
11. En calculant

(s_(qq)^' - s_(pp)^')^2 - (s_(qq) - s_(pp))^2

, montrer que

|s_(qq)^' - s_(pp)^'| ⩾ |s_(qq) - s_(pp)|

Dorénavant, et jusqu'à la fin du problème, on choisit la racine $t_0$ de (1) et donc l'angle $θ_0$ , mentionnés à la Question 8b.
(a) Montrer que $s_(pp) - s_(pp)^'$ et $s_(qq)^' - s_(qq)$ sont du même signe que $s_(qq) - s_(pp)$ .
(b) Si $1 ⩽ i ⩽ n$ , montrer que

|s_(ii) - s_(qq)^'| + |s_(ii) - s_(pp)^'| - |s_(ii) - s_(pp)| - |s_(ii) - s_(qq)| ⩾ 0

On définit

R = \sum_(i, j = 1)^n|s_(jj) - s_(ii)| et R^' = \sum_(i, j = 1)^n|s_(jj)^' - s_(ii)^'|

Montrer que

R^' - R ⩾ 2(|s_(qq)^' - s_(qq)| + |s_(pp)^' - s_(pp)|) = 2\sum_(i = 1)^n|s_(ii)^' - s_(ii)|.

3 Algorithme de Jacobi incomplet

Dans l'algorithme de Jacobi, on part d'une matrice

Σ \in S_n

et on construit une suite de matrices symétriques

Σ^((m))

, dont les coefficients sont notés

σ_(ij)^((m))

, de la façon suivante :

On pose $Σ^((0)) = Σ$ .
Lorsque $Σ^((m))$ est connue, on choisit un couple $(p_m, q_m)$ avec $p_m < q_m$ .
On applique alors les calculs de la Partie 2 à la matrice $S = Σ^((m))$ et au couple $(p, q) = (p_m, q_m)$ : on forme la matrice $S^'$ étudiée dans cette partie, et on l'appelle $Σ^((m + 1))$ .

À ce stade, on ne précise pas la manière de choisir

(p_m, q_m)

; c'est pourquoi l'algorithme est dit incomplet.
14. On définit

R_m = \sum_(i, j = 1)^n|σ_(jj)^((m)) - σ_(ii)^((m))|, ε_m = \sum_(i = 1)^n|σ_(ii)^((m + 1)) - σ_(ii)^((m))|

Vérifier que

R_(m + 1) - R_m ⩾ 2ε_m

. En déduire que la série

\sum_(m = 1)^\inftyε_m

est convergente.
15. On décompose

Σ^((m))

sous la forme

D^((m)) + E^((m))

où

D^((m))

est diagonale et

E^((m))

est à diagonale nulle. Montrer que la suite

(D^((m)))_(m \in ℕ)

est convergente. On notera

D

sa limite.

4 Convergence et polynôme caractéristique

Soit

(A^((m)))_(m \in ℕ)

une suite dans

M_n

. On suppose que pour tout

m \in ℕ

, la matrice

A^((m + 1))

est semblable à

A^((m))

.
16. Montrer que

A^((m))

est semblable à

A^((0))

.
17. On suppose de plus que cette suite converge vers une matrice diagonale

D

. Si

P_m

désigne le polynôme caractéristique de

A^((m))

, montrer que les coefficients de

P_m

convergent vers ceux du polynôme caractéristique de

D

quand

m \to + \infty

.
En déduire que le polynôme caractéristique de

D

est égal à celui de

A^((0))

.
18. Finalement, montrer que les termes diagonaux de

D

sont les valeurs propres de

A^((0))

. Que peut-on dire de leurs multiplicités ?

5 Algorithme de Jacobi ; version optimale

Dans la version optimale de l'algorithme de Jacobi, on choisit pour chaque

m

un couple (

p_m, q_m

) de sorte que la valeur absolue du coefficient

σ_(ij)^((m))

soit maximale précisément quand

(i, j) = (p_m, q_m)

. Autrement dit,

\foralli < j, |σ_(ij)^((m))| ⩽ |σ_(p_m q_m)^((m))|.

Montrer que pour $m \to + \infty$ , la suite $(Σ^((m)))_(m \in ℕ)$ converge vers la matrice diagonale $D$ .
Montrer alors que les coefficients diagonaux de $D$ sont les valeurs propres de $Σ$ .
Soit $m \in ℕ$ . Montrer que

‖D - D^((m))‖ ⩽ (ρ^m)/(1 - ρ)‖E^((0))‖

En vous appuyant sur les réponses aux questions précédentes, donnez votre avis quant à la rapidité de la convergence des $d_(ii)^((m))$ vers les valeurs propres de $Σ$ .

Les propriétés de la méthode de Jacobi sont aujourd'hui encore mal comprises. Dans sa version optimale, et sous l'hypothèse que les valeurs propres de

Σ

sont simples, elle converge au moins quadratiquement, et probablement encore plus vite. L'estimation de la question 21 est donc grossière. Elle est d'ailleurs satisfaite "en moyenne" lorsqu'on choisit (

p_m, q_m

) au hasard, ce qui entraine la convergence "presque surement".

Questions fréquentes

3 questions

Sur quels chapitres porte la composition de mathématiques X-ENS-ESPCI PC 2013 ?

Elle porte sur les matrices de rotation, la réduction des matrices symétriques, le polynôme caractéristique et les algorithmes numériques de diagonalisation, à travers l'étude de l'algorithme de Jacobi.

Quelles erreurs le jury a-t-il le plus relevées à l'X-ENS mathématiques PC 2013 ?

Une confusion entre matrices semblables et matrices équivalentes, l'oubli des relations coefficients-racines, une exploitation trigonométrique manquée, et une continuité du polynôme caractéristique non justifiée.

La composition de mathématiques X-ENS-ESPCI PC 2013 est-elle difficile ?

Oui, la moyenne s'établit à 8,04 sur 20 avec un écart-type de 3,46, et le rapport signale que les résultats ont été très moyens, plusieurs questions n'ayant été traitées que par une infime minorité de candidats.

Pas de description pour le moment

Commentaires• X ENS Mathématiques PC 2013

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...