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.