WikiPrépaLivrets

Mines Mathématiques 2 MP 2003Sujet, corrigé et rapport du jury

Pas encore noté
Logo concours Mines

Explorer les annales

BanqueMinesAnnée2003FilièreMPMatièreMathématiques
Annales Mines MP MathématiquesMines MP 2003MP MathématiquesMathématiques 2003

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Corrigé 2
Rapport du juryLire en ligneLaTeXWord

Présentation du sujet

Accessible
Résolution de Ax = b par méthode du gradient et du lagrangien
Afficher ou masquer la section

Le problème étudie la résolution de l'équation linéaire Ax = b, où A est une matrice symétrique positive, par des méthodes analytiques itératives : la méthode du gradient dans une première partie, puis la méthode du lagrangien lorsqu'on impose au vecteur inconnu x d'appartenir à un sous-espace F dans une seconde partie assimilable à la recherche d'un extremum lié.

  1. 1Première partie : résolution de Ax = b par la méthode du gradientRappels sur les matrices symétriques (questions 1 à 3), étude de la convergence d'une suite récurrente vers la solution z, puis caractérisation de z comme minimum d'une fonction f et construction d'une suite accélérant la convergence.
  2. 2Deuxième partie : résolution sous contrainte x appartient à FÉtude du minimum de f restreinte au sous-espace F, mise en évidence d'un argument de compacité, puis construction d'un algorithme d'approximation via la méthode du lagrangien.

Accessible. Le rapport qualifie explicitement le problème de très abordable, avec un énoncé de longueur raisonnable permettant aux meilleurs candidats de l'explorer complètement, tout en produisant un écart-type important qui a bien classé les candidats.

Ce qu'a observé le jury

6 erreurs relevées
Croire que tout vecteur est vecteur propre · Inversibilité de A non invoquée · Oubli de la symétrie de A
Afficher ou masquer la section

Le sujet, jugé très abordable et bien construit, permettait à tout candidat maîtrisant les bases du programme de MP d'obtenir une note convenable. Les questions préliminaires de rappel de cours donnaient dès le début une bonne indication de la qualité de la copie, et le sujet a globalement bien rempli sa fonction de classement.

Les erreurs les plus sanctionnées

  1. 1
    Croire que tout vecteur est vecteur propreQ1, Q2, Q3

    Dans beaucoup trop de copies, les candidats affirment à tort que tout vecteur de l'espace est vecteur propre de la matrice M, sans établir la formule attendue dans une base orthonormée de vecteurs propres.

  2. 2
    Inversibilité de A non invoquéeQ4

    L'inversibilité de A, pourtant nécessaire pour assurer l'existence et l'unicité de la limite z, est rarement invoquée par les candidats.

    « L'inversibilité de A a rarem ent été invoquée pour assurer l'existence et l'unicité de z »
  3. 3
    Oubli de la symétrie de AQ5

    De nombreux candidats oublient d'utiliser la symétrie de A pour évacuer un terme dans le calcul attendu.

    « à signaler l'oubli de la symétrie de A pour évacuer le terme »
  4. 4
    Confusions en calcul différentielQ6 à Q9

    Les notions de continuité, dérivabilité, différentiabilité et existence de dérivées partielles sont dans l'ensemble fort malmenées, avec des quotients de taux d'accroissement mal écrits.

  5. 5
    Contrainte d'appartenance à F ignoréePartie II

    De nombreux candidats se contentent de répéter les calculs de la première partie sans tenir compte de la contrainte que x doit appartenir au sous-espace F.

  6. 6
    Confusion entre minimum global et minimum restreintQ16, Q17, Q20, Q21

    Plusieurs questions de la seconde partie confondent le minimum de f sur l'espace entier et le minimum de sa restriction au sous-espace F, menant à une argumentation floue.

Ce qui a été bien réussi

  • Les meilleurs candidats ont pu explorer complètement l'énoncé, certains apportant une note personnelle sur la traduction de la seconde partie en termes d'extremum lié.
  • La question 27, qui rassemblait tous les résultats, a été très bien traitée dans les excellentes copies.
  • Le jury a constaté une augmentation de la prise en compte du soin et de la présentation des copies.

Conseils du jury

  • Éviter le grappillage au fil des questions et bien comprendre le rôle d'articulation de chaque question dans le déroulement du problème.
  • Traiter les questions dans l'ordre en respectant le déroulement logique de l'énoncé.
  • Indiquer clairement quelles questions sont admises et se concentrer sur la rigueur pour les autres.
  • Ne pas omettre les quantificateurs, dont l'absence contribue à un manque de rigueur.
  • Distinguer clairement condition nécessaire et condition suffisante dans une démonstration d'équivalence.
  • Soigner l'orthographe, des difficultés subsistant encore trop fréquemment selon le jury.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES. ÉCOLES NATIONALES SUPÉRIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE, DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY, DES TÉLÉCOMMUNICATIONS DE BRETAGNE. ÉCOLE POLYTECHNIQUE (Filière TSI).

CONCOURS D'ADMISSION 2003

ÉPREUVE DE MATHÉMATIQUES DEUXIÈME ÉPREUVEFiliè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-EIVP.
Les candidats sont priés de mentionner de façon apparente sur la première
page de la copie :
MATHÉMATIQUES 2-Filière 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 ℝ^n et x un vecteur inconnu de ℝ^n ou d'un sous-espace vectoriel F de ℝ^n.
Dans tout le problème, l'entier n est un entier naturel supérieur ou égal à 2 (n ≥ 2); la base canonique de ℝ^n est notée e_1, e_2, …, e_n; le produit scalaire de deux vecteurs x et y de ℝ^n est noté ( x|y ). La norme d'un vecteur x est notée ‖x‖.
Les matrices considérées sont réelles ; l'espace vectoriel des matrices carrées réelles d'ordre n est noté M_n(ℝ). Il est admis que l'application qui, à une matrice M de M_n(ℝ), associe la borne supérieure N(M) des normes des images par M des vecteurs unitaires de ℝ^n est une norme :
N(M) = sup_(‖x‖ = 1)‖M.x‖
Une matrice symétrique A est dite positive lorsque, pour tout vecteur x de ℝ^n, le produit scalaire des vecteurs A.x et x est positif ou nul (A.x|x) ≥ 0.

Première partie

Le but de cette partie est la résolution de l'équation A ⋅ x = b où A est une matrice carrée d'ordre n symétrique positive et inversible, b un vecteur donné de ℝ^n 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 ℝ^n, le produit scalaire ( M.x|x ) vérifie l'encadrement suivant :
p‖x‖^2 ≤ (M.x|x) ≤ q‖x‖^2.
Préciser ces deux réels p et q en fonction des valeurs propres de la matrice 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 λ_i(1 ≤ i ≤ n) de la matrice M :
N(M) = sup_(1 ≤ i ≤ n)|λ_i|
Étant donnés la matrice carrée, d'ordre n, symétrique positive A et le vecteur b, soit α un réel strictement positif strictement majoré par 2/λ_n(0 < α < 2/λ_n) où λ_n est la plus grande valeur propre de la matrice A; soit (x^k)_(k ∈ N) la suite définie par un premier vecteur x^0 choisi arbitrairement dans ℝ^n et par la relation de récurrence suivante : pour tout entier naturel k,
x^(k + 1) = x^k + α(b − A ⋅ x^k)
Étude de la suite (x^k)_(k ∈ N) :
4. Démontrer que la suite (x^k)_(k ∈ N) est une suite convergente de limite le vecteur z de l'espace ℝ^n, solution de l'équation A.x = b.
Soit f la fonction réelle, définie dans ℝ^n, par la relation :
f(x) = 1/2(A ⋅ x|x) − (b|x)

Minimum de f :

  1. Calcul préparatoire : démontrer que l'expression f(x + u) − f(x) se calcule en fonction des expressions (A ⋅ u|u), (A ⋅ x|u) et (b|u).
  2. Démontrer que la fonction f : x ⟼ f(x) admet des dérivées partielles (∂f)/(∂x_k)(1 ≤ k ≤ n) :
x ⟼ (∂f)/(∂x_k)(x).
Étant donné un vecteur x de ℝ^n, soit g(x) le vecteur de ℝ^n dont les coordonnées, dans la base canonique de ℝ^n, sont égales aux valeurs des dérivées partielles de la fonction f en ce point x :
g(x) = ∑_(k = 1)^n(∂f)/(∂x_k)(x)e_k.
  1. Exprimer ce vecteur g(x) au moyen de la matrice A et des vecteurs x et b.
Étant donnés deux vecteurs x et u de ℝ^n, soit I(x, u) l'expression suivante:
I(x, u) = f(x + u) − f(x) − (g(x)|u).
  1. Démontrer que, pour tout vecteur x donné, il existe deux constantes positives ou nulles r et s telles que, pour tout vecteur u, I(x, u) vérifie la relation suivante :
r‖u‖^2 ≤ I(x, u) ≤ s‖u‖^2.
  1. Démontrer que, pour que la fonction f admette en z un minimum, il faut et il suffit que le vecteur z vérifie la relation A.z = b.

Recherche du minimum de f :

Soit α un réel compris strictement entre 0 et 2/λ_n(0 < α < 2/λ_n).
10. Étant donné un vecteur x de ℝ^n, déterminer le signe de l'expression suivante
f(x − αg(x)) − f(x).
  1. Proposer, à partir de ce résultat, une méthode pour construire une suite de vecteurs (y^k)_(k ∈ N) qui converge vers le vecteur z en lequel la fonction f atteint son minimum ; la justification de la convergence n'est pas demandée.

Seconde partie

Le but de cette partie est de rechercher un vecteur x appartenant à un sousespace vectoriel F de ℝ^n qui vérifie l'équation A.x = b où A est une matrice carrée d'ordre n symétrique positive et inversible. Le sous-espace vectoriel F de ℝ^n est supposé être le noyau d'une matrice B appartenant à M_n(ℝ); ce noyau est supposé différent de tout l'espace ℝ^n ( kerB ≠ ℝ^n ).
L'équivalence, établie dans la première partie, entre d'une part résoudre l'équation A.x = b et d'autre part chercher le vecteur z rendant minimum la fonction f définie sur ℝ^n par la relation suivante
f(x) = 1/2(A ⋅ x|x) − (b|x),
conduit à se poser le problème suivant :
Soit B une matrice appartenant à M_n(ℝ) dont le noyau F est différent de ℝ^n; rechercher un vecteur x¯ appartenant à F rendant minimum la restriction de la fonction f au sous-espace vectoriel F.

Existence du minimum de la fonction f dans F :

  1. Démontrer que la fonction f possède la propriété suivante : pour tout réel c, il existe un réel ρ, tel que, pour tout vecteur x de F de norme supérieure ou égale à ρ(‖x‖ ≥ ρ), le réel f(x) est supérieur ou égal à c(f(x) ≥ c).
  2. En déduire que, si y est un point de F, il existe un réel r tel que pour tout vecteur x de F de norme supérieure ou égale à r(‖x‖ ≥ r), f(x) est supérieur ou égal à f(y).
  3. Démontrer à l'aide du résultat précédent qu'il existe au moins un vecteur x¯ du sous-espace vectoriel F en lequel la restriction de la fonction f à ce sousespace F atteint un minimum.
  4. Démontrer qu'il existe un seul vecteur x¯ en lequel la fonction f atteint son minimum dans F, en admettant que la fonction f est convexe ; c'est-à-dire : pour tout couple (x, y) ∈ ℝ^n × ℝ^n de vecteurs et tout réel λ appartenant à l'intervalle ouvert ]0, 1[, les valeurs prises par la fonction f vérifient la relation suivante :
f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y),
où l'inégalité est stricte si et seulement si les vecteurs x et y sont différents.

Propriétés du point x¯ :

  1. Démontrer que, pour qu'un vecteur y de F rende minimum la restriction de la fonction f au sous-espace vectoriel F, il faut et il suffit que le vecteur Ay − b soit orthogonal à ce sous-espace F de ℝ^n.
  2. Démontrer que la valeur prise par la fonction f au point x¯, en lequel elle atteint son minimum dans F, est donnée par la relation suivante :
f(x¯) = − 1/2(Ax¯|x¯) = − 1/2(b|x¯)

Le Lagrangien L :

Soit L la fonction définie sur l'espace produit ℝ^n × ℝ^n par la relation suivante
L(x, y) = f(x) + (y|Bx)
Un point (x^∗, y^∗) de l'espace produit ℝ^n × ℝ^n est dit point selle de la fonction L, s'il possède la propriété suivante : quel que soit le point (x, y) de l'espace produit ℝ^n × ℝ^n, les valeurs prises par la fonction L aux points ( x^∗, y ) , (x^∗, y^∗) et (x, y^∗) vérifient la double inégalité suivante :
L(x^∗, y) ≤ L(x^∗, y^∗) ≤ L(x, y^∗)

Propriétés du Lagrangien et de ses points selles :

  1. Établir l'inégalité suivante :
sup_(y ∈ ℝ^n)(inf_(x ∈ ℝ^n)L(x, y)) ≤ inf_(x ∈ ℝ^n)(sup_(y ∈ ℝ^n)L(x, y))
Il est supposé dans toute la suite qu'il existe un point selle (x^∗, y^∗) de la fonction L.
19. Démontrer que la valeur prise par la fonction L en un point selle ( x^∗, y^∗ ) vérifie les égalités suivantes :
L(x^∗, y^∗) = sup_(y ∈ ℝ^n)(inf_(x ∈ ℝ^n)L(x, y)) = inf_(x ∈ ℝ^n)(sup_(y ∈ ℝ^n)L(x, y))
  1. Démontrer, pour tout point (x_1, y_1) de ℝ^n × ℝ^n, les équivalences suivantes :
∀y, ∈, ℝ^n,L(x_1, y) ≤ L(x_1, y_1) ⟺ Bx_1 = 0.
  1. Soient x_1 un vecteur du sous-espace vectoriel F et y_1 un vecteur de ℝ^n. Démontrer qu'une condition nécessaire et suffisante pour que le couple ( x_1, y_1 )
    soit un point selle du Lagrangien L est que le vecteur x_1 réalise le minimum de la restriction de la fonction f à F et que les vecteurs x_1 et y_1 vérifient la relation suivante :
Ax_1 + ^t By_1 = 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^0 arbitraire de ℝ^n, une suite (ρ_m)_(m ∈ N) de réels, qui seront précisés plus loin, soient (x^m)_(m ∈ N) et (y^m)_(m ∈ N) les deux suites de vecteurs définies par les conditions suivantes :
  • Pour tout entier naturel m, le vecteur x^m est le vecteur qui rend minimum la fonction x ⟼ L(x, y^m).
  • Pour tout entier naturel m, le vecteur y^(m + 1) est défini par la relation suivante:
y^(m + 1) = y^m + ρ_m Bx^m
Existence des deux suites (x^m)_(m ∈ N) et (y^m)_(m ∈ N) :
22. Démontrer que les conditions énoncées permettent de déterminer tous les termes de ces deux suites (x^m)_(m ∈ N) et (y^m)_(m ∈ N) et que les vecteurs de ces suites vérifient, pour tout entier naturel m, les relations suivantes :
A(x^m − x^∗) + ^t B(y^m − y^∗) = 0,; y^(m + 1) − y^∗ = y^m − y^∗ + ρ_m B(x^m − x^∗).
où x^∗ et y^∗ sont les deux vecteurs d'un point selle de L.
23. En déduire l'égalité ci-dessous :
‖y^(m + 1) − y^∗‖^2 = ‖y^m − y^∗‖^2 − 2ρ_m(A(x^m − x^∗)|(x^m − x^∗)) + (ρ_m)^2‖B(x^m − x^∗)‖^2.
Convergence de la suite numérique de terme général ‖y^m − y^∗‖^2, m ∈ ℕ :
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^(1/2), telle que :
(A^(1/2))^2 = A
Soit C la matrice définie par la relation suivante :
C = A^(− 1/2) ⋅ ^t B ⋅ B ⋅ A^(− 1/2),
où la matrice A^(− 1/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 ν telle que, pour tout vecteur u de ℝ^n, l'inégalité cidessous soit vraie :
‖Bu‖^2 ≤ ν(Au|u)
Soient α et β deux réels tels que le segment [α, β] soit contenu dans l'intervalle ouvert ]0, 2/ν[, (0 < α < β < 2/ν). La suite des réels ρ_m est supposée vérifier pour tout entier naturel m l'inégalité suivante :
α ≤ ρ_m ≤ β.
  1. Démontrer que la suite de terme général ‖y^m − y^∗‖^2, m ∈ ℕ est monotone décroissante ; utiliser, pour simplifier, la suite (u^m)_(m ∈ N) dont le terme général est définie par la relation suivante :
u^m = x^m − x^∗
Convergence de la suite (x^m)_(m ∈ N) :
27. En déduire la convergence et la limite de la suite (x^m)_(m ∈ N).
FIN DU PROBLÈME

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet Mathématiques 2 Mines MP 2003 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet Mathématiques 2 Mines MP 2003 ?

Le sujet porte sur l'algèbre bilinéaire des matrices symétriques positives, le calcul différentiel et l'optimisation, à travers la résolution de l'équation Ax = b par les méthodes du gradient et du lagrangien.

Le sujet Mathématiques 2 Mines MP 2003 est-il difficile ?

Non, le rapport le qualifie explicitement de très abordable, avec un énoncé de longueur raisonnable, tout en ayant bien discriminé les candidats grâce à un écart-type important.

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet Mines Mathématiques 2 MP 2003 ?

La croyance erronée que tout vecteur est vecteur propre, l'oubli de la symétrie de A, des confusions en calcul différentiel et l'oubli de la contrainte d'appartenance au sous-espace F dans la seconde partie.

Ce sujet Mines Mathématiques 2 MP 2003 est-il adapté pour réviser l'optimisation sous contrainte ?

Oui, la seconde partie traduit la résolution sous contrainte en termes de recherche d'un extremum lié, ce qui en fait un bon exercice sur ce thème.

Pas de description pour le moment