Кіріспе
Математикалық тізбек түрі
Математикада, төмен айырмашылық тізбек – бұл N-нің барлық мәндері үшін оның x1, …, xN кіші тізбектерінің төмен айырмашылығы бар тізбек. Деректеп айтқанда, егер кез келген жиынтық B-ге түсетін тізбектегі нүктелердің үлесі B өлшеміне пропорционалды болса, онда тізбектің айырмашылығы төмен болады, бұл тең үлестірілген тізбектерде орташа есеп бойынша (бірақ нақты мысалдар үшін емес) болатын жағдайға ұқсас. Айырмашылықтың нақты анықтамалары B таңдауына қарай (гиперсфералар, гиперкубтар және т.б.) және әр B үшін айырмашылық қалай есептеліп (әдетте нормаланады) және біріктіріледі (әдетте нашар мән алынады) деген тұрғыдан өзгешеленеді. Төмен айырмашылық тізбектер квази-кездейсоқ тізбектер деп те аталады, себебі олар біркелкі үлестірілген кездейсоқ сандардың орнына жиі қолданылады. "Квази" сөздері төмен айырмашылық тізбектің мәндерінің кездейсоқ немесе псевдокездейсоқ емес екенін нақты көрсету үшін қолданылады, бірақ мұндай тізбектер кездейсоқ айнымалылардың кейбір қасиеттерін бөліседі және квази Монте-Карло әдісі сияқты кейбір қолданыстарда олардың төменгі айырмашылығы маңызды артықшылық болып табылады.
In mathematics, a low discrepancy sequence is a sequence with the property that for all values of N, its subsequence x1, , xN has a low discrepancy. Roughly speaking, the discrepancy of a sequence is low if the proportion of points in the sequence falling into an arbitrary set B is close to proportional to the measure of B, as would happen on average (but not for particular samples) in the case of an equidistributed sequence. Specific definitions of discrepancy differ regarding the choice of B (hyperspheres, hypercubes, etc.) and how the discrepancy for every B is computed (usually normalized) and combined (usually by taking the worst value). Low discrepancy sequences are also called quasirandom sequences, due to their common use as a replacement of uniformly distributed random numbers. The "quasi" modifier is used to denote more clearly that the values of a low discrepancy sequence are neither random nor pseudorandom, but such sequences share some properties of random variables and in certain applications such as the quasi Monte Carlo method their lower discrepancy is an important advantage.
Қолданбалар
Квазирандомдық сандар таза рандомдық сандарға қарағанда артықшылыққа ие, себебі олар қызығушылық тудыратын саланың тез және біркелкі жабуын қамтамасыз етеді. Екі пайдалы қолданысы – ықтималдық тығыздық функциясының сипаттамалық функциясын табу және аз мөлшерде шуы бар детерминистік функцияның туындысын табу. Квазирандомдық сандар жоғары ретті моменттерді жоғары дәлдікпен өте жылдам есептеуге мүмкіндік береді. Сорттауды қажет етпейтін қолданыстарға статистикалық таралымның орташасы, стандартты ауытқуы, қисықтығы және куртозын табу, сондай-ақ күрделі детерминистік функциялардың интегралын және жаһандық максимумдарын мен минимумдарын табу жатады. Квазирандомдық сандар Ньютон-Рафсон итерациясы сияқты тек локальды жұмыс істейтін детерминистік алгоритмдерге бастапқы мәндерді беру үшін де қолданылуы мүмкін. Квазирандомдық сандарды іздеу алгоритмдерімен де үйлестіруге болады. Іздеу алгоритмімен квазирандомдық сандар статистикалық таралымның модасын, медианасын, сенімдік интервалдарын және жиынтық таралымын, сондай-ақ детерминистік функциялардың барлық локальды минимумдарын және барлық шешімдерін табу үшін пайдаланылуы мүмкін.
Негізгі болжамдар
1-ші болжам. Тек s өлшемге ғана тәуелді cs тұрақтысы бар, яғни кез келген шекті нүктелер жиыны {x1, ..., xN} үшін. 2-ші болжам. Тек s-ке ғана тәуелді c's тұрақтысы бар, яғни кез келген шексіз x1, x2, x3 тізбегі үшін N сандарының шексіз санына сәйкес. Бұл болжамдар эквивалентті. Олар В. М. Шмидт тарапынан s ≤ 2 үшін дәлелденген. Жоғары өлшемдерде сәйкес мәселе әлі де шешілмеген. Ең жақсы белгілі төменгі шектер Майкл Лейси және оның әріптестеріне тиесілі.
for any finite point set {x1, ,xN}. Conjecture 2. There is a constant c's depending only on s, such that
for infinite number of N for any infinite sequence x1,x2,x3,
These conjectures are equivalent. They have been proved for s ≤ 2 by W. M. Schmidt. In higher dimensions, the corresponding problem is still open. The best known lower bounds are due to Michael Lacey and collaborators.
Кездейсоқ сандар
Квазирандомдық сандар тізбектерін, рандомдық сандарға теріс корреляция қою арқылы жасауға болады. Мұны істеудің бір жолы – рандомдық сандар жиынынан бастап, біркелкі таралатын квазирандомдық сандарды келесі формула бойынша құру: тақ n үшін және жұп n үшін. Бастапқы рандомдық сандарды қолдана отырып, екінші жолы – 0.5 смещениесімен рандомдық жүріс құру: яғни, алдыңғы квазирандомдық санға 0.5 пен рандомдық санды қосып, нәтижені 1-ге дейін модулдеу. Екі және одан көп өлшемдер үшін, доменнің толық және тең қамтылуын қамтамасыз ету үшін тиісті өлшемдегі латын квадраттарын смещениелер жасау үшін пайдалануға болады.
for odd and for even. A second way to do it with the starting random numbers is to construct a random walk with offset 0.5 as in:
That is, take the previous quasirandom number, add 0.5 and the random number, and take the result modulo 1. For more than one dimension, Latin squares of the appropriate dimension can be used to provide offsets to ensure that the whole domain is covered evenly.
Халтон реті
Халтон тізбектілігі ван дер Корпут тізбектілігінің жоғары өлшемдерге табиғи жалпыламасы болып табылады. s кез келген өлшем және b1, …, bs 1-ден үлкен кез келген өзара жай бүтін сандар болсын. Онда былай анықталады:
Содан кейін, тек b1, …, bs-ке ғана тәуелді C тұрақтысы бар, сондықтан {x(n)}n≥1 тізбегі s өлшемді тізбек болып табылады, және
Хаммерсли жиынтығы
b1, …, bs−1 – 1-ден үлкен өзара жай оң бүтін сандар болсын. Берілген s және N үшін, N өлшеміндегі s өлшемді Хаммерсли жиыны келесідей анықталады:
for n = 1, , N. Then
where C is a constant depending only on b1, , bs−1. Note: The formulas show that the Hammersley set is actually the Halton sequence, but we get one more dimension for free by adding a linear sweep. This is only possible if N is known upfront. A linear set is also the set with lowest possible one dimensional discrepancy in general. Unfortunately, for higher dimensions, no such "discrepancy record sets" are known. For s = 2, most low discrepancy point set generators deliver at least near optimum discrepancies.
n = 1, …, N үшін. Онда C – тек b1, …, bs−1-ге ғана тәуелді тұрақты шама. Ескерту: Формулалар Хаммерсли жиынының іс жүзінде Халтон тізбегі екенін көрсетеді, бірақ сызықтық сканерлеуді қосу арқылы біз қосымша бір өлшемді тегін аламыз. Бұл тек қана N алдын ала белгілі болған жағдайда ғана мүмкін. Сызықтық жиын – әдетте, ең төменгі бір өлшемді сәйкессіздікке ие жиын. Алайда, жоғары өлшемдер үшін мұндай «сәйкессіздік рекордтары жиыны» белгілі емес. s = 2 үшін, ең төменгі сәйкессіздік нүктелері жиынын құратын көптеген генераторлар кем дегенде оңтайлы сәйкессіздіктерге жуық нәтижелер береді.
for n = 1, , N. Then
where C is a constant depending only on b1, , bs−1. Note: The formulas show that the Hammersley set is actually the Halton sequence, but we get one more dimension for free by adding a linear sweep. This is only possible if N is known upfront. A linear set is also the set with lowest possible one dimensional discrepancy in general. Unfortunately, for higher dimensions, no such "discrepancy record sets" are known. For s = 2, most low discrepancy point set generators deliver at least near optimum discrepancies.
Собол тізбегі
Антонов–Салеев нұсқасы бойынша Собол тізбегі, бағыт сандары деп аталатын арнайы екілік бөлшектер жиынтығынан нөл мен бір арасындағы сандарды ұзындығы екілік бөлшектер ретінде тікелей тудырады. Грей кодінің , , биттері бағыт сандарын таңдау үшін пайдаланылады. Собол тізбегінің мәнін алу үшін, Грей кодінің екілік мәнін тиісті бағыт санымен "ексклюзивті немесе" операциясын қолданыңыз. Қажетті өлшемдер саны таңдауға әсер етеді.
Графикалық мысалдар
Төменде көрсетілген нүктелер – Собол' типіндегі тізбектегі алғашқы 100, 1000 және 10000 элемент. Салыстыру үшін псевдорандомдық нүктелер тізбегінің 10000 элементі де көрсетілген. Аз айырмашылыққа ие тізбек TOMS алгоритмі 659 арқылы жасалды. Алгоритмнің Фортрандағы нұсқасы Netlib-тен қолжетімді.