Aller au contenu

Suite de van der Corput

Un article de Wikipédia, l'encyclopédie libre.
Illustration du remplissage de l'intervalle unité (axe horizontal) par les n premiers termes de la suite de Van der Corput décimale, pour n de 0 à 999 (axe vertical)

Une suite de van der Corput est un des exemples les plus simples de suite à discrépance faible en dimension 1, sur l'intervalle unité. Ces suites ont été décrites pour la première fois en 1935 par le mathématicien néerlandais Johannes van der Corput. Elles sont construites en inversant la représentation en base n de la suite des nombres naturels (1, 2, 3,…).

On se donne un entier . Pour tout entier positif , on considère son écriture en base  : est le -ième chiffre de en base . Le -ième nombre de la suite de van der Corput associée à est

Par exemple, pour obtenir la suite de van der Corput décimale, on commence par diviser les nombres 1 à 9 par dix (). Pour un nombre à deux chiffres, on inverse l'ordre des chiffres et on divise par cent. On obtient ainsi les numérateurs, regroupés par leur dernier chiffre : d'abord, tous les numérateurs à deux chiffres qui se terminent par 1, c'est-à-dire 01, 11, 21, 31, 41, 51, 61, 71, 81, 91, puis les numérateurs se terminent par 2, à savoir 02, 12, 22, 32, 42, 52, 62, 72, 82, 92, et ainsi de suite...

La suite commence donc de la façon suivante :

ou, en écriture décimale :

0,1 ; 0,2 ; 0,3 ; 0,4 ; 0,5 ; 0,6 ; 0,7 ; 0,8 ; 0,9 ; 0,01 ; 0,11 ; 0,21 ; 0,31 ; 0,41 ; 0,51 ; 0,61 ; 0,71 ; 0,81 ; 0,91 ; 0,02 ; 0,12 ; 0,22 ; 0,32…

On peut faire de même en base deux, ce qui donne la suite de van der Corput binaire :

0,12 ; 0,012 ; 0,112 ; 0,0012 ; 0,1012 ; 0,0112 ; 0,1112 ; 0,00012 ; 0,10012 ; 0,01012 ; 0,11012 ; 0,00112 ; 0,10112 ; 0,01112 ; 0,11112...

ou, de façon équivalente,

Propriétés : densité, équirépartition, discrépance étoile faible

[modifier | modifier le code]

Les termes d'une suite de van der Corput (dans n'importe quelle base ) forment une partie dense de l'intervalle unité. Cela signifie que pour tout nombre réel dans , il existe une sous-suite de la suite de van der Corput qui converge vers ce nombre.

Plus précisément, ils sont équirépartis sur l’intervalle unité : étant donné un sous-intervalle de , la proportion d'entiers tels que tend vers la longueur de lorsque tend vers l'infini.

Cette propriété étant acquise, on peut raffiner la répartition des termes à l'aide de la notion de discrépance. On peut démontrer qu'il existe une constante C dépendant uniquement de b telle que (gb(n))n ≥ 1 vérifie

Implémentation en C

[modifier | modifier le code]
double corput(int n, int base){
  double q=0, bk=(double)1/base;

  while (n > 0) {
   q += (n % base)*bk;
   n /= base;
   bk /= base;
  }

  return q;
}

Articles connexes

[modifier | modifier le code]

Notes et références

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]