Qu’ont en commun un couvercle de la Vache qui Rit et un principe de compression d’images à l’aide de fractales (par exemple un programme simple pour tracer la fougère)? L’explication exige le détour par les travaux du mathématicien polonais, Stefan Banach.
Jouons le jeu suivant: étant donné un point du couvercle, associons-lui le point correspondant sur la boucle d’oreille gauche. Ainsi, à l’extrémité du menton de la vache on associe l’extrémité du menton de la petite vache dessinée sur la boucle d’oreille gauche. Au coin gauche de la bouche, le coin gauche de la bouche, etc.
Cette association est en fait une fonction, f, dont le domaine est le couvercle et l’image est la boucle d’oreille gauche. La question qui nous intéresse est la suivante:
y a-t-il un point qui est envoyé sur lui-même par ce procédé?
Un tel point sera appelé point fixe de la fonction définie ci-dessus.
Allons-y par élimination: on voit bien que ce n’est pas l’extrémité de la corne droite, appelée \(p_0\), puisque son image est l’extrémité de la corne droite de la vache apparaissant sur le couvercle, soit \(p_1\). Mais ce n’est pas non plus \(p_1\), puisque son image est \(p_2\), etc. On génère ainsi une suite infinie. Mais, en pratique, on ne voit que les premiers points \(p_1, …, p-n\). Tous les autres semblent confondus en un point a qui semble bien un point fixe. Essayons maintenant avec le point situé à la base du cou, \(q_0\), et ses images, \(q_1, q_2, …\) Ici, encore on ne voit que les premiers points et tous les autres semblent confondus avec le même point fixe a! Il est facile de se convaincre que si l’on partait de n’importe quel point du couvercle et qu’on répétait le même processus, on aboutirait à a.
Ce que nous venons de découvrir n’est pas anodin! En fait, c’est un exemple d’un des plus grands théorèmes des mathématiques: le théorème de point fixe de Banach. Que dit ce célèbre théorème? Pour l’énoncer, il nous faut introduire un peu de vocabulaire. Notre couvercle est un ensemble de points, M et, étant donné deux points p et q de M, on peut mesurer (ou calculer) la distance, d (p, q), qui sépare p et q. Un tel ensemble s’appelle un espace métrique. On a aussi une fonction \(f : M \to M\). L’image du couvercle par cette fonction est la petite boucle d’oreille gauche. C’est donc une fonction qui contracte les distances: si p et q sont situés à distance d(p, q) l’un de l’autre, leurs images f(p) et f(q) sont plus proches d’un facteur \(c \in ]0,1[: d(f(p),f(q))≤cd(p,q).\)
Une telle fonction est appelée une contraction. Nous pouvons maintenant énoncer le théorème.
(Nous reviendrons sur le mot complet que nous n’avons pas encore défini.) Comment montre-t-on le théorème? Exactement comme le jeu qu’on a joué avec notre couvercle. On prend un point, \(p_0\), son image, \(p_1 = f(p_0)\), l’image \(p_2\) de \(p_1\) et, plus généralement, \(p_{n+1} = f(p_n).\) On obtient ainsi une suite infinie \(\{pn\}\), mais dont on ne voit que les premiers termes. Tous les autres sont confondus. Si on prend une loupe, on voit un peu plus de termes, mais les autres sont confondus. Même chose si on prend un microscope, ou encore un microscope électronique. Donc, quelle que soit la précision que l’on choisit, on ne distingue qu’un nombre fini de termes et tous les autres (en nombre infini) sont trop groupés pour qu’on les distingue.
Les mathématiciens ont donné un nom à ce concept. Ils diront que la suite \(\{p_n\}\) est une suite de Cauchy.
Le point fixe que l’on cherche est la limite de la suite. Encore faut-il que cette limite existe. D’où la dernière hypothèse du théorème, puisqu’un espace métrique complet est un espace dans lequel toute suite de Cauchy a une limite.
Le théorème affirme aussi que ce point fixe est unique: cette partie est plus facile et vous pouvez vous amuser à donner l’argument.
L’importance du théorème de point fixe de Banach en mathématiques vient surtout de ses applications. En effet, l’ensemble M que nous avons considéré était un disque, soit un ensemble de points. Mais rien n’empêche que les éléments de M, au lieu d’être des points, soient des ensembles ou des fonctions.
L’exemple que nous allons regarder illustre comment une idée toute simple peut mener à une percée scientifique majeure.
Dans cet exemple les éléments de M sont des sous-ensembles bornés (et fermés) du plan et le point fixe sera le triangle de Sierpiński (du nom d’un autre mathématicien polonais, Wacłav Sierpiński).
Ainsi, un exemple d’élément de M est le carré \(B_0\) de côté 1 pour lequel l’origine est situé au coin inférieur gauche:
Il faut travailler un peu pour définir la fonction \(f : M \to M.\) En effet, f(B0) doit aussi être un ensemble. On va introduire trois transformations affines:
\[\begin{array}{r c l}T_1(x,y)&=& \displaystyle \left ( \frac{x}{2}, \frac{y}{2} \right ) \\T_2(x,y)&=& \displaystyle \left ( \frac{x}{2} + \frac{1}{2}, \frac{y}{2} \right ) \\T_3(x,y)&=& \displaystyle \left ( \frac{x}{2} + \frac{1}{4}, \frac{y}{2}+ \frac{1}{2}\right ) \end{array} \]
L’image de \(B_0\) par chacune de ces transformations est un carré de côté 1/2. L’ensemble \(B_1 = f(B_0)\) est la réunion de ces trois images:
Plus généralement, si B est un ensemble, son image, f(B), est définie comme suit:
\[ f(B)=T_1(B) \cup T_2(B)\cup T_3(B) \]
À partir de maintenant, on peut recommencer à jouer. On peut donc calculer
etc. On voit que notre suite converge vers un triangle de Sierpiński S:
Appliquons maintenant f au triangle de Sierpiński S, on retombe sur S! Donc, S est un point fixe de f:
\[f(S) = S,\]
et on a pu construire S comme la limite de la suite d’ensembles \(\{B_n\}\). Que se passerait-il si, au lieu de \(B_0\), on partait d’un autre ensemble, \(C_0\) et qu’on construisait la suite \(\{C_n\},\) où \(C_{n+1} = f (C_n)\)? On aboutirait aussi en S! Faisons ici un deuxième exemple et à vous de faire les suivants.
On voit donc que ce procédé très simple permet de construire des fractales très complexes! Il suffit de bien choisir les transformations affines \(T_i\). La méthode s’appelle les systèmes de fonctions itérées.
Avez-vous compris la méthode? Pour faire le test, essayez d’imaginer une manière de construire le fractale ci-contre.
Pour cela, il vous suffit de choisir un système d’axes et de trouver trois transformations affines, \(T_1(x, y), T_2(x, y)\) et \(T_3(x, y),\) telles que ce fractale soit le point fixe de la fonction:
\[ f(B)=T_1(B) \cup T_2(B)\cup T_3(B).\]
Quatre transformations affines ont permis de construire la fougère de la première page. (Pouvez-vous les trouver? L’une d’elles est plus difficile à imaginer: pour tracer la queue il faut utiliser une projection sur l’axe vertical.)
Très rapidement les mathématiciens ont vu les applications potentielles: la compression d’images.
Au lieu de mettre en mémoire chaque pixel de l’image, on met en mémoire un programme pour la reconstruire. Pour la fougère, un tel programme est très simple et tient en une quinzaine de lignes.
Il a fallu pas mal d’imagination pour adapter la méthode à la compression de vraies photos. La méthode, encore expérimentale, fonctionne et donne de très belles images, mais l’encodage est beaucoup plus fastidieux que dans le format JPEG et ne permet qu’un niveau de compression modéré. Elle ne s’est donc pas (pas encore?) imposée en pratique.
Distance de Hausdorff
On peut définir une distance entre deux ensembles qui fait de l’ensemble des sous-ensembles bornés du plan, M, un espace métrique. Cette distance, appelée distance de Hausdorff, a la propriété que la distance entre deux ensembles est plus petite qu’un nombre e si, avec une précision e, on ne peut affirmer que les deux ensembles sont distincts. La distance entre les deux ensembles est le seuil de précision au-delà duquel on peut les différencier.
Stefan Banach
Stefan Banach est l’un des grands mathématiciens du 20e siècle. Il est né en 1892 dans une localité près de Cracovie qui faisait alors partie de l’empire austro-hongrois. Autodidacte, il a la chance que son génie soit reconnu par Steinhaus, ce qui lui permet d’obtenir un poste d’assistant à Lvov et d’y soutenir sa thèse en 1922. Il y fut nommé professeur en 1924. Même en l’absence de ressources, la présence de Banach à Lvov en fit l’un des grands centres mathématiques de l’Europe jusqu’à sa mort en 1945.
La thèse de Banach posait les premiers fondements de l’analyse fonctionnelle. Grosso modo, l’analyse fonctionnelle est l’étude des fonctions: une fonction est une règle qui associe à tout élément de l’ensemble M un unique élément de l’ensemble N. En analyse fonctionnelle, on utilise comme ensembles M et N, non pas des ensembles de points, mais des ensembles de fonctions. Les applications sont très importantes et le génie de Banach a marqué profondément l’analyse moderne.
