WikiPrépaLivrets

X ENS Mathématiques PSI 2016Sujet et corrigé

Pas encore noté
  • Matrices orthogonales
  • Produit scalaire euclidien
  • Matrices par blocs
  • Récurrence en algèbre linéaire
  • Optimisation linéaire : lemme de Farkas
Logo concours X-ENS

Explorer les annales

BanqueX-ENSAnnée2016FilièrePSIMatièreMathématiques
Annales X-ENS PSI MathématiquesX-ENS PSI 2016PSI MathématiquesMathématiques 2016

Téléchargements

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

Présentation du sujet

Théorème de Broyden, lien avec le théorème de Tucker et le lemme de Farkas
Afficher ou masquer la section

Le problème démontre le théorème de Broyden, qui affirme que toute matrice orthogonale peut s'écrire comme le produit d'une matrice diagonale de signes et d'un vecteur strictement positif. Il en étudie d'abord le cas de la dimension 2, puis établit son équivalence avec le théorème de Tucker sur les matrices antisymétriques, avant d'en donner une preuve par récurrence et d'en déduire le lemme de Farkas de la théorie de l'optimisation linéaire.

  1. 1PréliminaireInégalités élémentaires sur les vecteurs positifs et les matrices diagonales de signes.
  2. 2A. Le cas n=2Étude explicite du théorème de Broyden pour les réflexions et rotations du plan.
  3. 3B. Le théorème de TuckerDémonstration de l'équivalence entre le théorème de Broyden et le théorème de Tucker sur les matrices antisymétriques.
  4. 4C. Preuve du théorème de BroydenDémonstration par récurrence sur la dimension à l'aide d'une décomposition par blocs de la matrice orthogonale.
  5. 5D. Lemme de FarkasDéduction du lemme de Farkas, résultat fondamental de la théorie de l'optimisation linéaire, à partir du théorème de Tucker.

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

Banque commune École Polytechnique - InterENS

PSI

Session 2016

Épreuve de Mathématiques

Durée : 4 heures

Aucun document n'est autoriséAucune calculatrice n'est autorisée

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.

Préambule

Dans tout le texte M_(n, m)(R) désigne l'ensemble des matrices à n lignes, m colonnes et à coefficients réels; on notera I_n la matrice identité de M_n(R) = M_(n, n)(R). Si A = [a_(i, j)]_(1 ⩽ i ⩽ n; 1 ⩽ j ⩽ m) ∈ M_(n, m)(R), on notera ^t A = [a_(j, i)]_(1 ⩽ j ⩽ m; 1 ⩽ i ⩽ n) ∈ M_(m, n)(R) la matrice transposée de A. On identifiera les vecteurs de R^n avec les éléments de M_(n, 1)(R). On utilisera la notation diag(λ_1, ⋯, λ_n) pour désigner la matrice diagonale de M_n(R) dont les coefficients diagonaux sont les λ_i. Une matrice S ∈ M_n(R) est dite diagonale de signes si elle est de la forme
S = diag(ε_1, ⋯, ε_n), où ∀i ∈ {1, ⋯, n}, ε_i ∈ { − 1, + 1}.
L'espace vectoriel R^n est muni du produit scalaire,
(x, y) ∈ R^n × R^n ↦ ⟨x|y⟩ = ^t xy ∈ R,
et on note ‖x‖ = √(⟨x|x⟩) la norme d'un vecteur x de R^n. On rappelle qu'une matrice A ∈ M_n(R) est dite orthogonale si ^t AA = I_n ou de manière équivalente si pour tout x, y ∈ R^n, on a ⟨Ax|Ay⟩ = ⟨x|y⟩.
Une matrice A = [a_(i, j)]_(1 ⩽ i ⩽ n; 1 ⩽ j ⩽ m) ∈ M_(n, m)(R) est dite positive et on note A ⩾ 0 si tous ses coefficients a_(i, j) sont positifs :
[a_(i, j)]_(1 ⩽ i ⩽ n; 1 ⩽ j ⩽ m) ⩾ 0 ⇔ ∀i ∈ {1, ⋯, n} et ∀j ∈ {1, ⋯, m} : a_(i, j) ⩾ 0.
On dira aussi qu'elle est strictement positive et on note A > 0, si tous ses coefficients le sont.
Dans le texte, on utilise les notations usuelles sur les matrices par blocs et les candidats sont invités à utiliser sans justification les calculs par blocs comme par exemple
(A, B; C, D)(X/Y) = ((AX + BY)/(CX + DY))
où A ∈ M_m(R), B ∈ M_(m, n)(R), C ∈ M_(n, m)(R), D ∈ M_n(R) et X ∈ R^m, Y ∈ R^n.
L'objectif de ce problème est de démontrer le théorème de Broyden suivant et ses liens avec le lemme de Farkas et le théorème de Tucker.
Théorème de Broyden : Soit O une matrice orthogonale de M_n(R). Il existe alors x > 0 dans R^n et une unique matrice diagonale de signes S = diag(ε_1, ⋯, ε_n), tels que
Ox = Sx.

Préliminaire

  1. Soient x, y des vecteurs strictement positifs de R^n et soient S, R deux matrices diagonales de signes.
1-a) Montrer que
⟨Sx|Ry⟩ ⩽ ⟨x|y⟩,
avec égalité si et seulement si R = S.
1-b) Démontrer l'unicité de S dans le théorème de Broyden.
1-c) Montrer que
‖Sx + Ry‖ ⩽ ‖x + y‖,
avec égalité si et seulement si R = S.
2) Soient O une matrice orthogonale de M_n(R) et S une matrice diagonale de signes. Montrer que l'égalité Ox = Sx avec x ∈ R^n strictement positive, est équivalente à
(∗){(I_n + O)x ⩾ 0,; (I_n − O)x ⩾ 0,; x > 0.
Les parties A, B, C et D suivantes sont indépendantes entre elles.

A- Le casn = 2

Dans cette question, on suppose n = 2. On identifie les éléments x = ((x_1)/(x_2)) ∈ R^2 aux vecteurs x⃗ = x_1 i⃗ + x_2 j⃗ du plan euclidien relativement à un repère orthonormé ( Ω, i⃗, j⃗ ) : les matrices de M_2(R) seront ainsi identifiées aux applications linéaires de ce plan (conservant donc l'origine Ω ).
3) Soit O la matrice d'une réflexion relativement à une droite passant par Ω et dirigée par un vecteur v⃗_+. Déterminer un vecteur x ∈ R^2 strictement positif ainsi qu'une matrice diagonale de signes S ∈ M_2(R) telle que Ox = Sx.
Indication : on commencera par traiter le cas où v⃗_+ ∈ {i⃗, j⃗}.
4) Soit à présent O la matrice d'une rotation de centre Ω et d'angle θ ∈ ] − π, π] non nul. À l'aide d'un dessin, trouver deux vecteurs x_+et x_−tels que
Ox_+ = diag(1, − 1)x_+ et Ox_− = diag(− 1, 1)x_−.
Discuter ensuite suivant le signe de θ, lequel de x_+et x_−est strictement positif.

B- Le théorème de Tucker

Dans cette section, nous allons prouver que le théorème de Broyden est équivalent au théorème de Tucker suivant :
Théorème de Tucker : Soit M ∈ M_n(R) une matrice antisymétrique (c'est à dire ^t M = − M ). Il existe alors un vecteur u ∈ R^n tel que
u ⩾ 0, Mu ⩾ 0, u + Mu > 0.
On suppose dans un premier temps que le théorème de Tucker est vrai.
5) Avec les notations du théorème de Broyden, on note M ∈ M_(3n)(R) la matrice par blocs suivante:
M = (0, 0, I_n + O; 0, 0, I_n − O; − (I_n + ^t O), − (I_n − ^t O), 0)
En utilisant le théorème de Tucker, montrer qu'il existe des vecteurs positifs x, z_1, z_2 ∈ R^n tels que
{(I_n + O)x ⩾ 0; (I_n − O)x ⩾ 0; − (I_n + ^t O)z_1 − (I_n − ^t O)z_2 ⩾ 0; z_1 + (I_n + O)x > 0; z_2 + (I_n − O)x > 0; x − (I_n + ^t O)z_1 − (I_n − ^t O)z_2 > 0
  1. Montrer que ‖z_1 + z_2‖ = ‖z_1 − z_2‖ et − (I_n + ^t O)z_1 − (I_n − ^t O)z_2 = 0.
  2. En déduire alors que x > 0 et x + Ox ⩾ 0 ainsi que x − Ox ⩾ 0. Conclure.
On suppose à présent que le théorème de Broyden est vrai.
8) Montrer que si M ∈ M_n(R) est antisymétrique alors I_n + M est une matrice inversible.
9) Montrer que pour M ∈ M_n(R) antisymétrique, la matrice
O = (I_n + M)^(− 1)(I_n − M)
est orthogonale.
10) Déduire du théorème de Broyden qu'il existe un vecteur strictement positif x ainsi qu'une matrice diagonale de signes S tels que Ox = Sx et en déduire que u = x + Sx est le vecteur positif du théorème de Tucker.

C- Preuve du théorème de Broyden

Nous allons prouver le théorème de Broyden par récurrence sur la dimension. Le cas de la dimension 1 étant trivial, nous supposons le résultat acquis jusqu'au rang n − 1 et on écrit O sous la forme d'une matrice par blocs
O = (P, r; ^t q, α)
où P ∈ M_(n − 1)(R) et donc r, q ∈ R^(n − 1) et α ∈ R.
11) Montrer que |α| ⩽ 1 avec égalité si et seulement si q = r = 0.
12) Traiter le cas |α| = 1.
On suppose à présent que |α| < 1 et on introduit les matrices
Q_− = P − (r^t q)/(α − 1), Q_+ = P − (r^t q)/(α + 1)
  1. Montrer que ^t PP + q^t q = I_(n − 1), ^t Pr + αq = 0 et ^t rr + α^2 = 1.
  2. Montrer que les matrices Q_+et Q_−sont orthogonales.
  3. Montrer que
^t Q_+Q_− = I_(n − 1) − 2/(1 − α^2)q^t q
et en déduire que
Q_− = Q_+ − 2/(1 − α^2)Q_+q^t q
En utilisant l'hypothèse de récurrence pour Q_+(resp. Q_−), on note x_+ > 0 (resp. x_− > 0 ) un vecteur de R^(n − 1) et S_+(resp. S_−) la matrice diagonale de signes, tels que
Q_+x_+ = S_+x_+, resp. Q_−x_− = S_−x_−.
  1. Montrer que
⟨S_+x_+|S_−x_−⟩ = ⟨x_+|x_−⟩ − 2/(1 − α^2)⟨x_+|q⟩⟨x_−|q⟩.
  1. On pose
  • η_+ = − (⟨x_+|q⟩)/(α + 1) (resp. η_− = − (⟨x_−|q⟩)/(α − 1) ),
  • z_+ = ((x_+)/(η_+))(resp. z_− = ((x_−)/(η_−)))
  • et S^+ = (S_+, 0; 0, + 1) (resp. S^− = (S_−, 0; 0, − 1) ).
Montrer, en utilisant la question 1-a), que dans le cas où S_+ ≠ S_−alors un des couples ( z_+, S^+) et ( z_−, S^−) vérifie le théorème de Broyden.
18) On suppose à présent S_+ = S_−et on suppose ⟨x_+|q⟩ = 0. On note z = ((x_+)/0), R_+ = (S_+, 0; 0, 1) et R_− = (S_+, 0; 0, − 1).
18-a) Montrer que Oz = R_+z = R_−z.
18-b) On écrit à présent
O = (α^′, t^′; r^′, P^′)
où P^′ ∈ M_(n − 1)(R). Construire alors z^′ = ((η^′)/(x^′)) ∈ R^n avec x^′ ∈ R^(n − 1) strictement positif et η^′ ⩾ 0 tel qu'il existe une matrice diagonale de signes R^′ vérifiant Oz^′ = R^′ z^′.
18-c) Dans le cas où η^′ = 0, et en utilisant la question 1-c), montrer qu'il existe une matrice diagonale de signes S telle que O(z + z^′) = S(z + z^′) et conclure.

D- Lemme de Farkas

Le but de cette section est de prouver le lemme de Farkas suivant.
Lemme de Farkas : Soient A ∈ M_(n, m)(R) et b ∈ R^n. Alors exactement une des deux propositions suivantes est vérifiée :
(I) il existe z ∈ R^m positif tel que Az = b;
(II) il existe z ∈ R^n tel que − ^t Az ⩾ 0 et ⟨b|z⟩ > 0.
Pour A ∈ M_(n, m)(R) et b ∈ R^n comme dans le lemme de Farkas, on pose
B = (0, 0, A, − b; 0, 0, − A, b; − ^t A, ^t A, 0, 0; ^t b, − ^t b, 0, 0)
Soit, d'après le théorème de Tucker, y = ^t(z_1, z_2, x, t) ⩾ 0 tel que
By ⩾ 0 et y + By > 0.
  1. Montrer que si t = 0 alors pour z = z_1 − z_2, on a − ^t Az ⩾ 0 et ⟨b|z⟩ > 0.
  2. Si t > 0 montrer que Ax = tb et conclure.

FIN DE L'ÉPREUVE

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet banque X-ENS maths PSI 2016 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet banque X-ENS maths PSI 2016 ?

Le sujet porte sur les matrices orthogonales, le produit scalaire euclidien, le calcul par blocs et l'optimisation linéaire via le lemme de Farkas.

Les parties du sujet sont-elles indépendantes ?

Les parties A, B, C et D sont indépendantes entre elles, une fois établi le préliminaire commun sur les matrices diagonales de signes.

Qu'est-ce que le théorème de Broyden étudié dans ce sujet ?

C'est le résultat selon lequel toute matrice orthogonale réelle admet un vecteur strictement positif et une unique matrice diagonale de signes vérifiant une relation de valeur propre généralisée.

Quel lien ce sujet établit-il avec l'optimisation linéaire ?

La partie D déduit du théorème de Tucker le lemme de Farkas, un résultat central de la dualité en programmation linéaire portant sur l'existence de solutions à un système d'inégalités.

Pas de description pour le moment