ENS Mathématiques C MP 2011Sujet et corrigé

Pas encore noté

Explorer les annales

BanqueX-ENS Année2011 FilièreMP MatièreMathématiques

Annales X-ENS MP Mathématiques X-ENS MP 2011 MP Mathématiques Mathématiques 2011

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Présentation du sujet

Diffusion sur des ensembles finis : constantes de Poincaré et de Sobolev

Le problème étudie des processus de diffusion sur des ensembles finis à travers deux constantes qui mesurent la vitesse de convergence vers la configuration uniforme : la constante de Poincaré, liée à la décroissance de l'énergie, et la constante de Sobolev, liée à la décroissance de l'entropie. Un exemple explicite est traité sur l'hypercube (Z/2Z)^d.

1Partie 1 : Énergie et inégalité de trou spectralÉtudie une matrice symétrique bistochastique irréductible, la forme de Dirichlet associée, la constante de Poincaré et la convergence exponentielle vers l'équilibre d'un système différentiel linéaire.
2Partie 2 : Entropie et inégalité de SobolevDéfinit l'entropie discrète, la constante de Sobolev, établit une inégalité la reliant à la constante de Poincaré et montre la décroissance exponentielle de l'entropie le long du système différentiel.
3Partie 3 : Exemple de l'hypercube (Z/2Z)^dApplique les résultats précédents à la diffusion sur l'hypercube, calcule explicitement les constantes de Poincaré et de Sobolev et compare les vitesses de convergence en variation totale.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ÉCOLES NORMALES SUPÉRIEURES

COMPOSITION DE MATHÉMATIQUES - C - (ULC)

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

Diffusion sur des ensembles finis

Préambule

Ce problème est constitué de trois parties.
Le but du problème est d'étudier des processus similaires à la diffusion sur des ensembles finis. La vitesse de convergence vers la configuration uniforme est mesurée à l'aide de deux constantes : la constante de Poincaré permet de mesurer la vitesse de décroissance de l'énergie (partie 1), tandis que la constante de Sobolev permet de mesurer la vitesse de décroissance de l'entropie, qui est dans ce contexte l'opposée de l'entropie physique (partie 2 ). Un exemple est traité dans la partie 3 : la diffusion classique sur l'hypercube

(ℤ/2ℤ)^d

avec le calcul de la constante de Poincaré.

Définitions, notations et rappels

On note

ℝ

le corps des nombres réels,

ℝ_+

le sous-ensemble des nombres réels positifs, et

ℝ_+^*

le sous-ensemble des nombres réels strictement positifs.

On introduit

⟨ \cdot, \cdot ⟩

le produit scalaire renormalisé sur

ℝ^N

⟨u, v⟩ = 1/N\sum_(i = 1)^N u_i v_i

On note

‖ \cdot ‖_2

la norme euclidienne associée :

‖u‖_2^2 = 1/N\sum_(i = 1)^N u_i^2

On introduit le vecteur constant

π = ^t(1, \dots, 1)

.
Si

E

est un ensemble, l'espace vectoriel des fonctions de

E

dans

ℝ

est noté

ℝ^E

Matrices stochastiques

Dans tout ce problème,

P \in M_N(ℝ)

désigne une matrice qui vérifie les propriétés suivantes :

∀(i, j) ∈ {1, …, N}^2 p_(i, j) = p_(j, i); ∀(i, j) ∈ {1, …, N}^2 p_(i, j) ≥ 0; ∀j ∈ {1, …, N} ∑_(i = 1)^N p_(i, j) = 1; ∀i ∈ {1, …, N} ∑_(j = 1)^N p_(i, j) = 1

On dira en raccourci que

P

est symétrique et bistochastique. On remarquera que la dernière propriété est une conséquence des précédentes.
Si

p_(i, j) > 0

on dit que l'état

j

est connecté à l'état

i

.
On dit que la matrice

P

est irréductible si pour tout couple d'indices

(i, j) ∈ {1, …, N}^2

il existe des états intermédiaires

(j_1, j_2, \dots, j_l)

qui permettent de connecter les états

j

i

p_(j_1, j) > 0 et p_(j_2, j_1) > 0 \dots p_(j_l, j_(l - 1)) > 0 et p_(i, j_l) > 0

Inégalités de convexité

Soit une fonction

φ : ℝ_+ \to ℝ

, continue et de classe

C^1

sur

ℝ_+^*

. On rappelle que

φ

est strictement convexe si et seulement si

φ^'

est strictement croissante.

Inégalité de Jensen, version discrète

Soit une fonction

φ : ℝ_+ \to ℝ

continue, de classe

C^1

sur

ℝ_+^*

et strictement convexe. Soit

β \in (ℝ_+)^N

tel que

\sum_(i = 1)^N β_i = 1

. Pour tout

f \in (ℝ_+)^N

on a

φ(\sum_(i = 1)^N β_i f_i) \leq \sum_(i = 1)^N β_i φ(f_i)

Dans le cas où

\foralliβ_i > 0

, cette inégalité est une égalité si et seulement si

f

est colinéaire au vecteur constant

π

Inégalité de Jensen, version continue

Soit une fonction

φ : ℝ_+ \to ℝ

continue, de classe

C^1

sur

ℝ_+^*

et strictement convexe. Soit

β

une fonction continue de

[a, b] \to ℝ_+

telle que

\int_a^b β(t)dt = 1

. Pour toute fonction continue

f(t)

[a, b]

dans

ℝ_+

on a

φ(\int_a^b β(t)f(t)dt) \leq \int_a^b β(t)φ(f(t))dt

Dans le cas où

\foralltβ(t) > 0

, cette inégalité est une égalité si et seulement si

f

est une fonction constante.

1 Energie et inégalité de trou spectral

Soit

P \in M_N(ℝ)

une matrice symétrique, bistochastique et irréductible.

(a) Montrer que le vecteur $π = ^t(1, \dots, 1)$ est un vecteur propre de $P$ .
(b) On suppose de plus que $∀(i, j) ∈ {1, …, N}^2 p_(i, j) > 0$ . Montrer que $λ = 1$ est une valeur propre simple de $P$ .
Indication. Si $u = (u_i)$ est un vecteur propre on pourra s'intéresser à la valeur maximale $U = max{u_i} = u_(i_0)$ .
(c) Montrer que l'on peut aboutir à la même conclusion sans l'hypothèse supplémentaire $∀(i, j) ∈ {1, …, N}^2 p_(i, j) > 0$ .
On définit la forme de Dirichlet associée à la matrice $P$

\forallu \in ℝ^N E(u, u) = 1/(2N)\sum_(i = 1)^N\sum_(j = 1)^N(u_i - u_j)^2 p_(ij)

(a) Montrer que

E(u, u) = ⟨u, (Id - P)u⟩ = ⟨(Id - P)u, u⟩

.
(b) On définit la constante de Poincaré :

μ = inf{(E(v, v))/(‖v‖_2^2)| v ∈ ℝ^N∖{0}, ⟨π, v⟩ = 0}

Montrer que l'infimum

μ

est atteint. En déduire que

μ

est strictement positif.
Interpréter

μ

en fonction des valeurs propres de

Id - P

.
Indication : Comme en

1b

, on pourra commencer par supposer :

\forall(i, j), p_(i, j) > 0

.
3. Soit

u^0 \in ℝ^N

tel que

⟨π, u^0⟩ = 1

. On définit le système différentiel linéaire de la façon suivante :

{u(0) = u^0; u^′(t) = (P − Id)u(t)

(a) Montrer qu'il existe une unique solution

u(t)

définie sur l'intervalle maximal

ℝ

.
(b) Montrer que :

\forallt \in ℝ ⟨π, u(t)⟩ = 1

u(t)

converge vers

π

à vitesse exponentielle lorsque

t

tend vers

+ \infty

\forallt \geq 0 ‖u(t) - π‖_2^2 \leq ‖u^0 - π‖_2^2 exp(- 2μt)

Indication. Si e

(t) = ‖u(t) - π‖_2^2

, chercher une inégalité qui relie

e^'(t)

et e(t) puis multiplier par une fonction exponentielle bien choisie.

2 Entropie et inégalité de Sobolev

Dans cette partie du problème,

P

désigne à nouveau une matrice symétrique, bistochastique et irréductible, et

u

désigne un vecteur de

ℝ^N

qui vérifie les deux propriétés suivantes :

∀i ∈ {1, …, N} u_i ≥ 0; ⟨π, u⟩ = 1

On définit l'entropie

H(u) = 1/N\sum_(i = 1)^N u_i lnu_i

avec la convention

u_i lnu_i = 0

u_i = 0

.
Montrer, à l'aide de l'inégalité de Jensen, que l'entropie est une quantité positive. À quelle condition a-t-on

H(u) = 0

?
2. Pour

f ∈ ℝ^N∖{0}

on définit

L(f) = 1/N\sum_(i = 1)^N f_i^2 ln(f_i^2)/(‖f‖_2^2)

ainsi que la constante de Sobolev :

α = inf{(E(f, f))/(L(f))| f ∈ ℝ^N∖{0}, L(f) ≠ 0}

(a) Soit

v ∈ ℝ^N∖{0}

tel que

⟨π, v⟩ = 0

. On écrit

f = π + εv

. Établir l'expression du développement limité :

L(f) = 2ε^2‖v‖_2^2 + O(ε^3), lorsque ε \to 0

(b) En faisant tendre

ε

vers 0 montrer que

α \leq μ/2

On admettra que

α

est strictement positif.
3. On étend la définition de

E

à des couples de vecteurs

(u, v) \in ℝ^N \times ℝ^N

E(u, v) = 1/(2N)\sum_(i = 1)^N\sum_(j = 1)^N(u_i - u_j)(v_i - v_j)p_(ij)

(a) Montrer que

E(u, v) = ⟨u, (Id - P)v⟩ = ⟨(Id - P)u, v⟩

.
(b) Montrer que pour tout couple (

a, b

) de réels distincts strictement positifs,

((\sqrtb - \sqrta)/(b - a))^2 \leq 1/4(lnb - lna)/(b - a)

Indication. On pourra écrire la différence

\sqrtb - \sqrta

comme une intégrale bien choisie sur

[a, b]

.
(c) Si

u \in (ℝ_+^*)^N

on définit les vecteurs auxiliaires

lnu = (lnu_i)

\sqrtu = (\sqrt(u_i))

. Déduire de la question précédente que

\forallu \in (ℝ_+^*)^N E(u, lnu) \geq 4E(\sqrtu, \sqrtu).

On considère à nouveau le système différentiel introduit en (1), où $u^0$ vérifie la propriété (4) et

∀i ∈ {1, …, N} u_i^0 > 0

(a) Montrer que

exp(t(P - Id))

est une matrice à termes positifs pour tout

t \geq 0

. En déduire:

∀t ≥ 0 ∀i ∈ {1, …, N} u_i(t) > 0

(b) Montrer que

(dH(u(t)))/(dt) = ⟨u^'(t), lnu(t) + π⟩

t \to + \infty

\forallt \geq 0 H(u(t)) \leq H(u^0)exp(- 4αt)

(d) Montrer que l'on peut étendre l'inégalité (6) au cas où

u^0

vérifie les propriétés (3) et (4).

Indication. On pourra considérer la condition initiale

u_ε^0 = (1 - ε)u^0 + επ

.
5. On définit la norme de la variation totale entre deux vecteurs

(u, v) \in ℝ^N \times ℝ^N

‖u - v‖_(VT) = 1/N\sum_(i = 1)^N|u_i - v_i|

(a) Donner une constante

C_N

telle que

‖u - v‖_(VT)^2 \leq C_N‖u - v‖_2^2

pour tout couple

(u, v) \in ℝ^N \times ℝ^N

.
(b) On admettra l'inégalité suivante, valable pour tout réel

a > 0

(3(a - 1)^2)/((4 + 2a)) \leq alna - a + 1

En déduire l'estimation suivante à l'aide de l'inégalité de Cauchy-Schwarz :

(\forallu \in (ℝ_+)^N tel que ⟨π, u⟩ = 1) ‖u - π‖_(VT)^2 \leq 2H(u).

3 Exemple de l'hypercube $(ℤ/2ℤ)^d$

Soit

d \geq 2

. On considère

E = (ℤ/2ℤ)^d

l'ensemble des

d

-uplets (

x_1, \dots, x_d

) avec

\foralli, x_i \in ℤ/2ℤ

. On remarquera que

x = - x

pour tout

x \in E

.
On note

N = |E| = 2^d

. On note

0 = (0, \dots, 0)

. On définit les éléments particuliers de

E

e_1 = (1, 0, \dots, 0), e_2 = (0, 1, \dots0,), \dots e_d = (0, \dots, 0, 1)

On note l'application de

E \times E \to ℝ

x \cdot y = \sum_(i = 1)^d x_i y_i

On identifie l'espace vectoriel

ℝ^E

avec

ℝ^N

muni du produit scalaire renormalisé

⟨ \cdot, \cdot ⟩

⟨u, v⟩ = 1/N\sum_(x \in E)u(x)v(x)

x \in E

on note

δ_x \in ℝ^E

la fonction telle que

δ_x(x) = 1

δ_x(y) = 0

y \neq x

A toute fonction $u \in ℝ^E$ on associe la fonction transformée $uˆ \in ℝ^E$ :

\forallξ \in E, uˆ(ξ) = \sum_(x \in E)(- 1)^(- ξ \cdot x)u(x)

(a) Montrer que pour tout

z \in E

z \neq 0 ⟹ \sum_(ξ \in E)(- 1)^(ξ \cdot z) = 0

(b) Montrer la formule d'inversion

\forally \in E, u(y) = 1/N\sum_(ξ \in E)(- 1)^(ξ \cdot y)uˆ(ξ)

Indication. On pourra chercher à démontrer cette identité sur des fonctions particulières.
(c) En déduire l'identité suivante :

⟨u, v⟩ = 1/N⟨uˆ, vˆ⟩

On définit la matrice $P = (p_(x, y)) \in M_N(ℝ)$ :

{p_(x, y) = 1/d, s'il existe i tel que y − x = e_i; p_(x, y) = 0, sinon

Montrer que la matrice

P

est symétrique, bistochastique et irréductible.
3. On définit

E

la forme de Dirichlet associée à

P

comme précédemment :

\forallu \in ℝ^E E(u, u) = 1/(2N)\sum_(x \in E)\sum_(y \in E)(u(x) - u(y))^2 p_(x, y)

ainsi que la constante de Poincaré

μ = inf{(E(v, v))/(‖v‖_2^2)| v ∈ ℝ^E∖{0}, ⟨π, v⟩ = 0}

Pour tout

ξ \in E

on définit

c(ξ) = 1 - 1/d\sum_(i = 1)^d(- 1)^(ξ_i)

(a) Montrer que

\forallξ \neq 0, c(ξ) \geq 2/d

(b) On définit

w = (Id - P)v

. Montrer que

\forallξ \in E, wˆ(ξ) = c(ξ)vˆ(ξ)

μ = 2/d

On admettra que la constante de Sobolev vaut $α = 1/d$ dans ce cas. On considère à nouveau le système différentiel introduit en (1), avec la donnée initiale $u^0 = Nδ_x$ .
Déterminer le temps $T$ suffisant pour atteindre la configuration uniforme $π$ avec la précision $ε > 0$ en variation totale :

\forallt \geq T ‖u(t) - π‖_(VT) \leq ε\dots

(a) ... en utilisant la constante de Poincaré et l'estimation (2),
(b) ... en utilisant la constante de Sobolev et l'estimation (6).

Que pouvez-vous en conclure?

Questions fréquentes

4 questions

Sur quels chapitres porte ce sujet de mathématiques C de l'ENS 2011 en filière MP ?

Il porte sur la réduction des matrices symétriques, les inégalités de convexité, les équations différentielles linéaires et une analyse de Fourier discrète sur l'hypercube.

Les parties de ce problème sont-elles indépendantes ?

Non, la partie 2 réutilise la constante de Poincaré définie en partie 1, et la partie 3 applique les résultats des deux premières parties à un exemple concret.

Quelles notions de probabilités ou d'algèbre linéaire faut-il maîtriser ?

Il faut connaître les matrices symétriques bistochastiques, la diagonalisation, ainsi que les notions d'énergie et d'entropie discrètes définies dans l'énoncé lui-même.

Ce sujet est-il accessible sans préparation spécifique sur les chaînes de Markov ?

Oui, l'énoncé définit lui-même toutes les notions utilisées (matrices stochastiques, forme de Dirichlet, entropie), aucune connaissance préalable sur les chaînes de Markov n'est requise.

Pas de description pour le moment

Commentaires• ENS Mathématiques C MP 2011

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...

Explorer les annales

Téléchargements

Présentation du sujet

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

ÉCOLES NORMALES SUPÉRIEURES

COMPOSITION DE MATHÉMATIQUES - C - (ULC)

Diffusion sur des ensembles finis

Préambule

Définitions, notations et rappels

Matrices stochastiques

Inégalités de convexité

Inégalité de Jensen, version discrète

Inégalité de Jensen, version continue

1 Energie et inégalité de trou spectral

2 Entropie et inégalité de Sobolev

3 Exemple de l'hypercube (ℤ/2ℤ)^d

Questions fréquentes

Sur quels chapitres porte ce sujet de mathématiques C de l'ENS 2011 en filière MP ?

Les parties de ce problème sont-elles indépendantes ?

Quelles notions de probabilités ou d'algèbre linéaire faut-il maîtriser ?

Ce sujet est-il accessible sans préparation spécifique sur les chaînes de Markov ?

Commentaires• ENS Mathématiques C MP 2011

Commentaires• ENS Mathématiques C MP 2011

3 Exemple de l'hypercube $(ℤ/2ℤ)^d$