Van der Corput-sekvens

Illustration av fyllningen av enhetsintervallet (horisontell axel) med de första n termerna av decimalsekvensen Van der Corput, för n från 0 till 999 (vertikal axel)

En van der Corput-sekvens är ett exempel på den enklaste endimensionella sekvensen med låg diskrepans över enhetsintervallet ; det beskrevs första gången 1935 av den holländska matematikern JG van der Corput . Den konstrueras genom att vända basrepresentationen ) . av sekvensen av naturliga tal (1, 2, 3, …

b $b$ -representationen av det positiva heltal $\displaystyle n\geq 1}$ är

n~=~\summa _{k=0 }^{L-1}d_{k}(n)b^{k}~=~d_{0}(n)b^{0}+\cdots +d_{L-1}(n)b^{ L-1},

där

b

är basen i vilken talet

n

representeras, och

0\leq d_{k}(n)<b;

det vill säga den

k

-te siffran i

b

-ary expansionen av

n.

Det

n

-te numret i van der Corput-sekvensen är

g_{b}(n)~=~\sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}~=~d_{0}( n)b^{-1}+\cdots +d_{L-1}(n)b^{-L}.

Exempel

Till exempel, för att få decimalsekvensen van der Corput, börjar vi med att dela talen 1 till 9 i tiondelar ( $x/10$ ), sedan ändrar vi nämnaren till 100 för att börja dividera i hundradelar ( $x/100$ ). När det gäller täljare börjar vi med alla tvåsiffriga tal från 10 till 99, men i baklänges siffror. Följaktligen kommer vi att få täljarna grupperade efter slutsiffran. Först alla tvåsiffriga täljare som slutar med 1, så nästa täljare är 01, 11, 21, 31, 41, 51, 61, 71, 81, 91. Sedan täljare som slutar med 2, så de är 02, 12 , 22, 32, 42, 52, 62, 72, 82, 92. Och efter det slutar täljarna på 3: 03, 13, 23 och så vidare...

Därmed börjar sekvensen

\left\{{\tfrac {1}{10}},{\tfrac {2}{10}},{\tfrac {3}{10}},{\tfrac {4}{10}},{\tfrac {5}{10}},{\tfrac {6}{10}},{\tfrac {7}{10}},{\tfrac {8}{10}},{\tfrac {9}{10}},{\tfrac {1}{100}},{\tfrac {11}{100}},{\tfrac {21}{100}},{\tfrac {31}{100}},{\tfrac {41}{100}},{\tfrac {51}{100}},{\tfrac {61}{100}},{\tfrac {71}{100}},{\tfrac {81}{100}},{\tfrac {91}{100}},{\tfrac {2}{100}},{\tfrac {12}{100}},{\tfrac {22}{100}},{\tfrac {32}{100}},\ldots \right\},

eller i decimalrepresentation:

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,1, 0,1, 0,1, 0,0. 12, 0,22, 0,32 , …,

Detsamma kan göras för det binära siffersystemet , och den binära van der Corput-sekvensen är

0,1 ₂ , 0,01 ₂ , 0,11 _{2 ,} 0,001 _{2 ,} 0,101 ₂ , 0,011 ₂ , 0,111 2 , 0,0001 2 , 0,1001 2 _{, 0,0101 2}_{, 0,0101}₂ , 0,0101 ₂ , 0,0101 ₂ , 0,0101 ₂ , 0,0101 2 . 0,1011 2 , 0,0111 _{2 ,} 0,1111 ₂_, …

eller på motsvarande sätt

{\tfrac {1}{2}},{\tfrac {1}{4}},{\tfrac {3}{4}},{\tfrac {1}{8}},{\tfrac {5}{8}},{\tfrac {3}{8}},{\tfrac {7}{8}},{\tfrac {1}{16}},{\tfrac {9}{16} },{\tfrac {5}{16}},{\tfrac {13}{16}},{\tfrac {3}{16}},{\tfrac {11}{16}},{\tfrac { 7}{16}},{\tfrac {15}{16}},\ldots .

Elementen i van der Corput-sekvensen (i valfri bas) bildar en tät uppsättning i enhetsintervallet; det vill säga för alla reella tal i $[0,1]$ , finns det en undersekvens av van der Corput-sekvensen som konvergerar till det talet. De är också jämnt fördelade över enhetsintervallet.

C implementering

    
     0 

       0 
          
        
        
    

     
 dubbel  korput  (  int  n  ,  int  bas  ){  dubbel  q  =  ,  bk  =  (  dubbel  )  1  /  bas  ;  medan  (  n  >  )  {  q  +=  (  n  %  bas  )  *  bk  ;  n  /=  bas  ;  bk  /=  bas  ;  }  returnera  q  ;  }

Se även

Bit-reversal permutation – Permutation som vänder binära tal
Konstruktioner av sekvenser med låg diskrepans
Halton-sekvens – sekvens av nästan likformigt fördelade tal som verkar vara slumpmässiga , en naturlig generalisering av van der Corput-sekvensen till högre dimensioner

van der Corput, JG (1935), "Verteilungsfunktionen (Erste Mitteilung)" (PDF) , Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam (på tyska), 38 : 813–821, Zbl 0012.34705
Kuipers, L.; Niederreiter, H. (2005) [1974], Enhetlig distribution av sekvenser , Dover Publications , sid. 129 158, ISBN 0-486-45019-8 , Zbl 0281.10001

externa länkar

Van der Corput-sekvens på MathWorld