X Maths PC 2013

ECOLE POLYTECHNIQUE -- ECOLES NORMALES SUPERIEURES
ECOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2013 FILIÈRE PC

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, 71 > 2 est un entier et Mn désigne l'espace vectoriel des 
matrices de taille
71 >< n a coefficients réels. La transposée d'une matrice A E Mn est notée 'A. 
Le sous--espace
vectoriel des matrices symétriques est noté Sn. Enfin, le groupe orthogonal est 
noté On. On
utilisera la notation de Kronecker
52-- = { 1 si 2' = j,

0 & i#j
On munit l'espace Mn de la norme euclidienne

UAH = 2 (%")2

1< 71
dont les coefficients 7°Z-j sont donnés, pour 1 < @, j { n, par

"% â j#R%
5".-' si i#p,q,
7°Z-j=< cos9 si i=j=pouq,

sin9 si i=qetj=p,
K--sin9 si i=petj=q.

Par exemple,

{cos9 --sin9 0 0\
sin9 cos9 () 0 cos9 --sin9
- - . O _
0 0 1 " ï s1n9 cos9 2X(n 2)
RI,2(9)-- . . _ _ . =
- _ . - _ . 0 O(n--2)X2 In--2
\ 0 0 0 1}

Soit (A -- AH = @.

m-->+oo

Il revient au même de dire que pour tout 1 { i, j { n, la suite des 
coefficients al'-"" de A lat--al -- là:--bl -- lat--cl + là:--dl ; 
montrer qu'elle est a valeurs
positives. Un raisonnement e'taye' par une représentation graphique sera le 
bienvenu.

2 Conjugaison par une matrice de rotation

7T 71"

On se donne une matrice S E S... un angle @ E l---- --{ et des entiers 1 < p < 
(] { n tels que

272

qu # 0. On définit S' : tRp,q(9)SRp,q(9) et on note % ses coefficients.

/ l _
6. Montrer que sqq + % -- sqq + spp.

7. Exprimer les coefficients % de S' en fonction de ceux de S.

8. On cherche un angle @ EUR ]--%, %l pour lequel on ait s2q : 0.

(8%)

Montrer que s;9q : 0 si et seulement si t : tan9 satisfait l'équation

... t2+Mt--1=O.

Spq
Montrer que cette équation admet une solution to EUR ]--1, 1] et une autre 151 
EUR ]--1, 1].
Quelle est la relation entre les angles 90 et 91 qui correspondent a ces 
racines ?

Dans toute la suite, on choisit l'une des deux racines t de l'équation (1). On 
a donc

s2q : 0. Un choioe plus précis sera fait a partir de la question 12.

/ - / _ _ / - / _
Ver1fier que % -- spp -- Ifqu , etabhr une formule analogue pour sqq sqq.

On décompose S sous la forme S = D + E avec D diagonale et E a diagonale nulle.
On décompose de même S' = D' + E'. Calculer HE'H2 en fonction de UE...2 et de

(Spq)2-

(e) En justifiant que HS'H : HSM, en déduire une expression de HD'H2 au moyen 
de MDN2
et de (qu)2.

9. Montrer que les coefficients de S' s'expriment uniquement en fonction de 
ceux de S et de
la racine (t0 ou tl) qu'on a choisie.

10. On suppose dans cette question que % est le coefficient de plus grande 
valeur absolue de
E.

(a ) Montrer que HE'H< pHEH où p < 1 est une constante que l' on explicitera.

(b) Si on choisit la racine %, montrer en outre que HD' -- DH< \ HEM.

11. En calculant (sqq -- Sîqp)2 -- (sqq -- spp)2, montrer que

i521q _ 5;9pi > i8qq _ Sppi-

12. Dorénavant, et jusqu'à la fin du problème, on choisit la racine % de (1) et
donc l'angle EUR... mentionnés à la Question 8b.

/ l A '
(a) Montrer que spp -- spp et sqq -- sqq sont du meme s1gne que sqq -- spp.

b Si 1< <,n montrer que
( )
lsZ-Z- -- l + lsZ-Z- -- S'pp--l lsZ-Z-- sppl -- lsZ-Z- -- Sqql > 0

13. On définit

n
R = E : 1817 _ 8111 et =Ë : 1833 Szzi
i7j=1i73=1
Montrer que

n
R, _ R > 2(iSflq _ Sqql + iS;)p _ Sppl) : 22 Mi _ Sii-

1=1
3 Algorithme de Jacobi incomplet

Dans l'algorithme de J acobi, on part d'une matrice 2 EUR SZZ et on construit 
une suite de matrices
symétriques EW), dont les coefficients sont notés og", de la façon suivante :

0 On pose E/125.... En déduire que la série Èm=1 EUR... est 
convergente.

15. On décompose E +oo.

En déduire que le polynôme caractéristique de D est égal a celui de A(O).

Finalement, montrer que les termes diagonaux de D sont les valeurs propres de 
A(O). Que
peut--on dire de leurs multiplicités ?

5 Algorithme de J acobi ; version optimale

19.
20.

21.

22.

Dans la version optimale de l'algorithme de Jacobi, on choisit pour chaque m un
couple (p...,q...) de sorte que la valeur absolue du coefficient of?" soit 
maximale
précisément quand (i, j ) = (p..., q...). Autrement dit,

W < j. \a£ÿ"\ < \v£îîà...l

Montrer que pour m --> +oo, la suite (E
			

X Maths PC 2013 -- Corrigé
Ce corrigé est proposé par Silvère Gangloff (ENS Ulm) ; il a été relu par Yvon
Vignaud (Professeur en CPGE) et Nicolas Martin (ENS Lyon).

L'épreuve est composée de cinq parties. Elle présente l'algorithme de Jacobi,
qui calcule les valeurs propres d'une matrice symétrique donnée S. Son principe 
est
de construire une suite de matrices semblables à S, qui converge vers une 
matrice
diagonale dont les coefficients diagonaux sont les valeurs propres de S, 
comptées
avec multiplicité. Une majoration de la vitesse de convergence permet de 
calculer ces
valeurs propres avec une précision arbitraire.
La première et la quatrième partie sont indépendantes des autres et peuvent être
traitées séparément. Les deux premières parties n'utilisent que le programme de 
la
classe de PCSI.
· La première partie, préliminaire, demande essentiellement des connaissances de
première année sur les matrices orthogonales, les matrices symétriques, la trace
et les études de fonctions.
· La deuxième partie concerne la base de l'algorithme. Il s'agit de montrer que
l'on peut conjuguer une matrice symétrique S par une matrice de rotation de
manière à annuler un coefficient non-diagonal de S. La norme euclidienne de
la matrice étant conservée, l'objectif de l'algorithme est de réitérer 
l'opération
pour concentrer la masse des coefficients sur la diagonale. On établit donc à
cet effet un certain nombre d'inégalités en fin de partie. Celle-ci demande une
bonne maîtrise du calcul matriciel, ainsi que des connaissances élémentaires
concernant la trigonométrie et les polynômes du second degré.
· La troisième partie étudie la convergence de la suite de matrices données par 
la
méthode précédente, lorsque l'on choisit arbitrairement le coefficient à 
annuler.
Cette partie utilise des résultats sur les séries à termes positifs et sur les 
suites.
· Dans la quatrième partie, on compare les valeurs propres des éléments d'une
suite de matrices convergente aux valeurs propres de la matrice limite. On y
utilise les outils de base de la réduction des endomorphismes.
· Enfin la cinquième partie présente l'algorithme de Jacobi optimisé, où l'on
annule à chaque étape un coefficient non-diagonal de module maximal.
Cette épreuve d'analyse numérique demande peu de connaissances du cours, ce qui
reflète assez bien l'esprit du concours de l'X, très éloigné des applications 
successives
de théorèmes.

Indications
t

4 Utiliser le résultat de la question 3 pour les matrices R = V et S = A A.
6 Se servir de la question 3 pour S et R = Rp,q ().
8.b Utiliser le fait que t0 t1 = -1. Pour la relation, utiliser le fait que
t0 + t1 = -(spp - sqq )/spq
et démontrer la formule suivante, valable pour tout couple d'angles (, ) tels
que ,  6= /2 (mod ) et tan() tan() 6= 1 :
tan( + ) =

tan() + tan()
1 - tan() tan()

8.c Utiliser la formule donnée en réponse à la question 7, puis se servir 
judicieusement de l'équation (1).
8.d Il est plus simple de calculer d'abord ||D || en fonction de ||D|| et de 
spq 2 . Utiliser
le fait que ||S || = ||S|| et démontrer les formules
||S||2 = ||D||2

et ||S ||2 = ||D||2 + ||E ||2

9 L'angle  peut s'exprimer en fonction de la racine choisie.
11 Décomposer le premier carré après avoir appliqué les formules de la question 
8.c,
puis utiliser l'équation (1).
12.a Démontrer que l'équation (1) peut se mettre sous la forme

sqq - spp
t2 1 +
=1
-tspq
12.b Distinguer deux cas : sqq - spp positif ou négatif. C'est alors une 
conséquence
des questions 5 et 12.a.
13 Montrer que R - R > 2(|sqq - spp | - |sqq - spp |) en reprenant le résultat 
de la
question 12.b puis distinguer les cas sqq - spp positif ou négatif.
14 Pour la convergence de la série, montrer que la suite (Rm )m>0 est bornée.
Utiliser pour cela le fait que la suite ((m) )m>0 est bornée, ce qui est une
conséquence de la question 4.
15 Voir que la convergence de la série des m entraîne la convergence de chaque
(m)
suite (ii )m>0 , ce qui entraîne la convergence de la suite (D(m) )m>0 .
16 Raisonner par récurrence.
17 Montrer que les coefficients du polynôme caractéristique d'une matrice N sont
des fonctions continues des coefficients de N.
18 Utiliser le fait que les valeurs propres d'une matrice sont les racines de 
son
polynôme caractéristique.
19 Montrer par récurrence, en appliquant l'inégalité démontrée à la question 
10.a,
que pour tout m > 0, ||E(m) || 6 m ||E(0) ||.
20 Utiliser les résultats de la partie 4.
21 C'est une conséquence de la question 10.b.

1. Préliminaires
1 Lorsque n = 3, on constate directement que
La matrice Rp,q () est la matrice dans la base canonique (e1 , e2 , e3 ) de R3
de la rotation autour de l'axe dirigé et orienté par ep  eq , et d'angle .
t

2 Notons reij les coefficients de la matrice (Rp,q ()). Par définition de la 
transposition, reij = rji , et par définition du produit matriciel, les 
coefficients ci,j de la matrice
t
(Rp,q ()) Rp,q () sont donnés par la formule
n
n
P
P
ci,j =
reik rkj =
rki rkj
k=1

k=1

Le k-ième terme de cette somme, pour k 6= p, q, est ki kj = ij ki . Il s'ensuit 
la formule
suivante, valable pour tous indices i et j
cij = ij (1 - ip )(1 - iq ) + rpi rpj + rqi rqj
cij = ij

Par conséquent, si i 6= p, q,
Si i = p ou i = q et que j 6= p, q alors

cpj = 0
Enfin on a les égalités suivantes
cpp = rpp 2 + rpq 2 = cos()2 + sin()2 = 1
cqq = rqq 2 + rpq 2 = cos()2 + sin()2 = 1
cpq = cqp = (rpp + rqq )rpq = 0
desquelles on conclut que
t

Ainsi,

(Rp,q ()) Rp,q () = In

On reconnaît que la matrice Rp,q () est orthogonale.

3 Pour toutes matrices R et S,
 t t t t  t t
t t
R SR = R S
R = R SR

Et comme on sait que la matrice S est symétrique

t t
t
R SR = R SR

t

De plus, comme R est une matrice orthogonale, elle vérifie R = R-1 et ainsi la
t
matrice R SR = R-1 SR est bien semblable à S. On en déduit que
La matrice t R SR est symétrique et semblable à S.
4 Par définition de la norme ||.||
t

t

t

t

||UAV||2 = Tr( (UAV) UAV) = Tr( V A U UAV)
Comme la matrice U est orthogonale, alors
t

t

||UAV||2 = Tr( V A AV)

D'après le résultat de la question 3 pour R = V qui est bien orthogonale par 
définition

t
t
t
t
t
t
t
et S = A A qui est bien symétrique car
AA = A
A = A A, la matrice
t

t

t

V A AV est semblable à A A, et comme la trace est invariante par similitude,
on obtient enfin :
q
t
||UAV|| = Tr( A A) = ||A||

5 Notons par commodité, la fonction f : x 7 |x - a| - |x - b| - |x - c| + |x - 
d|.
Pour tout x 6 a on a
f (x) = a - x - (b - x) - (c - x) + d - x = a + d - b - c = 0
Ensuite, si a 6 x 6 b, alors
f (x) = x - a - (b - x) - (c - x) + d - x = 2(x - a) > 0
Si b 6 x 6 c
f (x) = x - a - (x - b) + (x - c) - (x - d) = b - c - a + d = 2(b - a) > 0
car d - c = b - a. Enfin, si c 6 x 6 d
f (x) = 2(d - x) > 0
et f (x) = 0 pour x > d. Résumons ceci dans un tableau de variation de la 
fonction f .
x

-

a

f (x)

b
c
2(b - a) - 2(b - a)

0

-

d

+

0

0

-

0

Par conséquent, comme on peut le voir sur le tableau
La fonction x 7 |x - a| - |x - b| - |x - c| + |x - d| est à valeurs positives.