X Maths PC 2013

Thème de l'épreuve Algorithme de Jacobi
Principaux outils utilisés réduction, séries numériques
Mots clefs Matrice symétrique, valeurs propres, polynôme caractéristique, matrice de rotation

Corrigé

 : 👈 gratuite pour tous les corrigés si tu crées un compte
👈 l'accès aux indications de tous les corrigés ne coûte que 1 € ⬅ clique ici
👈 gratuite pour tous les corrigés si tu crées un compte
- - - - - - - - - - - - - - - - - - - - - - - - -

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


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