IFS, fractales & jeu du chaos

Cadre mathématique et démonstrations


Distances


Une distance est une application $d$ sur un ensemble et à valeurs positives qui vérifie les trois propriétés:
  • $d(x,y)=d(y,x)$ (symétrie)
  • $d(x,y)=0 \iff x=y$ (séparation)
  • Pour tous $x$, $y$ et $z$, $d(x,y)\leqslant d(x,z)+d(z,y)$ (inégalité triangulaire)


Par exemple, en géométrie dans le plan $\R^2$, la distance $d(A,B)=AB$ entre les points $A$ et $B$ est bien sûr une distance au sens mathématique:
  • $AB=BA$
  • $AB=0 \iff A=B$
  • pour tout point $C$, $AB\leqslant AC+CB$


Si le plan est rapporté à un repère orthonormé, et que $A\left( x;y\rp$ et $B\left( x',y'\rp$, alors
\[d(A,B)=AB=\sqrt{\left( x-x'\rp^2+\left( y-y'\rp^2}\]

est une distance, la distance euclidienne.

On peut définir de nombreuses distances, suivant le contexte, les éléments dont on cherche à mesurer la distance: distances entre des points, entre des fonctions, entre des matrices, …  et aussi, ce qui nous intéresse plus ici, entre des ensembles géométriques de points (c'est-à-dire des figures géométriques, ou encore des images).


Distance et norme

Un espace normé est un espace muni d'une norme, un espace métrique est lui muni d'une distance.

Une norme, notée en général $\|x\|$, induit immédiatement une distance par la relation $d(x,y)=\|y-x\|$.
La réciproque n'est par contre pas toujours vraie: une distance peut ne pas découler d'une norme.

En d'autres termes, un espace normé est nécessairement aussi métrisé (ou métrique), par contre un espace métrique n'est pas toujours normé.
La notion de norme est plus fine que celle de distance.

Une distance entre éléments d'un espace permet par contre aussi d'induire un distance entre des ensembles d'éléments: c'est la distance de Hausdorff.


Distance de Hausdorff

Définition et propriété


En traitement d'image par exemple, on cherche à donner un sens à la proximité de deux images entre elles: deux images, par exemple une floue et la même filtrée et plus nette, sont elles "proches" entre elles.
Plus précisément sur une série d'images filtrées et traîtées, laquelle est la plus "proche" de l'image souhaitée.
Comment quantifier cette "proximité" ? Comment vérifier que deux motifs, ou parties d'images sont identiques ?

Une distance est un outil mathématique qui permet exactement de définir la notion de proximité.
La distance de Hausdorff est une distance qui permet de mesurer la différence entre des ensembles, de points par exemple (c'est à dire des images).
Pour définir cette distance de Hausdorff, on a besoin de la définition de la distance d'un point à un ensemble, puis de celle de voisinage d'un ensemble.


Définition: distance d'un point à un ensemble La distance d'un point $x$ à un ensemble $A$ est la plus petite des distances entre $x$ et les points de $A$:
\[d(x,A)=\inf\Bigl\{ d(x,y) , y\in A \Bigr\}\]


\[\begin{pspicture}(-2,1)(5,5.5) \psellipse[fillstyle=solid,fillcolor=lightgray](2,2)(3,1) \rput(1.1,2){\Large$A$} \rput(0,5){\large$\tm$}\rput(-.25,5.2){\large$x$} \psline[linewidth=1.5pt,linecolor=magenta,arrowsize=8.5pt]{<->}(0,5)(0.4,2.82) \rput(1.1,4){\large\magenta$d(x,A)$} \end{pspicture}\]




Définition: Voisinage On appelle voisinage, ou $r-voisinage$ d'un ensemble $A$ de points du plan l'ensemble des points
\[V_r(A)=\Bigl\{ x \text{ tel que } d(x,A)<r \Bigr\}\]


\[\begin{pspicture}(-2.2,0)(6.2,4.2) \psellipse[fillstyle=solid,fillcolor=lightgray](2,2)(3,1) \rput(1.1,2){\Large$A$} \psellipse[fillstyle=vlines,hatchsep=2.1em,hatchcolor=blue](2,2)(4,1.9) \psellipse[linestyle=none,fillstyle=solid,fillcolor=white](.42,3.15)(.29,.28) \psellipse[linestyle=none,fillstyle=solid,fillcolor=white](.42,3.15)(.29,.28) \psellipse[linestyle=none,fillstyle=solid,fillcolor=white](4,3.15)(.5,.28) \psline[linewidth=2pt,linecolor=magenta,arrowsize=7pt]{<->}(4,2.7)(4.5,3.5) \rput(4,3.2){\large\magenta$r$} \psellipse[linestyle=none,fillstyle=solid,fillcolor=white](.42,3.15)(.29,.28) \rput(.2,3.1){\large\blue$V_r(A)$} \end{pspicture}\]



Définition: distance de Hausdorff La distance de Hausdorff entre deux ensembles $A$ et $B$ est définie par
\[d_H(A,B)=\inf\Bigl\{ r>0 \text{ tel que } A\subset V_r(B) \text{ et } B\subset V_r(A) \Bigr\} \]


La distance de Hausdorff est définie à partir de la notion de voisinage, qui elle-même est dépend de la distance dans l'espace considéré.
La distance de Hausdorff n'est pas une distance sur tous les ensembles; par exemple, pour des ensembles de points non-bornés, la distance de Hausdorff n'est pas définie (ou vaut dans ce cas l'infini).
Par contre, en se limitant aux ensembles compacts, qui sont dans le plan les ensembles fermés et bornés, la distance de Hausdorff définie bien une distance: en notant $\mathcal{K}(E)$ l'ensemble des ensembles compacts de $E$,

Propriété: La distance de Hausdorff est une distance sur $\mathcal{K}(E)$.


Démonstration. Il faut démontrer les trois propriétés d'une distance.
  • Symétrie: elle est évidente, la définition de la distance étant elle même symétrique: $d_H(A,B)=d_H(B,A)$.

  • Séparation: Supposons $A$ et $B$ sont deux ensembles compacts tels que $d_H(A,B)=0$.
    Cela signifie que pour tout $\epsilon>0$, on a $A\subset V_\epsilon(B)$ (et de même $B\subset V_\epsilon(A)$).
    Prenons par exemple $\epsilon=\dfrac1n$, tel que $A\subset V_{1/n}(B)£$.
    Alors, il existe $y_n\in B$ tel que $d\left( x,y_n\rp<\dfrac1n$.
    Comme pour tous entiers $p$ et $q$ on a d'après l'inégalité triangulaire $d\left( y_p,y_q\right) \leqslant d\left( y_p,x\rp+d\left( x,y_q\rp \leqslant\dfrac1p+\dfrac1q$, la suite $\left( y_n\rp$ est de Cauchy. Comme on est dans un espace complet, cette suite converge, ce qui signifie qu'il existe $y$ tel que $\lim_{n\to+\infty} y_n\to y$.
    Enfin, comme $B$ est compact, et que pour tout $n$, $y_n\in B$, on a aussi que $y\in B$.

    Ainsi, en passant à la limite, on obtient $d(x,y)=0$ soit donc $x=y\in B$.
    Finalement, on a donc $A\subset B$.


    En raisonnant de même en interchangeant $A$ et $B$, on obtient aussi $B\subset A$, et donc $A=B$.

  • Inégalité triangulaire: soit $A$, $B$ et $C$ trois ensembles compacts, on cherche à montrer que, $d_H(A,C)\leqslant d_H(A,B)+d_H(B,C)$.
    On note $d=d_H(A,C)$, $d_1=d_H(A,B)$ et $d_2=d_H(B,C)$.
    On a alors $A\subset V_{d_1}(B)$ et $B\subset V_{d_2}(C)$.
    Ainsi, $A\subset V_{d_1}\left( V_{d_2}\left( C\rp\rp$
    Or $V_{d_1}\left( V_{d_2}\left( C\rp\rp\subset V_{d_1+d_2}(C)$ d'après le lemme suivant.
    Ainsi, $A\subset V_{d_1+d_2}(C)$.
    De même, on arrive symétriquement à $C\subset V_{d_1+d_2}(A)$.

    On a ainsi, $d_H(A,C)\leqslant d_1+d_2=d_H(A,B)+d_H(B,C)$.


Lemme: Pour tout ensemble $A$, et $\alpha>0$ et $\beta>0$, on a $V_\alpha\left( V_\beta\left( A\rp\rp\subset V_{\alpha+\beta}(A)$.


Démonstration. Soit $x\in V_\alpha\left( V_\beta\left( A\rp\rp$, alors il existe $y\in V_\beta(A)$ tel que $d(x,y)<\alpha$.
De même, comme $y\in V_\beta(A)$, il existe $z\in A$ tel que $d(y,z)<\beta$.

D'après l'inégalité triangulaire, on a $d(x,z)\leqslant d(x,y)+d(y,z) <\alpha+\beta$, ce qui signifie que $x\in V_{\alpha+\beta}(A)$.



Exemples



Exemple 1:
On cherche par exemple la distance de Hausdorff entre les ensembles $A$ et $B$ suivants, le carré $A$ et le disque $B$:
\[\begin{pspicture}(-3,-2.2)(3.2,2.8) \pspolygon[linecolor=blue,fillstyle=vlines,hatchcolor=blue,hatchsep=1.1em](2,-2)(2,2)(-2,2)(-2,-2) \pscircle[linecolor=red,fillstyle=hlines,hatchcolor=red,hatchsep=1.1em](1,.5){2} \pscircle[fillstyle=solid,fillcolor=white,linestyle=none](-1.7,-1.6){.25} \rput(-1.7,-1.5){\large\blue$A$} \rput(2.5,.3){\large\red$B$} \end{pspicture}\]


On trace le plus petit voisinage de $A$ contenant $B$, et de même le plus petit voisinage de $B$ contenant $A$:
\[\begin{pspicture}(-3.5,-3.5)(3.5,3.5) \pspolygon[linecolor=blue,fillstyle=vlines,hatchcolor=blue,hatchsep=1.1em](2,-2)(2,2)(-2,2)(-2,-2) \pscircle[fillstyle=solid,fillcolor=white,linestyle=none](-1.7,-1.6){.25} \rput(-1.7,-1.5){\large\blue$A$} \pscircle[linecolor=red,fillstyle=hlines,hatchcolor=red,hatchsep=1.1em](1,.5){2} \pscircle[fillstyle=solid,fillcolor=white,,linestyle=none](2.5,.3){.3} \rput(2.5,.3){\large\red$B$} \psline[arrowsize=6pt,linecolor=blue,linewidth=1.5pt]{<->}(-3,1)(-2,1) \rput(-2.5,1.3){\large\blue$r_1$} \psline(3,-2)(3,2) \psline(2,3)(-2,3) \psline(-3,2)(-3,-2) \psline(-2,-3)(2,-3) \psarc(2,2){1}{0}{90} \psarc(-2,2){1}{90}{180} \psarc(-2,-2){1}{180}{270} \psarc(2,-2){1}{270}{360} \end{pspicture}\]



\[\begin{pspicture}(7,-3.5)(15,4.5) \pspolygon[linecolor=blue,fillstyle=vlines,hatchcolor=blue,hatchsep=1.1em](12,-2)(12,2)(8,2)(8,-2) \pscircle[linecolor=red,fillstyle=hlines,hatchcolor=red,hatchsep=1.1em](11,.5){2} \psline[arrowsize=6pt,linecolor=red,linewidth=1.5pt]{<->}(13,.5)(14.95,.5) \rput(14,.8){\large\red$r_2$} \pscircle(11,.5){3.95} \pscircle[fillstyle=solid,fillcolor=white,linestyle=none](8.3,-1.6){.25} \rput(8.3,-1.5){\large\blue$A$} \pscircle[fillstyle=solid,fillcolor=white,,linestyle=none](12.5,.3){.3} \rput(12.5,.3){\large\red$B$} \end{pspicture}\]



On a ici $r_1<r_2$ et $B\subset V_{r_1}(A)$ mais $A\not\subset V_{r_1}(B)$
Par contre $A\subset V_{r_2}(B)$ et $B\subset V_{r_1}(A)\subset V_{r_2}(A)$.
Ainsi, $d_H(A,B)=r_2$.

Exemple 2: La distance de Hausdorff est une distance sur $\mathcal{K}(E)$, l'ensemble des compacts (ou fermés bornés, dans le plan), pas sur $\mathcal{P}(E)$, l'ensemble des parties de $E$.
Par exemple, si $A$ est le carré unité ouvert: $A=]0;1[\tm]0;1[$, et $\overline{A}$ le carré unité fermé: $\overline{A}=[0;1]\times[0;1]$, on a $d_H\left( A,\overline{A}\rp=0$, mais bien sûr $A\not=\overline{A}$.


Application contractante


Une application contractante est une application qui rapproche les points, c'est-à-dire que les images de deux points sont plus proches que les points eux-même. Plus précisément,
Définition: application contractante Une application $f$ est contractante si il existe un nombre réel $k<1$ tel que, pour tous $x$ et $y$,
\[d\left( f(x),f(y)\rp\leqslant k\,d\left( x,y\rp\]


Il faut ici faire attention à la distance utilisée. Ce n'est pas forcément la même distance à gauche et à droite de l'inégalité précédente. La distance euclidienne peut être utilisée s'il s'agit de distance entre points du plan, celle de Hausdorff pour des ensembles de points.


L'opérateur de Hutchinson $F$ est contractant


On peut maintenant revenir sur l'opérateur de Hutchinson.

Propriété: L'opérateur de Hutchinson $F$ est contractant sur $\mathcal{K}(E)$ pour la distance de Hausdorff.



Pour démontrer cette propriété, qui est la propriété fondamentale garantissant l'existence et l'unicité de l'attracteur d'un IFS, on a besoin de résultats intermédiaires.

Lemme 1: Pour tous ensemble $A$ et $B$, et réel $k>0$, on a $V_k(A)\cup V_k(B)\subset V_k\left( A\cup B\rp$.


Démonstration. Soit $x\in V_k(A)\cup V_k(B)$. $A$ et $B$ jouant des rôles symétriques, on peut supposer $x\in V_k(A)$.
Il existe donc $y\in A$ tel que $d(x,y)<k$.
Mais alors, on a aussi $y\in A\cup B$ et toujours $d(x,y)<k$, ce qui signifie que $x\in V_k\left( A\cup B\rp$.


Lemme 2: Soit $f$ une contraction du plan de rapport $r$, alors, pour tous ensembles $A$ et $B$,
\[d_H\left( f(A),f(B)\rp\leqslant d_H(A,B)\]



Démonstration. On pose $k=d_H(A,B)$.
Soit $a'\in f(A)$, alors il existe $a\in A$ tel que $a'=f(a)$.
Comme $k=d_H(A,B)$, on a $A\subset V_k(B)$, et donc il existe $b\in B$ tel que $d(a,b)\leqslant k$. On pose alors $b'=f(b)$ et on a, comme $f$ est $r$-contractante,
\[ d\left( a',b'\rp=d\left( f(a),f(b)\rp \leqslant r d(a,b) \leqslant rk\]

En d'autres termes, on a trouvé que pour tout $a'\in f(A)$, il existe $b'\in f(B)$ tel que $d\left( a',b'\rp\leqslant rk$, d'où $f(A)\subset V_{rk}\left( f(B)\rp$.

De même, en inversant les rôles de $A$ et $B$, on aboutit à $f(B)\subset V_{rk}\left( f(A)\rp$.
On a donc finalement, $d_H\left( f(A),f(B)\rp\leqslant rk=rd_H(A,B)$.


Lemme 3: Pour tous compacts $A$ et $B$ du plan,
\[d_H\left( A\cup B,C\cup D\rp\leqslant \max\Bigl\{d_H(A,C),d_H(B,D)\Bigr\}\]



Démonstration. On pose $d=d_H(A,C)$ et $d'=d_H(B,D)$.
On a alors, par définition de la distance de Hausdorff,
\[A\subset V_d(C) \ \text{ et } \ C\subset V_d(A)\]

et de même
\[B\subset V_{d'}(D) \ \text{ et } \ D\subset V_{d'}(B)\]

et donc, en notant $k=\max\left\{}\newcommand{\ra}{\right\} d,d'\ra$,
\[A\subset V_k(C) \ \text{ et } \ C\subset V_k(A)\]

et de même
\[B\subset V_k(D) \ \text{ et } \ D\subset V_k(B)\]


Or, d'après le lemme 1, $V_k(C)\cup V_k(D) \subset V_k\left( C\cup D\rp$
et donc,
\[A\cup B\subset V_k(C)\cup V_k(D) \subset V_k\left( C\cup D\rp\]

et de même
\[C\cup D\subset V_k(A)\cup V_k(B) \subset V_k\left( A\cup B\rp\]

et on a donc,
\[d_H\left( A\cup B,C\cup D\rp\leqslant k=\max\left\{}\newcommand{\ra}{\right\} d,d'\ra =\max\Bigl\{d_H(A,C),d_H(B,D)\Bigr\}\]





On peut maintenant démontrer la propriété fondamentale sur l'opérateur de Hutchinson.

Démonstration. Soit $A$ et $B$ deux ensembles compacts du plan, alors
\[d_H\left( F(A),F(B)\right) =d_H\Bigl( f_1(A)\cup f_2(A)\cup\dots\cup f_N(A), f_1(B)\cup f_2(B)\cup\dots\cup f_N(B)\Bigr) \]

soit, en utilisant le lemme 3,
\[\begin{array}{ll} d_H\left( F(A),F(B)\right) &=d_H\Bigl( f_1(A)\cup D, f_1(B)\cup E\Bigr)\\[1em] &\leqslant\max\Bigl\{ d_H\Bigl( f_1(A),f_1(B)\Bigr) , d_H\left( D,E\right) \Bigr\} \enar\]

avec $D=f_2(A)\cup\dots f_N(A)$ et $E=f_2(B)\cup\dots f_N(B)$.
Or, comme $f_1$ est $r_1$-contractante, d'après le lemme 2, $d_H\Bigl( f_1(A),f_1(B)\Bigr)\leqslant r_1d_H(A,b)$, d'où
\[d_H\left( F(A),F(B)\right) \leqslant \max\Bigl\{ r_1d_H (A,B), d_H(D,E)\Bigr\}\]

On continue avec les ensemble $D$ et $E$:
\[\begin{array}{ll} d_H(D,E) &=d_H\Bigl( f_2(A)\cup f_3(A)\cup\dots\cup f_N(A), f_2(B)\cup f_3(B)\cup\dots\cup f_N(B)\Bigr) \\[1em] &=d_H\Bigl( f_2(A)\cup D',f_2(B)\cup E'\Bigr) \enar\]

avec $E'=f_3(A)\cup\dots\cup f_N(A)$ et $D'=f_3(B)\cup\dots\cup f_N(B)$ d'où, à nouveau à l'aide du lemme 3,
\[\begin{array}{ll} d_H(D,E)\leqslant \max\Bigl\{ d_H\Bigl(f_2(A),f_2(B)\Bigr),d_H\left( D',E'\rp\Bigr\} \enar\]

avec, d'après le lemme 2, $d_H\Bigl(f_2(A),f_2(B)\Bigr)\leqslant r_2d_H(A,B)$.
En poursuivant ainsi, on arrive donc enfin à:
\[\begin{array}{ll} d_H\left( F(A),F(B)\rp&\leqslant \max\Bigl\{ r_1d_H(A,B),r_2d_H(A,B),\dots,r_Nd_H(A,B)\Bigr\}\\[1.2em] &=\max\Bigl\{ r_1,r_2,\dots,r_N\Bigr\} d_H(A,B)\\[1em] &=rd_H(A,B) \enar\]

avec $r=\max\Bigl\{ r_1,r_2,\dots,r_N\Bigr\}<1$.



Théorème du point fixe


Il existe de nombreux théorèmes du point fixe en analyse. Ils permettent de démontrer l'existence et l'unicité d'une solution à des problèmes, en fournissant de plus une méthode constructive pour les déterminer (ou du moins en donner une approximation, avec une précsion souhaitée).

Le théorème du point fixe utilisé ici est celui de Banach, ou de Picard, et se place dans un espace métrique complet.
Un espace métrique est un espace dans lequel on peut mesurer, c'est-à-dire muni d'une distance telle que vue précédemment. On note justement $d$ cette distance dans le théorème suivant.

Théorème du point fixe de Banach / Picard: Une application $f$ contractante dans un espace métrique complet admet un unique point fixe, c'est-à-dire un unique $x$ tel que $f(x)=x$.

De plus, $x$ est la limite de toute suite $\left( x_n\rp$ définie par récurrence selon $x_{n+1}=f\left( x_n\rp$.
On a de plus alors les majorations
\[d\left( x_n,x\right) \leqslant k^n d\left( x_0,x\right)\]

et
\[d\left( x_n,x\right) \leqslant \dfrac{k^n}{1-k} d\left( x_0,x_1\right)\]

où $k<1$ est le rapport de contraction de $f$.


Démonstration: Ce théorème donne deux résultats: l'existence et l'unicité du point fixe $x$.
On démontre les deux séparemment.
  • Unicité. Supposons au contraire qu'il y ait deux points fixes $x$ et $y$: $f(x)=x$ et $f(y)=y$ avec $x\not=y$.
    On aurait alors $d\left( f(x)-f(y)\right) = d\left( x,y\right)$ or, comme $f$ est contractance de rapport $k<1$, on a aussi $d\left( f(x)-f(y)\rp\leqslant kd(x,y)<d(x,y)$.
    On devrait donc avoir $d(x,y)<d(x,y)$ ce qui est impossible.
    Ainsi, si un point fixe existe, il est nécessairement unique.
  • Existence.
    L'existence se démontre par le procédé construcif même utilisé tout au long de ces pages: soit $(x_n)$ une suite définie par récurrence par $x_{n+1}=f\left( x_n\rp$.
    Alors on, our tout entier $n$ et $p$
    \[d\left( x_n,x_p\rp\leqslant \dfrac{k^n}{1-k}d(x_0,x_1)\]

    avec, comme $0<k<1$, $\dsp\lim_{n\to+\infty}k^n=0$.
    Ceci montre que la suite $\left( x_n\rp$ est une suite de Cauchy, et alors, comme on est dans un espace complet, la suite converge donc vers une limite $x$.

    Par unicité du point fixe, on voit donc que ce procédé constructif ne dépend pas du point initial $x_0$ de la suite: pour tout $x_0$ la suite $\left( x_n\rp$ ainsi définie converge, vers le point fixe de $f$.


Liste des figures et bibliographie


Lien


LongPage: h2: 2 - h3: 6