Distance (mathématiques)
Modèle:Voir homonymes En mathématiques, une distance est une application qui formalise l'idée intuitive de distance, c'est-à-dire la longueur qui sépare deux points. C'est par l'analyse des principales propriétés de la distance usuelle que Fréchet introduit la notion d'espace métrique, développée ensuite par Hausdorff. Elle introduit un langage géométrique dans de nombreuses questions d'analyse et de théorie des nombres<ref>Modèle:Chapitre</ref>.
À partir de la définition d'une distance, vue comme une application satisfaisant à certains axiomes, d'autres notions de distance peuvent être définies, comme la distance entre deux parties, ou la distance d'un point à une partie, sans que ces dernières répondent à la définition première d'une distance.
Définition
On appelle distance sur un ensemble Modèle:Formule toute application Modèle:Formule définie sur le produit Modèle:Formule et à valeurs dans l'ensemble ℝ+ des réels positifs ou nuls,
vérifiant les propriétés suivantes<ref>Modèle:Lien web.</ref> :
| Nom | Propriété |
|---|---|
| symétrie | <math>\forall (a,b)\in E^2,\ d(a,b)=d(b,a)</math> |
| séparation | <math>\forall (a,b)\in E^2,\ d(a,b)=0 \Leftrightarrow a=b</math> |
| inégalité triangulaire | <math>\forall (a,b,c)\in E^3,\ d(a,c)\leq d(a,b)+d(b,c)</math> |
Un ensemble muni d'une distance s'appelle un espace métrique.
- Remarques
-
- Ces conditions expriment les notions intuitives du concept de distance. Par exemple, que la distance entre des points distincts est strictement positive et que la distance de x à y est la même que la distance de y à x. L'inégalité triangulaire signifie que la distance parcourue directement entre x et z, n'est pas plus grande que la distance à parcourir en partant d'abord de x vers y puis de y vers z. Euclide Modèle:Fix Modèle:Douteux que Modèle:Pas clair, ce qui était l'inégalité triangulaire pour sa géométrie.
- Dans la définition d'une distance, on peut se contenter de supposer que l'ensemble d'arrivée est ℝ, et que d vérifie l'axiome de séparation et l'une quelconque des trois variantes suivantes de l'inégalité triangulaire : d(a, c) ≤ d(b, a) + d(b, c), ou d(a, c) ≤ d(a, b) + d(c, b), ou encore Modèle:Nobr La positivité et la symétrie se déduisent facilement de ces seuls axiomes<ref>Modèle:Article (Modèle:P.).</ref>.
Propriétés simples
- Si Modèle:Formule est un sous-ensemble de Modèle:Formule et si Modèle:Formule ℝ+ est une distance sur Modèle:Formule, alors la restriction de Modèle:Formule à Modèle:Formule est une distance sur Modèle:Formule.
- Si Modèle:Formule et Modèle:Formule sont respectivement des distances sur Modèle:Formule et Modèle:Formule et si Modèle:Formule est le produit Modèle:Formule, alors l'application Modèle:Formule ℝ+ définie parModèle:Retraitest une distance sur Modèle:Formule. Pour des généralisations, voir Produit d'espaces métriques.
- Si Modèle:Formule et Modèle:Formule sont des distances sur Modèle:Formule alors Modèle:Formule aussi (d'après les deux points précédents, en identifiant Modèle:Formule à la diagonale de Modèle:Formule).
Cas particuliers
Distance ultramétrique
La distance est dite ultramétrique si de plus :
| Nom | Propriété |
|---|---|
| Ultramétrie | <math>\forall a,b,c\in E: d(a,c)\leq \max( d(a,b), d(b,c) ).</math> |
Un exemple de telle distance intervient de façon cruciale dans la théorie des valuations [[nombre p-adique|Modèle:Formule-adiques]]. L'interprétation géométrique de l'inégalité triangulaire dans un espace ultramétrique amène à dire que tous les triangles sont isocèles ; de plus, toutes les boules de rayon donné définies sur cet ensemble constituent une partition de cet ensemble ; en faisant croître ce rayon depuis 0, l'espace se trouve doté d'une structure hiérarchique de proximité, utilisable en classification automatique, en particulier pour le clustering hiérarchique.
Exemples de distances classiques
Distance sur des espaces vectoriels
Sur un espace vectoriel normé <math>(E,\|\cdot\|)</math>, la distance Modèle:Mvar « induite par » la norme<ref>Inversement, si une distance d sur un espace vectoriel E satisfait les propriétés :
- <math>d(x,y) = d(x+a,y+a)</math> (invariance par translation) ;
- <math>d(\alpha x, \alpha y) = |\alpha| d(x,y)</math> (homogénéité),
alors on peut définir une norme <math>\|\cdot\|</math> sur E par : <math>\|x\| : = d(x,0)</math>.</ref> <math>\|\cdot\|</math> est définie par :
- <math>\forall (x,y) \in E\times E\quad d(x,y) = \|y-x\|</math>.
En particulier, dans ℝModèle:Formule (donc aussi dans ses sous-ensembles<ref>Modèle:Ouvrage.</ref>), on peut définir de plusieurs manières la distance entre deux points, bien qu'elle soit généralement donnée par la distance euclidienne (ou 2-distance). Soit deux points de Modèle:Formule, Modèle:Formule et Modèle:Formule, on exprime les différentes distances ainsi :
| Nom | Paramètre | Fonction |
|---|---|---|
| distance de Manhattan | 1-distance | x_i-y_i|</math> |
| distance euclidienne | 2-distance | <math>\sqrt{\sum_{i=1}^n (x_i-y_i)^2}</math> |
| distance de Minkowski | Modèle:Formule-distance | x_i-y_i|^p}</math> |
| distance de Tchebychev | Modèle:Math-distance | x_i-y_i|^p} = \sup_{1 \leq i \leq n}{|x_i-y_i|}</math> |
La 2-distance permet de généraliser l'application du théorème de Pythagore à un espace de dimension Modèle:Formule. C'est la distance la plus « intuitive ».
La Modèle:Formule-distance est rarement utilisée en dehors des cas Modèle:Formule = 1, 2 ou Modèle:Math. L'Modèle:Math-distance présente la particularité amusante de permettre la définition en toute rigueur de sphères cubiques (voir oxymore). La 1-distance permet de définir des sphères octaédriques.
Distance discrète
Sur n'importe quel ensemble, la distance discrète d est définie par : si x = y alors d(x, y) = 0 et sinon, d(x, y) = 1.
Distance sur une sphère
Distances entre deux permutations
Il est également possible de définir des distances entre des permutations. L'exemple suivant est très utilisé dans le réarrangement de génomes. Soit Modèle:Formule un ensemble de permutations modélisant diverses opérations ; alors la distance entre deux permutations Modèle:Formule et Modèle:Formule est la longueur d'une séquence minimale formée du produit d'éléments de Modèle:Formule telle que cette séquence transforme Modèle:Formule en Modèle:Formule.
On peut utiliser la distance de Kendall qui mesure le nombre de transpositions permettant de passer d'une permutation à une autre, ce qui revient à calculer l'indice tau = (somme des couples concordants) - (somme des couples discordants) / n(n-1)/2. L'indice varie de -1 à +1 selon la ressemblance entre les permutations.
Ces distances peuvent également servir à mesurer, de diverses manières, le désordre présent dans une séquence. On utilise alors ces mesures pour analyser les performances de divers algorithmes de tri, ou pour construire de nouveaux algorithmes de tri qui effectuent un nombre de comparaisons optimal par rapport à la mesure de désordre choisie.
Distance de Levenshtein
Modèle:Article détaillé La distance de Levenshtein est un exemple de distance définie sur l'ensemble des chaînes de caractères. Elle est définie pour deux chaînes Modèle:Formule et Modèle:Formule comme le nombre minimal d'opération d'ajout/suppression/remplacement de caractères pour transformer la chaîne Modèle:Formule en la chaîne Modèle:Formule.
Exemples:
- Levenshtein('BONJOUR', 'BONSOIR')=2 (il est nécessaire et suffisant de remplacer 'J' par 'S' et 'U' par 'I').
- Levenshtein('DEBUT', 'FIN')=5
- Levenshtein('DUNKERQUE', 'PERPIGNAN')=9<ref>Un calculateur en ligne: http://planetcalc.com/1721/</ref>.
Ce type de distance est couramment utilisé pour des applications de filtrage/correction d'erreurs, par exemple la correction automatique pour des programmes de traitement de texte (le programme va rechercher dans un dictionnaire les mots présentant les distances les plus faibles avec le mot mal orthographié), l'appareillement de lectures optiques de plaques minéralogiques...
Il existe des variantes de cette distance, telles que la distance de Damerau-Levenshtein.
Le même principe général peut être utilisé pour les applications de reconnaissance de formes.
Exemples d'autres emplois du terme distance
Le terme distance est parfois utilisé pour désigner des applications ne répondant pas à la définition classique pour les espaces métriques, présentée en début d'article.
Distance entre deux ensembles
Soient Modèle:Formule et Modèle:Formule deux parties non vides d'un espace métrique Modèle:Formule muni d'une distance Modèle:Formule, on définit la distance entre ces deux ensembles comme : Modèle:Retrait
C'est un réel positif, comme borne inférieure d'un ensemble non vide de réels positifs.
- N.B.
- Cette « distance » n'est pas une distance sur l'ensemble des parties de Modèle:Formule au sens des axiomes définis plus haut. En particulier si la distance entre deux ensembles est nulle, on ne peut pas en déduire que ces ensembles sont égaux, ni même que leurs adhérences se rencontrent.
Néanmoins, il est possible de définir une vraie distance entre les parties compactes d'un espace métrique. Pour cela, voir : distance de Hausdorff.
Théorème
Avec les notations ci-dessus, <math>d(E_1,E_2)=d(\bar{E_1},\bar{E_2})</math>, où <math>\bar{F}</math> désigne l'adhérence d'une partie <math>F</math> de <math>E</math><ref>Modèle:Ouvrage</ref>.
Distance d'un point à une partie
On peut particulariser la définition précédente en prenant l'un des deux ensembles réduit à un point.
Si Modèle:Formule est une partie non vide d'un espace métrique Modèle:Formule, et si Modèle:Formule est élément de Modèle:Formule, on définit la distance de Modèle:Formule à Modèle:Formule comme une borne inférieure :
C'est<ref>Modèle:Harvsp.</ref> le rayon de la plus grande boule ouverte de centre Modèle:Formule qui ne rencontre pas Modèle:Formule.
On prendra garde au fait que Modèle:Formule n'implique pas en général que Modèle:Formule soit élément de Modèle:Formule. Par exemple, dans ℝ muni de la valeur absolue, la distance de 0 à l'intervalle ouvert ]0, 1[ est nulle, ou la distance de tout réel à l'ensemble des rationnels est nulle également.
Plus précisément, la distance de Modèle:Mvar à Modèle:Mvar est nulle si et seulement si<ref>E. Ramis, C. Deschamps et J. Odoux, Mathématiques spéciales, T.3, topologie et éléments d'analyse, Masson, Paris, 1976, Modèle:P..</ref>,<ref>Modèle:Ouvrage.</ref> Modèle:Mvar est un point adhérent à Modèle:Mvar (autrement dit : l'implication précédente est vraie si et seulement si Modèle:Mvar est fermé). Plus généralement, la distance de Modèle:Mvar à Modèle:Mvar est égale à la distance de Modèle:Mvar à l'adhérence de Modèle:Mvar.
L'application de Modèle:Mvar dans ℝ qui à tout élément Modèle:Mvar de Modèle:Mvar associe Modèle:Formule est continue, et même 1-lipschitzienne<ref>Modèle:Ouvrage.</ref>,<ref>Modèle:Note autre projet</ref> : Modèle:Retrait
Distance algébrique
Soit deux points Modèle:Formule et Modèle:Formule d'un espace affine par lesquels passe une droite orientée (une droite munie d'un sens, c'est-à-dire engendrée par un vecteur <math>\vec{v}</math> non nul). On appelle distance algébriqueModèle:Refnec de Modèle:Formule vers Modèle:Formule le réel tel que :
- sa valeur absolue soit la distance (définie ci-dessus) entre Modèle:Formule et Modèle:Formule
- si la valeur est non nulle :
- le réel soit positif dans le cas où le vecteur <math>\overrightarrow{\rm AB}</math> est de même sens que <math>\vec{v}</math>, c'est-à-dire égal à <math>k\vec{v}</math>, avec <math>k>0</math>,
- négatif sinon.
On peut démontrer que la distance algébrique de Modèle:Formule vers Modèle:Formule (notée <math>d_a(\mathrm{A}, \mathrm{B})</math>) vaut :
- <math> d_a(\mathrm{A}, \mathrm{B}) = \frac{\overrightarrow{\mathrm{AB}}.\vec{v}}{\|\vec{v}\|}</math>
Attention, la distance algébrique n'est pas une distance, puisqu'elle est non symétrique :
- <math>d_a(\mathrm{A}, \mathrm{B}) = - d_a(\mathrm{B}, \mathrm{A})</math>
Généralisations
En allégeant les axiomes de la définition d'une distance, on arrive à diverses généralisations de celle-ci :
| Nom | valeurs finies | symétrie | <math>\mathrm d(x,x)=0</math> | <math>\mathrm d(x,y)=0 \implies x=y</math> | inégalité du <math>\Delta</math> |
|---|---|---|---|---|---|
| distance | ✔ | ✔ | ✔ | ✔ | ✔ |
| quasi-distance | ✔ | ✘ | ✔ | ✔ | ✔ |
| métamétrique | ✔ | ✔ | ✘ | ✔ | ✔ |
| pseudo-distance | ✔ | ✔ | ✔ | ✘ | ✔ |
| semi-distance | ✔ | ✔ | ✔ | ✔ | ✘ |
| distance faible | ✔ | ✘ | ✔ | ✘ | ✔ |
| pramétrique | ✔ | ✘ | ✔ | ✘ | ✘ |
| écart | ✘ | ✔ | ✔ | ✘ | ✔ |
La condition que la distance prenne ses valeurs dans Modèle:Math peut être aussi assouplie en considérant des « distances à valeurs dans un ensemble ordonné filtrant ». La reformulation des axiomes dans ce cas conduit à la construction des espaces uniformes : des espaces topologiques avec une structure abstraite permettant de comparer les topologies locales de points différents.
Parmi les catégories correspondant aux diverses variantes de distance, celle des espaces pseudo-métriques « étendus » (Modèle:C.-à-d. autorisant la valeur Modèle:Math), avec comme morphismes les applications 1-lipschitziennes, est celle qui se comporte le mieux : Modèle:Refnec Modèle:Refnec
Il existe aussi, en géométrie différentielle, les notions de métriques riemanniennes et pseudo-riemanniennes sur une variété différentielle (et non plus simplement sur un ensemble).
Les quasi-distances sont plutôt appelées distances asymétriques. Le terme quasi étant souvent utilisé en géométrie pour désigner une propriété à constante près.
Voir aussi
Notes et références
<references/>
