WikiPrépaLivrets

X ENS Mathématiques PSI 2019Sujet et corrigé

Pas encore noté
Logo concours X-ENS

Explorer les annales

BanqueX-ENSAnnée2019FilièrePSIMatièreMathématiques
Annales X-ENS PSI MathématiquesX-ENS PSI 2019PSI MathématiquesMathématiques 2019

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Lire en ligneLaTeXWord
  • Rapport du jury : non disponible

Présentation du sujet

Résolution effective d'un système linéaire symétrique défini positif par la méthode du gradient conjugué
Afficher ou masquer la section

Le problème construit et étudie la méthode du gradient conjugué pour résoudre Ax = b lorsque A est symétrique définie positive. Il établit d'abord des outils sur les matrices symétriques et la norme associée à A, montre que le vecteur solution minimise une fonctionnelle quadratique, obtient une majoration de l'erreur par les polynômes de Tchebychev, puis retrouve l'algorithme du gradient conjugué à partir d'une famille de directions orthogonales.

  1. 1Partie I : outils sur les matrices symétriquesÉtablit des propriétés des matrices symétriques définies positives, de la norme matricielle subordonnée et de la racine carrée d'une telle matrice.
  2. 2Partie II : sous-espaces de KrylovConstruit les sous-espaces engendrés par les polynômes en A appliqués au résidu initial et étudie leur dimension.
  3. 3Partie III : minimisation et majoration de l'erreurMontre que le vecteur solution minimise une fonctionnelle quadratique sur les sous-espaces de Krylov et majore l'erreur à l'aide des polynômes de Tchebychev.
  4. 4Partie IV : algorithme du gradient conjuguéConstruit une famille de directions orthogonales pour A et retrouve les relations de récurrence de l'algorithme du gradient conjugué.

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

Maths - X-ENS PSI 2019

Avertissement : Ce problème est très mal construit et très mal rédigé, pas toujours dans l'esprit du programme de spé mais pourrait faire un sujet intéressant avec un peu de travail pour reprendre l'énoncé.

Notations

Soit N ≥ 2 un entier. On munit l'espace ℝ^N du produit scalaire canonique
⟨x, y⟩ = ∑_(i = 1)^N x_i y_i
et de la norme associée ‖x‖ = ⟨x, x⟩^(1/2).
On note M_N(ℝ) l'espace vectoriel réel des matrices carrée d'ordre N à coefficients réels, S_N(ℝ) ⊂ M_N(ℝ) le sous-espace vectoriel réel des matrices symétriques et S_N^+(ℝ) l'ensemble (des matrices symétriques définies positives) défini de la façon suivante :
S_N^+(ℝ) = {A ∈ S_N(ℝ)|⟨Ax, x⟩ > 0 pour tout x ∈ ℝ^N, x ≠ 0}
Pour tout polynôme P(X) = c_k X^k + c_(k − 1)X^(k − 1) + ⋯ + c_0 ∈ ℝ[X] et toute matrice M dans M_N(ℝ), on note P(M) la matrice
P(M) = c_k M^k + c_(k − 1)M^(k − 1) + ⋯ + c_0 I_N ∈ M_N(ℝ)
où I_N ∈ M_N(ℝ) est la matrice identité.
Pour toute matrice M ∈ M_N(ℝ), on note M^T sa transposée.
On rappelle le théorème spectral : toute matrice A ∈ S_N(ℝ) admet une base orthonormale de vecteurs propres. En particulier, si l'on note λ_1 < ⋯ < λ_d les d valeurs propres de A (distinctes deux à deux), et F_1, …, F_d les sous-espaces propres associés, ℝ^N est somme directe orthogonales des F_i, c'est-à-dire que tout x ∈ ℝ^N s'écrit de façon unique
x = ∑_(i = 1)^d x_i
où p_(F_i) est la projection orthogonale de ℝ^N sur F_i.
Ce problème porte sur la résolution effective du problème Ax = b, où A ∈ S_N^+(ℝ), plus précisément sur la construction et l'étude, à partir d'un vecteur initial x_0 arbitraire, d'une suite x_0, x_1, …, x_k, … de ℝ^N, qui s'identifie à la solution x~ du système précédent au-delà d'un certain rang, et telle que x_k se rapproche dans un certain sens de x~ en deça de ce rang.

Problème

Partie I

  1. Soit A ∈ S_N(ℝ). Montrer que A ∈ S_N^+(ℝ) si et seulement si les valeurs propres de A sont toutes réelles strictement positives.
  2. Pour toute matrice B ∈ M_N(ℝ), on pose ‖B‖‖ = sup_(‖x‖ = 1)‖Bx‖.
Après avoir justifié l'existence de ‖‖B‖‖, montrer que B ↦ ‖B‖‖ est une norme sur M_N(ℝ) vérifiant
∀x ∈ ℝ^N ‖Bx‖ ≤ ‖B‖‖‖x‖.
  1. Soit A ∈ S_N(ℝ) une matrice de valeurs propres (non nécessairement distinctes) λ_1, …, λ_N. Montrer que
‖A‖‖ = max_(1 ≤ i ≤ N)|λ_i|.
  1. Soit A ∈ S_N^+(ℝ). Pour tout x ∈ ℝ^N, on pose ‖x‖_A = ⟨x, Ax⟩^(1/2).
    a) Montrer que l'application x ↦ ‖x‖_A est une norme sur ℝ^N.
    b) Montrer qu'il existe des constantes C_1 et C_2 strictement positives, que l'on exprimera en fonction des valeurs propres de A, telles que
∀x ∈ ℝ^N C_1‖x‖ ≤ ‖x‖_A ≤ C_2‖x‖.
  1. Soit A ∈ S_N(ℝ) et soit P ∈ ℝ[X] un polynôme. Montrer que P(A) ∈ S_N(ℝ) et préciser les valeurs propres et vecteurs propres de P(A) en fonction de ceux de A.
  2. Soit A ∈ S_N^+(ℝ). On note 0 < λ_1 < ⋯ < λ_d les d valeurs propres de A (distinctes deux à deux) et et F_1, …, F_d les sous-espaces propres associés. On considère l'application linéaire de ℝ^N dans ℝ^N :
x ↦ ∑_(i = 1)^d λ_i^(1/2)p_(F_i)(x),
où p_(F_i) est la projection orthogonale (pour le produit scalaire canonique) sur F_i. On note A^(1/2) la matrice associée à cette application linéaire dans la base canonique.
a) On écrit A = UDU^T, où D ∈ M_N(ℝ) est la matrice diagonale qui contient les valeurs propres de A dans l'ordre croissant, avec leurs ordres de multiplicité, et U une matrice orthogonale. On note D^(1/2) la matrice diagonale dont les coefficients diagonaux sont les racines carrées de ceux de D. Montrer que A^(1/2) = UD^(1/2)U^T.
b) Montrer que A^(1/2) ∈ S_N^+(ℝ), que A^(1/2)A^(1/2) = A, et que A^(1/2) commute avec A.
c) Montrer que, pour tout x ∈ ℝ^N, ‖x‖_A = ‖A^(1/2)x‖, où ‖x‖_A est la norme définie à la question 4 .

Partie II

Soit A ∈ S_N^+(ℝ). On supposera dans toute la suite du problème que la matrice A n'est pas proportionnelle à l'identité.
On se donne b ∈ ℝ^N et l'on note x~ ∈ ℝ^N l'unique vecteur qui vérifie Ax~ = b. On se donne un vecteur x_0 ∈ ℝ^N, différent de x~, et l'on note r_0 = b − Ax_0. On pose H_0 = {0} et pour k ≥ 1,
H_k = {P(A)r_0|P ∈ ℝ[X], deg(P) ≤ k − 1},
où deg(P) ∈ ℕ désigne le degré du polynôme P.
7. Montrer que les H_k forment une suite de sous-espaces vecgtoriels de ℝ^N, et montrer que H_k ⊂ H_(k + 1) pour tout k ∈ ℕ.
a) Montrer qu'il existe nécessairement k tel que H_(k + 1) = H_k. On note alors m le plus petit entier k tel que H_(k + 1) = H_k.
b) Montrer que dim(H_k) = m pour tout k ≥ m, et que dim(H_k) = k pour k ≤ m.
8. On note d le nombre de valeurs propres distinctes de A.
a) Dans le cas particulier où r_0 est un vecteur propre de A, montrer que l'entier m de la question précédente est égal à 1 .
b) Dans le cas général, montrer que m est inférieur ou égal à d.
c) Pour tout entier n entre 1 et d, construire un x_0 tel que l'entier m de la question 7 soit égal à n.
d) Montrer que l'ensemble des x_0 pour lesquels la dimension m est exactement égale à d est le complémentaire d'une union finie d'ensembles de la forme x~ + E, où E est un espace vectoriel de dimension inférieure ou égale à N − 1.
9. Montrer qu'il existe un polynôme Q de degré m (entier défini dans la question 7 ) tel que Q(A)e_0 = 0, où e_0 = x_0 − x~.
10. Montrer que le polynôme Q de la question précédente vérifie Q(0) ≠ 0.
11. On définit x_0 + H_k comme le sous-ensemble des points de ℝ^N de la forme x_0 + x où x décrit l'espace vectoriel H_k.
a) Montrer que x~ ∈ x_0 + H_m.
b) Montrer que, pour tout k ∈ {0, …, m − 1}, on a x~ ∉ x_0 + H_k.

Partie III

On garde dans cette partie les notations de la partie II. On introduit l'application
J : ℝ^N, → ℝ; x, ↦ 1/2⟨x, Ax⟩ − ⟨b, x⟩.
  1. Pour tout x ∈ ℝ^N, exprimer ‖x − x~‖_A^2 = ⟨x − x~, A(x − x~)⟩ en fonction de J(x~) et de J(x) et en déduire que x~ est l'unique minimiseur de J sur ℝ^N, c'est-à-dire que J(x~) ≤ J(x) pour tout x ∈ ℝ^N, et que x~ est le seul point qui vérifie cette propriété.
  2. Montrer que J admet un minimiseur unique sur le sous-ensemble x_0 + H_k (défini à la question 11), quelque soit k ∈ ℕ.
  3. On note x_k le minimiseur de la question précédente. Montrer que x_k s'identifie à la projection sur x_0 + H_k pour la norme ‖ ⋅ ‖_A associée à la matrice A (définie dans la question 4), c'est-à-dire que
‖x_k − x~‖_A = min_(x ∈ x_0 + H_k)‖x − x~‖_A
On notera r_k = b − Ax_k et e_k = x_k − x~. On remarquera que r_k = − Ae_k.
15. Montrer que e_k ≠ 0 pour k ∈ {0, …, m − 1}, et que e_k = 0 pour k ≥ m.
16. On rappelle que I_N est la matrice identité d'ordre N. Montrer que
‖e_k‖_A = min{‖(I_N + AQ(A))e_0‖_A|Q ∈ ℝ[X], deg(Q) ≤ k − 1}
  1. Montrer que
‖e_k‖_A ≤ ‖e_0‖_A min{‖I_N + AQ(A)‖‖|Q ∈ ℝ[X], deg(Q) ≤ k − 1},
où ‖| ⋅ ||| est la norme matricielle définie dans la question 2 .
(On pourra utiliser les propriétés sur A^(1/2) démontrées dans la question 6.)
18. On note λ_1 (respectivement λ_N ) la plus petite (respectivement la plus grande) valeur propre de A, et l'on définit
Λ_k = {Q ∈ ℝ[X]|deg(Q) ≤ k, Q(0) = 1}
Montrer que
‖e_k‖_A ≤ ‖e_0‖_A min_(Q ∈ Λ_k)max_(t ∈ [λ_1, λ_N])|Q(t)|.
Les questions qui suivent (de 19 à 23) portent sur la construction explicite d'un polynôme permettant de préciser la majoration précédente.
Soit k un entier positif ou nul.
On définit la fonction f_k de l'intervalle [ − 1, 1] dans lui-même par f_k(x) = cos(karccosx).
19. a) Développer l'expression f_(k + 1)(x) + f_(k − 1)(x), et en déduire la relation
∀x ∈ [ − 1, 1] f_(k + 1)(x) = 2xf_k(x) − f_(k − 1)(x)
b) En déduire que f_k s'identifie sur [ − 1, 1] à un polynôme T_k, de degré k, de même parité que k.
20. On note arcosh la fonction réciproque du cosinus hyperbolique ^1, définie de [1, + ∞[ dans [0, + ∞[. Montrer que
∀x ∈ ] − ∞, − 1] T_k(x) = (− 1)^k cosh(karcosh(− x)).
21. On rappelle que A, par hypothèse énoncée au début de la partie II, n'est pas proportionnelle à l'identité. On pose ω_k = 1/(T_k(− (λ_N + λ_1)/(λ_N − λ_1))). Montrer que ω_k est bien défini, que le polynôme
Q_k(X) = ω_k T_k((2X − λ_1 − λ_N)/(λ_N − λ_1))
est élément de Λ_k (ensemble défini à la question 18), et que le maximum de |Q(t)| sur [λ_1, λ_N] est |ω_k|.
22. On pose θ = arcosh((λ_N + λ_1)/(λ_N − λ_1)) > 0 et α = e^(− θ). Montrer que α est une racine du polynôme
X^2 − 2(λ_N + λ_1)/(λ_N − λ_1)X + 1
et en déduire l'expression de α en fonction de la quantité β = (λ_N + λ_1)/(λ_N − λ_1).
23. On note κ = λ_N/λ_1. Montrer que le réel α de la question précédente vaut α = (√κ − 1)/(√κ + 1) et en déduire que
‖e_k‖_A = ‖x − x~‖_A ≤ 2‖e_0‖_A((√κ − 1)/(√κ + 1))^k

Partie IV

On garde les notations des parties précédentes. En particulier, on note toujours x_k le minimiseur de J sur x_0 + H_k (voir question 13).
24. Montrer qu'il existe une famille ( p_0, …, p_(m − 1) ) de vecteurs de ℝ^N telle que
(i) Pour tout k ∈ {1, …, m}, la famille (p_0, …, p_(k − 1)) est une base de H_k.
(ii) La famille est orthogonale pour le produit scalaire associé à A, c'est-à-dire que
∀i, j ∈ {0, …, m − 1} i ≠ j ⇒ ⟨Ap_i, p_j⟩ = 0
  1. On suppose connue une famille (p_0, …, p_(m − 1)) de vecteurs vérifiant les propriétés de la question précédente. Montrer que x_(k + 1) − x_k est alors colinéaire à p_k pour tout entier k ∈ {0, …, m − 1}.
  2. On se donne x_0 ∈ ℝ^N. On considère les suites réelles finies (α_k) et (β_k), ainsi que les suites finies (x~_k), (r~_k) et ( p~_k ) d'éléments de ℝ^N, construites selon les relations de récurrences suivantes, pour k ∈ {0, …, m − 1},
α_k, = (‖r~_k‖^2)/(⟨Ap~_k, p~_k⟩); x~_(k + 1), = x~_k + α_k p~_k; r~_(k + 1), = r~_k − α_k Ap~_k; β_k, = (‖r~_(k + 1)‖^2)/(‖r~_k‖^2); p~_(k + 1), = r~_(k + 1) + β_k p~_k
avec x~_0 = x_0, r~_0 = b − Ax_0 et p~_0 = r~_0.
Montrer que les propriétés suivantes sont vérifiées :
(i) Pour tout k ∈ {0, …, m − 1}, pour tout i ∈ {0, …, k − 1}, on a
⟨r~_i, r~_k⟩ = 0, ⟨p~_i, r~_k⟩ = 0, ⟨p~_i, Ap~_k⟩ = 0
(ii) Pour tout k ∈ {0, …, m}, x~_k s'identifie à x_k, le minimiseur de J sur x_0 + H_k défini dans la question 13.
(iii) Pour tout k ∈ {0, …, m}, r~_k s'identifie à r_k = A − bx_k.
(iv) La famille ( p~_0, …, p~_k ) est une base de H_(k + 1), pour tout k ∈ {0, …, m − 1}.
  1. ^1 On n'utilisera de cette notion hors programme que le fait que arcosh(1) = 0, et cosh(arcosh(− x)) = − x pour x ∈ ] − ∞, − 1].

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet de mathématiques X-ENS PSI 2019 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet de mathématiques X-ENS PSI 2019 ?

Il porte sur la réduction des matrices symétriques réelles, les normes euclidiennes et matricielles, et se termine par la construction de l'algorithme du gradient conjugué pour résoudre un système linéaire.

Quelles parties sont indépendantes dans ce problème ?

La partie I pose les outils utilisés dans tout le reste du sujet ; les parties II, III et IV s'enchaînent ensuite logiquement autour de la construction du gradient conjugué.

Faut-il connaître les polynômes de Tchebychev pour ce sujet ?

Ils ne sont pas supposés connus : le sujet les introduit et démontre leurs propriétés nécessaires à la majoration de l'erreur de la méthode.

Ce sujet est-il centré sur l'algèbre linéaire ou sur l'analyse ?

Le sujet combine les deux : réduction des matrices symétriques et normes en algèbre linéaire, étude de suites et de fonctions polynomiales en analyse.

Pas de description pour le moment