Suite de van der Corput
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f2/Van_der_Corput_sequence_999.svg/330px-Van_der_Corput_sequence_999.svg.png)
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 :où est le -ième chiffre de en base . Le -ième nombre de la suite de van der Corput associée à est
Exemples
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
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
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
- Suites à discrépance faible
- Permutation d'inversion des chiffres binaires (en)
- Suite de Halton (en) : type de suite numérique utilisée en statistique qui généralise les suites de van der Corput en dimension supérieure.
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Van der Corput sequence » (voir la liste des auteurs).
- (de) J. G. van der Corput, « Verteilungsfunktionen (Erste Mitteilung) », Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam, vol. 38, , p. 813-821 (zbMATH 0012.34705, lire en ligne)
- L. Kuipers et H. Niederreiter, Uniform distribution of sequences, Dover Publications, (1re éd. 1974), xiv+390 p. (ISBN 0-486-45019-8, zbMATH 0281.10001), p. 129, 158
Liens externes
- Suite de Van der Corput sur MathWorld
- (en) Eric W. Weisstein, « Van der Corput sequence », sur MathWorld
Portail des mathématiques