ENS Mathématiques 2 MP 2009Sujet et corrigé

Pas encore noté

Explorer les annales

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

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

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

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

Les différentes fonctions étudiées dans ce problème sont utilisées en traitement d'images pour obtenir une image de bonne qualité u à partir d'une image bruitée f. La régularisation quadratique présente l'avantage d'être très simple et très rapide, mais aussi le défaut de détruire les bords de l'image en donnant une impression de flou. La régularisation à croissance linéaire permet d'obtenir de bien meilleurs résultats de restauration. Malheureusement, elle implique aussi de savoir minimiser efficacement des fonctions non différentiables, ce qui augmente considérablement la difficulté du problème.

Fin de l'épreuve.

Filière MP (groupes MP/MPI et groupe I)

Épreuve commune aux ENS de Paris, Lyon et Cachan

MATHÉMATIQUES MPI 2
Durée : 4 heures
L'usage de calculatrices est interdit.

Notations

Soit $N \geq 2$ . On considère $X = ℝ^N$ muni du produit scalaire euclidien usuel :

On note

‖

é ‖lanormeeuclidienneassociée.

u \in X

, on note

u_i, 1 \leq i \leq N

, les composantes de

u

.
On note

u^n

le terme général d'une suite d'éléments de

X

.
On note

e = (1, \dots, 1)

l'élément de

X

tel que

e_i = 1

pour tout

i

Dans tout le problème, on considère $A$ une matrice de $M_N(ℝ)$ (ensemble des matrices carrées de taille $N^2$ à coefficients réels), de coefficients $A_(i, j)$ . On note $A^*$ la matrice transposée de $A$ .

On suppose que

A

n'est pas la matrice nulle, et vérifie la propriété suivante:

e \in KerA

On rappelle qu'on dit qu'une fonction $F : X \to ℝ$ est convexe sur $X$ si et seulement si pour tout $u \in X, v \in X$ , et $t \in [0, 1]$ , on a est donné par :

F(tu + (1 - t)v) \leq tF(u) + (1 - t)F(v)

On dit qu'une fonction

F : X \to ℝ

est strictement convexe sur

X

si et seulement si pour tout

u \in X, v \in X, u \neq v

, et

t \in ]0, 1[

, on a

F(tu + (1 - t)v) < tF(u) + (1 - t)F(v)

Si $F$ est différentiable en $u \in X$ , on rappelle que le gradient de $F$ en $u$

\nablaF(u) = ((\partialF)/(\partialx_1)(u); ⋮; (\partialF)/(\partialx_N)(u))

Si $F$ est $C^2$ , on note $\nabla^2 F(u)$ la matrice hessienne de $F$ . Il s'agit d'une matrice de $M_N(ℝ)$ , dont le coefficient en position $i, j$ est donné par :

On admettra alors que

F

est strictement convexe si :

⟨\nabla^2 F(u)(v - u), v - u⟩ > 0

pour tout

u \in X, v \in X, u \neq v

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

(\partial^2 F)/(\partialx_j\partialx_i)(u)

5 Régularisation non différentiable

et
Si

u \in X

, on définit :
On considère l'application

H : X \to ℝ

définie par :
Dans cette dernière partie, on suppose de plus que la matrice

A

est symétrique.

On s'intéresse au problème :
Trouver

u

dans

X

tel que

H(u) = min_(v \in X)H(v)

On considère l'ensemble

K

défini par :
On admet qu'il existe un unique élément

w \in K

tel que

‖f - w‖ = d(f, K)

, où

d(f, K)

désigne la distance euclidienne de

f

K

On admet aussi que si

z \in K

, alors

⟨f - w, z - w⟩ \leq 0

On considère l'application $L : X \to ℝ$ définie par :
(a) Soit $u$ un élément de $X$ . Exprimer $sup_(‖v‖_\infty \leq 1)L(u, v)$ en fonction de $H$ .
(b) Montrer que : $u = f - w$ .
Démontrer l'égalité (5).

‖u‖_1 = \sum_(i = 1)^N|u_i|

‖u‖_\infty = max_(1 \leq i \leq N)|u_i|

H(u) = 1/2‖f - u‖^2 + ‖Au‖_1

K = {Av tel que ‖v‖_∞ ≤ 1}

L(u, v) = 1/2‖f - u‖^2 + ⟨v, Au⟩

L(u, v) = 1/2‖f - u - Av‖^2 - 1/2‖f - Av‖^2 + 1/2‖f‖^2

sup_(‖v‖_\infty \leq 1)inf_(u \in X)L(u, v) = inf_(u \in X)sup_(‖v‖_\infty \leq 1)L(u, v)

Montrer que

u

est solution du problème (4) si et seulement si
avec

(A_ε(u))_i = \sqrt(ε^2 + (Au)_i^2)

. On définit :
avec

A(u)

élément de

M_N(ℝ)

donné par (on note

I_N

la matrice identité de

M_N(ℝ))

G(v, u) = G(u) + ⟨v - u, \nablaG(u)⟩ + 1/2⟨v - u, A(u)(v - u)⟩

où

C(u) \in M_N(ℝ)

et si

1 \leq i, j \leq N

:
On rappelle qu'on note

u^n

le terme général d'une suite d'éléments de

X

. suite (

u^n

) unique : et

b_i = \sqrt((A_ε(v))_i)

.
(a) Montrer que : notée

u

A(u) = I_N + A^* C(u)

(C(u))_(i, j) = (A_(i, j))/((A_ε(u))_i)

Montrer que pour tout $u$ et $v$ dans $X$ , on a :

⟨Av, C(u)v⟩ \geq 0

Soit $u^0 \in X$ . Montrer que la relation de récurrence suivante définit une

G(u^(n + 1), u^n) = min_v G(v, u^n)

En déduire que la suite (

u^n

) ainsi définie vérifie :

0 = u^(n + 1) - f + A^* C(u^n)u^(n + 1)

Soit $u$ et $v$ deux éléments de $X$ . Si $1 \leq i \leq N$ , on pose $a_i = \sqrt((A_ε(u))_i)$

a_i - b_i + 1/2(b_i^2 - a_i^2)/(a_i) \geq 0

(b) Déduire de la question précedente que :

G(v) \leq G(v, u)

Montrer que la suite $(u^(n + 1) - u^n)$ converge.
Montrer que la suite ( $u^n$ ) converge vers la solution du problème (3)

1 Convexité

On pourra admettre les résultats de cette première partie pour traiter les questions des parties suivantes.

Soit $F : X \to ℝ$ une fonction continue, telle que $F(u) \to + \infty$ si $‖u‖ \to + \infty$ .
(a) Montrer qu'il existe au moins un élément $u$ dans $X$ tel que $F(u) = min_(v \in X)F(v)$ .
(b) L'élément précédent $u$ est-il en général unique? Si $F$ est supposée de plus strictement convexe sur $X$ , a-t-on unicité pour $u$ ?
Soit $F$ une fonction différentiable sur $X$ .
(a) Montrer que si $F$ est convexe, alors :
pour tout ( $u, v$ ) dans $X^2$ .
(b) Réciproquement, montrer que si pour tout ( $u, v$ ) dans $X^2$ l'inégalité (1) est vérifiée, alors $F$ est convexe.

Indication : on pourra introduire le point

w = u + t(v - u)

pour

t \in [0, 1]

, et appliquer l'inégalité aux couples

(w, u)

(w, v)

.
3. Soit

F

une fonction différentiable sur

X

. Montrer que

F

est strictement convexe si et seulement si :

F(v) > F(u) + ⟨\nablaF(u), v - u⟩

pour tout

(u, v)

dans

X^2

avec

u \neq v

.
4. On suppose

F

différentiable sur

X

. On rappelle qu'une condition nécessaire pour que

u

puisse être un point de minimimum de

F

est que

\nablaF(u) = 0

. pour que

u

soit un point de minimum de

F

?
(b) Si on suppose de plus

F

convexe sur

X

, la condition nécessaire
5. Soit

F

une fonction différentiable sur

X

. a:

F(v) \geq F(u) + ⟨\nablaF(u), v - u⟩

(a) La condition nécessaire

\nablaF(u) = 0

est-elle en général suffisante

\nablaF(u) = 0

est-elle suffisante?
(a) Montrer que si

F

est convexe, alors pour tout (

u, v

) dans

X^2

⟨\nablaF(u) - \nablaF(v), u - v⟩ \geq 0

(b) Réciproquement, montrer que si pour tout

(u, v)

dans

X^2

l'inégalité (2) est vérifiée, alors

F

est convexe.

Indication : on pourra étudier les variations de la fonction

φ(t) = (1 - t)F(u) + tF(v) - F((1 - t)u + tv)

Soit $F$ une fonction $C^2$ sur $X$ . Montrer que $F$ est convexe si et seulepar: ment si pour tout ( $u, v$ ) dans $X^2$ :

⟨\nabla^2 F(u)v, v⟩ \geq 0

2 Régularisation quadratique

Soit

λ \geq 0

, et

f \in X

. On considère l'application

F_λ : X \to ℝ

définie par :

F_λ(u) = ‖f - u‖^2 + λ‖Au‖^2

Montrer que $F_λ$ est $C^2$ sur $X$ . Calculer $\nablaF_λ(u)$ , puis $\nabla^2 F_λ(u)$ .
Montrer que $F_λ$ est convexe sur $X.F_λ$ est-elle strictement convexe?
Montrer qu'il existe exactement un élément $u_λ$ dans $X$ tel que $F_λ(u_λ) = min_(v \in X)F_λ(v)$ . Montrer que $u_λ$ est caractérisé par la relation :
(a) Que dire de la solution $u_λ$ lorsque $λ \to 0$ ?
Pour $i \in {1, 2}$ , on note pour $f_1$ et $f_2$ dans $X$ :

Donner une majoration de

‖u_λ^1 - u_λ^2‖

dépendant de

‖f_1 - f_2‖

X

tel que

e_i = 1

pour tout

i

. On considère l'application

G : X \to ℝ

définie

G(u) = 1/2‖f - u‖^2 + ⟨e, A_ε(u)⟩

avec

A_ε(u) \in X

et si

1 \leq i \leq N

u_λ - f + λA^* Au_λ = 0

(b) Que dire de

Au_λ

lorsque

λ \to + \infty

F_λ^i(u) = ‖f_i - u‖^2 + λ‖Au‖^2

On note

u_λ^i

un point où

F_λ^i

atteint son minimum sur

X

3 Régularisation à croissance linéaire

Soit

ε > 0

, et

f \in X

. On rappelle qu'on note

e = (1, \dots, 1)

l'élément de

(A_ε(u))_i = \sqrt(ε^2 + (Au)_i^2)

On rappelle qu'on note

u^n

le terme général d'une suite d'éléments de

X

. On considère le problème :

Montrer que $G$ est différentiable. Calculer $\nablaG(u)$ . que cette solution $u$ est caractérisée par la relation :
avec $B(u) \in X$ et si $1 \leq i \leq N$ :
Soit $τ \geq 0$ .

Trouver u dans X tel que G(u) = min_(v \in X)G(v)

Montrer que le problème (3) admet une unique solution $u$ dans $X$ , et $X \to ℝ$ définie par :

(B(u))_i = ((Au)_i)/((A_ε(u))_i)

Supposons un élément

u^n

fixé dans

X

. On considère l'application

G_n

G_n(u) = τ/2‖u - f‖^2 + τ⟨e, A_ε(u)⟩ + 1/2‖u - u^n‖^2

Montrer qu'il existe un unique élément

u^(n + 1)

dans

X

tel que

G_n(u^(n + 1)) = min_(u \in X)G_n(u)

, et que l'on a la relation suivante :

Montrer que la série

\sum‖u^n - u^(n + 1)‖^2

est convergente.
5. Montrer que la suite

(u^n)

est bornée. blème (3).

u - f + A^* B(u) = 0

(u^(n + 1) - u^n)/τ = - u^(n + 1) + f - A^* B(u^(n + 1))

On fixe $u^0$ dans $X$ , et on considère la suite $(u^n)$ définie par récurrence par la relation $G_n(u^(n + 1)) = min_(u \in X)G_n(u)$ .
En déduire que la suite $(u^n)$ converge vers $u$ unique solution du pro-
Dans le cas $ε = 0, G$ est-elle différentiable sur $X$ ?

4 Méthode de type quasi-Newton

Soit

ε > 0

f \in X

. On rappelle que:

G(u) = 1/2‖f - u‖^2 + ⟨e, A_ε(u)⟩

Pas de description pour le moment

Commentaires• ENS Mathématiques 2 MP 2009

Connectez-vous pour participer aux discussions

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

Chargement des commentaires...