La nuit des courbes monstres
Courbe de Hilbert (7 itérations)
Nous nous étions arrêtés la semaine dernière aux monstres du peuple des courbes, à savoir les courbes continues mais dérivables nulle part (Courbe de Weierstrass, de Bolzano, du blanc-manger, de Koch...). Mais ces courbes restent des monstres gentils, face aux démons réveillés par Peano. Il est temps de passer du côté obscur, avec les courbes de Peano-Hilbert, qui parviennent à visiter chaque point d'un carré unité.
La courbe de Peano (1890)
Courbe de Peano (4 itérations)
L'histoire se déroule à la fin du XIXe siècle, où Cantor étudie l'infini. De ses travaux découlent différents type d'infini : le dénombrable et le continu (et le reste). D'un côté, il y a les ensembles dénombrables, qui ont "autant" d'élément qu'il y a d'entiers dans ℕ. De l'autre, les ensembles continus, qui ont "autant" d'éléments qu'il y a des réels dans ℝ.
Un ensemble de nombres (pourvu qu'il ne soit pas trop compliqué) est soit fini, soit dénombrable, soit continu. Par exemple, l'ensemble des nombres pairs est dénombrable : il y a autant d'entiers pairs que d'entiers (en doublant un entier, on trouve toujours un entier pair, et vice-versa). De même, en étirant un segment de longueur 1 ([0,1]), on peut obtenir un segment de longueur 2 ([0,2]) : il y a "autant" d'éléments dans [0,1] que dans [0,2]. En poussant un peu, on peut voir qu'il y a autant de nombres dans [0,1] que dans ℝ.
Cantor finit par démontrer (en 1877) qu'il y a "autant" d'éléments dans [0,1] que dans [0,1]×[0,1]. Dit autrement, il y a "autant" d'élément dans le côté d'un carré que dans le carré ! Lui-même n'arrive pas à croire ce qu'il vient de démontrer !
Pour s'en convaincre, il faudrait construire une courbe (le déformé d'un segment, dont autant de point que dans [0,1]) qui recouvre entièrement un carré. On montrerait alors qu'il y a le même nombre de points dans un carré et dans son côté.
Quand on cherche, on trouve ! En 1890, c'est Peano qui a eu le privilège de donner le premier exemple d'une telle courbe, qui seront appelés courbes de Peano-Hilbert.
La courbe est donnée par la fonction suivante :
où (t1t2t3...)3 est la décomposition de x∈[0,1] en base 3 (tk∈{0,1,2})
et k(0)=2, k(1)=1 et k(2)=0
J'admets, cette formulation est complètement tordue, mais je la trouvais au moins aussi jolie que la courbe qu'elle engendre !
En fait, on construit dans la pratique la courbe de Peano plutôt comme la limite d'une suite de courbes :
4 premières étapes de la construction de la courbe de Peano
Pour construire cette courbe, on part d'un carré que l'on divise en 9 régions (3×3). On numérote alors ces régions en suivant le chemin en N de la première étape illustré ci-dessus. En reliant les centres des cases, on trouve la première étape de la courbe de Peano.
Pour obtenir la deuxième étape, on part de la grille de 9 régions déjà dessinée, et on découpe chacune d'entre elles en 9 cases (on obtient une grille vierge de sudoku). Pour chaque région, on numérote les cases de 1 à 9 en suivant le motif en N (ou son symétrique par un axe vertical), de façon à ce que le 9 d'une région touche le 1 de la suivante. Pour chaque région, on relie de 1 à 9 le centre des cases : on obtient l'étape 2 de la construction de la courbe de Peano.
On réitère ce principe pour obtenir les étapes suivantes de la construction.
De façon générale, on peut obtenir de nombreuses courbes de Peano-Hilbert par ce procédé. En découpant à chaque étape les carrés en 4, on peut par exemple obtenir la courbe de Hilbert, la courbe de Lebesgue ou la courbe de Moore (De telles courbes sont appellées courbes de Peano-Hilbert binaire).
La courbe de Peano est une fonction P(x)=(x(t),y(t)). On peut alors remarquer que les deux fonctions x(t) et y(t) sont continues partout et dérivables nulle part ! Tout concorde !
Graphe de la première composante de la fonction de Peano : continue partout, dérivable nulle part
La courbe de Hilbert (1891)
Courbe de Hilbert (7 itérations)
L'année suivante, Hilbert donne un autre exemple de courbe remplissante, donnant à ce type de courbe le nom de courbe de Peano-Hilbert. Elle se construit sur le même principe que la courbe précédente.
6 premières étapes de la construction de la courbe de Hilbert
Grâce à un langage comme Logo (Mon tout premier langage de programmation, découvert en CM1 !) et le L-système, on peut construire facilement ce type de courbe.
Le L-système est une façon de décrire ce type de courbe de manière algorithmique. Pour cela, il suffit simplement de définir des règles de remplacement. Pour la courbe de Hilbert, elles sont :
"L" ↦ "+RF-LFL-FR+"
"R" ↦ "-LF+RFR+FL-"
A l'étape 0, on commence par "L" (l'axiome). Chaque étape consiste alors à remplacer les L et R par l'expression correspondant.
Etape 0 : "L"
Etape 1 : "+RF-LFL-FR+"
Etape 2 : "+-LF+RFR+FL-F-+RF-LFL-FR+F+RF-LFL-FR+-F-LF+RFR+FL-+"
Pour dessiner la n-ième étape de la construction de la courbe de Hilbert, on commence par calculer l'expression de l'étape n. On enlève ensuite les L et R qui deviennent inutiles, puis on dessine la courbe en convenant que :
+ signifie tourner à gauche
- signifie tourner à droite
F signifie avancer d'une unité
Par exemple, l'algorithme de l'étape 1 est : "+F-F-F+", c'est à dire :
gauche - avancer - droite - avancer - droite - avancer - gauche
La courbe de Peano peut se représenter de la même façon, avec pour axiome X et les deux règles de remplacement :
"X" ↦ "XFYFX+F+YFXFY-F-XFYFX"
"Y" ↦ "YFXFY-F-XFYFX+F+YFXFY"
La courbe de Lebesgue (1904)
Courbe de Lebesgue (4 itérations)
Cette courbe se construit sur le même principe que les deux précédente (c'est une courbe de Peano-Hilbert binaire), en découpant le carré unité en N, puis en reportant exactement le même motif dans chaque sous-case.
Reliez les points
Contrairement aux courbes de Peano et deux Hilbert, cette courbe est un peu moins monstrueuse. En effet, elle est dérivable presque partout !
Toutes ces courbes (à priori, de dimension 1) ont la particularité d'être de dimension 2 (de Hausdorff) !
Les autres
Terminons cet article avec quelques autres jolies courbes de la famille Peano-Hilbert:
La courbe de Moore (7 itérations)
C'est simplement 4 courbes de Hilbert recollées
La courbe de Sierpiński
Sources :
Courbes remplissante sur Mathcurves.com (D'où proviennent la courbe de Lebesgue et de Sierpiński)
Continuous Nowhere Differentiable Functions - Thèse de Johan This