vignette|Comparaison asymptotique des fonctions utilisées en informatique plus précisément en algorithme. On voit par exemple que la fonction exponentielle () croit plus vite que la fonction linéaire (). En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode permettant d'étudier le comportement d'une fonction.
En présence d'une fonction sans irrégularité particulière on peut par exemple étudier sa vitesse de croissance: ainsi la fonction exponentielle croit plus vite qu'une fonction linéaire.
Lorsque en revanche la fonction étudiée est plus erratique on peut par exemple étudier l'amplitude de ses oscillations: ainsi la fonction de reste du théorème des nombres premiers prend, de façon quantifiable, des valeurs de tailles arbitrairement grandes aussi bien positives que négatives.
La comparaison asymptotique permet d'étudier une fonction quelconque par rapport à une fonction considérée comme plus « simple ». Celle-ci est souvent choisie sur une échelle de référence, contenant en général au moins certaines fonctions dites élémentaires, en particulier les sommes et produits de polynômes, d'exponentielles et de logarithmes G. H. Hardy, « The "Infinitärcalcül" of Paul du Bois-Reymond », Cambridge Tracts in Mathematics, 12, 1910, deuxième édition 1924. Lire en ligne .. La comparaison s'effectue en l'infini ou alors au voisinage d'un point.
Le concept de comparaison asymptotique est aussi utilisé en informatique, par exemple pour décrire la complexité de certains algorithmes. En effet, la comparaison asymptotique est intéressante en l'infini, car on s'intéresse au comportement d'un algorithme sur des données arbitrairement grandes. Cette méthode de comparaison est également employée en théorie analytique des nombres pour évaluer finement l'erreur commise en remplaçant une fonction irrégulière, comme celle comptant les nombres premiers, par une fonction de l'échelle choisie.
La méthode a été introduite par les travaux de Paul du Bois-Reymond à partir de 1872 ; pour faciliter les calculs et la présentation des résultats, diverses notations ont été développées, en particulier par Bachmann (1894), Landau (1909), Hardy (1910), Hardy et Littlewood (1914 et 1916), et Vinogradov ( 1930).
Exemples de comparaison
La relation de prépondérance
Exemple Soit et les fonctions réelles définies par les formules
Par une étude des deux fonctions, on sait que prend des valeurs aussi grandes que l'on veut au voisinage de l'infini, tandis que ne peut prendre des valeurs qu'entre 1 et 3. Le quotient divisé par au voisinage de l'infini ne cesse d'augmenter et n'est pas borné. Dans ce contexte, on peut dire que est négligeable devant , ou que est prépondérante devant , au voisinage de l'infini, on écrit (notation de Landau) : ou (notation de Hardy, éd., ., désuèteQuoique toujours mentionnée dans la du Hardy and Wright, p. 7, comme étant occasionnellement utilisée, elle n'est en fait jamais employée dans la suite de l'ouvrage, où les auteurs recourent systématiquement à la notation équivalente o. Hardy lui-même n'a plus jamais utilisé cette notation dans ses travaux publiés après 1913.)
La notation de Hardy permet d'enchaîner les relations de prépondérance, par exemple :
Définition formelle lorsque la fonction g ne s'annule pas Pour définir formellement cette propriété on considère le comportement du quotient .
Soit
Soient et deux fonctions de la variable réelle . On suppose que ne s'annule pas sur un voisinage de a. On dit que est négligeable devant , ou que est prépondéranteE. Ramis, C. Deschamp et J. Odoux, Cours de mathématiques spéciales, tome 3, p. 148 devant en , et on note , lorsque
Si le contexte est clair, on ne précise pas le domaine d'étude et on note : , voire . Cependant, la notation est toujours associée à un lieu a et au voisinage de ce lieu : être négligeable est un concept local.
Dans cette notation de Landau (parfois aussi ), le symbole se lit petit o. La notation équivalente de Hardy est . On utilise aujourd'hui exclusivement la notation de Landau.
Propriétés Par ce qui peut sembler un abus de langage, on effectue des opérations sur les . En effet, on peut écrire :
. Dans les côtés gauche de chaque formule les deux symboles représentent des fonctions a priori différentes. La première formule se lit : "la somme de deux fonctions qui sont toutes deux des petits est une fonction qui est également un ".
Exemples
Pour toute fonction , telle que , on a :
Équivalence
Définition formelle Soit .
Soient et deux fonctions de la variable réelle . On suppose que ne s'annule pas sur un voisinage de . On dit que est équivalente à en , ou que équivaut à en , et on note , lorsque .
Exemple
Domination
La notation grand O de Landau dénote le caractère dominé d'une fonction par rapport à une autre. Généralement, comme Paul Bachmann qui a introduit ce symbole en 1894, on utilise la lettre O majuscule (de l'allemand , « ordre »). C'est beaucoup plus tard (1976), par analogie avec le symbole oméga majuscule Ω (voir plus bas), que Donald Knuth a discrètement suggéré de rebaptiser le symbole O du nom de la lettre omicron majuscule (qui n'apparaît que dans le titre de son article), celle-ci étant rarement dessinée de manière clairement différente du O. Dans les deux cas, le symbole utilisé est distinct du symbole 0 (zéro). Définition formelle
Soient et deux fonctions de la variable réelle . On dit que est dominée par en , ou que domine en , et on note (notation de Bachmann, 1894, ou de Landau, 1909)
ou (notation de Hardy, 1910, désuète)
ou encore (notation de Vinogradov, années 1930)
lorsqu'il existe des constantes et telles que
Intuitivement, cela signifie que ne croît pas plus vite que .
De même, si est un nombre réel, nous écrivons
s’il existe des constantes et telles que
Ceci est équivalent, lorsque ne s'annule pas, à
Exemples
En un point , si est négligeable devant ou équivalente à , alors elle est dominée par . Une fonction est bornée sur un voisinage de si et seulement si .
Absence de prépondérance et oscillations
Notation Ω de Hardy et Littlewood (théorie des nombres) En 1914, Hardy et Littlewood ont introduit le nouveau symbole Ω G. H. Hardy et J. E. Littlewood, « Some problems of Diophantine approximation », Acta Mathematica, vol. 37, 1914, p. 225 défini ainsi :
.
Les fonctions et sont supposées définies, et positive, dans un voisinage de l'infini. Ainsi est la négation de .
En 1916, les mêmes auteurs introduisent les deux nouveaux symboles Ω et Ω G. H. Hardy et J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes », Acta Mathematica, vol. 41, 1916., définis de la façon suivante :
.
Comme avant, les fonctions et sont supposées définies, et positive, dans un voisinage de l'infini. Ainsi, est la négation de , et la négation de .
Contrairement à ce qu'affirmera plus tard D.E. Knuth Donald Knuth, « », SIGACT News, avril-juin 1976, p. 18-24 ., Edmund Landau a également utilisé ces trois symboles en 1924 E. Landau, « Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV », Nachr. Gesell. Wiss. Gött. Math-phys. Kl., 1924, p. 137-150.
Ces notations de Hardy et Littlewood sont des prototypes, qui après Landau semblent n'avoir jamais été utilisés tels quels : Ω est devenu Ω, et Ω est devenu Ω.
Ces trois symboles, à savoir , et , sont maintenant couramment utilisés en théorie analytique des nombres, de même que pour signifier que les conditions et sont toutes deux satisfaites.
Il est clair que dans chacune de ces définitions on peut remplacer par ou par un nombre réel.
Exemples
On a
et plus précisément,
On a
et plus précisément,
cependant,
Deux définitions incompatibles
Il est important de souligner le fait que l'écriture
possède en mathématiques deux définitions incompatibles, toutes les deux très répandues, l'une en théorie analytique des nombres, qu'on vient de présenter, l'autre en théorie de la complexité des algorithmes. Lorsque ces deux disciplines se rencontrent, cette situation est susceptible de créer une grande confusion.
La définition de Knuth
En 1976, Knuth publie un article dont le but principal est de justifier son utilisation du même symbole Ω pour décrire une autre propriété que celle décrite par Hardy et Littlewood. Il tente de convaincre le lecteur que la définition de Hardy et Littlewood n'est quasiment jamais utilisée (ce qui, même en 1976, est faux depuis en tout cas 25 ans E. C. Titchmarsh, The Theory of the Riemann Zeta-Function, Oxford, Clarendon Press, 1951). Il va jusqu'à prétendre que Landau ne l'a jamais utilisée (ce qui est également faux). Il ressent impérativement le besoin d'une autre notion (), et a décidé que l'utilisation du symbole Ω doit être réservé pour la décrire. Il est fortement contrarié par l'ancienne définition ().
Il prend donc le risque de créer la confusion, et définit
Il se justifie en écrivant : .
Utilisation des comparaisons
Développements limités En mathématiques, il est souvent important de garder un œil sur le terme d'erreur d'une approximation. Cette notation est particulièrement utilisée dès que l'on a affaire à des développements limités et à des calculs d'équivalents. Par exemple, le développement de la fonction exponentielle à l'ordre 2 peut aussi s'écrire :
pour exprimer le fait que l'erreur, la différence , est négligeable devant quand tend vers 0.
Il faut préciser que le nombre d'opérandes dans ce genre d'écriture doit être borné par une constante qui ne dépend pas de la variable : par exemple l'assertion est évidemment fausse si les points de suspension cachent un nombre de termes qui n'est pas borné lorsque x varie.
Échelle de comparaison Voici une liste de catégories de fonctions couramment utilisées en analyse. La variable (notée ici n) tend vers et c est une constante réelle arbitraire. Lorsque c est une constante supérieure à 1, les fonctions apparaissent dans cette liste par ordre croissant de grandeur.
notation grandeur au plus O(1) module majoré par une constante O(log(n)) logarithmique O((log(n))) (polylogarithmique si c est entier positif) O(n) linéaire O(n log(n)) parfois appelée « linéarithmique » O(n log(n)) parfois appelé « quasi linéaire » O(n) quadratique O(n) (polynomiale si c est entier positif) O(c) (exponentielle si c est positif, parfois « géométrique ») O(n!) factorielle
O(n) et O(c) sont très différents. Le dernier autorise une croissance bien plus rapide, et ce pour n'importe quelle constante c > 1. Une fonction qui croît plus rapidement que n'importe quel polynôme est dite superpolynomiale. Une fonction qui croît plus lentement que toute exponentielle est dite sous-exponentielle. Il existe des fonctions à la fois superpolynomiales et sous-exponentielles, comme la fonction nlog(n).
Remarquons aussi que O(log n) est exactement identique à O(log(n)), puisque ces deux logarithmes sont multiples l'un de l'autre par un facteur constant et que la notation grand O « ignore » les constantes multiplicatives. De manière analogue, les logarithmes dans des bases constantes différentes sont équivalents.
La liste précédente est utile à cause de la propriété suivante : si une fonction f est une somme de fonctions, et si une des fonctions de la somme croît plus vite que les autres, alors elle détermine l'ordre de croissance de f(n).
Exemple : si f(n) = 10 log(n) + 5 (log(n)) + 7 n + 3 n + 6 n, alors f(n) = O(n).
Fonction à plusieurs variables
Cette notation peut aussi être utilisée avec des fonctions de plusieurs variables : L'écriture : quand correspond à la proposition : Pour certains, cette notation abuse du symbole d'égalité, puisqu'elle semble violer l'axiome d'égalité : « des choses égales à la même chose sont égales entre elles » (autrement dit, avec cette notation, l'égalité n'est plus une relation d'équivalence). Mais on peut également considérer que dans l'écriture