348
11 Compression d’images par fonctions it´ er´ ees
Il faut maintenant d´ emontrer l’existence de a. Pour obtenir a on va prendre un
point quelconque x 0 ∈ R et construire la suite de ses it´ er´ ees x 1 = f (x 0 ), x 2 = f (x 1 ),
. . ., x n+1 = f (x n ). . . Si x 1 = x 0 , alors x 0 est un point fixe. Consid´ erons le cas x 1 = x 0 .
Alors,
|x n+1 − x n | = |f (x n ) − f (x n−1 )| ≤ r|x n − x n−1 |.
En it´ erant, on obtient
|x n+1 − x n | ≤ r
n
|x 1 − x 0 |.
On veut montrer que la suite {x n } converge vers un point a ∈ R et que sa limite a est
un point fixe de f . Pour montrer qu’une suite converge sans avoir de candidat pr´ ealable
pour sa limite, il existe un outil tr` es puissant : il suffit de montrer que c’est une suite de
Cauchy. (Rappel : une suite {x n } est une suite de Cauchy si ∀ > 0, ∃N ∈ N tel que, si
n, m > N , alors |x n − x m | < <.) Supposons n > m. Alors,
|x n − x m | = |(x n − x n−1 ) + (x n−1 − x n−2 ) + · · · + (x m+1 − x m )|
≤ |x n − x n−1 | + |x n−1 − x n−2 | + · · · + |x m+1 − x m |
≤ (r
n−1 + r
n−2 + · · · + r
m )|x 1 − x 0 |
≤ r
m (r
n−m−1 + · · · + 1)|x 1 − x 0 |
≤
r
m
1−r |x 1 − x 0 |.
Pour que |x n − x m | < <, il suffit donc de prendre m assez grand pour que
r
m
|x 1 − x 0 |
1 − r
< <,
c’est-` a-dire r
m <
(1−r)
|x1−x0| . Comme 0 < r < 1 et donc, r
m < r
N pour m > N, on prend N
assez grand pour que
r
N |x1−x0|
1−r
< <, ce qui montre que la suite est une suite de Cauchy.
Puisque dans R, toute suite de Cauchy converge, il existe un nombre a ∈ R tel que
la suite {x n } converge vers a. Montrons que a est un point fixe de f . Pour cela, on doit
montrer que f est continue. En fait, f est mˆ eme uniform´ ement continue sur R. En effet,
soit > 0, et prenons δ = . Alors si |x − x
| < δ,
|f (x) − f (x
)| ≤ r|x − x
| < rδ = rr < <.
Comme f est continue, l’image de la suite convergente {x n } de limite a est encore
une suite convergente de limite f (a). Alors,
f (a) = lim
n→∞
f (x n ) = lim
n→∞
x n+1 = lim
n→∞
x n = a.
On peut g´ en´ eraliser l’´ enonc´ e du th´ eor` eme pr´ ec´ edent tout en gardant exactement la
mˆ eme preuve. Nous remplacerons R par un espace K qui a les mˆ emes bonnes propri´ et´ es
que R. Ce devra ˆ etre un espace m´ etrique complet. Comme K pourrait ˆ etre, par exemple,
R
n on notera les ´ el´ ements de K par les lettres v, w. . . D´ efinissons d’abord la notion de
distance d(v, w) entre deux ´ el´ ements de K ; elle aura les mˆ emes propri´ et´ es que la valeur
absolue |x − x
| dans R.
11 Compression d’images par fonctions it´ er´ ees
Il faut maintenant d´ emontrer l’existence de a. Pour obtenir a on va prendre un
point quelconque x 0 ∈ R et construire la suite de ses it´ er´ ees x 1 = f (x 0 ), x 2 = f (x 1 ),
. . ., x n+1 = f (x n ). . . Si x 1 = x 0 , alors x 0 est un point fixe. Consid´ erons le cas x 1 = x 0 .
Alors,
|x n+1 − x n | = |f (x n ) − f (x n−1 )| ≤ r|x n − x n−1 |.
En it´ erant, on obtient
|x n+1 − x n | ≤ r
n
|x 1 − x 0 |.
On veut montrer que la suite {x n } converge vers un point a ∈ R et que sa limite a est
un point fixe de f . Pour montrer qu’une suite converge sans avoir de candidat pr´ ealable
pour sa limite, il existe un outil tr` es puissant : il suffit de montrer que c’est une suite de
Cauchy. (Rappel : une suite {x n } est une suite de Cauchy si ∀ > 0, ∃N ∈ N tel que, si
n, m > N , alors |x n − x m | < <.) Supposons n > m. Alors,
|x n − x m | = |(x n − x n−1 ) + (x n−1 − x n−2 ) + · · · + (x m+1 − x m )|
≤ |x n − x n−1 | + |x n−1 − x n−2 | + · · · + |x m+1 − x m |
≤ (r
n−1 + r
n−2 + · · · + r
m )|x 1 − x 0 |
≤ r
m (r
n−m−1 + · · · + 1)|x 1 − x 0 |
≤
r
m
1−r |x 1 − x 0 |.
Pour que |x n − x m | < <, il suffit donc de prendre m assez grand pour que
r
m
|x 1 − x 0 |
1 − r
< <,
c’est-` a-dire r
m <
(1−r)
|x1−x0| . Comme 0 < r < 1 et donc, r
m < r
N pour m > N, on prend N
assez grand pour que
r
N |x1−x0|
1−r
< <, ce qui montre que la suite est une suite de Cauchy.
Puisque dans R, toute suite de Cauchy converge, il existe un nombre a ∈ R tel que
la suite {x n } converge vers a. Montrons que a est un point fixe de f . Pour cela, on doit
montrer que f est continue. En fait, f est mˆ eme uniform´ ement continue sur R. En effet,
soit > 0, et prenons δ = . Alors si |x − x
| < δ,
|f (x) − f (x
)| ≤ r|x − x
| < rδ = rr < <.
Comme f est continue, l’image de la suite convergente {x n } de limite a est encore
une suite convergente de limite f (a). Alors,
f (a) = lim
n→∞
f (x n ) = lim
n→∞
x n+1 = lim
n→∞
x n = a.
On peut g´ en´ eraliser l’´ enonc´ e du th´ eor` eme pr´ ec´ edent tout en gardant exactement la
mˆ eme preuve. Nous remplacerons R par un espace K qui a les mˆ emes bonnes propri´ et´ es
que R. Ce devra ˆ etre un espace m´ etrique complet. Comme K pourrait ˆ etre, par exemple,
R
n on notera les ´ el´ ements de K par les lettres v, w. . . D´ efinissons d’abord la notion de
distance d(v, w) entre deux ´ el´ ements de K ; elle aura les mˆ emes propri´ et´ es que la valeur
absolue |x − x
| dans R.