WikiPrépaLivrets

Centrale Mathématiques 2 MP 2008Sujet, corrigé et rapport du jury

Pas encore noté
Logo concours Centrale

Explorer les annales

BanqueCentraleAnnée2008FilièreMPMatièreMathématiques
Annales Centrale MP MathématiquesCentrale MP 2008MP MathématiquesMathématiques 2008

Téléchargements

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

Présentation du sujet

Difficulté moyenne
Décomposition LU des matrices carrées : méthode de Gauss, cas tridiagonal et résolution itérative de systèmes linéaires
Afficher ou masquer la section

Le sujet de mathématiques 2, Centrale MP 2008, est consacré à la décomposition LU des matrices carrées, outil central de l'algorithmique matricielle qui ramène la résolution d'un système de Cramer à deux résolutions de systèmes triangulaires. Il détaille la traduction matricielle de la méthode de Gauss, applique cette factorisation au cas particulier des matrices tridiagonales à travers un exemple explicite, puis étudie une méthode itérative de résolution d'un système linéaire.

  1. 1Partie I : méthode de Gauss et factorisationReprésentation matricielle de la méthode du pivot de Gauss à l'aide de matrices d'élimination, démonstration de l'existence et de l'unicité de la factorisation A = LU, écriture d'un algorithme et calcul de sa complexité.
  2. 2Partie II : applications et cas particuliersApplication de la factorisation LU à la résolution de systèmes linéaires et à l'inversion de matrices, étude du cas tridiagonal, puis d'un exemple explicite lié à la discrétisation d'une équation différentielle du second ordre.
  3. 3Partie III : une méthode itérativeÉtude de la norme matricielle subordonnée et du rayon spectral, convergence d'une suite vectorielle itérée vers la solution du système, puis application numérique à la matrice tridiagonale de la partie II et comparaison avec la méthode LU.

Difficulté moyenne. Le rapport indique que le niveau des copies s'est révélé extrêmement disparate : certaines montrent la maîtrise attendue face à des questions dans l'ensemble élémentaires, tandis que d'autres témoignent d'un manque évident de recul, y compris sur la première partie proche du cours de première année.

Ce qu'a observé le jury

6 erreurs relevées
Détour inutile pour reconstituer une matrice de forme quadratique · Combinaison linéaire de colonnes et déterminant mal formulée · Algorithme réduit à un vague principe
Afficher ou masquer la section

Le sujet, consacré à la décomposition LU, comportait des questions dans l'ensemble élémentaires mais le niveau des copies s'est révélé extrêmement disparate. La première partie, très proche du cours de première année, a paradoxalement été ressentie comme trop lointaine par de nombreux candidats qui l'ont délaissée, tandis que d'autres y ont glané l'essentiel de leurs points au prix de calculs laborieux. Les algorithmes demandés ont été très souvent ignorés ou mal compris. Le jury rappelle que le programme des épreuves réunit les deux années de classes préparatoires.

Les erreurs les plus sanctionnées

  1. 1
    Détour inutile pour reconstituer une matrice de forme quadratiqueII.C1

    Peu de candidats ont su traiter en un minimum de calculs cette question, qui ne demandait après tout que de reconstituer la matrice d'une forme quadratique dont une expression analytique était donnée : il était permis, voire conseillé, de démontrer que B égale A pour établir que A égale B.

    « il était permis, voire conseillé, de démontrer que B=A pour établir que A=B »
  2. 2
    Combinaison linéaire de colonnes et déterminant mal formuléePartie I

    Il est courant de lire qu'un déterminant ne change pas lorsque l'on effectue une combinaison linéaire de ses colonnes, formulation vague qui ne précise pas que l'opération licite revient à additionner à une colonne une combinaison des autres colonnes.

    « l’opération « licite » revient à additionner à une colonne une combinaison des autres colonnes »
  3. 3
    Algorithme réduit à un vague principeI.A1

    Les algorithmes demandés ont été très souvent ignorés ; parmi ceux qui s'y sont risqués, beaucoup font un contresens total en pensant que donner un algorithme revient à exposer un vague principe, tel que « on calcule les composantes de proche en proche ».

    « donner un algorithme revient à exposer un vague principe, tel que on calcule les composantes de proche en proche »
  4. 4
    Notion de matrice définie positive mal assimiléePartie II

    Le détour par la notion de matrice définie positive, nécessaire pour établir implicitement la propriété des mineurs emboîtés par les conditions de Sylvester, a laissé aux correcteurs une impression mitigée sur son assimilation.

  5. 5
    Recours injustifié au théorème du point fixePartie III

    Le recours au théorème du point fixe, hors programme, est souvent constaté dans les copies alors qu'il était bien inutile puisque l'existence de ce point fixe était préalablement acquise dans le contexte du problème.

    « le recours au théorème du point fixe »
  6. 6
    Flou sur le signe strict ou large des sommesII.C1

    Les correcteurs ont noté un flou savamment entretenu quant au signe des sommes, qualifiées de positives alors qu'il était crucial de préciser s'il s'agissait d'une positivité stricte ou au sens large.

Ce qui a été bien réussi

  • Dans certaines copies, on trouve la preuve de la maîtrise que l'on est en droit d'attendre de candidats confrontés à des questions dans l'ensemble élémentaires.
  • Le jury a constaté avec plaisir que, dans un certain nombre de copies, les algorithmes et les calculs de complexité sont commentés de façon constructive et intelligente.

Conseils du jury

  • Lire attentivement le sujet et retenir tout au long de l'épreuve les hypothèses et propriétés mises en jeu dans l'énoncé.
  • Écrire un véritable algorithme et non se contenter d'énoncer un principe général.
  • Préciser sans ambiguïté si une inégalité ou une positivité est stricte ou au sens large.
  • Ne pas se limiter à un ordre de grandeur quand l'énoncé attend un calcul précis, notamment pour les calculs de complexité.
  • Numéroter systématiquement les questions et ne pas répondre à côté de ce qui est demandé.
  • Connaître l'intégralité du programme des deux années de classes préparatoires, sans stratégie d'impasse.

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

Épreuve: MATHÉMATIQUES II

Notations
  • Dans tout le problème n est un entier supérieur à 2, M_n est l'ensemble des matrices carrées à n lignes, à coefficients réels.
  • On note ( E_(ij), 1 ⩽ i ⩽ n, 1 ⩽ j ⩽ n ) la base canonique de M_n. Ainsi, pour tout couple ( i, j ) d'entiers compris entre 1 et n, tous les coefficients de la matrice E_(ij) sont nuls sauf le coefficient d'indices ( i, j ) qui vaut 1 . On rappelle le résultat suivant :
∀i, j, k, l ∈ {1, …, n}, E_(ij)E_(kl) = δ_(jk)E_(il)
où δ_(jk) = 1 si j = k et 0 sinon.
  • Pour tout couple ( p, q ) d'entiers strictement positifs, on note M_(p, q) l'espace vectoriel des matrices à p lignes et q colonnes, à coefficients réels.
  • Pour toute matrice M de M_(p, q), on note ^t M sa matrice transposée.
  • L'espace ℝ^n est identifié à l'espace M_(n, 1). On note B = (e_1, …, e_n) la base canonique de ℝ^n. Ainsi, pour tout entier k compris entre 1 et n, e_k = ^t(0, …, 0, 1, 0…, 0) où 1 est en k^(ième) position.
    On munit ℝ^n de sa structure euclidienne canonique.
    Pour tout couple ( u, v ) de vecteurs de ℝ^n, u = ^t(u_1, …, u_n) et v = ^t(v_1, …, v_n), on note ⟨u, v⟩ = ^t u.v = ∑_(k = 1)^n u_k v_k leur produit scalaire.
  • Pour tout couple d'entiers p, q tels que p ⩽ q, on note :
[[p, q]] = {k ∈ ℕ, p ⩽ k ⩽ q}.
  • Étant donné ^t(α_1, α_2, …, α_n) ∈ ℝ^n, on note D = diag(α_1, α_2, …, α_n) ∈ M_n la matrice diagonale telle que, pour tout i de [[1, n]], d_(ii) = α_i.
    On note I_n = diag(1, 1, …, 1) la matrice de l'identité.
    Soit A = [a_(ij)]_(1 ≤ i, j ≤ n) ∈ M_n. On considère le système linéaire
Au = w
où w = ^t(w_1, …, w_n) ∈ ℝ^n est donné, et u = ^t(u_1, …, u_n) est l'inconnue. L'objet du problème est l'étude de quelques méthodes de résolution de ce système linéaire. On rappelle que ∑_(k = 1)^n k = (n(n + 1))/2, ∑_(k = 1)^n k^2 = (n(n + 1)(2n + 1))/6.

Partie I - Méthode de Gauss et factorisation

Le but de cette partie est de représenter matriciellement la méthode de Gauss pour la résolution du système (1).
On note TS_n ⊂ M_n l'ensemble des matrices M = [m_(ij)]_(1 ≤ i, j ≤ n) triangulaires supérieures (c'est-à-dire m_(ij) = 0 pour i > j ) et TI_n ⊂ M_n l'ensemble des matrice triangulaires inférieures à diagonale unité (c'est-à-dire m_(ii) = 1 et m_(ij) = 0 pour i < j ). Dans toute cette partie, on suppose que det(A) ≠ 0, de sorte que le système
(1) admette une unique solution u = ^t(u_1, …, u_n) ∈ ℝ^n.

I.A - Résolution d'un système triangulaire

On suppose dans cette question que A ∈ TS_n.
I.A.1) Calculer u_n puis pour k ∈ [[1, n − 1]] exprimer u_(n − k) en fonction de u_n, u_(n − 1), …, u_(n − k + 1). Écrire l'algorithme de résolution du système (1).
I.A.2) Exprimer en fonction de n le nombre d'additions, de multiplications et de divisions nécessaires à la résolution du système (1).

I.B - Matrices d'élimination de Gauss

La matrice A de M_n est de nouveau quelconque avec detA ≠ 0.
Étant donné M = [m_(ij)]_(1 ≤ i, j ≤ n) ∈ M_n, on note pour tout entier q de [[1, n]], Δ_q(M) la sous-matrice de M définie par Δ_q(M) = [m_(ij)]_(1 ⩽ i, j ⩽ q) élément de M_q, et on note D_q(M) = detΔ_q(M)(D_1(M), …, D_n(M) sont appelés les mineurs principaux de M).
Par ailleurs, on note L_i(M) le i^(ième) vecteur ligne de la matrice M et défini par L_i(M) = (m_(i1), m_(i2), …, m_(in)). On note aussi C_j(M) le j^(ième) vecteur colonne de M défini par C_j(M) = ^t(m_(1j), m_(2j), …, m_(nj)). On dira aussi dans la suite les lignes L_i de M et les colonnes C_j de M.
I.B.1) Soient M une matrice de M_n et P = MA. Exprimer, pour tout entier q de [[1, n]], L_q(P) en fonction des lignes L_i(A) de la matrice A.
(On pourra, si l'on veut, utiliser la décomposition de L_q(P) sous la forme ∑_(j = 1)^n p_(qj)E_(qj) avec P = (p_(ij))_(1 ⩽ i, j ⩽ n)).
I.B.2) Pour un entier k de [[1, n − 1]] et un vecteur β = ^t(β_(k + 1), …, β_n) ∈ ℝ^(n − k), on note F(k, β) la matrice de M_n qui réalise par le produit à gauche P = F(k, β)A les combinaisons linéaires de lignes suivantes, en notant pour simplifier L_i = L_i(A) et L_i^′ = L_i(P) :
∀i ∈ [[1, k]], L_i^′ = L_i et ∀i ∈ [[k + 1, n]], L_i^′ = L_i + β_i L_k
a) Montrer que F(k, β)^(− 1) = F(k, − β).
b) Montrer que si P = F(k, β)A on a :
∀q ∈ [[1, n]], D_q(P) = D_q(A)
c) Déterminer les coefficients ε_(ij) de F(k, β) pour tout couple (i, j) d'entiers de [[1, n]] × [[1, n]]. Montrer que F(k, β) ∈ TI_n.
I.B.3)
a) Étant donnée une matrice M = [m_(ij)]_(1 ≤ i, j ≤ n) de M_n, exprimer les vecteurs colonnes C_j^′ du produit matriciel MF(k, β) en fonction des colonnes C_j de M.
b) Soit q un entier de [[1, n]] et pour tout entier k de [[1, q]], β_k = ^t(β_(k + 1, k), …, β_(n, k)) un vecteur de ℝ^(n − k). On considère la matrice produit
P_q = F(1, β_1) ⋅ F(2, β_2)…F(q, β_q) = ∏_(k = 1)^q F(k, β_k)
On note C_j^q les vecteurs colonnes de la matrice P_q et pour tout entier k de [[1, q]], b_k = ^t(0, …, 0, 1, β_(k + 1, k), …, β_(n, k)) ∈ ℝ^n.
Montrer par récurrence sur q que :
∀j ∈ [[q + 1, n]], C_j^q = e_j et ∀j ∈ [[1, q]], C_j^q = b_j.
En déduire que P_q appartient à TI_n et que P_(n − 1) = [b_1, …, b_(n − 1), e_n].

I.C - Factorisation de A

Dans cette question, on suppose que pour chaque k ∈ [[1, n]], Δ_k(A) est inversible. On note A_1 = A = [a_(ij)^1]_(1 ⩽ i, j ⩽ n) la matrice initiale.
I.C.1) Montrer que a_(11)^1 ≠ 0. Déterminer β_1 = ^t(β_(21), …., β_(n1)) ∈ ℝ^(n − 1) pour que la première colonne de A_2 = F(1, − β_1)A_1 soit proportionnelle à e_1. Que vaut la première ligne de A_2 ?
I.C.2) On pose F_1 = F(1, − β_1).
a) Montrer par récurrence sur k l'existence des suites de matrices (F_(k − 1))_(2 ⩽ k ⩽ n), (A_k)_(2 ⩽ k ⩽ n) avec
F_(k − 1) = F(k − 1, − β_(k − 1)) A_k = [a_(ij)^k]_(1 ⩽ i, j ⩽ n) = F_(k − 1)A_(k − 1)
et telles que :
∀j ∈ [[1, k − 1]], ∀i ∈ [[j + 1, n]], a_(ij)^k = 0 et ∀m ∈ [[1, n]], D_m(A_k) ≠ 0
Exprimer le vecteur β_k à l'aide des coefficients de A_k.
b) Montrer que les lignes 1 à k de A_k et A_(k + 1) sont identiques.
c) Pour k ∈ [[1, n − 1]], soit N_k le nombre de multiplications nécessaires pour passer de A_k à A_(k + 1). Calculer le nombre N_k.
I.C.3)
a) Déduire des questions précédentes qu'il existe une matrice L de TI_n et une matrice U de TS_n telles que l'on ait
A = LU
b) Exprimer les coefficients l_(ij) de L pour i > j et les coefficients u_(ij) de U pour i ⩽ j en fonction des coefficients a_(ij)^k des matrices A_k (Utiliser (I.B.2a) et (I.C.2a)).
I.C.4) Montrer que les matrices L et U de la factorisation (5) sont uniques.
I.C.5) Écrire dans le langage de son choix un programme réalisant la factorisation A = LU qui n'utilise qu'un seul tableau carré encore nommé A pour contenir toutes les itérations A_k. On prendra soin de commenter les principales lignes du programme. Comment aura-t-on en final les facteurs L et U à partir du tableau A ?
I.C.6) Soit S_n le nombre de multiplications nécessaires à la factorisation A = LU. Calculer S_n (Indication : utiliser la question I.C.2.c.)

Partie II-Applications et cas particuliers

Dans cette partie, on applique à certains exemples la factorisation vue en Partie I. Par commodité d'écriture, lorsque l'on représente une matrice, les espaces laissés vides sont remplis de 0 qui ne sont pas systématiquement écrits.

II.A - Application à la résolution de systèmes linéaires

II.A.1) On veut résoudre le système (1) en utilisant la factorisation (5). On fait toujours l'hypothèse que pour tout entier k de [[1, n]], D_k(A) ≠ 0.
Sans compter les opérations nécessaires à la factorisation, montrer qu'il suffit de n(n − 1) multiplications pour résoudre le système (préciser la méthode utilisée).
II.A.2) En déduire une méthode pour inverser la matrice A en utilisant la factorisation (5). Exprimer le nombre total de multiplications et divisions nécessaires à cette inversion, incluant cette fois-ci le calcul de la factorisation. En donné un équivalent lorsque n → ∞.

II.B - Étude du cas tridiagonal

On suppose la matrice A tridiagonale, c'est-à-dire de la forme
A = (b_1, c_1; a_2, b_2, c_2; ⋅, ⋅, ⋅; ⋅, ⋅, ⋅; ⋅, ⋅, ⋅; a_(n − 1), b_(n − 1), c_(n − 1); a_n, b_n)
II.B.1) On pose δ_k = D_k(A), δ_0 = 1. On suppose que pour tout k de [[1, n]], δ_k ≠ 0. Calculer δ_1 puis, pour k ∈ [[2, n]], exprimer δ_k en fonction de δ_(k − 1) et de δ_(k − 2).
II.B.2) Montrer que les matrices L et U de la factorisation (5) sont de la forme
L = (1; l_(21), 1; l_(32), 1; ⋅, ⋅; ⋅, ⋅; 1; l_(nn − 1), 1)
avec pour tout i de [[2, n]], l_(i, i − 1) = a_i(δ_(i − 2))/(δ_(i − 1)),
U = ((δ_1)/(δ_0), c_1; (δ_2)/(δ_1), c_2; (δ_3)/(δ_2), ⋅; ⋅, ⋅; ⋅, ⋅; c_(n − 1); (δ_n)/(δ_(n − 1)))
II.B.3) Écrire un algorithme de résolution du système Au = w en utilisant la
factorisation précédente pour une matrice tridiagonale. Donner le nombre de multiplications, de divisions et d'additions nécessaires à cette résolution.

II.C - Étude d'un exemple

Soit A_n = [a_(ij)]_(1 ⩽ i, j ⩽ n) ∈ M_n, symétrique et tridiagonale définie par
∀i ∈ [[1, n]], a_(ii) = 2, ∀i ∈ [[2, n − 1]], a_(i + 1) = a_(i − 1) = − 1, a_(12) = a_(nn − 1) = − 1
tous les autres coefficients étant nuls, c'est-à-dire
A_n = (2, − 1; − 1, 2, − 1; ⋅, ⋅, ⋅; ⋅, ⋅, ⋅; ⋅, ⋅; − 1, 2; − 1; 2)
II.C.1)
a) Montrer que pour chaque v = ^t(v_1, …, v_n) de ℝ^n, on a
< A_n v, v>=v_1^2 + v_n^2 + ∑_(i = 2)^n(v_i − v_(i − 1))^2
b) En déduire que la matrice A_n est définie positive.
c) Montrer que pour chaque k de [[1, n]] la matrice Δ_k(A_n) est symétrique et définie positive. En déduire qu'il existe une factorisation A_n = L_n U_n de la forme (5).
II.C.2) On reprend les notations de la question II.B. Expliciter et résoudre la récurrence sur δ_k. En déduire l'expression des matrices L_n et U_n.
II.C.3) On veut résoudre le système A_n x = e_k pour un entier fixé k ∈ [[1, n]].
a) Résoudre le système L_n y = e_k.
b) Résoudre le système U_n x = y.
(On montrera que : x_i = (i(n + 1 − k))/(n + 1) si i ⩽ k et x_i = (k(n + 1 − i))/(n + 1) si i ⩾ k ).
II.C.4) On pose A_n^(− 1) = [b_(ij)]_(1 ≤ j, k ≤ n). Calculer b_(ij) pour (i, j) ∈ [[1, n]] × [[1, n]].

Partie III - Une méthode itérative

III.A -

Soit A = [a_(ij)]_(1 ≤ i, j ≤ n) une matrice inversible de M_n. On étudie ici une méthode itérative de résolution du système (1). On utilise la norme euclidienne sur ℝ^n, définie par‖x‖^2=<x, x>=∑_(k = 1)^n x_k^2, avec x = ^t(x_1, …, x_n) ∈ ℝ^n. On rappelle que la norme matricielle subordonnée de A ∈ M_n est définie par ‖A‖ = sup_(‖x‖ = 1)‖Ax‖.
III.A.1)
a) Exprimer ‖Ax‖^2 en fonction de B = ^t A.A et de x. En déduire que B est une matrice symétrique positive.
On note sp(B) = {λ_1(B), …, λ_n(B)} le spectre de B, c'est-à-dire l'ensemble des valeurs propres de B énoncées de sorte que λ_1(B) ≤ … ≤ λ_n(B).
b) Montrer que ‖A‖ = √(λ_n(B)).
c) On suppose que A est symétrique et on note ρ(A) = max_(λ ∈ sp(A))|λ|, où sp(A) est l'ensemble des valeurs propres de A. Montrer que l'on a ‖A‖ = ρ(A).
III.A.2) On note H une matrice de M_n et c un vecteur de ℝ^n tels que le système (1) peut se réécrire sous la forme
u = Hu + c
Soit U_0 ∈ ℝ^n. On considère la suite vectorielle itérée (U_k)_(k ∈ ℕ) définie par la relation de récurrrence U_(k + 1) = HU_k + c. Montrer que, si ‖H‖ < 1, la suite (U_k)_(k ∈ ℕ) est convergente dans ℝ^n de limite u, solution de l'équation (7).
III.A.3) Dans les questions qui suivent, on applique la méthode itérative ci-dessus au système A_n u = w où A_n est définie en II.C par (6). On décompose A_n en
A_n = 2I_n − M_n
a) Calculer les valeurs propres de M_n (Indication : interpréter le système M_n x = λx comme une équation récurrente sur la suite (x_k)_(0 ⩽ k ⩽ n + 1) avec x_0 = x_(n + 1) = 0. (On constatera qu'il n'y a de solution non nulle que si |λ| < 2 ).
b) En déduire qu'il existe une suite de réels (μ_n)_(n ∈ ℕ) telle que
∀n ∈ ℕ^⋆, μ_n > 0, lim_(n → ∞)μ_n = 0, ‖M_n‖ = 2 − μ_n
c) Donner un équivalent de μ_n quand n tend vers l'infini.
III.A.4) On considère la décomposition (8). On choisit la donnée initiale U_0 de sorte que ‖U_0‖ = 1. On suppose en outre que ‖w‖ = 1.
a) On choisit H = (M_n)/2. Expliciter le vecteur c de manière à appliquer la méthode itérative puis donner l'expression complète de U_k en fonction de U_0, de c et des matrices H^m pour m ∈ [[1, k]].
b) Majorer l'erreur ε_k = ‖U_k − u‖ en fonction de k, μ_n et ‖A_n^(− 1)‖.
c) Montrer que lim_(n → ∞)‖A_n^(− 1)‖ = + ∞ et donner un équivalent de ‖A_n^(− 1)‖ pour n tendant vers l'infini.
d) Déterminer un nombre d'itérations k suffisant pour avoir ε_k < 10^(− 4). Donner un équivalent du nombre de multiplications pour obtenir cette approximation et comparer à la méthode de factorisation LU. Pour n grand, quelle méthode est préférable?

Questions fréquentes

4 questions
Sur quels chapitres porte l'épreuve de mathématiques 2 Centrale MP 2008 ?
Afficher ou masquer la section

Sur quels chapitres porte l'épreuve de mathématiques 2 Centrale MP 2008 ?

Le sujet porte sur la décomposition LU des matrices carrées : méthode de Gauss, matrices tridiagonales et définies positives, puis une méthode itérative de résolution de systèmes linéaires basée sur la norme subordonnée.

Quelle est la moyenne à l'épreuve de mathématiques 2 Centrale MP 2008 ?

Le rapport ne communique aucune moyenne ni écart-type chiffrés pour cette épreuve.

Quelles erreurs le jury a-t-il le plus relevées à cette épreuve de mathématiques 2 Centrale MP 2008 ?

Le jury relève des algorithmes très souvent ignorés ou réduits à un vague principe, une notion de matrice définie positive mal assimilée, un recours injustifié au théorème du point fixe, et un flou sur le caractère strict ou large de certaines inégalités.

Cette épreuve de mathématiques 2 Centrale MP 2008 est-elle difficile ?

Le niveau des copies est décrit comme extrêmement disparate : la première partie, proche du cours de première année, était accessible mais a été délaissée par beaucoup, tandis que la partie sur la méthode itérative demandait une bonne compréhension de la topologie.

Pas de description pour le moment