WikiPrépaLivrets

Centrale Mathématiques 2 PC 2009Sujet, corrigé et rapport du jury

Pas encore noté
Logo concours Centrale

Explorer les annales

BanqueCentraleAnnée2009FilièrePCMatièreMathématiques
Annales Centrale PC MathématiquesCentrale PC 2009PC MathématiquesMathématiques 2009

Téléchargements

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

Présentation du sujet

Méthodes itératives de résolution d'un système linéaire Ax=b : méthode du gradient à pas constant et à pas optimal
Afficher ou masquer la section

Ce problème de mathématiques II, filière PC, étudie des méthodes itératives pour approcher la solution d'un système linéaire Ax=b où A est une matrice symétrique réelle définie positive. Il s'appuie sur la fonctionnelle J dont le minimum correspond à la solution du système, puis développe la méthode du gradient à pas constant à l'aide de normes matricielles et du rayon spectral, avant d'aborder la méthode du gradient à pas optimal.

  1. 1Partie I : la fonctionnelle JÉtude d'une fonctionnelle quadratique J dont le minimum correspond à la solution du système linéaire, avec une question préliminaire et une étude de quadriques.
  2. 2Partie II : méthode du gradient à pas constantNormes matricielles et rayon spectral, puis mise en œuvre de la méthode du gradient à pas constant pour approcher la solution du système.
  3. 3Partie III : méthode du gradient à pas optimalÉtude de la méthode du gradient à pas optimal, prolongeant les résultats des parties précédentes.

Ce qu'a observé le jury

5 erreurs relevées
Réciproque mal argumentée en I.A · Nomenclature des quadriques mal connue · Norme infinie mal caractérisée
Afficher ou masquer la section

Le jury observe que les résultats et méthodes d'algèbre linéaire paraissent familiers aux candidats sans être toujours parfaitement maîtrisés en dehors de leurs applications les plus classiques, et relève de nombreuses erreurs de calcul même sur des questions calculatoires simples. Les parties III sont très peu abordées, souvent par des candidats ayant échoué sur les parties précédentes.

Les erreurs les plus sanctionnées

  1. 1
    Réciproque mal argumentée en I.AI.A

    Beaucoup moins de candidats ont su argumenter correctement la réciproque de l'implication attendue, en exprimant la forme quadratique à l'aide des coordonnées dans une base orthonormée et des valeurs propres avec multiplicités.

  2. 2
    Nomenclature des quadriques mal connueI.B.d

    La détermination des quadriques pose des difficultés, et une fois celle-ci faite, la nomenclature est parfois mal connue, avec de nombreuses réponses erronées appelant à tort des surfaces des « cylindres ».

  3. 3
    Norme infinie mal caractériséeII.A.1

    La plupart des copies ne montrent que l'inégalité attendue sans établir l'égalité, et beaucoup se trompent sur le vecteur qui réalise le maximum.

  4. 4
    Lien entre norme et rayon spectral peu exploréII.A.5

    Très peu de candidats abordent cette question, pourtant fondamentale, qui relie la norme d'une matrice à son spectre via le théorème du rayon spectral.

  5. 5
    Parties finales rarement abordéesIII.A, III.B

    Bien peu de copies abordent la partie III, qui nécessitait une bonne connaissance des résultats établis en partie I ; les calculs y débouchent sur des fractions rationnelles peu simplifiables.

Ce qui a été bien réussi

  • La question II.B.1 a été convenablement traitée en général.
  • Beaucoup de candidats ont su établir l'implication du sens direct en I.A.
  • Un bon nombre de candidats a su résoudre la question II.B.3, proche de la notion de factorisation d'une application linéaire.
  • L'écriture du terme général du produit de Cauchy en III.A.2 est en général correcte.

Conseils du jury

  • Maîtriser les applications classiques de l'algèbre linéaire au-delà de leur seule reconnaissance.
  • Ne pas négliger les parties calculatoires : des calculs simples doivent être réussis sans erreur.
  • Réutiliser explicitement les résultats déjà établis dans les parties précédentes plutôt que de refaire un raisonnement complet.
  • Bien connaître la classification des quadriques et sa nomenclature précise.
  • Prendre le temps d'aborder les dernières parties du sujet, souvent délaissées faute de temps.

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

Les calculatrices sont autorisées

Notations et objet du problème

  • La notation 𝕂 désigne indifféremment l'ensemble ℝ des nombres réels ou l'ensemble ℂ des nombres complexes.
  • n désigne un entier supérieur ou égal à 1 .
  • On note M_n(𝕂) l'ensemble des matrices carrées d'ordre n ⩾ 1 à coefficients dans 𝕂. La matrice identité de M_n(𝕂) est notée I.
  • Dans tout le problème, on identifie les deux espaces vectoriels M_(n, 1)(𝕂) et 𝕂^n, c'est-à-dire qu'on identifie un vecteur de 𝕂^n avec le vecteur colonne de ses composantes dans la base canonique de 𝕂^n. De la sorte, si M ∈ M_n(𝕂) et x ∈ 𝕂^n, on peut former le produit Mx ∈ 𝕂^n, ce qui permet de définir l'endomorphisme f_M canoniquement associé à M par :
∀x ∈ 𝕂^n, f_M(x) = Mx.
L'image de f_M, (Imf_M) sera notée Im(M) et le noyau de f_M, (Kerf_M) sera noté Ker(M).
Pour toute matrice M de M_n(𝕂), on note σ(M) le spectre de M, c'est-à-dire l'ensemble de ses valeurs propres complexes. On note ρ(M) le rayon spectral de M, c'est-à-dire le plus grand module des valeurs propres de M.
  • On dira qu'une suite de 𝕂^n (respectivement de M_n(𝕂) ) converge, ou est convergente, si elle converge pour une norme particulière de 𝕂^n (respectivement de M_n(𝕂) ). On sait qu'elle converge alors pour toute norme de 𝕂^n (respectivement de M_n(𝕂) ) puisque ces espaces sont de dimension finie.
  • L'espace vectoriel ℝ^n est muni de son produit scalaire canonique, noté ⟨, ⟩. La norme euclidienne associée est notée || ||.
    Un endomorphisme symétrique f de ℝ^n est dit positif si, pour tout x de ℝ^n, ⟨f(x), x⟩ ⩾ 0.
    Un endomorphisme symétrique est dit défini positif si, pour tout x de ℝ^n, x non nul, ⟨f(x), x⟩ > 0.
    On dit de même qu'une matrice symétrique M ∈ M_n(ℝ) est positive si l'endomorphisme de ℝ^n canoniquement associé à M est positif, et qu'elle est définie positive si ce même endomorphisme est défini positif.
    Dans tout le problème, A ∈ M_n(ℝ) est une matrice symétrique, b ∈ ℝ^n est un vecteur fixé, et l'on étudie des méthodes itératives pour approcher la ou les solutions du système Ax = b.

Partie I - La fonctionnelle J

I.A - Question préliminaire

I.A.1) Montrer qu'une matrice symétrique M de M_n(ℝ) est positive si et seulement si son spectre σ(M) est inclus dans ℝ^+, et qu'elle est définie positive si et seulement si son spectre σ(M) est inclus dans ℝ^+∖{0}.
I.B - Cas particulier : n = 2
Dans cette question, on pose A = [13, − 4; − 4, 7] et b = ((75)/(− 75)). On définit la fonction F sur ℝ^2 à valeurs dans ℝ de la façon suivante :
pour tout v = ((x_1)/(x_2)) de ℝ^2, F(v) = 1/2⟨Av, v⟩ − ⟨b, v⟩.
a) Justifier que la fonction F est de classe C^1 sur ℝ^2.
La fonction gradient de F(gradF) est notée ∇F.
b) Prouver que :
∀v ∈ ℝ^2, ∇F(v) = Av − b.
c) En déduire que la fonction F admet un unique point critique sur ℝ^2.
d) Déterminer la nature géométrique de la surface Σ de ℝ^3 d'équation x_3 = F(x_1, x_2).
e) Déduire de la question précédente que la fonction F admet un minimum global sur ℝ^2, que l'on précisera.
I.C - On suppose dans cette question que la matrice A de M_n(ℝ) est symétrique positive et on définit l'application J de ℝ^n dans ℝ :
∀v ∈ ℝ^n, J(v) = 1/2⟨Av, v⟩ − ⟨b, v⟩.
appelée la fonctionnelle associée à A.
I.C.1) Prouver que, pour tout couple ( v, h ) de vecteurs de ℝ^n, on a :
⟨Av, h⟩ = ⟨Ah, v⟩.
On pose ∇J(v) = Av − b pour tout v ∈ ℝ^n.
I.C.2)
a) Expliciter la fonction R : ℝ^n → ℝ telle que
∀v, h ∈ ℝ^n, J(v + h) = J(v) + ⟨∇J(v), h⟩ + R(h).
Quel est le signe de R(h) ?
b) On suppose qu'un vecteur v_0 ∈ ℝ^n est tel que J(v) ⩾ J(v_0) pour tout v ∈ ℝ^n.
En observant que J(v_0 + th) ⩾ J(v_0) pour tout h ∈ ℝ^n et tout t ∈ ℝ, montrer que:
∇J(v_0) = 0
I.C.3) On suppose que la matrice A est symétrique définie positive.
a) Montrer qu'il existe un unique v_0 ∈ ℝ^n tel que J(v_0) = inf_(v ∈ ℝ^n)J(v), et le déterminer en fonction de A et b.
b) Soit v ∈ ℝ^n et d ∈ ℝ^n, d non nul.
Montrer qu'il existe un unique r ∈ ℝ tel que J(v − rd) = inf_(ρ ∈ ℝ)J(v − ρd).
Exprimer r en fonction de v, d et A.
I.C.4) On suppose encore que la matrice A est définie positive. Déterminer deux constantes α > 0 et m > 0 en fonction du spectre de A telles que:
⟨∇J(v) − ∇J(u), v − u⟩ ⩾ α‖v − u‖^2; ‖∇J(v) − ∇J(u)‖ ⩽ m‖v − u‖
pour tout couple ( u, v ) de vecteurs de ℝ^n.
I.C.5) On suppose que la matrice A est symétrique positive, mais non inversible, et que b appartient à Im(A). On note u_0 un élément de ℝ^n tel que Au_0 = b. Déterminer l'ensemble des vecteurs v_0 tels que J(v_0) = inf_(v ∈ ℝ^n)J(v) et préciser sa nature géométrique.

Partie II - Méthode du gradient à pas constant

II.A - Normes matricielles et rayon spectral

Une norme N sur M_n(ℂ) est dite subordonnée s'il existe une norme v sur ℂ^n telle que, pour tout M ∈ M_n(ℂ),
N(M) = max_(x ∈ ℂ^n, x ≠ 0)(v(Mx))/(v(x))
On dit que N est subordonnée à v.
II.A.1) On définit sur ℂ^n la norme ‖‖_∞ par:
∀x ∈ ℝ^n, x = (x_1, …, x_n), ‖x‖_∞ = max_(1 ⩽ i ⩽ n)|x_i|.
On note N_∞ la norme sur M_n(ℂ) subordonnée à ‖.‖_∞.
Montrer que, pour toute matrice M = (m_(ij)) ∈ M_n(ℂ), N_∞(M) = max_(1 ⩽ i ⩽ n)∑_(j = 1)^n|m_(ij)|.
II.A.2) Soit N une norme subordonnée sur M_n(ℂ).
a) Montrer que: ∀A, B ∈ M_n(ℂ), N(AB) ⩽ N(A) ⋅ N(B).
En déduire que: ∀n ∈ ℕ, N(A^n) ⩽ (N(A))^n.
b) Montrer que, pour tout M ∈ M_n(ℂ), ρ(M) ⩽ N(M).
II.A.3) Soit M = (m_(ij))_(1 ⩽ i, j ⩽ n) une matrice triangulaire supérieure de M_n(ℂ) ( c'est-à-dire m_(ij) = 0 si i > j ).
Soit α un nombre réel strictement positif, et P_α la matrice diagonale diag(1, α, ⋯, α^(n − 1)), c^′ est-à-dire dont le i-ème coefficient diagonal est α^(i − 1).
a) Calculer P_α^(− 1)MP_α.
b) En déduire que, pour tout ε > 0, il existe α > 0 tel que N_∞(P_α^(− 1)MP_α) ⩽ ρ(M) + ε.
II.A.4) Soit M une matrice de M_n(ℂ) et ε > 0 fixé.
a) Prouver l'existence d'une matrice P inversible et d'un réel α > 0 tel que :
N_∞(P_α^(− 1)P^(− 1)MPP_α) ⩽ ρ(M) + ε
b) En déduire qu'il existe une norme subordonnée N sur M_n(ℂ) telle que :
N(M) ⩽ ρ(M) + ε
II.A.5) Soit M ∈ M_n(ℂ) et c ∈ ℂ^n. On définit l'application f de ℂ^n dans ℂ^n par :
x ↦ Mx + c.
Montrer l'équivalence des assertions (i) et (ii) ci-dessous :
(i) Pour tout x_0 ∈ ℂ^n, la suite (x_k)_(k ∈ ℕ), définie par x_(k + 1) = f(x_k), est convergente, et sa limite est indépendante de x_0.
(ii) I − M est inversible et ρ(M) < 1.
Il pourra être utile d'introduire un réel ε > 0 et de choisir une norme subordonnée N sur M_n(ℂ) telle qu'on ait l'inégalité N(M) ⩽ ρ(M) + ε pour la matrice M considérée.

II.B - Méthode du gradient à pas constant

Soit A une matrice symétrique positive, mais pas nécessairement inversible, b un vecteur appartenant à l'espace Im(A), et J la fonctionnelle associée à A.
On note x_0 un élément de ℝ^n tel que b = Ax_0 On désigne par S une matrice symétrique définie positive donnée.
II.B.1) Montrer que l'application définie par φ(u, v) = ⟨Su, v⟩, pour tout couple ( u, v ) de vecteurs de ℝ^n, fournit un produit scalaire sur l'espace ℝ^n.
II.B.2) Montrer que les sous-espaces Im(S^(− 1)A) et Ker(A) sont orthogonaux pour le produit scalaire φ défini à la question précédente.
En déduire qu'ils sont supplémentaires.
II.B.3) Montrer que, dans Im(S^(− 1)A), le système linéaire Au = b possède une unique solution notée u^′. Décrire l'ensemble des solutions dans ℝ^n.
II.B.4) Étant donné un nombre réel γ, on définit la suite récurrente
u_(k + 1) = u_k − γS^(− 1)∇J(u_k)
pour tout k ∈ ℕ, u_0 ∈ ℝ^n étant arbitrairement choisi.
a) Montrer que la composante du vecteur u_k sur le sous-espace Ker(A), dans la décomposition ℝ^n = Im(S^(− 1)A) ⊕ Ker(A), est indépendante de k; on la note w.
b) Pour tout k, u_k s'écrit donc u_k = w + u_k^′ avec u_k^′ ∈ Im(S^(− 1)A). Préciser l'application f : Im(S^(− 1)A) → Im(S^(− 1)A) telle que u_(k + 1)^′ = f(u_k^′) pour tout k.
c) Montrer que les valeurs propres complexes de la matrice S^(− 1)A sont toutes réelles positives ou nulles.
Il pourra être utile de montrer que pour toute matrice X de M_(n, 1)(ℂ), X ≠ 0, ^t X¯SX > 0.
d) Montrer qu'on définit un automorphisme linéaire g de Im(S^(− 1)A) en posant g(x) = S^(− 1)Ax pour tout x ∈ Im(S^(− 1)A).
On note Λ_n la plus grande valeur propre de S^(− 1)A, et l'on suppose, jusqu'à la fin de cette partie, que 0 < γ < 2/(Λ_n).
e) Dans cette question, on note id l'endomorphisme identité de l'espace Im(S^(− 1)A). Montrer que le polynôme caractéristique de id − γg est scindé sur ℝ, et que le rayon spectral de id − γg est strictement inférieur à 1 .
f) En déduire que la suite (u_k^′)_(k ∈ ℕ) est convergente dans le sous-espace Im(S^(− 1)A). On note u^′ sa limite. On peut donc écrire :
lim_(k → + ∞)u_k = u^′ + w
g) Quelle relation le vecteur u^′ vérifie -t-il?

Partie III - Méthode du gradient à pas optimal

Dans cette partie, A ∈ M_n(ℝ) est symétrique définie positive. On note v_0 ∈ ℝ^n le vecteur tel que Av_0 = b.
On construit une suite (u_k)_(k ∈ ℕ) par récurrence :
  • on choisit u_0 ∈ ℝ^n et l'on pose d_0 = ∇J(u_0);
  • en supposant u_k déjà construit, on définit u_(k + 1) en fonction de u_k de la façon suivante :
    on pose d_k = ∇J(u_k) et on détermine r_k ∈ ℝ tel que J(u_k − r_k d_k) = inf_(ρ ∈ ℝ)J(u_k − ρd_k) (cf. I.C.3.b).
    On pose alors u_(k + 1) = u_k − r_k d_k. La suite (u_k)_(k ∈ ℕ) est donc bien définie, ainsi que la suite (d_k)_(k ∈ ℕ).
    III.A -
    III.A.1) Montrer que, pour tout entier k, ⟨d_(k + 1), d_k⟩ = 0.
    III.A.2) Montrer qu'il existe α > 0 dépendant du spectre de A tel que :
J(u_k) − J(u_(k + 1)) ⩾ α/2‖u_(k + 1) − u_k‖^2
III.A.3) Prouver que la suite (J(u_k))_(k ∈ ℕ) est convergente.
Montrer alors que lim_(k → ∞)||u_(k + 1) − u_k|| = 0.
III.A.4) Montrer que ‖d_k‖ ⩽ ‖d_k − d_(k + 1)‖, puis que lim_(k → + ∞)d_k = 0.
III.A.5) Montrer que ⟨∇J(u_k), u_k − v_0⟩ ⩾ α‖u_k − v_0‖^2. Prouver finalement que lim_(k → ∞)‖u_k − v_0‖ = 0.
III.B - Un exemple : n = 2, c > 0 est différent de 1, A est la matrice (1, 0; 0, c), et b = 0. On suppose que u_0 = ((x_0)/(y_0)) n'a aucune composante nulle. On construit la suite ( u_k ) par la méthode décrite dans cette partie. On note u_k = ((x_k)/(y_k))
III.B.1) Expliciter les composantes de u_(k + 1) en fonction de celles de u_k et de c. En déduire que pour tout k ∈ ℕ, les deux composantes de u_k sont différentes de 0 .
III.B.2) Montrer que le produit des coefficients directeurs de u_(k + 1) et u_k est une constante indépendante de k, que l'on déterminera. On rappelle que le coefficient directeur de u_k = ((x_k)/(y_k)) est t_k = (y_k)/(x_k).
III.B.3) Montrer que u_(k + 2) et u_k sont colinéaires, et calculer le coefficient de colinéarité. Illustrer géométriquement le comportement de la suite ( u_k ) pour c > 1.

Questions fréquentes

4 questions
Sur quels chapitres porte l'épreuve de mathématiques II de Centrale PC 2009 ?
Afficher ou masquer la section

Sur quels chapitres porte l'épreuve de mathématiques II de Centrale PC 2009 ?

Elle porte sur la résolution itérative d'un système linéaire Ax=b par des méthodes de gradient, en mobilisant l'algèbre linéaire (matrices symétriques, formes quadratiques) et les normes matricielles.

Quelles erreurs le jury a-t-il le plus relevées sur cette épreuve de maths II Centrale PC ?

Le jury signale des réciproques mal argumentées, une nomenclature des quadriques mal connue, de nombreuses erreurs de calcul et un lien entre norme matricielle et rayon spectral rarement exploré.

Faut-il traiter toutes les parties de ce sujet de maths II Centrale PC 2009 pour bien réussir ?

Non, le jury note que la partie III est rarement abordée et souvent par des candidats ayant échoué sur les parties précédentes ; mieux vaut consolider les parties I et II.

Ce sujet sur les méthodes du gradient de Centrale PC 2009 nécessite-t-il de bonnes bases en algèbre linéaire ?

Oui, le jury indique que les meilleures copies proviennent de candidats ayant une bonne culture en algèbre linéaire, capables aussi de comprendre les finalités et méthodes propres à l'énoncé.

Pas de description pour le moment