Concours Centrale Supélec MATHÉMATIQUES II

Michel Andr”Ani

Description

Niveau: Supérieur
MATHÉMATIQUES II Concours Centrale-Supélec 2001 1/7 MATHÉMATIQUES II Filière PSI Rappels, notations et objectifs du problème. Dans tout ce problème, désigne un entier supérieur ou égal à . Toutes les matrices considérées ici sont à coefficients réels. On note : • l'ensemble des matrices carrées d'ordre . • (resp. ) l'ensemble des matrices symétriques (resp. symétriques définies positives c'est-à-dire dont les valeurs propres sont strictement posi- tives). • l'ensemble des matrices triangulaires supérieures (termes sous-diago- naux nuls) et l'ensemble des matrices appartenant à dont tous les termes diagonaux sont positifs ou nuls. • l'ensemble des matrices triangulaires inférieures dont les termes diago- naux valent . Le symbole désigne la matrice unité diag élément de . Pour , le terme de situé sur la ligne et la colonne est noté . Dans les parties I et II seulement, si , désigne la matrice d'ordre extraite de . On confond respectivement : • matrice et endomorphisme de canoniquement associé. • vecteur de et matrice colonne de ses coordonnées. • une matrice d'ordre et le réel la constituant. Si nécessaire, sera muni de sa structure euclidienne rendant la base cano- nique orthonormale. Ainsi, si , est une matrice de tandis que représente (norme euclidienne).

• structure euclidienne rendant la base cano- nique orthonormale


• sn sn


• décomposition


• n≤ ≤


• unicité de la décomposition

Sujets

• Décomposition

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 68
• Langue: Français

Extrait

MATHƒMATIQUES II

MATHƒMATIQUES II

FiliËre PSI

Rappels, notations et objectifs du problËme. Dans tout ce problËme, n  dÈsigne un entier supÈrieur ou Ègal ‡ 2 . Toutes les matrices considÈrÈes ici sont ‡ coefÞcients rÈels. On note : ¥ M n .lÕensemble des matrices carrÈes dÕordre n  ++ ¥ S n  (resp. S n ) lÕensemble des matrices symÈtriques (resp. symÈtriques dÈÞnies positives cÕest-‡-dire dont les valeurs propres sont strictement posi- tives). ¥ U n  lÕensemble des matrices triangulaires supÈrieures (termes sous-diago- + U naux nuls) et n lÕensemble des matrices appartenant ‡ U n dont tous les termes diagonaux sont positifs ou nuls. L ¥ n lÕensemble des matrices triangulaires infÈrieures dont les termes diago- naux valent 1 . Le symbole I dÈsigne la matrice unitÈ diag (1, …,1) ÈlÈment n de M n . Pour A∈ M n , le terme de A situÈ sur la ligne i et la colonne j est notÈ A . i,j Dans les parties I et II seulement, si 1≤i≤n , A dÈsigne la matrice dÕordre i  i A A…A 1,1 1,2 1,i A A…A 2,1 2,2 2,i extraite de A . M M M M A A…A i,1i,2i,i On confond respectivement : n ¥ matrice et endomorphisme de IR canoniquement associÈ. n ¥ vecteur de IR et matrice colonne de ses coordonnÈes. ¥ une matrice dÕordre 1 et le rÈel la constituant. n Si nÈcessaire, IR sera muni de sa structure euclidienne rendant la base cano- n t t nique orthonormale. Ainsi, si ∈ , v est une matrice de M n tandis que vv vIRv 2 reprÈsente v (norme euclidienne). Le but de ce problËme est dÕÈtudier trois types de dÈcompositions matricielles : dÈcomposition LU I), dÈcomposition de Cholesky (partie II), (partie dÈcomposition QR (partie III).

Concours Centrale-SupÈlec 2001

1/7

MATHƒMATIQUES II

FiliËre PSI

FiliËre PSI

La partie IV utilise des dÈcompositions des parties I ‡ III, pour dÈterminer des approximations des valeurs propres dÕune matrice.

Partie I -

I.A - M I.A.1) Montrer que si A ‡ appartient n triangulaire inversible, son est Ð1 inverse A est aussi triangulaire. L I.A.2) Montrer que ( n ,×) est un groupe. I.B -Soit ∈ M n : A I.B.1) Montrer que si A  est inversible, il existe au plus un couple (L,U)∈ n × U n tel que A=LU . L Si cÕest le cas, on dira que A possËde une dÈcomposition LU ( L comme Lower et U comme Upper). I.B.2) Montrer que si A  est inversible et possËde une dÈcomposition LU , alors pour tout k de {1, …,n} , det(A) ≠0 k (on pourra utiliser une dÈcomposition par blocs de A ). I.B.3) On suppose que det(A) ≠0 et on Ècrit A par blocs sous la forme : nÐ1   A V   nÐ1 A= .   W A n,n   Montrer quÕil existe H dans L n telle que : (∀i∈ {1, …,nÐ1},)(HA)=0 . n,i

  H0 nÐ1 En posanta priori H= expliciter une telle matrice H ainsi que son    H  ′1 inverse, cÕest-‡-dire expliciter les blocs H et H′ , ainsi que les blocs corres- nÐ1 Ð1 pondants de H en fonction des blocs de la matrice A .

I.B.4) Montrer que si pour tout k  dans {1, …,n} , det(A) ≠0  alors A une a k dÈcomposition LU (on pourra opÈrer par rÈcurrence en utilisant une dÈcomposition par blocs de A ).

Concours Centrale-SupÈlec 2001

2/7

MATHƒMATIQUES II

FiliËre PSI

I.C - I.C.1) Soit deux entiers p et q tel que 1≤p<q≤n . Montrer que lÕopÈration ÈlÈmentaire consistant ‡ Èchanger les lignes p et q dÕune matrice de M n cor- respond ‡ la multiplication ‡ gauche par une matrice de M n ‡ dÈterminer. I.C.2) Pour 1≤k≤n et 1≤i<i< … <i≤n , 1≤j<j< … <j≤n , le symbole 1 2k1 2k

i i…i 1 2k j j…j 1 2k

A

dÈsigne le dÈterminant de la matrice

  A A…A  1 2 1 1 1k  i,j i,j i,j   A A…A i,j i,j i,  22 1 2 2 j k    M M M M     A A…A i,j i,j i,j   k1k2k k

extraite de A . Ainsi par exemple, det(A)= i

1 2…i . 1 2…i A

Sous les hypothËses de la question I.B.4, et notant A=LU la dÈcomposition LU de A , trouver dans lÕordre : a) la premiËre ligne de U , b) la premiËre colonne de L , c) les ÈlÈments diagonaux de U , d) les ÈlÈments de L des colonnes 2,3, …,n (on utilisera I.C.1) sous forme PA=PLU o˘ P est une matrice telle que la multiplication de M par P ‡ gauche permute deux lignes de M ), e) les ÈlÈments de U des lignes 2,3, …,n .

1 2…jÐ1i 1 2…jÐ1j A On montrera que pour 2≤j≤i≤n , L= - et on donnera i,j 1 2…j 1 2…j A pour U ( 2≤i≤j≤n ) une formule analogue. i,j

Concours Centrale-SupÈlec 2001

3/7

MATHƒMATIQUES II

FiliËre PSI

I.D - …criture de lÕalgorithme En utilisant : ¥ un algorithme induit par la question I.C.2), ¥ un langage de programmation (quÕon prÈcisera) comprenant la fonction dÈterminant (notÈe det), Ècrire une procÈdure donnant, pour une matrice A satisfaisant aux conditions du I.B.4), les matrices L et U telles que A=LU . I.E - Exemples: I.E.1) a) ¿ lÕaide de lÕalgorithme mis en place au I.D - , effectuer la dÈcomposition L  U de la matrice   1 1 3 1    1 31 2  A=   0 1Ð1 2    1Ð1 2 1  en indiquant les diffÈrentes Ètapes et les calculs intermÈdiaires. b) En dÈduire la rÈsolution du systËme matriciel AX=Y dÕinconnue     x a     y b     X= et de paramËtre Y= .     z c      t   t  M 2 I.E.2) Donner deux exemples de matrices de, lÕune ne possÈdant pas de dÈcomposition LU , lÕautre en possÈdant plusieurs. q I.E.3) Dans cette question C dÈsigne le coefÞcient du binÙme de Newton p q avec la convention C=0 si p<q , si p<0 ou si q<0 . p a) Soient p , q et r entiers naturels. Montrer la formule de Vandermonde : r k rÐk C=C C  ∑ p+qq p k∈ZZ (on pourra utiliser la formule du binÙme de Newton). b) Soit p∈IN ; dÈterminer la dÈcomposition LU de la matrice de M n telle A iÐ1 que A=C . En dÈduire detA . i,j p+jÐ1 …crire A , L , U lorsque p=1 et n=4 .

Concours Centrale-SupÈlec 2001

4/7

MATHƒMATIQUES II

FiliËre PSI

Partie II - ++ II.A -Soit A∈ S n . Montrer que A appartient ‡ n si et seulement si pour S n t tout v appartenant ‡ IR non nul, vAv>0 .  ++ On suppose dans le reste de cette partie II - , que ∈ S n . A II.A.1) Montrer que A possËde une dÈcomposition LU unique notÈe : = o˘ ∈ L n et ∈ U n . (on pourra utiliser I.B). A LU L U II.A.2) Montrer que ∀i∈ {1, …,n} , U>0 . i,i II.B - t U II.B.1) Montrer quÕil existe B dans n telle que A=BB (on pourra modiÞer L et U et se ramener au cas de matrices triangulaires infÈrieure et supÈrieure ‡ diagonales identiques). II.B.2) Montrer que la dÈcomposition obtenue ‡ la question prÈcÈdente est unique si on impose ∀i∈ {1, …,n} , B>0 . i,i M II.C -Si ∈ n , montrer que les 3 propositions suivantes sont Èquivalentes : M ++ i) M∈ S n , t ii) ∃B∈ U n inversible telle que M=BB , ∈ S n ∀1, …,et( k ) >0 iii) M et k∈ {n} , dM .

Partie III - n(v)t III.A -Soit v∈IR unitaire (v=1) . On pose H=IÐ2v v (matrice de Hou- n (0) seholder)et par convention H=I . n (v) III.A.1) Montrer que H est une symÈtrie orthogonale que lÕon caractÈrisera. n n(v) III.A.2) Montrer que pour tout a dans IR , il existe v dans IR tel que H a soit de la forme ( ,0,0, …,0) . * III.B -Soit ∈ M n . A III.B.1) Montrer quÕil existe H, …,H matrices de Householder telles que : 1nÐ1 nÐ1 …H A∈ U n H H . nÐ2 1 III.B.2) En dÈduire que toute matrice de M n sÕÈcrit sous la forme A=QR o˘ + M Q∈ n est orthogonale et ∈ U n (on parle de dÈcomposition QR ). R III.B.3) Montrer que si A est inversible, il y a unicitÈ de la dÈcomposition. III.C -Quel rÈsultat de cours permet dÕobtenir directement une dÈcomposition du type QR lorsque A est supposÈe inversible ?

Concours Centrale-SupÈlec 2001

5/7

MATHƒMATIQUES II

FiliËre PSI

Partie IV - M Dans cette partie A est une matrice de n inversible et possÈdant n valeurs propres rÈelles λ , …λ avec λ… > λ > λ > . 1n1 2n IV.A -Dans cette section, on montre des rÈsultats prÈliminaires. IV.A.1) On rappelle quÕune suite de matrice (M) vers une converge k k∈IN matrice M si et seulement si chaque coefÞcient de M converge vers le coefÞ- k cient de M correspondant. k k IN k ∈ M M Montrer que si ( ) et (N) sont deux suites de n convergentes de ∈kIN limites respectives M et N alors la suite (M N) converge vers MN . k k k∈IN IV.A.2) Pour tout ∈ M n , on dÈÞnit M = sup , M MX ≤1 X et on admet que dÈÞnit une norme dans M n . MaM a) Montrer que si et sont dans M n , on a M N MN≤M⋅N . ∈ M n M<1M+ n b) Montrer que si M vÈriÞe alors I est inversible. Ð1 IV.A.3) JustiÞer lÕexistence dÕune matrice P  inversible telle que A  =PD P avec D diagonale :    λ  1 (0)   .   D . = .     (0)   λ n   Ð1 On suppose dans la suite de cette partie que P possËde une dÈcomposition LU Ð1 sous la forme P=LU et on pose P=QR la dÈcomposition QR de P . IV.B -suite dÕÈlÈments deSoit la M par rÈcurrence de la dÈÞnie A( k ) n k≥1 faÁon suivante : ¥ A=A ; 1 ¥ si A a ÈtÈ construite, on pose A=Q R la dÈcomposition QR de A ; k k k k k ¥ on dÈÞnit A=R Q . k+1k k Montrer que les matrices A ( k≥1 ) sont semblables ‡ A . k

Concours Centrale-SupÈlec 2001

6/7

MATHƒMATIQUES II FiliËre PSI kÐk kÐk IV.C -DÈterminer explicitement la matrice DD L et limDD L (la matrice k→+∞ D est celle dÈÞnie au IV.A.3)). kÐk On posera dans la suite E=D L DÐI . k n Ð1 IV.D -Montrer quÕ‡ partir dÕun certain rang I+R E R une admet n k dÈcomposition QR unique de la forme : Ð1 ÷ ÷ I+R E R=Q R k k n k ÷ o˘ R k est ‡ termes diagonaux strictement positifs.

÷ ≥ M On admet dans toute la suite que la suite (Q k ) k1 converge dans n . IV.E -. ÷ ÷ IV.E.1) Montrer que la limite Q de la suite (Q k ) est orthogonale. k≥1 + ÷ ÷ IV.E.2) Montrer que la suite ( k ) k≥1 converge et que sa limite est dans U n . R R ÷ ÷ IV.E.3) DÈterminer Q et R . k IV.F -En utilisant deux compositions QR de A , montrer que la suite (A) k k≥1 est telle que : lim(A)=λ (1≤i≤n)   lim(A)=0(1≤j<i≤n) k i k i,i i,j k→+∞k→+∞

Concours Centrale-SupÈlec 2001

¥¥¥ FIN ¥¥¥

7/7