© Éditions H&K
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.
© Éditions H&K
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.
© Éditions H&K
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)
© Éditions H&K
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.
