11.4 It´ eration d’une contraction et point fixe
349
D´ efinition 11.7 1. Une distance sur un ensemble K est une fonction d : K × K →
R
+
∪ {0} telle que :
(i) d(v, w) ≥ 0 ;
(ii) d(v, w) = d(w, v) ;
(iii) d(v, w) = 0 si et seulement si v = w ;
(iv) pour tous v, w, z, d(v, w) ≤ d(v, z)+d(z, w). C’est ce qu’on appelle « l’in´ egalit´ e
du triangle ».
2. Un ensemble K muni d’une distance d est un espace m´ etrique.
3. Une suite {v n } d’´ el´ ements de K est une suite de Cauchy si ∀ > 0, ∃N ∈ N tel que,
pour tous m, n > N , on a d(v n , v m ) < <.
4. Une suite {v n } d’´ el´ ements de K converge vers un ´ el´ ement w ∈ K si ∀ > 0, ∃N ∈ N
tel que, pour tout n > N, on a d(v n , w) < <.
5. Un espace m´ etrique K est complet si toute suite de Cauchy d’´ el´ ements de K converge
vers un ´ el´ ement de K.
Exemple 11.8 1. R
n dot´ e de la distance euclidienne est un espace m´ etrique complet.
2. Soit K l’ensemble des sous-ensembles de R
2 qui sont ferm´ es et born´ es : on les
appellera les sous-ensembles compacts de R
2 . La distance sur K que l’on utilisera
est la distance de Hausdorff que l’on va d´ efinir et ´ etudier en d´ etail `
a la section 11.5.
Muni de cette distance, K sera un espace m´ etrique complet. (La preuve, que nous
ne ferons pas, se trouve dans [1].)
3. Lorsque nous passerons ` a la pratique de la compression d’images `
a la section 11.7,
une photographie en noir et blanc sur un rectangle R sera une fonction f : R → S,
S d´ enotant l’ensemble des tons de gris. Nous pourrons alors d´ efinir la distance entre
deux fonctions f et f
` a l’aide d’une des deux d´ efinitions suivantes :
d 1 (f, f
) = max
(x,y)∈R
|f (x, y) − f
(x, y)|
(11.7)
et
d 2 (f, f
) =
R
(f (x, y) − f
(x, y))
2 dx dy
1/2
.
(11.8)
Muni d’une de ces distances, l’espace des fonctions f : R → S est un espace m´ etrique
complet. On peut remplacer R = [a, b] × [c, d] par un ensemble discret de pixels
recouvrant le rectangle en adaptant l´ eg` erement les d´ efinitions ci-dessus. Par exemple,
l’int´ egrale double devient alors une somme discr` ete sur chacun des pixels. Si x et y
prennent les valeurs {0, . . . , h − 1} et {0, . . . , v − 1} respectivement, alors la distance
devient
d 3 (f, f
) =
h−1
x=0
v−1
y=0
(f (x, y) − f
(x, y))
2
1/2
.
(11.9)
349
D´ efinition 11.7 1. Une distance sur un ensemble K est une fonction d : K × K →
R
+
∪ {0} telle que :
(i) d(v, w) ≥ 0 ;
(ii) d(v, w) = d(w, v) ;
(iii) d(v, w) = 0 si et seulement si v = w ;
(iv) pour tous v, w, z, d(v, w) ≤ d(v, z)+d(z, w). C’est ce qu’on appelle « l’in´ egalit´ e
du triangle ».
2. Un ensemble K muni d’une distance d est un espace m´ etrique.
3. Une suite {v n } d’´ el´ ements de K est une suite de Cauchy si ∀ > 0, ∃N ∈ N tel que,
pour tous m, n > N , on a d(v n , v m ) < <.
4. Une suite {v n } d’´ el´ ements de K converge vers un ´ el´ ement w ∈ K si ∀ > 0, ∃N ∈ N
tel que, pour tout n > N, on a d(v n , w) < <.
5. Un espace m´ etrique K est complet si toute suite de Cauchy d’´ el´ ements de K converge
vers un ´ el´ ement de K.
Exemple 11.8 1. R
n dot´ e de la distance euclidienne est un espace m´ etrique complet.
2. Soit K l’ensemble des sous-ensembles de R
2 qui sont ferm´ es et born´ es : on les
appellera les sous-ensembles compacts de R
2 . La distance sur K que l’on utilisera
est la distance de Hausdorff que l’on va d´ efinir et ´ etudier en d´ etail `
a la section 11.5.
Muni de cette distance, K sera un espace m´ etrique complet. (La preuve, que nous
ne ferons pas, se trouve dans [1].)
3. Lorsque nous passerons ` a la pratique de la compression d’images `
a la section 11.7,
une photographie en noir et blanc sur un rectangle R sera une fonction f : R → S,
S d´ enotant l’ensemble des tons de gris. Nous pourrons alors d´ efinir la distance entre
deux fonctions f et f
` a l’aide d’une des deux d´ efinitions suivantes :
d 1 (f, f
) = max
(x,y)∈R
|f (x, y) − f
(x, y)|
(11.7)
et
d 2 (f, f
) =
R
(f (x, y) − f
(x, y))
2 dx dy
1/2
.
(11.8)
Muni d’une de ces distances, l’espace des fonctions f : R → S est un espace m´ etrique
complet. On peut remplacer R = [a, b] × [c, d] par un ensemble discret de pixels
recouvrant le rectangle en adaptant l´ eg` erement les d´ efinitions ci-dessus. Par exemple,
l’int´ egrale double devient alors une somme discr` ete sur chacun des pixels. Si x et y
prennent les valeurs {0, . . . , h − 1} et {0, . . . , v − 1} respectivement, alors la distance
devient
d 3 (f, f
) =
h−1
x=0
v−1
y=0
(f (x, y) − f
(x, y))
2
1/2
.
(11.9)