AOP_Tom2 (1021737), страница 25
Текст из файла (страница 25)
ПуСтЬ ЛН = Езх'lм -- ПЕрВООбраЗНЫй т-й КОРЕНЬ ИЗ ЕдИНИцЫ. ЕСЛИ (ХЫ..., Х~) и ())м..., рл) — два вектора с компонентами из области О < х ч у < т, то справедливо равенство (х~ — ул)или-"Е(х, — у,)и, т , ЕСЛИ (ХМ ...,ХЛ) = (РЛ .,)О) Е Ф О, если (хы, хс) Ф (Ры., рл). 0<но...,и, <пъ Поэтому число векторов (х„,...,х„„,,) в В для О < и < )у', когда область Л определена в (43), может быть выражено следующим образом: 1 х н~ Л хх ~~ 1н~ ), ~~, ' -(у1н1Ч- -ланг) ,п~ — Е 0<и<Я О(но...,и~ <ил а1<у1<Д1 а,<у~<О~ Когда в втой сумме ил = = щ = О, то она равна Л('т', умноженному на объем В. Следовательно, Рн можно выразить, как максимум по Л выражения а) 1 Е х и1+ 0ьх .н-1и~ ~ (умн с Ьу!и ) Хт' 0« М 0<и,...,и < а~<01<01 а~йую<Д (и,,....и,)у(О,,О) Поскольку комплексные числа удовлетворяют неравенствам )ш + х! < (ш~ + )х~ и )шг( = )ш))г(, справедливы соотношения Р(,,) < шах — ~~~ ~~~ ...
~~~ ы (У'"'~с'ьх'и') О(ил,...,ил) 1 и тл О<им...,и,<ш а1<у,<З1 а,<у,<А (н1, . Он)х-(0,...,0) < — ~~~ шах ~~~ ... ~~~ ы (у'и'+' '~у'"') д(иы..., ил) 1 тл я О(иь...,и, <т ил <у~ <91 а~ <у~ <Ш (и1,...,и~)ф(О,...,О) (44) Диы..., ил) у(иы..., и,), 0<иь.,.,и, <т (и,...,и, ) Ф(О„.,О) где ( ) ' х„и~С- -Сх и, 1и, 1 с: с Л о«, н /(им..., ис) = тах— 1 я т' а1<р1<д1 асйр <А 1 1 я т т и~<рс<Л1 а~<о~<А И /, и д можно упростить в дальнейшем для того, чтобы получить хорошую верхнюю грань для Р, . Справедливо равенство О) „ — Ли „ †2 1 — ир < т х т ы —" — 1 ~ т)оси — 1~ то)п(ли/т) ' и<и<э где и ф О и сумма < 1, когда и = О. Следовательно, /(им,ис) < г(ис,,ис), (45) где х„ис+.
+х„сс — сис =х„ис+(ах„+с)иг+ .+(а х,+с(а + +1))ис = (ис+аиг+.. +а' 'ис)х„+)с(ис,,ис), где )с(ис,...,ис) не зависит от и. Значит, ф ) „р(ии...,и,)х 1 о<и<ср (47) где с)(ис,...,ис) = ис + аиг + + а ис. (48) Здесь устанавливается связь со спектральным критерием. Покажем, что сумма д(ис,..., ис) будет маленькой, если только не выполняется с)(ис,...,ис) = О (по модулю т); другими словами, вклад суммы (44) определяется, в основном, решением (15). Кроме того, в упр.
27 показано, что г(ис,...,ис) будет малым, когда (ис,..., ис) является иболыпими решением (15). Следовательно, разброс Р,~,) будет малым, когда (15) имеет только "большие" решения, а именно— когда пройдена проверка спектральным критерием. Осталось определить количественные аналоги этих качественных утверждений, чтобы осуществлять точные вычисления. ( 'и)хх П 1 (46) с«р<с т сйп(кис/т) риф~ Кроме того, когда (х„) порождена по модулю т линейной конгрузнтной последовательностью, справедливы равенства Сначала рассмотрим величину у(и1,..., и,). Когда»т' = т, так что сумма (47) берется по всему периоду, д(им..., и») = О, кроме случая, когда (иы..., и!) удовлетворяет уравнению (15).
Поэтому разброс ограничен сверху суммой г(иы,,.,и»), взятой по всем ненулевым решениям (15). Теперь рассмотрим, что произойдет с такой же, как (47), суммой, когда Х меньше т и д(иы...,и») не кратно га. Справедливы равенства 1 в ~;~ ~~, ' -ьь ~~,~ кгьть 1 1 Х »ч т 0<»»<Ф ока<)г о<в< о<»< « И . ")' а<в< о<а<ай' (49) где Пусть в — минимальное число среди чисел, для которых а' = 1 (по модулю га), и пусть в' = (а' — 1) с/(а — 1) шой т.
Тогда в — это делитель т (см. лемму 3.2.1.2Р) и л„+, = х„+ зв» (по модулю гп). Сумма по 1 равна нулю„за исключением случая, когда у — ( кратно в, поэтому получим, что )я ~з = Е уэвз 3»' О й» <»»»»»» Справсцливо равенство в' = »7»в, где !)» и т — взаимно простые (см. упр, 3.2.1.2-21)» поэтому оказывается, что ) О, если й + д' ~ О (по модулю т/в), Г1) (Яво~ = з )( т/з/в, если Й + д' = О (по модулю т/в).
! о Используя эти равенства в (49) и вспомнив неравенство (45), можно показать, что — ь»*" < — ~~» г(к), 1 т »"1(»»' /в О<а<гг ь (52) т е»+ув (50) а<1< Сейчас Яц = ы 'вЯмь поэтому (Яц) = )Яве) для всех(, и можно вычислить это общее значение, выполнив экспоненциальное суммирование: в !Яво!' = — ,'!. 1Яв()' о<(< 1 ~».»»з-»в ~;,„-*».»»-»гв О<(<т О<1<а» е« '»а ()-»)В ~ ~ь»е»-цз! 1 т О <»зз <»»» О«<т (»'-а)в ~~, [р»»-1)к»в»+(а» »-1)с/(а-1) т О<»<»»»»<1<»»»+» о<~<. где сумма берется по 0 < к < т, таким, что й+ д' ги 0 (по модулю т/в).
Если воспользоватьсн упр. 25, чтобы оценить оставшуюся сумму, то получится, что (53) — ы*" < — —, 1п в + О ~ — ), Те же гРани могУт быть использованы, чтобы оценить ~Х ' 2',е<„<н ыч*" ~ длЯ любого д ф 0 (по модулю т), так как можно заменить тп делителем гл.
В действительности верхняя грань будет даже меньше, когда д имеет общий делитель с т, так как з и т/~/з, вообще говоря, становятся меньше (см. упр. 26). Мы доказали, что часть д(иы..., и~) нашей верхней грани разброса (44) мала, когда 1д достаточно большое и когда (иы ..,, и~) не удовлетворяет (15). В упр. 27 доказывается, что часть Д(им..., сч) нашей верхней грани мала, когда сумма берется по всем не равным нулю векторам (иы..., и,), удовлетворяющим (15), и таким, что эти векторы достаточно далеки от (О,...,0). Объединив результаты, получим следующую теорему Нидеррейтера ( ч1едегге11ег).
Теорема (ч. Пусть (Х„) — линейная конгрузнтная последовательность (Хе, а, с, т) с периодом длиной т и пусть з — наименьшее положительное число, такое, что а'—: 1 (по модулю т). Тогда $-мерный разброс Рм относительно первых Х значений 0) (Х„), «ак определено в (42), удовлетворяет равенствам 010 = 0((1ойгп)'гм,„). (55) Здесы,„„— максимальное значение величины г(иы..., и~), определенной в (46), которая взята по всем удонлетворяюшнмуравпенню (15) ненулевым целым векторам (иы..., и~). Доказашельсшво.
Первые два члена 0 в (54) определяются векторами (им...,и~) из (44), не удовлетворяющими (15), так как в упр. 25 доказываетсн, что /(им..., и~), где сумма берется по всем (им..., и~), равна 0(((2/я)!и гл)'), и упр. 26 ограничивает каждое д(и~,...,и~). (Эти члены отсутствуют в (55), поскольку в этом случае д(иы ..,, и~) = 0.) Оставшийся член 0 в (54) и (55) определяется ненулевым вектором (иы., ., и,), который удовлетворяет (15), если использовать грани, полученные в упр. 27.
(Внимательно проверяя данное доказательство, каждое 0 в атой формуле можно заменить функцией от 1.) 1 Равенство (55) относится к критерию серий при размерности 1 для полного периода, тогда как равенство (54) дает полезную информацию о распределении первых Л сгенерированных значений, когда 1ч' меньше гп, если только д' не слишком малб. Заметим, что (54) гарантирует малый разброс только тогда, когда в достаточно большое, иначе будет доминировать член гп/~/за Если т = р",...р'„" и Оса(а — 1, т) = р~~'...р/", то з равно р" ,б ...р,'" г" по лемме 3.2.1.2Р.
Таким образом, наибольшие значения а соответствуют большому потенциалу. В общем олучае т = 2', о = 5 (по молулю 8) и получаем я = -'т. Значит, Рь/ равно 0) 0(л/т(1ойт)'л/Ал) + 0(()ойт)лг,„). Не составляет труда доказать, что 1 гжах < л/8, (56) (см. упр. 29). Следовательно, равенство (54), в частности, указывает, что разброс в й-мерном случае будет мал, если критерий серий пройден и если Х в некоторой степени больше л/т (1о8 т)' В смысле теоремы Х это почти так же строго.
Из результатов упр. 30 следует, что линейные конгруэнтные последовательности, подобные приведенным в строках 8 и 13 табл. 1, имеют разброс порядка (1о8 т)з/т при размерности 2. Разброс в этом случае чрезвычайно мал несмотря на то, что существуют области, имеющие вид параллелограмма площадью — 1/л/т, в которых нет точки ((7„, (/„„.л). Тот факт., что разброс может столь резко измениться, когда тачки вращаются, предупреждает о том, что критерий серий может быть не так точен прн определении случайности, как инвариантный относительно вращения спектральный критерий.
С. Историческая справка. В 1959 году, когда верхнюю грань ошибки вычисления й-мерного интеграла определяли методом Монте-Карло, Н. М. Коробов придумал метод оценки множителя линейной конгруэнтной погчедовательности. Его усложненная формула связана, скорее, со спектральным критерием, так как на нее сильно влияют 'малые" решения (15); ио это не совсем одно и то же. Критерий Коробова широко обсуждался в литературе и изучался Купером и Нидеррейтером (см. Кшрегя апй) ."лйеййеггеййег, (/шгогш 7уйяйгйЬий1оп оу яеййиепсея (7ллелл уог1с %11еу, 1974), 32.5). Необычно сформулировали спектральный критерий Р, Р. Ковэю и Р. Д. МакФерсон (В.
Н. Сохеуои апй) В. 1У, МасРЬегяоп, ХАСЫ 1 ~ (1967), 100 — 119), введя его интересным косвенным путем. Вместо того чтобы работать с решеточной структурой последовательных точек, они рассматривали случайные числа генераторов квк ч чт...л,, „,, '-'„= о (по модулю йп), в их трактовке рассматривались как "частоты' волн или точки "спектра', определенного генератором случайных чисел, с низкочастотными волнами, которые неблагоприятны для случайности.
Отсюда название спектральный критерий. Ковзю и Мак-Ферсон ввели аналогичную алгоритму Б процедуру для выполнения их критерия, основанную на принципах леммы А. Тем не менее их оригинальная процедура (в которой используются матрицы (/(/~ и ГГ вместо У и Ъ') имела дело с крайне болыиими числами. Идея работы непосредственно с 7/ и 1г была независимо предложена Ф. Янссгнсом и У. Дитером (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
