Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 36
Текст из файла (страница 36)
25 доказывается, что /(иы ", иэ), где сумма берется по всем (иэ,..., и~) „равна О(((2/к)!и ш)'), и упр. 26 ограничивает каждое У(нь...,цс) (Этн члены отсутствуют в (55), поскольку в этом случае й(оы..., сч) = 0.) Оставшийся член 0 в (54) и (55) определяется ненулевым вектором (иэ,, и~), который удовлетворяет (15), если использовать грани, полученные в упр. 27. (Внимательно проверяя данное доказательство, каждое О в этой формзше можно заменить функцией от 1.) $ Равенство (55) относится к критерию серий при размерности $ для полного периода, тогда как равенство (54) дает полезную информацию о распределении первых Х сгенерированных значений, когда Ю меньше гп, если только Ю не слишком малб. Звметнм, что (54) гарантнрует малый разброс только тогда, когда э достаточно большое, нначе будет доминировать член ти/~/з.
Если ш = р~'...р'„" н йод(а — 1, т) = р(' ...рГ",. то э равно р" ,д...р'; г" по лемме 3.2.1.2Р. Таким образом, наибольшие значения э соответствуют большому потенцналу. В общем случае т = 2', а и 5 (по модулю 8) и получаем а = -'ш, Значит, 0~~',~ равно О( /т (1ой т)'~'/Х) + 0((1ойт)'г,„). Не составляет труда доказать, что 1 гмвц ,/8 и, (56) (см, упр. 29). Следовательно, равенство (54), в частности, указывает, что разброс в 1-мерном случае будет мал, если критерий серий пройден и если Ю в некоторой степени больше ~/т (1о8 т)'+'.
В смысле теоремы Х это почти так же строго. Из результатов упр. 30 следует, что линейные конгруэнтные последовательности, подобные приведенным в строках 8 и 13 табл. 1, имеют разброс порядка (1ойт)т/ш при размерности 2. Разброс в этом случае чрезвычайно мал несмотря на то, что существуют области, имеющие вид параллелограмма площадью ш 1/„/т, в которых нет точки (У„, У„+1). Тот факт, что разброс может столь резко измениться, когда точки вращаются, предупреждает о том, что критерий серий может быть не так точен при определении случайности, как инвариантный относительно вращения спектральный критерий. О.
Историческая справка. В 19о9 году, когда верхнюю грань ошибки вычисления Г-мерного интеграла определяли методом Монте-Карло, Н. М. Коробов придумал метод оценки множителя линейной конгруэнтной последовательности. Его усложненная формула связана. скорее, со спектральным критерием, так как на нее сильно влияют "малые" решения (15); но зто не совсем одно и то же. Критерий Коробова широко обсуждался в литературе и изучался Купером и Нидеррейтером (см. Кшрегз апд К1едегге(гег, Ушуогт 0ЫгпЬиВоп о/бейиепсеа (Хек Ъог)с: %1)еу.
1974), 32.5). Необычно сформулировали спектральный критерий Р. Р. Ковэю н Р. Д. МакФерсон (В. Н. Сотеуои апд В. 1). Масрйегзоп, йАСМ 14; (1967), 100 — 119), введя его интересным косвенным путем. Вместо того чтобы работать с решеточной структурой последовательных точек, они рассматривали случайные числа генераторов как «-Щ "".Ч ф+'+ч, „,:, ~ -'*,=В (по модулю т), в их трактовке рассматривались как "частоты" волн или точки '*спектра", определенного генератором случайных чисел, с низкочастотными волнами, которые неблагоприятны для случайности.
Отсюда название спектпральнмй кршперий. Ковэю и Мак-Ферсои авели аналогичную алгоритму 8 процедуру для выполнения их критерия, основанную на принципах леммы А. Тем не менее их оригинальная процедура (в которой используются матрицы УУ и Ь'Ъ вместо У и 1') имела дело с крайне большими числами. Идея работы непосредственно с (/ и Г' была независимо предложена Ф.
Янссенсом и У. Дитером (см. Г. 3апзеепз апд Н. 01егег, ЛХаГЬ. Сотр. 29 (1975), 827-833). Несколько других авторов указывают, что спектральный критерий можно было бы объяснять в намного более конкретных терминах, н предлагают изучить решетки и решетчатые структуры соответствующих линейных конгруэнтных последовательностей, что сделает фундаментальные ограничения случайности графически нш лядными, [См. работы Марсалья, Вуда, Ковзю, Беера, Руфа и Вильямсон, Марсалья и Веера: О. Магааб)(а, Ргос, Хм.
Асад. Бс). 61 (1968), 25-28; Ч~. %'. аоод, Х Сйеш. РЬуа. 48 (1968), 427; В. К. Сотеуои, Янаев 1п Аррйед Май, 3 (РМ)аде1рййа: ЯАМ, 1969), 70 — 111; %. А. Веуег, В. В. Воо(, апд О. Ч"11!1ашзоп, Масй. Сотр. 25 (1971), 345-360; 6, Магва811а апд 11!. А. Веуег. АррНсаг!опв о/!г)птйег Тйеогу во Нппгег!са! Апа!уяв, ес()тес) Ьу Б.
К. ЕагепгЬа (Кеге Уог1с Асаг(епг)с Ргевв, 1972), 249-28о, 361-370.) Р. Дж. Стоунхам (11. С. Бгоггейат). используя оценки зкспоненцивльных сумм, показал, что рг !ггч или более элементов последовательности па Хо тос1 р имеют асимптотически малый разброс, когда а — примитивный корень по модулю простого числа р [Асса АгНЛпгеНса 22 (1973), 371-389]. У Гаральда Нидеррейтера это обьяснение растннулось на несколько статей (см.
работы НагаЫ %ее(егге1сег, Млгй. Сотр. 28 (1974), 1117-1132; 30 (1976), 571-597; Аг!гзпсев гп Магй. 26 (1977), 99-181; Вп!!. Апгег, Лгавй. Бос. 84 (1978), 957-1041. См. также его книгу Н. К!едессе(гег, Еапдот МптЪег Сггпеглг!оп алг! б!пав(-й!опве Свг!о М!егйог(в (РЫ!вс(е1рЫа: 8!АМ, 1992)). УПРАЖНЕНИЯ 1. [М!О) Что произойдет со спектральным критерием. если размерность уменьшить до единицы? (другими словами, что произойдет при г = 1?) 2. [НМ20) Пусть 1'и ..., И вЂ” линейно независимые векторы в 1-мерном пространстве, пусть бо — решетка из точек, определенных в (10), и пусть Ь и ..., (й определены в (19].
Докажите, что максимальное расстояние между (! — 1)-мерными гиперплоскостями семейства парзллельных гиперплоскостей, покрывающих бо, равно 1/ш1л(/(хм, х~)п (х,..., х,) гг (О,..., О) ), где / определено в (17). 3. [М24[ Определите ег и щ для всех линейных конгрузнтных генераторов с потенциалом 2 и периодом длиной пь ° 4. [Мбу[ Пусть и1м и1г, игг, игг — элементы матрицы размера 2 х 2, состоящей из целых чисел и такой, чго и11 + пиш ш иш + аиш ш О (по модулю гл) и и11игг — им им = еь а) Докажите, что все целые решения (ум уг) уравнения у~ +аут ш О (по модулю ег) имеют вид (ум уз) = (хги1~+хгигмх1и1г+хгигг) для иелых хм хг.
Ь) Если вдобавок 2[ипиш + и1гигг[ < и(1+ и,г < и„+ игг, докажите, что (умуг) = (игми~г) минимизирует у, + уг по всем соответствующим ненулевым решениям этого уравнения. б. [Муд) докажите, что двумерный спектральный критерий на шагах Б1-БЗ алгоритма Б выполняется правильно. [Указание. См. упр. 4; дохазательстно того, что (й' + Ь)г + (р' + р)г > Ьг + р", начните с шага Б2,) То, что указанное неравенство, несомненно, впервые выполняется на шаге Б2, является неожиданным. Целое числов', минимизирующее (!/-Рй)~+(р'-др)~, согласно (24) равно Р' = округление((й'Ь + р'р)/(Ь' + рг)).
Если (Ь' — Р'Ь)г + (р' — д'р)г < Ьг + рг, получим Р' ф О, Р';В -1. Следовательно, (р' — Р'р) > рг; отсюда (Ь' — Р'Ь) < Ьг, т. е. [Ь' — д'М < й либо Р' равно Р или д+ 1. Получим Ьи+ ре > й(Ь' — д'Ь) + р(р' — о'р) > --,' (Ьг + рг), Егли иг + ег < г, то на следующей итерации шага Б2 будет сохранено предположение указания. Если из+ ег > в > (и — Ь)г+(е-р)г, получим 2[й(и — Ь)+р(е-р)[ = 2(Ь(Л-и)+р(р-е)) = (и — й) + (е — р)г + Ьг 4рг — (из+ ег) < (и — Ь) + (е — р) < йг + рг. Следовательно, согласно упр. 4 (и — й) + (е — р)г является минимальным.
Наконец, если и иг + ег, и (и — й)г + (е — р) будут > г, псаожим й = й' — Р'Ь, г/ = р' — д'р; тогда согласно упр. 4 2[йи'+рг'[ < Ьг+рг < и' + е' и Ьг+р минимальны. [Общие правила нахождения кратчайших 2-Еьвекторов относительно других метрик обсуждают Кзйб и Шнорр в работе КшЬ авг( Бсйпогг. г'. А!Бопгйшв 21 (1996), ббб — 578.! б, [МУО[ Пусть ае, ам ..., а~ 1 — частичные отношения а/ш, определенные в разделе 3.3.3, и пусть А = п1вхе«, а,.
Докажите, что,иг > 2я/(Л + 1+ 1/А). 7. [НМ22) Докажите, что вопросы (а) и (Ь), поставленные после (23), имеют такое же решение для действительных чисел йм ..., аз-и о;,, ..., аг (см. (24) и (28)). 8. [М13] В строке 10 табл. 1 значение дт очень малб, однако дз совершенно удовлетво. рвтельно. Чему равно наибольшее возможное значение дз, когда дз = 10 е и гп = 10'еу 9. [НМ89] (Ч. Эрмнт (С. Нсгппсе), 184б.) Пусть /(хм,я~) — положительно определенная квадратичная форма, определенная матрицей (7, как в (17), и пусть Π— минимальное значение / в не равной нулю целой точке. докажите, что О < (1)0 МГт [йег ц~~'. [Указанпе. Если И' — любая целочисленная матрица с определителем, равным 1, матрица И'(/ определена формой, эквивалентной /. Если же Я вЂ” любая ортогональная матрица (т. е.
если Я ' = Й), матрица (/Я определена формой, равной /. Покажите, что существует эквивалентная форма 9, минимум которой О достигается в (1,0,...,О). Затем докажите общий результат инлукцией по А записывая 9(зм.,.,яв) ж О(х) +/)зяз + + Дяс) + Й(зы, х~), где Ь вЂ” положительно определенная квадратичная форма 1 — 1 переменной.] 10. [М28~ Пусть щ пуз — взаимно простые числа, такие, что у~+вузщб(по модулю пг) и 9( + уз < ~/4/3гп, Покажите, что существуют целые числа о~ и пз, такие, что к~ +акт щ0 (по модулю ш), кгуз — изщ = гп, 2[пью + пзуз[ < щ1п(о(+из,уг+уз) и (к] + п1)(9, + уз) > щ . (Следователько, согласно упр. 4 кз = пип(и~+из, 9[+От).) ь 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
