Mines Maths 2 MP 2003

Thème de l'épreuve Méthodes analytiques pour la résolution d'une équation linéaire A.x=b .
Principaux outils utilisés algèbre bilinéaire, analyse réelle
Mots clefs point selle, optimisation, algorithme du gradient, algorithme d'Uzawa, analyse numérique

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE NATIONALE DES PONTS ET CHAUS SÉES ÉCOLES NATIONALES SUPÉROEURES DE L' AÉRÇNAUTÏQUE ET DE L ESPACE, DE TECHNIQUES AVANCÉES, DES TELECOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT--ETIENNE, DES MINES DE NANCY, DES TELECOMMUNICAIIONS DE BRETAGNE. ÉCOLE POLYTECHNIQUE (Filière TSI). CONCOURS D'ADMISSION 2003 ÉPREUVE DE MATHÉMATIQUES DEUXIEME EPREUVE Filière MP (Durée de l'épreuve : 4 heures) (L'usage d'ordinateur ou de calculette est interdit). Sujet mis àla disposition des concours : Cycle International, ENSTIM, ENSAE (Statistique), INT , TPE--BNP. Les candidats sont priés de mentionner de façon apparente sur la première page de la copie: MATHÉMATIQUES 2-F111ere MP Cet énoncé comporte 6 pages de texte. Si, au Cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le * signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre. L'objet du problème est l'étude de méthodes analytiques (méthodes du gradient, du Lagrangien) pour résoudre l'équation linéaire A.x = b oùA est une matrice symétrique positive, inversible, b un vecteur donné de R" et x un vecteur inconnu de R" ou d'un sous--espace vectoriel F de R". Dans tout le problème, l'entier n est un entier naturel supérieur ou égal à 2 (n 2 2) ; la base canonique de R" est notée el, ez, ..., e,, ; le produit scalaire de deux vecteurs x et y de R" est noté * (x | y). La norme d'un vecteur x est notée ||): II. Les matrices considérées sont réelles ; l'espace vectoriel des matrices carrées réelles d'ordre n est noté M ,,(R). Il est admis que l'application qui, à une matrice M de M ,,(R), associe la borne supérieure N (M) des normes des images parM des vecteurs unitaires de R" est une norme : N(M) =5up llM--xll- nxn=l Une matrice symétrique A est dite positive lorsque, pour tout vecteur x de R", le produit scalaire des vecteurs A.x et x est positif ou nul (A.): | x) 2 O. Première partie Le but de cette partie est la résolution de l'équation A.): = b où A est une matrice carrée d'ordre n symétrique positive et inversible, b un vecteur donné de R" et x un vecteur inconnu. Résultats préliminaires : Soit M une matrice carrée symétrique d'ordre n. 1. Démontrer qu'il existe un plus grand réel p et un plus petit réel q tels que, pour tout vecteur x de R", le produit scalaire (M.): | x) vérifie l'encadrement suivant : p ||x||2 S (Mx | x) 5 q lle2. Préciser ces deux réels p et q en fonction des valeurs propres de la matn'ce M. 2. Montrer que, pour que cette matrice M soit inversible et positive, il faut et il suffit que toutes ses valeurs propres soient strictement positives. 3. Démontrer que la norme N (M) d'une matrice M symétrique est égale àla plus grande valeur absolue des valeurs propres À,-- (1 5 i 5 n) de la matriceM : N (!'/I) =5"P Mil-- 1_<_iSn Étant donnés la matrice carrée, d'ordre n, symétrique positive A et le vecteur b, soit a un réel strictement positif strictement majoré par 2/2... (0 < a < 2/À,,) où A,, est la plus grande valeur propre de la matrice A ; soit (x" ) keN la suite définie par un premier vecteur x° choisi arbitrairement dans R" et par la relation de récurrence suivante : pour tout entier naturel k, ):"+1 = x" + a (b ----A.x"). Étude de la suite (x" ) keN : 4. Démontrer que la suite (x" ) keN IR", solution de l'équafimA.x : b . est une suite convergente de limite le vecteur 2 de l'espace Soit f la fonction réelle, définie dans IR", par la relation : f(x) = --â--Ax1+'Byl : b. 21. Soient xl un vecteur du sous--espace vectoriel F et y1 un vecteur de R". Démontrer qu'une condition nécessaire et suffisante pour que le couple (xl , y1 ) soit un point selle du Lagrangien L est que le vecteur xl réalise le minimum de la restriction de la fonction f à F et que les vecteurs x1 et y1 vérifient la relation suivante : Ax1 + tBy1 = b. La suite logique est la recherche d'un point selle du Lagrangien L. Algorithme d'Uzawa : soit toujours (x*, y*) un point selle, supposé exister ; étant donnés un vecteur y° arbitraire de R", une suite (pm )...ä de réels, qui seront précisés plus loin, soient (x'" )meN et (y'" )mËN les deux suites de vecteurs définies par les conditions suivantes : . Pour tout entier naturel m, le vecteur x'" est le vecteur qui rend minimum la fonction x +--» L (x, y'" ) . Pour tout entier naturel m, le vecteur y'"+1 est défini par la relation suivante : ym+l =ym +Pm me_ Existence des deux suites (x'" )meN et (y"' )meN : 22. Démontrer que les conditions énoncées permettent de déterminer tous les termes de ces deux suites (x'" )mGN et @" )...N et que les vecteurs de ces suites vérifient, pour tout entier naturel m, les relations suivantes : A(x'" --x*) + 'B(y"' --y*) = O, ym+l _y* =ym _y* +])": B(xm _x*)_ où x* et y* sont les deux vecteurs d'un point selle de L. 23. En déduire l'égalité ci--dessous : "ÿ"... --y* Il2 = Il)!" --y* Il2 --2 Pm (A(x"' --x*) | (x"' --x*)) + (m»)2 IIB(X'" --x*) "2- Convergence de la suite numérique de terme général Hy'" -- y* || 2, m & N : 24. Un résultat préliminaire : démontrer l'existence d'une matrice carrée d'ordre n symétrique positive inversible, notée A ", telle que : (Al/Z)2 =A. Soit C la matrice définie par la relation suivante C : A""2.'B.B...»4""2 où la matrice A'"2 est la matrice inverse de la matrice A 1/2. 25. Démontrer que la matrice C est une matrice symétrique positive. Établir qu'il existe une constante v telle que, pour tout vecteur u de R", l'inégalité ci--dessous soit vraie : "Eu"2 5 v (Au | u). Soient a et B deux réels tels que le segment [a, fl] soit contenu dans l'intervalle ouvert ]0, 2/v [, (0 < a < 5 < 2/v). La suite des réels p... est supposée vérifier pour tout entier naturel m l'inégalité suivante : aSpm_<_fl. 26. Démontrer que la suite de tenue général ||y'" --- y* || 2, m G N est monotone décroissante ; utiliser, pour simplifier, la suite (um) dont le terme général est définie par la relation suivante : me"-N Convergence de la suite (x'" )meN : 27. En déduire la convergence et la limite de la suite (x") meN ' FIN DU PROBLÈME

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


 Mines Maths 2 MP 2003 -- Corrigé Ce corrigé est proposé par Antoine Gloria (École Polytechnique) ; il a été relu par Céline Chevalier (ENS Ulm) et Thomas Chomette (ENS Ulm). Ce sujet propose une introduction aux bases de l'analyse numérique et du calcul scientifique enseignés dans les cursus de mathématiques appliquées des écoles d'ingénieur. Il fait appel à de bonnes connaissances en algèbre bilinéaire et à une certaine aisance dans le calcul. Il y a beaucoup de raisonnements par contraposée et certaines questions requièrent des résultats d'analyse sur les fonctions continues. Plutôt longue et exigeante sur la rédaction, cette épreuve nécessite des calculs réfléchis, parfois délicats et dont les méthodes sont assez générales. Dans la première partie, on s'attache à caractériser le minimum d'une fonction quadratique à plusieurs variables et à rechercher ce minimum à l'aide de l'inversion d'un système matriciel. La méthode du gradient est étudiée à cet effet. La seconde partie propose d'autres méthodes pour caracteriser le minimum d'une fonction convexe (méthode de point selle) et pour le déterminer (algorithme d'Uzawa). Indications Première partie 1-2-3 Diagonaliser la matrice M. 4 Procéder par récurrence sur xk - z en utilisant A.z = b, puis se servir de la question 3 en faisant apparaître la norme de In - A. 5 Utiliser la symétrie de A. 7 Travailler dans une base où A est diagonale. 9 Raisonner par condition nécessaire et suffisante ainsi que par contraposée. 11 Construire une suite décroissante à l'aide de la question 10. Seconde partie 12 Utiliser la question 1 et l'inégalité de Cauchy-Schwarz. 14 Découper l'espace en deux parties : l'une où f est « grande » et l'autre où f atteint ses bornes (un compact). 15 Raisonner par l'absurde en supposant l'existence de deux vecteurs distincts. 16 Raisonner par l'absurde en supposant qu'il existe u F tel que (g(y) | u) 6= 0, prendre v = µu, avec µ bien choisi pour obtenir une contradiction entre l'hypothèse et le caractère minimal. 17 x F donc (A.x - b | x) = 0. 18 Lire la remarque du corrigé précédant la question sur les bornes inférieures et supérieures. 19 Montrer que Sup Infn L(x, y) > L(x , y ) > Infn Sup L(x, y) . yRn xR xR yRn 20 Faire intervenir y-y1. Pour démontrer la deuxième équivalence, faire apparaître A.x1 + t B.y1 - b dans le membre de gauche et s'inspirer de la question 16. 21 Remarquer que si x F, L(x, y) = f (x). 22 Utiliser les résultats d'existence et d'unicité du minimum d'une fonction quadratique obtenus dans la première partie. 23 Exprimer le carré scalaire de y m+1 - y . 24 Diagonaliser la matrice A. 25 Démontrer que la matrice A-1/2 est symétrique. Utiliser le vecteur v Rn défini par u = A-1/2 .v. 26 Utiliser les questions 23 et 25. 27 Utiliser la question 26 pour démontrer la convergence de la série de terme général kum k2 . Première partie Résultats préliminaires 1 M est une matrice symétrique réelle, elle est donc diagonalisable sur R dans une base orthonormale (e ej )j=1,...,n , avec une matrice de passage orthogonale O (qui vérifie t O = O-1 ). O est la matrice formée des coordonnées des vecteurs (e ej )j=1,...,n dans la base canonique. On a ainsi M = ODO-1 , avec 1 0 · · · 0 0 2 · · · 0 D= . .. . . . .. . .. . 0 0 · · · n où (j )j=1,...,n sont les valeurs propres de M comptées avec leur multiplicité. Pour x Rn , on note (e xj )j=1,...,n ses coordonnées dans la base (e ej )j=1,...,n , soit x= n P xi ei = i=1 n P i=1 x ei eei En utilisant la linéarité de M, la bilinéarité du produit scalaire et le caractère orthonormal de la base (e ej )j=1,...,n , il vient P n n P (M.x | x) = M.(e xi eei )| x ej e ej i=1 = = (M.x | x) = n P i,j=1 n P i,j=1 n P i=1 j=1 (i x ei eei | x ej eej ) i x ei x ej (e ei | eej ) i x ei 2 Notons 1 et n respectivement la plus petite et la plus grande valeur propre de M. On obtient, d'une part, (M.x | x) = n P i=1 i x ei 2 n P 6 n i=1 (M.x | x) 6 n kxk et d'autre part, (M.x | x) = n P i=1 > 1 x ei 2 2 i x ei 2 n P i=1 x ei 2 (M.x | x) > 1 kxk2 De plus, (M.x1 | x1 ) = 1 et (M.xn | xn ) = n . On en déduit l'existence et l'unicité des réels p et q : p = 1 et q = n 2 Montrons qu'une condition nécessaire et suffisante pour que M soit positive au sens des matrices symétriques est que ses valeurs propres soient toutes positives. Rappelons que 1 est la plus petite valeur propre de M. Si 1 > 0, d'après la question précédente, x Rn (M.x | x) > 0 Réciproquement, un raisonnement par contraposée montre que, si 1 < 0, alors (M.e e1 | ee1 ) = 1 < 0 où ee1 est un vecteur propre (de la base orthonormale) associé à 1 . M n'est par conséquent pas positive. Pour que M soit inversible, il faut et suffit que son déterminant soit non nul, c'est-à-dire que ses valeurs propres soient toutes non nulles. M est symétrique, positive et inversible si et seulement si toutes ses valeurs propres sont strictement positives. 3 Soit x Rn tel que kxk = 1 ; notons x = n P i=1 2 kM.xk = = n P i=1 n P i=1 n P i x ei eei . i 2 x ei 2 6 ( Sup (i 2 )) i=1,...,n j=1 n P i=1 kM.xk2 6 Sup (i 2 ) i=1,...,n donc x ei eei , avec n P i=1 j x ej eej ! x ei 2 = 1. On a x ei 2 Sup kM.xk 6 Sup |i | kxk=1 i=1,...,n Par un calcul analogue, en prenant x = eei le vecteur propre associé à la valeur propre de plus grande valeur absolue, on obtient l'inégalité dans l'autre sens, de sorte que finalement, N(M) = Sup |i | i=1,...,n Ces résultats préliminaires, qui serviront à plusieurs reprises, sont des applications directes du cours d'algèbre linéaire et bilinéaire de la filière MP. Le même genre d'application directe du cours est demandé aux questions 24 et 25. Il est toujours profitable de lire l'énoncé en entier pour ne pas oublier de traiter les questions faciles placées en fin d'épreuve.