CCP Maths 2 MP 2000

Thème de l'épreuve Étude de familles de matrices
Principaux outils utilisés algèbre linéaire et bilinéaire

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Énoncé obtenu par reconnaissance optique des caractères


SESSION 2000 A CONCOURS COMMUNS IP0lYÎECHNIOIIES ÉPREUVE SPÉCIFIQUE-FILIÈRE MP MATHÉMATIQUES z DURÉE : 4 heures Les calculatrices programmables et alphanumériques sont autorisées, sous réserve des conditions définies dans la circulaire n°99-018 du 01.02.99. Préambule Dans ce problème, on se propose d'étudier des familles de matrices que l'on rencontre lors de la résolution numérique de problèmes relatifs à des équations aux dérivées partielles de type elliptique par des méthodes de différences finies. Matrices irréductibles - Matrices à diagonales faiblement ou fortement dominantes. Notations : Dans tout le problème, on suppose que N est un entier supérieur ou égal à 2. MN (R) est l'ensemble des matrices carrées réelles à N lignes et N colonnes, MN_p (R) l'ensemble des matrices réelles à N lignes et P colonnes. IN est la matrice unité de MN (R). SN (R) est l'ensemble des matrices symétriques à N lignes et Ncolonnes. Si Ae MN (R), (Ae 5N(R) @ 'A = A). SiA appartient à MN (R) on pourra écrire A = ("g") i: 1,...,N j= 1,...,N . aij étant l'élément de la i--ème ligne et de la j-ème colonne de A. 2 u,v l--> u v de (RN) dans R dési ne le roduit scalaire euclidien canonique de RN. On N g P identifiera RN et M,... (R) et pour A & MN (R), v & MN,1 (R) on écrira par exemple (Avlv)N le produit scalaire des éléments de RN correspondants: on a donc, en raison de l'identification (Avlv)N : 'vAv. WN est l'ensemble des N premiers entiers strictement positifs. Rappel : une matrice réelle symétrique est dite positive (définie positive) si ses valeurs propres sont positives (strictement positives). Tournez la page S.V.P. Définition 1 : Soient (el,e2,...,eN) la base canonique de RN et O' une permutation de l'ensemble {1,2,...,N}. On appellera matrice de permutation PÔ associée à 6, la matrice Pc de MN (R) telle que Pcei : eo(i)- Alors P5 = (51.6...) où ô,-j est le symbole de Kronecker. Définition 2 : Soit A 6 MN (R). On dit qu'une matrice A = ("i/') est irréductible si pour tout couple (S, T) de parties de WN telles que S (\ T= @ et S U T : WN, il existe un élément aij # 0 avec t' e S et j e T. Dans le cas contraire on dira que A est réductible. Définition 3 : A & MN (R) A : (a,-j) est à diagonale faiblement dominante si : N 1) pour tout indice i & WN, la,-il Z Zlaijl J'=l j=ti N 2) pour au moins un indice i e WN, lah-' > 2'"Ül j=1 j;=i Définition 4 : N A & MN (R) est à diagonale fortement dominante si, pour tout indice i e WN, |ail--l > Elu," j=l j1=i _ Question 1-1 a) Soient o et 6' deux permutations de l'ensemble WN. a.1) Montrer que P6 Po, : PGO, . a.2) Montrer que PC est inversible et que P: : PG_. . a.3) Montrer que Pg1 : [PC. b) Soit AeMN (R) et POEMN (R) la matrice associée à la permutation 6. On définit B : pc--1A po : (bij). Exprimer b,, à l'aide de o. 0) Montrer que Ae MN (R) est irréductible si et seulement s'il n'existe pas de matrice de permutation Po telle que PO-- 1APÔ soit de la forme: _1 F 0 POAPG=G H où F et H sont des matrices appartenant respectivement à MP (R) et MN_p (R) et 0 une matrice dont tous les éléments sont nuls. Question 1-2 F 0 G H MN_p(R) et sont inversibles. Résoudre le système linéaire CX =U où X & MN,] (R) est la matrice des inconnues et U & MN,} (R) est donnée. On utilisera pour cela une décomposition a) Soit C 6 MN (R) telle que C =( ) où F et H appartiennent respectivement à M F (R) et U1 X1 convenable de X et de U en blocs U = , X = . U2 X2 b) On suppose que A & MN (R) est réductible. Proposer une méthode de résolution du système AX : U . Question 1-3 On veut montrer que A & .'MN (R) est irréductible si et seulement si la propriété (P) suivante est vérifiée : (P) pour tout couple (i, j) d'indices distincts de WN , "tj # 0 ou alors il existe un entier s et des indices i],i2,...,is tels que le produit aülaili7 ...a-- , - soit non nul. .r--l'x a...- a) Etablir que la condition est suffisante. b) On suppose maintenant que Ae MN (R) est irréductible. Pour chaque indice ieWN, on définit X ,- comme l'ensemble des indices j de WN tels que : l) j;fii 2) soit a,-]- #0 soit il existe il ,...,is tels que le produit aiilail,--2 "'aiç_1içaiçj soit différent de 0. Montrer que X ,- : WN \{i} et en déduire que la condition est nécessaire. Tournez la page S.V.P. Question 1-4 Le concept d'irréductibilité peut être illustré graphiquement. Soit AG MN(R), A=(aij) et {Fj- l i GW} un ensemble de N points distincts du plan. Pour . . 2 \ . . chaque couple (1,1) EUR (WN) tel que aÿ- # 0, on trace une fleche allant du pornt P,- vers le pomt Pj. Si ail» et a ji sont non nuls, il y aura une flèche du point B-- vers le point Pj et une autre de Pj vers P,-- . Si a,--,-- $ 0 on pourra tracer une boucle allant de P,- vers lui--même. Pj Pi #0 i au CZÙ'$O et afi$0 On associe ainsi à chaque matrice ce que l'on appelle un graphe orienté. En étudiant les graphes associés aux deux matrices suivantes : 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 donner une interprétation graphique du caractère réductible ou irréductible de chacune d'elles. Deuxième partie Question 2-1 Soit AEMN(R) à diagonale fortement dominante; soit UGMN,1(R) tel que AU :O "1 U = E ; soit i, un indice tel que lu,--i: max{lull,...,\uN'}. En considérant la i-ème ligne du "N produit AU montrer que l'on a nécessairement U = 0. Que peut-on en déduire pour det A '? Question 2-2 On suppose que A EUR M N (R) est irréductible et à diagonale faiblement dominante. a) Montrer qu'alors pour tout indice i & WN , \aHI > O. b) Montrer que det A # 0. Pour cela, on raisonnera comme dans la question 2--1 et on montrera d'abord que si AU : 0, tous les éléments de la matrice colonne U sont nécessairement égaux en valeur absolue. Question 2-3 a) Si A EUR SN (R) est une matrice dont les éléments diagonaux sont ?. 0 et si, de plus, elle est à diagonale faiblement dominante, montrer que toutes les valeurs propres de A sont 2 0 . b) Si, de plus, A est irréductible ou inversible, on montrera que toutes les valeurs propres de A sont strictement positives. Troisième partie Définition 5 : Une matrice A & SN (R) est une L-matrice si : l) pour tout indice i & WN , on a a,,- > 0 2 . . 2) pour tout couple d'indices (i, j) EUR (WN) tels que 1 $ ] , on a aij < 0 Définition 6 : Une matrice A & 5N (R) est une S-matrice si : 1) A est définie positive, 2 . . 2) pour tout couple d'indices (i,j) & (WN) tels que 1 $ ] , on a % < 0 Définition 7 : Une matrice A & SN (R) est une M-matrice si : 2 . . l) pour tout couple d'indices (i,j) & (WN) tels que 1 $ ] , on a aij < 0 , 2) A est inversible, 3) tous les éléments de A_1 sont 20. Question 3-1 a) Soit A & SN (R) définie positive, montrer qu'alors a,--, > 0 pour tout indice i & WN . En déduire que A EUR 5 N (R) est une S-matrice si et seulement si A est une L-matrice définie positive. b) Montrer que toute M--matrice est une L-matrice. Tournez la page S.V.P. c) Montrer que si A & SN (R) est une L-matrice l) irréductible, 2) à diagonale faiblement dominante, alors A est une S-matrice. Question 3-2 Le spectre de Q est, par définition, l'ensemble des valeurs propres réelles ou complexes de Q. Sp(Q) = {À & C/ det(Q -- 7JN ): O} . On appelle alors rayon spectral de Q, S (Q) : max(lM). ÀeSp Q a) Si Q & MN (R), montrer que la série EQ" est convergente si et seulement si S (Q) < 1 . k20 On admettra l'équivalence : Q" Î;----> 0 «: S (Q) < 1. Dans toute la suite de la question 3-2, on considère une L-matrice A d'ordre N et D la matrice diagonale ayant la même diagonale que A, donc définie par : 2 Pour tout couple d'indices (i , j) & (WN) tels que i # j, on a d,-]- = 0 Pour tout indice i & WN , on a dû : a,--,-- Soit C = (cg) appartenant à MN(R), telle que A=D--C et soit 8: D_1C (on justifiera l'existence de D_l). On suppose que S (B) < 1. --1 b) Justifier le fait que IN -- B est inversible et montrer que tous les éléments de (IN -- B) sont positifs ou nuls. c) Montrer que A est inversible et que A est une M--matrice. Question 3-3 Si D est une matrice diagonale à coefficients diagonaux strictement positifs, on définit DV2 et ' 1 il" et pour V dii D--l/2 matrices diagonales dont les éléments diagonaux sont respectivement d tout indice i & WN . Soit A une M--matrice. A On définit D, C, B comme à la question précédente et Ae£MN (R) par A A A A = D'V2AD"'/2 = IN - D"V2CD--V2 et B 6 MN (R) par B = Dl/2BD"V2. A a) Montrer que A est une M--matrice et que : A--l A---l A A2 Am A--1Am+l (A) =(lN--B] =IN+B+(B) +....+(BJ +(lN--B) (B) pour t0Ut entier '" strictement positif. /\ A "1 b) Soit G... G MN (R) définie par: G... : IN +B+....+(B) . Montrer que tous les éléments de G... sont positifs et majorés indépendamment de m. c) En déduire que S(B) < 1. Question 3-4 Soit A & SN (R) une S--matrice. On utilise les mêmes notations qu'en 3-2 et 3-3. . . _ --l _ a) Montrer que A est 1nversrble et que A l : (IN -- B) D ' . b) On veut maintenant montrer que S ( B) < 1 ce qui suffira pour établir que toute S--matrice est une M--matrice. A bl) Montrer que A est définie positive. b2) En supposant S (B) 2 l, montrer que l'on est conduit à une contradiction et que donc toute S-matrice est une M--matrice. On admettra que si Q & MN (R) a tous ses éléments positifs ou nuls, alors, il existe 11 & Sp(Q) tel que u = S (Q) Fin de l'énoncé.

Extrait du corrigé obtenu par reconnaissance optique des caractères


 CCP Maths 2 MP 2000 -- Corrigé Ce corrigé est proposé par Brice Goglin (ENS Lyon) ; il a été relu par Guilhem Bichot (Mines de Paris) et Francesco Colonna-Romano (ENS Ulm). Le but du problème est d'étudier certaines familles de matrices. Dans une première partie, on s'intéresse à la réductibilité des matrices. Ensuite, on étudie cette propriété sur des matrices à diagonale faiblement ou fortement dominante. Dans la troisième partie, on étudie trois familles de matrices qui satisfont certaines conditions sur leurs coefficients. Cette épreuve n'est pas très difficile, et parfois assez calculatoire. Les seules compétences requises sont quelques connaissances en algèbre linéaire et bilinéaire des espaces vectoriels réels de dimension finie, et quelques notions sur l'étude des séries géométriques de matrices. Les parties sont assez largement indépendantes. Indications 1-1.a.3 Remarquer que les permutations sont des bijections et en déduire que i-1 (j) = (i)j . 1-1.c Partitionner WN en {1, . . . , P} et {P + 1, . . . , N}. 1-3.a Prendre (i, j) S × T, et remarquer que les indices i, i1 , . . . , is , j sont dans S puis dans T. 1-3.b Prendre S = {i} et T = WN - {i}. Choisir i1 tel que aii1 6= 0 et faire passer i1 de T à S. Réitérer le processus et remarquer que j va forcément passer de T à S à une des N - 1 étapes. 2-1 Expliciter la nullité du ie terme du produit AU. 3-1.b Écrire la nullité du terme (i, j) du produit AA-1 pour i 6= j. 3-2.a Remarquer que Q - IN est inversible et étudier la convergence de la suite n P (Q - IN ) Qk . k=0 3-2.b Déterminer le signe des coefficients de B et de ses puissances, puis appliquer la question 3-2.a à la série des puissances de B. 3-3.c Utiliser la caractérisation obtenue à la question 3-2.a. b est symétrique, positive puis définie positive. 3-4.b.1 Montrer que A 3-4.b.2 Utiliser une valeur propre de IN - B négative et un vecteur propre associé. Première partie 1-1.a.1 Soient et deux permutations de l'ensemble WN . Soient i et j deux éléments de WN . Évaluons l'élément x situé sur la ie ligne et la j e colonne de la matrice produit P P . On a N P x= (P )ik (P )kj k=1 Par définition de P , on a (P )ik = i(k) . Donc x= N P i(k) k (j) k=1 Le terme k (j) est non nul si et seulement si k = (j). Il vaut alors 1. La somme citée ci-dessus ne comporte donc que le terme correspondant au cas k = (j). D'où x = i( (j)) = (P )ij Or, ce terme (P )ij est exactement la valeur de l'élément situé sur la ligne i et sur la colonne de j dans la matrice P . On a donc P P = P 1-1.a.2 Les permutations de WN sont, bien entendu, des bijections et sont donc inversibles. On peut donc appliquer la formule précédente à une permutation et à son inverse. On obtient P P-1 = P-1 = PId La matrice PId de la permutation identité est en fait la matrice des symboles de Kronecker. C'est donc la matrice identité IN . Donc P P-1 = IN Comme les matrices considérées ici sont carrées, on peut en déduire -1 (P ) = P-1 1-1.a.3 Les permutations étant des bijections, on a i = j si et seulement si (i) = (j). Les symboles de Kronecker ij valent donc également (i)(j) . Si on applique cette remarque avec -1 (j) à la place de j, on déduit i-1 (j) = (i)j (i)j est en fait le terme situé sur la ligne i et la colonne j dans la transposée de la matrice P . Les termes de la transposée de P sont donc les i-1 (j) , c'est-à-dire les termes de P-1 . Donc t P -1 = P-1 = P P est une matrice orthogonale. 1-1.b Soient i et j deux indices. On a bij = N P P-1 k=1 (AP )kj N P A(i)k (P )kj ik est le symbole de Kronecker i-1 (k) . Il ne reste donc dans la Le terme P-1 ik somme que le terme vérifiant i = -1 (k), c'est-à-dire k = (i). Donc bij = (AP )(i)j = k=1 De la même façon, il ne reste dans cette somme que le terme tel que k = (j). D'où bij = A(i)(j) Comme on vient de le voir, les matrices P sont orthogonales. Ce sont donc des matrices de changement de base orthonormée. En fait, il s'agit d'une permutation des vecteurs de base de l'espace. On comprend donc d'où vient la formule que l'on vient d'obtenir. 1-1.c Supposons qu'il existe une matrice de permutation P telle que F O -1 P AP = G H avec F MP (R), H MN-P (R) et O nulle. Alors pour tout couple (i, j) vérifiant 1 6 i 6 P et P < j 6 N, on a P-1 AP ij = 0. D'après la question précédente, on en déduit pour 1 6 i 6 P et P < j 6 N A(i)(j) = 0 Considérons l'ensemble S des images des entiers 1, . . . , P par et T celui de l'image de P + 1, . . . , N par . Les ensembles 1, . . . , P et P + 1, . . . , N forment une partition de WN . Or, réalise une bijection de WN , S et T forment donc une partition de WN . On a donc obtenu deux ensembles S et T d'intersection vide et d'union WN , tels que pour tout couple (i, j) de S × T, Aij = 0. A est donc réductible. On constate que ce raisonnement utilise des équivalences à chaque étape. Pour construire la permutation , il suffit de faire correspondre S à un ensemble {1, . . . , P} et T à {P + 1, . . . , N}. On a ainsi montré l'équivalence demandée. F O -1 A est irréductible telle que P AP = G H 1-2.a Notons U1 le vecteur constitué des P premières composantes de U et U2 celui composé des N - P dernières composantes. Notons de la même façon X1 et X2 . F O X1 FX1 On a = G H X2 GX1 + HX2 Résoudre le système CX = U revient donc à résoudre les deux systèmes FX1 = U1 et GX1 + HX2 = U2 . On a donc X1 = F-1 U1