Table des matières

Où nous apprenons que les carrés sont des cercles, et que 2 est au milieu entre 1 et l'infini…

Introduction

Une distance est la longueur du plus court chemin entre deux points donnés. En pratique, elle dépend du mode de transport utilisé. Par exemple une distance « à vol d'oiseau » peut ne pas être très pertinente si vous êtes en voiture et devez suivre les routes pour avancer. Ainsi, les moyens de locomotion correspondent en fait aux chemins possibles pouvant être pris : un oiseau passera par le ciel donc évitera les obstacles au sol, contrairement à un piéton qui aura besoin d'un pont. La distance pour un utilisateur correspondra donc à sa définition de l'espace. Par exemple les distances entre les étoiles ne sont pas perçues de la même façon selon que l'on ait accès ou non à l'hyperespace. Il faut donc fixer ce que l'on entend par espace.

L'espace

On repère un point dans un espace par ses coordonnées. Par exemple un GPS utilisera trois coordonnées pour nous repérer sur Terre : la latitude, la longitude et la hauteur. C'est pour cela qu'on parle d'espace à trois dimensions. Un exemple d'espace à deux dimensions est le plan, où chaque point possède une abscisse $x$ et une ordonnée $y$ qui le caractérisent, on parlera donc du point $(x,y)$. Tout ce qui sera écrit par la suite peut être généralisé à un espace à $n$ dimensions, mais dans les équations et exemples suivants je me contenterai du plan afin de mettre l'accent sur les différentes distances possibles sans que l'espace soit trop compliqué.

Formalisation

Mathématiquement, une distance sur un espace $E$ est une application $d : E \times E \mapsto \mathbb{R}^+$, c'est à dire prenant en entrées deux points de l'espace et ayant comme sortie une valeur dans les nombres réels positifs. De plus, elle doit vérifier les trois propriétés suivantes :

  1. symétrie : Pour tous points $a$ et $b$ nous avons que $d(a,b) = d(b,a)$, c'est à dire que la distance entre $a$ et $b$ a la même valeur que la distance entre $b$ et $a$.
  2. séparation : Pour tous points $a$ et $b$ nous avons que $d(a,b) = 0$ si et seulement si $a=b$, c'est à dire que d'une part la distance entre un point et lui-même est nulle et d'autre part que la distance entre deux points distincts est non nulle.
  3. inégalité triangulaire : Pour tous points $a$, $b$ et $c$ nous avons que $d(a,b) \le d(a,c) + d(c,b)$, c'est à dire qu'il n'est pas possible de réduire la distance entre $a$ et $b$ en passant par un point intermédiaire $c$ (la distance entre $a$ et $b$ est VRAIMENT la longueur du plus court chemin entre $a$ et $b$).

Distance entre mots

Comme toujours, si on se donne la peine de formaliser les notions d'espace et de distance, c'est parce qu'elles sont utilisables dans beaucoup de situations différentes. Par exemple, prenons comme espace l'ensemble des mots possibles avec notre alphabet, et une application $d$ prenant en entrées deux mots et ressortant le plus petit nombre de corrections nécessaires pour passer d'un mot à l'autre. Par corrections, j'entends :

  1. l'insertion d'une lettre
  2. la suppression d'une lettre
  3. le remplacement d'une lettre par une autre
  4. l'échange de deux lettres adjacentes

Avec les trois premières corrections on obtient la distance de Levenshtein, et avec les quatre on obtient la distance de Damerau.

L'idée derrière cette application est de compter le nombre de fautes d'orthographe dans un mot, par exemple $d(or,hors) = 2$ car il faut ajouter deux lettres. Mais on peut comparer des mots n'ayant rien à voir comme $d(bateau,rat) = 4$ car il faut remplacer la première lettre et effacer les trois dernières.

De façon informelle, on prouve assez rapidement que ce sont bien des distances. En effet, les corrections peuvent être inversées en une étape, ce qui permet la symétrie. Les corrections changent bien les mots, ce qui assure la séparation. Et l'inégalité triangulaire s'obtient par définition puisqu'on prend à chaque fois le plus petit nombre de corrections nécessaires.

Distances de Minkowski

Revenons à présent au plan et à des distances plus classiques. Comme précisé précédemment, les distances suivantes sont généralisables à un espace de dimension $n$, mais nous nous focaliserons sur le plan par souci de simplicité. Nous allons d'abord présenter différentes distances, et ensuite montrer en quoi elles font en fait partie de la même famille.

Distance euclidienne

Il s'agit de la distance qui vient habituellement à l'esprit quand on parle de distance sur un plan. Pour tracer tous les points situés à même distance d'un point donné, il suffit de prendre ce point comme centre, d'ouvrir un compas avec la bonne distance, et de tracer :

Plus formellement, la distance euclidienne (que je vais noter $d_2$ pour le moment, vous verrez pourquoi plus tard ^^) entre deux points $A = (x_A,y_A)$ et $B = (x_B,y_B)$ est définie par :

$$d_2(A,B) = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}$$

Exercice : montrer qu'il s'agit bien d'une distance (de même pour les autres ^^).

Si on récrit la définition par $d_2(A,B)^2 = (x_B - x_A)^2 + (y_B - y_A)^2$, cela devrait vous rappeler un peu le théorème de Pythagore, et pour cause :

Ainsi, la distance euclidienne est la distance « à vol d'oiseau », mais comme annoncé il existe des distances moins classiques…

Distance de Manhattan

Supposons que vous soyez au volant de votre voiture / char dans une ville américaine / romaine caricaturale. Prenons par exemple une version un peu idéalisée de New-York où tous les blocs sont strictement carrés. Un pas peut se faire vers le nord, l'est, le sud ou l'ouest, et consiste à avancer vers l'intersection correspondante.

Une autre façon de le voir est de prendre le déplacement de la tour dans le jeu d'échecs. On constate dans l'exemple que si on s'intéresse aux intersections situées à deux pas de distance, on peut aller dans l'intersection située à deux pas au nord, à l'est, au sud ou à l'ouest, mais qu'il faut deux pas pour faire un pas en diagonale pour aller vers les intersections nord-est, sud-est, nord-ouest ou sud-ouest.

Remarque : Contrairement à la distance euclidienne, il n'y a pas qu'un seul chemin de plus courte distance. Par exemple pour aller à l'intersection nord-est on peut aller au nord puis à l'est, ou à l'est puis au nord. Ainsi, contrairement au plan habituel, on ne peut pas parler du plus court chemin, mais plutôt des plus courts chemins.

Formellement, la distance de Manhattan $d_1$ est définie par :

$$d_1(A,B) = |x_A - x_B| + |y_A - y_B|$$

où $|x|$ est la valeur absolue du réel $x$, pour rappel : $|x| = \left\{ \begin{array}{rl} x & \text{si } x \ge 0 \\ -x & \text{si } x < 0 \\ \end{array} \right.$

La distance de Manhattan $d_1$ ressemble un peu à la distance euclidienne $d_2$, à ceci près qu'on a enlevé la racine et les carrés. Toutefois elle est bien différente. Par exemple, en prenant des $x$ réels et plus seulement entiers comme dans le cas de Manhattan, on peut tracer tous les points situés à distance $1$ du centre :

Comme dans l'exemple précédent avec les huit points cardinaux, on obtient un losange et plus un cercle. Ou pour être exact, si on définit un cercle comme l'ensemble des points situés à égale distance d'un centre donné, le cercle pour $d_1$ ressemble à un losange, alors que le cercle pour $d_2$ est arrondi. Changer la distance a changé la forme du cercle.

Distance de Tchebychev

Cette fois nous prenons comme analogie le roi dans le jeu d'échecs : il peut se déplacer d'une case en haut, en bas, à droite, à gauche mais aussi en diagonale. La distance de Tchebychev est tout simplement le plus petit nombre de déplacements nécessaires au roi pour partir d'un point $A$ et arriver au point $B$.

Formellement, la distance de Tchebychev est définie par :

$$d_\infty(A,B) = max(|x_A - x_B|,|y_A - y_B|)$$

Cela peut sembler curieux de la noter $d_\infty$, mais tout sera révélé à la prochaine section, patience ! En attendant, l'ensemble des points situés à distance $1$ du centre forment cette fois-ci un carré, mais maintenant il en faut plus pour vous surprendre, n'est-ce pas ?

Nous allons nous contenter de ces trois distances. Avant de passer à davantage de technique, voilà un (joli, si si) dessin résumant les cercles que nous avons déjà vus :

Généralisation

A l'ordre p

J'ai appelé ces distances des « distances de Minkowski » dans la section précédente, parce qu'elles sont des généralisations de la distance de Minkowski d'ordre $p$, définie par :

$$d_p(A,B) = (|x_A - x_B|^p + |y_A - y_B|^p)^\frac{1}{p}$$

  • Pour $p=1$ nous avons bien $d_1(A,B) = (|x_A - x_B|^1 + |y_A - y_B|^1)^\frac{1}{1} = |x_A - x_B| + |y_A - y_B|$.
  • Pour $p=2$ nous avons $d_2(A,B) = (|x_A - x_B|^2 + |y_A - y_B|^2)^\frac{1}{2}$. Or $x^\frac{1}{2}$ est une notation pour $\sqrt{x}$. Vous pouvez vous en convaincre en appliquant la formule $(x^a)^b = x^{a \times b}$ au cas $a = \frac{1}{2}$ et $b=2$ : $(x^\frac{1}{2})^2 = x$, donc pour un $x$ positif, nous avons bien que $x^\frac{1}{2} = \sqrt{x}$. D'où, comme la somme de deux carrés est positive, $d_2(A,B) = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}$.
  • Pour $p=\infty$… quoi ? Oui, je ne vous ai pas encore dit que $p$ pouvait prendre ses valeurs entre $1$ et l'infini, détail… que vaut $(|x|^p + |y|^p)^\frac{1}{p}$ quand $p$ tend vers l'infini ? Et bien justement $max(|x|,|y|)$ (à prouver ?), c'est pour cela que $d_\infty(A,B) = max(|x_A - x_B|,|y_A - y_B|)$. Bon, vous vous doutez bien qu'il faudra manier ce $p=\infty$ avec précaution, mais admettons.

Bref, les trois distances précédentes sont bien de la même famille, et sont des exemples pour $1 \le p \le \infty$, mais on pourrait en prendre d'autres, comme $p=42$ au hasard… Allez, je vous mets une jolie image de Wikipédia qui généralise mon dessin plus haut :

Norme

Les deux sous-sections suivantes sont un tantinet plus velues que ce qui a précédé, mais si vous êtes toujours là c'est que vous êtes courageux. Il s'agit juste d'esquisser des notions proches de celle de distance, et qui serviront pour la discussion du cas $p=2$.

Prenons un point $A = (x,y)$. On peut tracer le vecteur $\overrightarrow{OA}$ entre l'origine $O = (0,0)$ et le point $A$. Ce vecteur a une direction et une longueur. La norme de $\overrightarrow{OA}$, notée $\|\overrightarrow{OA}\|$, c'est tout simplement la distance entre $0$ et $A$ : $\|\overrightarrow{OA}\| = d(O,A)$. En fait, depuis le début nous confondons le point $A$ avec le vecteur $\overrightarrow{OA} = (x_A,y_A)$. En continuant allègrement, nous pouvons donc obtenir la norme de $A$ en fonction de la distance : $\|A\| = d(O,A)$.

On peut bien sûr parler du vecteur $\overrightarrow{AB}$ et généraliser la présentation. Comme $\overrightarrow{AB} = \overrightarrow{AO} + \overrightarrow{OB} = \overrightarrow{OB} - \overrightarrow{OA}$, nous avons que $d(A,B) = \|\overrightarrow{AB}\| = \|B-A\|$. Ainsi, nous aurions pu partir de la norme et définir la distance par $d(A,B) = \|B-A\|$. C'est ce qui explique les $-$ dans les définitions précédentes des distances. Ce qu'il faut retenir, c'est que les notions de distance et normes sont très proches, et qu'on peut partir de n'importe laquelle pour arriver à l'autre.

En l’occurrence, la norme d'ordre $p$ est définie par :

$$\|A\|_p = (|x_A|^p + |y_A|^p)^\frac{1}{p}$$

Et nous repassons bien à la distance d'ordre $p$ en prenant $d_p(A,B) = \|B-A\|_p = (|x_A - x_B|^p + |y_A - y_B|^p)^\frac{1}{p}$.

Continuité

Je vous ai dit précédemment que notre présentation était généralisable à d'autres dimensions. Par exemple, pour la distance euclidienne dans $\mathbb{R}^3$ en rajoutant la hauteur $z$ nous passerions de $d_2(A,B) = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}$ à $d_2(A,B) = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2 + (z_A -z_B)^2}$. Nous pouvons le faire sans problème pour n'importe quel nombre de dimension, que ce soit pour la distance ou la norme. Mais… et pour une infinité de dimensions ?

En prenant un point $X = (x_1, x_2, \dots, x_n, \dots)$ nous pourrions définir la norme de $X$ par :

$$\|X\|_p = (\sum_{i \in \mathbb{N}}|x_i|^p)^\frac{1}{p}$$

En faisant tendre $n$ vers l'infini nous aurions bien sûr des problèmes de convergence, mais ce n'est pas le plus intéressant. Ici nous avons défini un point en associant une coordonnée $x_i$ à chaque numéro $i$ de dimension, mais nous pourrions généraliser cela en définissant un point par une fonction $f$ qui prendrait ses valeurs par exemple dans les réels et plus dans les entiers:

$$\|f\|_p = (\int_\mathbb{R} |f(x)|^p \, \mathrm dx)^\frac{1}{p}$$

C'est le successeur direct de la distance de Minkowski d'ordre $p$ : on a « juste » remplacé la somme discrète $\sum$ par la somme continue $\int$, et la coordonnée $x_i$ dépendant de $i \in \mathbb{N}$ par un $f(x)$ dépendant de $x \in \mathbb{R}$. Et notre point n'est plus une liste de coordonnées mais une fonction $f$.

Bien sûr, comme il s'agit d'une somme infinie, il y a BEAUCOUP de fonctions $f$ pour lesquelles $\|f\|_p = \infty$. Nous nous intéressons à l'ensemble des fonctions $f$ telles que $\|f\|_p$ soit fini, et nous notons $L^p$ cet espace de fonctions. Par exemple, en violant davantage la notion de cercle, on pourrait dire que le cercle de rayon $1$ dans $L^p$ est l'ensemble des fonctions $f$ telles que $\|f\|_p = 1$.

Le cas p = 2

Bon, on va se calmer un peu et revenir sur les distances de Minkowski d'ordre $p$, histoire de finir un peu plus en douceur. Je vous ai dit au début que la distance euclidienne « à vol d'oiseau » est celle qui vient la première à l'esprit, et je voulais donc vous dire en quoi $d_2$ est spéciale.

Au sujet des espace $L^p$ il y a un résultat assez important appelé l'inégalité de Hölder, qui montre que pour deux nombres $0 < p,q \le \infty$ vérifiant $\frac{1}{p} + \frac{1}{q} = 1$ si $f \in L^p$ et $g \in L^q$ alors le produit $fg$ de $f$ et de $g$ vérifie $\|fg\|_1 \le \|f\|_p\|g\|_p$, donc est dans $L^1$.

Si vous avez le sens du détail, vous aurez remarqué que je parle ici d'un nombre $p$ entre $0$ et l'infini, alors que dans la définition des distances de Minkowski je parlais d'un $p$ entre $1$ et l'infini… alors ? Oh, c'est juste que cette inégalité est valide aussi pour $0 < p < 1$, mais que dans ce cas $d_p$ ne vérifie plus l'inégalité triangulaire donc n'est plus une distance.

Bon, c'est assez compliqué, mais je voulais surtout attirer votre attention sur la condition $\frac{1}{p} + \frac{1}{q} = 1$. D'ailleurs pour $p$ et $q$ la vérifiant on peut montrer en utilisant l'inégalité de Hölder qu'en un sens (de dualité topologique, si vous voulez VRAIMENT tout savoir) $L^p$ et $L^q$ sont des reflets l'un de l'autre. Pour avoir une joli symétrie il faut donc que $L^p$ soit son propre reflet. Dans ce cas nous avons $\frac{1}{p} + \frac{1}{p} = 1$, donc $p = 2$, et oui !

C'est pour cela qu'en un sens $d_2$ est exactement la distance « médiane » entre $d_1$ et $d_\infty$ (ce qui se voit bien sur le dessin, je trouve), qui sont elles-mêmes les extrémités des distances de Minkowski. Certes, il y a d'autres distances (par exemple la distance entre deux mots), mais ce sont les distances de Minkowski que nous utilisons dans les espaces usuels (le plan, l'espace, etc.). Personnellement, je trouve assez formidable qu'une distance dérivant de quelque chose d'aussi simple et ancien que le théorème de Pythagore ait une place aussi privilégiée parmi les espaces de fonctions compliqués que nous étudions de nos jours…

Note : J'applique le cas p = 2 dans mon article de conception sur les distances dans Nova. Et en passant voici un article intéressant sur le pavage hexagonal.

Petit note : cette vidéo de Science4All évoque aussi le fait que les fonctions $f$ telles que $\int |f(x)|^2 \, \mathrm dx < \infty$ sont celles qui sont égales à leur série de Fourier…