Sekwencja Van der Corputa

Ilustracja wypełnienia przedziału jednostkowego (oś pozioma) za pomocą pierwszych n wyrazów dziesiętnego ciągu Van der Corputa, dla n od 0 do 999 (oś pionowa)

Sekwencja van der Corput jest przykładem najprostszej jednowymiarowej sekwencji o niskiej rozbieżności w przedziale jednostkowym ; został po raz pierwszy opisany w 1935 roku przez holenderskiego matematyka JG van der Corputa . Jest konstruowany przez odwrócenie . podstawowej reprezentacji ciągu liczb naturalnych (1, 2, 3, …)

b ${\ displaystyle b}$ -ary reprezentacja dodatniej liczby całkowitej $}$ b

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

gdzie $(n) <b;}$ podstawą, w której jest $liczba$$n$$\ Displaystyle 0 \ równoważnik d_ {k$${\ displaystyle n.}$ to znaczy -ta w $rozwinięciu$ n -ta $displaystyle n}$ w sekwencji van der Corput to n {\

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

Przykłady

Na przykład, aby uzyskać dziesiętną sekwencję van der Corput, $($ od podzielenia liczb od 1 do 9 na części dziesiąte ( a następnie zmieniamy mianownik na 100, aby rozpocząć dzielenie na części setne ${\ displaystyle x/100}$ ). Jeśli chodzi o licznik, zaczynamy od wszystkich liczb dwucyfrowych od 10 do 99, ale w odwrotnej kolejności cyfr. W rezultacie otrzymamy liczniki pogrupowane według cyfry końcowej. Po pierwsze wszystkie dwucyfrowe liczniki kończące się na 1, więc kolejne liczniki to 01, 11, 21, 31, 41, 51, 61, 71, 81, 91. Następnie liczniki kończące się na 2, czyli 02, 12 , 22, 32, 42, 52, 62, 72, 82, 92. A potem liczniki kończące się na 3: 03, 13, 23 i tak dalej...

W ten sposób rozpoczyna się sekwencja

$${\ Displaystyle \ lewo \ {{\ 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\},}$$

lub w reprezentacji dziesiętnej:

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

To samo można zrobić dla binarnego systemu liczbowego , a binarny ciąg van der Corput jest

₂ 0,1011 ₂ , 0,0111 ₂ , 0,1111 _{2 ,} … _{_} _ _{_} _ _{_} _ _{_} _ _{_} _ _{_} _ _{_} _ _{_} _ _{_} _ _{_} _

lub równoważnie,

$${\ Displaystyle {\ 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 .}$$

Elementy ciągu van der Corputa (o dowolnej podstawie) tworzą gęsty zbiór w przedziale jednostkowym; to znaczy dla dowolnej liczby rzeczywistej w $podsekwencja$ van der Corput, która zbiega się tej liczby Są one również równomiernie rozmieszczone w przedziale jednostkowym.

Implementacja C

    
     0 

       0 
          
        
        
    

      double  corput  (  int  n  ,  int  base  ) {  double  q  =  ,  bk  =  (  double  )  1  /  base  ;  while  (  n  >  )  {  q  +=  (  n  %  podstawa  )  *  bk  ;  n  /=  podstawa  ;  bk  /=  podstawa  ;  }  zwróć  q 
 ;  } 

Zobacz też

• Permutacja z odwróceniem bitów - permutacja, która odwraca liczby binarne
• Konstrukcje ciągów o małej rozbieżności
• Sekwencja Haltona - sekwencja prawie równomiernie rozłożonych liczb, które wydają się być losowymi Stronami wyświetlającymi opisy danych wiki jako rezerwowe , naturalne uogólnienie sekwencji van der Corput na wyższe wymiary

•   van der Corput, JG (1935), „Verteilungsfunktionen (Erste Mitteilung)” (PDF) , Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam (w języku niemieckim), 38 : 813–821, Zbl 0012.34705
•    Kuipers, L.; Niederreiter, H. (2005) [1974], Jednolity rozkład sekwencji , Dover Publications , s. 129158, ISBN 0-486-45019-8 , Zbl 0281.10001

Linki zewnętrzne

• Sekwencja Van der Corputa w MathWorld