Nombres harmoniques
Les nombres harmoniques forment une suite mathématique obtenue en additionnant les inverses des premiers entiers naturels. Ils apparaissent dans de nombreux domaines des mathématiques appliquées et de l'informatique, notamment dans l'analyse des algorithmes, les probabilités, les structures de données, les problèmes de dénombrement, les méthodes aléatoires et l'étude de certaines séries.
Le nombre harmonique d'ordre n représente la somme des fractions allant de 1 à 1/n. Bien que chaque nouveau terme ajouté soit de plus en plus petit, la suite des nombres harmoniques augmente sans limite. Cette croissance est cependant très lente et se rapproche de celle du logarithme naturel. Cette propriété explique pourquoi les nombres harmoniques interviennent fréquemment dans l'analyse moyenne de certains algorithmes.
Définition
Le n-ième nombre harmonique est noté :
| Hn |
Il est défini par la somme suivante :
| Hn = 1 + 1/2 + 1/3 + ... + 1/n |
En notation de sommation :
| Hn = ∑i=1n 1/i |
où :
- n représente l'ordre du nombre harmonique ;
- i représente l'indice de sommation ;
- chaque terme correspond à l'inverse d'un entier naturel.
Premières valeurs
Les premières valeurs de la suite harmonique sont :
|
H1 = 1 H2 = 1 + 1/2 = 3/2 = 1,5 H3 = 1 + 1/2 + 1/3 = 11/6 ≈ 1,833333 H4 = 1 + 1/2 + 1/3 + 1/4 = 25/12 ≈ 2,083333 H5 = 1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60 ≈ 2,283333 |
Quelques valeurs supplémentaires sont présentées dans le tableau suivant :
| n | Hn approximatif |
|---|---|
| 1 | 1,000000 |
| 2 | 1,500000 |
| 3 | 1,833333 |
| 4 | 2,083333 |
| 5 | 2,283333 |
| 10 | 2,928968 |
| 20 | 3,597740 |
| 50 | 4,499205 |
| 100 | 5,187378 |
| 1 000 | 7,485471 |
| 1 000 000 | 14,392727 |
Ce tableau montre que la croissance des nombres harmoniques est très lente.
Définition récursive
Les nombres harmoniques peuvent être définis récursivement.
| H0 = 0 |
et, pour :
| n ≥ 1 |
on a :
| Hn = Hn-1 + 1/n |
Par exemple :
| H4 = H3 + 1/4 |
Comme :
| H3 = 11/6 |
on obtient :
| H4 = 11/6 + 1/4 |
soit :
| H4 = 25/12 |
Cette relation permet de construire progressivement tous les nombres harmoniques.
Algorithme itératif
Le calcul d'un nombre harmonique peut être réalisé avec une boucle.
|
MODULE NombreHarmonique(n) somme ← 0 BOUCLE POUR i ← 1 JUSQU'A n somme ← somme + 1 / i FIN BOUCLE POUR RETOURNER somme |
La variable somme doit être de type réel afin d'éviter une division entière.
Si 1 / i est calculé avec des entiers, certains langages retourneront zéro pour toutes les valeurs de i supérieures à 1.
Exemple en Java
L'exemple suivant calcule le nombre harmonique d'ordre n :
- public class NombreHarmoniqueSample {
-
- public static double nombreHarmonique(int n) {
- if (n < 0) {
- throw new IllegalArgumentException(
- "L'ordre doit être positif ou nul."
- );
- }
-
- double somme = 0.0;
-
- for (int i = 1; i <= n; i++) {
- somme += 1.0 / i;
- }
-
- return somme;
- }
-
- public static void main(String[] args) {
- System.out.println(
- "H10 = " + nombreHarmonique(10)
- );
-
- System.out.println(
- "H100 = " + nombreHarmonique(100)
- );
- }
- }
Le programme affiche approximativement :
H10 = 2.9289682539682538H100 = 5.187377517639621
L'utilisation de :
| 1.0 / i |
garantit que la division est effectuée en virgule flottante.
Complexité du calcul direct
L'algorithme itératif effectue une addition pour chaque entier compris entre 1 et n.
Sa complexité temporelle est donc :
| O(n) |
La mémoire supplémentaire utilisée est constante :
| O(1) |
Cette méthode est suffisante pour des valeurs modérées de n, mais elle peut devenir coûteuse lorsque n est extrêmement grand.
Croissance logarithmique
Les nombres harmoniques croissent approximativement comme le logarithme naturel.
On a :
| Hn ≈ ln(n) + γ |
où :
- ln(n) représente le logarithme naturel de n ;
- γ représente la constante d'Euler-Mascheroni.
La valeur approximative de cette constante est :
| γ ≈ 0,5772156649 |
Ainsi, pour :
| n = 1000 |
on obtient :
| ln(1000) + γ |
soit environ :
| 7,484971 |
alors que la valeur exacte de H???? est approximativement :
| 7,485471 |
L'approximation est donc déjà très précise.
Approximation plus précise
Une approximation plus complète est donnée par :
| Hn ≈ ln(n) + γ + 1/(2n) - 1/(12n2) |
Des termes supplémentaires peuvent être ajoutés pour augmenter la précision.
Par exemple :
|
Hn = ln(n) + γ + 1/(2n) - 1/(12n2) + 1/(120n4) - ... |
Cette formule permet d'estimer rapidement un nombre harmonique de très grand ordre sans effectuer toutes les additions.
Divergence de la série harmonique
La suite des nombres harmoniques augmente sans limite.
On écrit :
|
lim Hn = +∞ n→∞ |
Cela signifie que la série harmonique :
| 1 + 1/2 + 1/3 + 1/4 + ... |
est divergente.
Cette propriété peut sembler surprenante, puisque les termes deviennent progressivement très petits. Toutefois, leur somme finit toujours par dépasser n'importe quelle valeur fixée, à condition d'ajouter suffisamment de termes.
Démonstration par regroupement
La divergence peut être illustrée en regroupant les termes.
|
1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + ... |
Dans le groupe :
| 1/3 + 1/4 |
chaque terme est supérieur ou égal à :
| 1/4 |
Le groupe contient deux termes, donc sa somme est au moins :
| 2 × 1/4 = 1/2 |
Dans le groupe suivant :
| 1/5 + 1/6 + 1/7 + 1/8 |
chaque terme est supérieur ou égal à :
| 1/8 |
Le groupe contient quatre termes, donc sa somme est au moins :
| 4 × 1/8 = 1/2 |
Chaque nouveau groupe ajoute donc au moins 1/2, ce qui prouve que la somme augmente sans limite.
Encadrement logarithmique
Les nombres harmoniques peuvent être comparés à une intégrale.
Pour tout entier positif n, on a notamment :
| ln(n + 1) ≤ Hn ≤ 1 + ln(n) |
Cet encadrement montre que la croissance de H? est logarithmique.
En notation asymptotique :
| Hn = Θ(log n) |
Dans ce contexte, la base du logarithme n'a pas d'importance pour la notation asymptotique, puisque deux logarithmes de bases différentes ne diffèrent que par un facteur constant.
Nombres harmoniques et analyse des algorithmes
Les nombres harmoniques apparaissent souvent lorsqu'un coût diminue proportionnellement à l'inverse d'un indice.
Par exemple, si un algorithme effectue approximativement :
| n/1 + n/2 + n/3 + ... + n/n |
opérations, le coût total peut être écrit :
| nHn |
Comme :
| Hn = Θ(log n) |
le coût devient :
| Θ(n log n) |
Cette transformation est fréquemment utilisée dans l'analyse de complexité.
Exemple avec des boucles
Considérons l'algorithme suivant :
|
POUR i ← 1 JUSQU'A n j ← i TANT QUE j ≤ n Traitement j ← j + i FIN TANT QUE FIN POUR |
Pour une valeur donnée de i, la boucle intérieure s'exécute environ :
| n / i |
fois.
Le nombre total d'exécutions est donc approximativement :
| n/1 + n/2 + n/3 + ... + n/n |
soit :
| nHn |
La complexité temporelle est alors :
| O(n log n) |
Tri rapide
Dans certaines analyses du tri rapide, ou Quicksort, les nombres harmoniques apparaissent dans le calcul du nombre moyen de comparaisons.
Le nombre moyen de comparaisons est approximativement :
| 2n ln(n) |
Une expression plus précise contient le nombre harmonique :
| 2(n + 1)Hn - 4n |
Cette relation montre le lien entre les nombres harmoniques et la complexité moyenne :
| O(n log n) |
du tri rapide.
Problème du collectionneur de coupons
Le problème du collectionneur de coupons consiste à déterminer combien de tirages sont nécessaires, en moyenne, pour obtenir tous les types de coupons disponibles.
Supposons qu'il existe n types de coupons et que chaque tirage produise aléatoirement un type avec la même probabilité.
Le nombre moyen de tirages nécessaires est :
| nHn |
Comme :
| Hn ≈ ln(n) + γ |
le nombre moyen de tirages est approximativement :
| n ln(n) + γn |
Ce problème apparaît dans l'analyse probabiliste des algorithmes, les tests aléatoires, les réseaux et la collecte de données.
Exemple du collectionneur de coupons
Supposons qu'il existe :
| 10 |
types de coupons.
Le nombre moyen de tirages nécessaires pour tous les obtenir est :
| 10H10 |
Comme :
| H10 ≈ 2,928968 |
on obtient :
| 10 × 2,928968 |
soit environ :
| 29,29 |
Il faut donc environ 29 tirages en moyenne pour compléter la collection.
Recherche de records aléatoires
Les nombres harmoniques interviennent également dans les permutations aléatoires.
Supposons que des valeurs soient examinées successivement et qu'une valeur soit appelée record lorsqu'elle est supérieure à toutes les valeurs précédentes.
La probabilité que la valeur située en position i soit un nouveau record est :
| 1/i |
Le nombre moyen de records parmi n valeurs est donc :
| 1 + 1/2 + 1/3 + ... + 1/n |
soit :
| Hn |
Cette propriété est utilisée dans l'analyse de certains algorithmes aléatoires.
Variante généralisée
Les nombres harmoniques généralisés sont définis par :
|
Hn(m) = ∑i=1n 1/im |
où m représente l'ordre de généralisation.
Pour :
| m = 1 |
on retrouve le nombre harmonique ordinaire :
| Hn(1) = Hn |
Pour :
| m = 2 |
on obtient :
|
Hn(2) = 1 + 1/22 + 1/32 + ... + 1/n2 |
Ces suites apparaissent dans l'analyse avancée des algorithmes, les probabilités et la théorie analytique des nombres.
Nombres harmoniques alternés
Une autre variante consiste à alterner le signe des termes :
| 1 - 1/2 + 1/3 - 1/4 + ... |
La somme partielle d'ordre n peut être écrite :
|
An = ∑i=1n (-1)i+1 / i |
Contrairement à la série harmonique ordinaire, cette série converge.
Sa limite vaut :
| ln(2) |
Cette propriété illustre l'influence de l'alternance des signes sur la convergence d'une série.
Calcul exact
Un nombre harmonique est toujours un nombre rationnel.
Il peut donc être représenté sous la forme :
| numérateur / dénominateur |
Par exemple :
| H5 = 137/60 |
Un calcul exact peut être réalisé en additionnant successivement des fractions et en simplifiant chaque résultat à l'aide du PGCD.
Cependant, les numérateurs et les dénominateurs deviennent rapidement très grands. Pour les ordres élevés, il est généralement préférable d'utiliser une représentation en virgule flottante ou une bibliothèque de nombres rationnels multiprécision.
Algorithme avec fractions exactes
|
MODULE NombreHarmoniqueExact(n) numérateur ← 0 dénominateur ← 1 POUR i ← 1 JUSQU'A n numérateur ← numérateur × i + dénominateur dénominateur ← dénominateur × i diviseur ← PGCD(numérateur,dénominateur) numérateur ← numérateur / diviseur dénominateur ← dénominateur / diviseur FIN POUR RETOURNER (numérateur,dénominateur) |
Cet algorithme conserve une fraction simplifiée après chaque addition.
Il nécessite toutefois des entiers multiprécision lorsque n devient grand.
Erreurs d'arrondi
Le calcul direct avec des nombres à virgule flottante peut accumuler des erreurs d'arrondi.
Lorsque n est grand, les termes :
| 1/i |
deviennent très petits par rapport à la somme déjà obtenue. Leur addition peut alors perdre une partie de leur précision.
Une amélioration simple consiste à effectuer la somme dans l'ordre inverse :
| 1/n + 1/(n-1) + ... + 1 |
En ajoutant d'abord les plus petits termes, on réduit généralement la perte de précision.
Sommation inverse
|
MODULE NombreHarmoniqueInverse(n) somme ← 0 BOUCLE POUR i ← n JUSQU'A 1 somme ← somme + 1 / i FIN BOUCLE POUR RETOURNER somme |
Cette méthode possède toujours une complexité temporelle de :
| O(n) |
mais elle peut fournir un résultat légèrement plus précis en virgule flottante.
Pour des calculs encore plus sensibles, on peut employer la sommation de Kahan.
Comparaison des méthodes
| Méthode | Temps | Mémoire | Précision |
|---|---|---|---|
| Somme directe croissante | O(n) | O(1) | Bonne pour n modéré |
| Somme directe décroissante | O(n) | O(1) | Meilleure en virgule flottante |
| Fraction exacte | O(n), hors coût des grands entiers | Variable | Exacte |
| Approximation logarithmique | O(1) | O(1) | Très bonne pour grand n |
| Développement asymptotique | O(1) | O(1) | Très précise |
Le choix dépend de la taille de n, de la précision recherchée et du type numérique disponible.
Applications
Les nombres harmoniques sont utilisés dans de nombreux domaines :
- analyse des algorithmes ;
- analyse moyenne du tri rapide ;
- probabilités ;
- problèmes de collecte aléatoire ;
- recherche de records ;
- structures de données ;
- théorie des nombres ;
- analyse asymptotique ;
- statistiques ;
- théorie des graphes ;
- algorithmes aléatoires ;
- optimisation ;
- calcul scientifique.
Ils interviennent également dans plusieurs identités combinatoires et dans l'étude des fonctions génératrices.
Avantages
Les nombres harmoniques présentent plusieurs avantages :
- ils décrivent naturellement certaines sommes d'inverses ;
- ils permettent d'analyser des coûts logarithmiques ;
- ils possèdent des approximations très précises ;
- ils apparaissent dans de nombreux problèmes probabilistes ;
- ils relient les sommes discrètes aux logarithmes ;
- ils facilitent l'analyse moyenne de certains algorithmes.
Limites et précautions
Plusieurs précautions doivent être prises :
- la série harmonique diverge malgré la diminution de ses termes ;
- le calcul direct devient lent pour des valeurs très grandes de n ;
- les additions en virgule flottante accumulent des erreurs ;
- les fractions exactes produisent rapidement de très grands entiers ;
- il ne faut pas confondre croissance lente et convergence ;
- les approximations sont moins précises pour de petites valeurs de n ;
- le type numérique utilisé doit permettre une division réelle.
Remarque
Les nombres harmoniques constituent un exemple important de lien entre les mathématiques discrètes, les logarithmes et l'analyse des algorithmes. Leur croissance est suffisamment lente pour ressembler à celle du logarithme naturel, mais suffisamment persistante pour rendre la série harmonique divergente. En informatique, ils apparaissent dès qu'un coût, une probabilité ou un nombre moyen d'opérations dépend d'une somme de termes de la forme 1/i. Leur étude prépare naturellement à celle des suites de Fibonacci, des fonctions génératrices, des probabilités discrètes et de l'analyse asymptotique des algorithmes.