AOP_Tom2 (1021737), страница 27
Текст из файла (страница 27)
[Мбб[ Пусть У;, 1» — векторы, координаты которых являются действительными числами с 11; Ъ' = бо длЯ 1 <», »' < й и такие, что К. К = 1, 2[К (/»[ < 1, 2[к) Р~[ < Р) для» ~ 1, Насколько большим может быть 12 г'~? (Этот вопрос имеет отношение к граням на шаге 87, если и (23), н преобразование из упр. 18, (Ь) не производят никаких сокращений. Известно, что максимальное значение равно (1+ 2)/3. Оно достигается. когда (/и = 1», У~' = ~1ь + -'»/3 1м Ъ) = 1» — (1г + + 1с)/»/3, (г~ = 211/»/3 для 2 < у < й где (1»,..., Д) — единичная матрица. Эту схел»у предложил Б.
В. Албксеев.) ь 24. [МЯб[ Обобщите спектральный критерий для последовательностей второго порядка вида Х = (аХ ~ +ЬХ„з) шобр, имеющих длину периода рз — 1 (см, формулу 3 2 2-(8)). Как следует изменить алгоритм Я? 26. [11»1194 [ Пусть б — делитель гл и пусть О < д < б. Докажите, что сумма 2„г()г), где суммирование производится по всем О < )с < т, таким, что й шо»1 б = д, меньше либо равна (2/бк) 1п(ш/б) + 0(1). (Здесь г(/») определено формулой (46) при 1 = 1.) 26. [М22) Объясните, почему, если использовать метод доказательства (53), можно получить грани, подобные полученным, для »Т-1 х»» е«в<я при О < д < ш.
Почему доказательство (53) ничего не дает, когда т = 1? 27. [НМ99[ (Э. Хлавка (Е. ЕВак 1»а) и Г. Нидеррейтер (Н. 1»1(е»(егге!сег).) Пусть г(им...,и~) — функция, определенная в (46). Докажите, что сумма 2,г(им...,и»), где суммирование производится по всем О < и»,..., ш < т так, что (им..., и~) и (О,..., О), и выполняется равенство (15), меньше нлн равна 2((»г+ 2я18»п)' г, ), где г, — максимальный член г(и»,..., и~) этой суммы. ° 28. [МЯб[ (Г.
Нидеррейгер.) Найдите аналог теоремы 1» для случая, когда»н — простое число, с = О, а — первообраэный корень по модулю т, Хо»ь О (по модулю т). [Укаэакас. Ваши экспоненциальные суммы должны включать ~ м е~~и1~ П так же, как ы.] Докажите, что в этом случае "средний" первообразный корень имеет разброс О,„, = О [1(1ой т) /р(т — 1)), следовательно, хороший первообразиый корень существует 01 для всех т.
28. [НМЯЯ] Докажите, что величина г „„из упр. 27 никогда не будет больше 1/~/8 во 80. [МЯУ] (С. К. Заремба (8. К. ХагешЬв).) Докажите, что г,„= О(швх(ац..., а.)/т) в двумерном случае, когда ам ..., а, — это частичные отношения, полученные в результате применения алгоритма Евклида к т и а. [Указание. В обозначениях из раздела 4.5.3 справедливо равенство а/т = //ам..., а,//; примените упр. 4.5.3-42.] 31. [НМ47] (И. Бараш (1 ВогоэЬ).) Докажите, что для всех достаточно больших т существует взаимно простое с т число а, такое, что все частичные отношения а/т меньше или равны 3.
Кроме того, множество всех т, удовлетворяющих этому условию, ио с частичными отношениями < 2, имеет положительную плотность. ь 32. [М81] Пусть т~ = 2з' — 1 и тэ = 2э' — 248 — модули генератора (38). а) Покажите, что если (/„= (Х~/т~ — 1'э/тз) шоб 1, то Ь'„ш йэ/ть Ь) Пусть Иа = (Хата — тат~) шоб т и И' +~ = аИ' шод т, где а и га имеют значения, приведенные в разделе после формулы (38). Докажите, что существует простое соотношение между И' и (/ . В следуюшем издании данной книги я планирую ввести новый раздел 3.3.5 под Ф назвылгем "Ез-аягоритм'. Это будет отклонение от общей темы (аСлучайиые числа"), но в нем будет продолжено рассмотрение решетчатого базиса, описанного в разделе 3.3.4. Основным предметом изучения станет неоклассический алгоритм А, К, Леистра (А.
К. йепзсга), Н. И". Х,епзсга,,Уг., апг( /. /.огвзв, Ма1Ь.Аппа1еп 261 (1982), 518 — 534, для нахождения приближенно оптимального множества базисных векторов и демонстрации того, что алгоритм можно применять к другим исследованиям. Примеры таких исследований лриводятсл в следующих статьях и содержлшейся в них библиографгги: М. Яеувеп, СогпЬ)пвСоНса 13 (1993), 363-373; С. Р. ВсЬпогг апд Н. Н. Ногпег, Еессиге Насев ш Сотр. Ясй 921 (1995), 1-13.
3.2. ГЕНЕРИРОВАНИЕ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ЧИСЕЛ В этом РАЭДеле будут рассмотрены методы генерирования последовательности случайных дробей, т. е, случайных действительных чисел П„, равномерно распределенных между кулем и единицей (на интервале (О, 1)7'. Так как компьютер может представлять действительные числа только с определенной точностью, мы будем генерировать целое число Х„между нулем и некоторым числом т: дробь Ь„= Х„/т будет, следовательно, лежать между нулем и единицей. Обычно т выбирают равным размеру слова в компьютере. (В этой книге размером слова (юогд э1ге) автор называет число Ь', где у — основание системы счисления, используемой в компьютере, а е — число, разрядов машины.
— Прим. ред.) Поэтому Х„можно по традиции рассматривать как целое число, занимающее все компьютерное слово, с точкой, которая отделяет целую часть числа от дробной, стоящей в правом конце слова, а τ— если хотите, как содержание того же слова с разделяющей точкой, стоящей в левом конце слова, 3.2.1. Линейный конгрузнтный метод В настоящее время наиболее популярными генераторами случайных чисел являются генераторы, в которых используется следующая схема, предложенная Д.
Г. Лехмером (П. Н. Ье)|шег) в 1949 году (см. Ргос. 2пд Бушр. оп Ьагйе-Бса1е П131га1 Са!си!айпй 51ас)11пагу (СашЬг1дке, Мэлэ.: Наггагд Нпгеегюсу Ргеээ, 1951, 141 — 146)]. Выберем четыре "волшебных числа": 0<т; О<а<т; 0<с<т; 0 < Л"а < т. т, модуль; а, множитель; с, приращение; Ха, начальное значение; Затем получим желаемую последовательность случайных чисел (Л'„), полагая Х„+г — -(аХ, +с)шодт, и > О. (2) Эта последовательность называется линейной конгруэнтной последовательностью. Получение остатков по модулю т отчасти напоминает предопределенность, когда шарик попадает в ячейку крутящегося колеса рулетки.
Например, для т = 10 и Ха = а = с = 7 получим поглеловательногть (3) 7, 6, 9, О, 7, 6, 9, О, Как показывает этот пример, такая последовательность не может быть "случайной" при некоторых наборах чисел т, а, с и Ха. Принципы выбора подходящих волшебных чисел будут подробно исследованы в следующих разделах этой главы. В примере (3) иллюстрируется тот факт, что конгруэнтная последовательность всегда образует петли., т. е. обязательно существует цикл, повторяющийся бесконечное число раз. Это свойство являетсн общим длн всех последовательностей вида Л +1 = 7(Х ), где Г преобразует конечное множество само в себя (см.
упр. 3.1 — 6). Повторяющиеся циклы называются периодами; длина периода последовательности (3) равна 4. Безусловно, последовательности, которые мы будем использовать, имеют относительно длинный период. Заслуживает внимания случай, когда с = О, так как генерируемые числа будут иметь меньший период, чем при с ф О. Мы убедимся в дальнейшем, что ограничение с = О уменьшает длину периода последовательности, хотя при этом все еще возможно сделать период достаточно длинным. В оригинальном методе, предложенном Д.
Г. Лехмером, с выбиралось равным нулю, хотя он и допускал случай, когда с ~ О, как один из возможных. Тот факт, что условие с ф О может приводить к появлению более длинных периодов, был установлен В. Е. Томсоном (Ч'. Е. ТЬошэоп) (Сошр. 2. 1 р. 83, 86] и независимо от него А. Ротенбергом (А. КосепЬег8) (2АСМ 7 (1960), 75 — 77). Многие авторы называют линейную конгруэнтную последовательность при с = О мулътипликативным конгруэнтноом мешодом, а при с ~ О— смешанным конгруэнгпнмм мешодом. Буквы т, а, с и Ло будут использованы в этой главе в том смысле, в каком они вводились раньше. То же самое относится н к константе (4) Ь=а — 1, которая вводится для упрощения многих наших формул. Можно сразу отбросить случай, когда а = 1, при котором последовательность Х„представима в виде Л„= (Хо + пс) шоб т и ведет себя явно не как случайная последовательность.
Случай, когда а = О, даже хуже предыдущего. Следовательно, для практических целей предполагаем,что (5) а>2, 6>1. Сейчас можно обобщить формулу (2) Хо ог — (аьХ„+ (аг — 1)с/Ь) плоб т, Ь > О, и > О, (6) где (и + к)-й член выражается непосредственно через п-й. (Случай, когда и = О, в этом уравнении также достоин внимания.) Из (4) следует, что подпослощовательностгч содержащая каждый Ь-й член последовательности (Х„), является также линейной Конгруэнтной последовательностью, множнтель которой равен а шог( ш и о приращение равно ((а" — 1)с/6) шог( пь Важным следствием из (6) является то. что общая последовательность, определенная с помощью а, с и Ло, может быть очень просто выражена в терминах специального случая, когда с = 1 и Ло = О.
Пусть (7) 1'о = О, 1'„~, = (аУ„+ 1) шоб т. В соответствии с (6) получим 1ь = (ао — 1)/Ь (по модулю т). Значит, последова- тельность, определенная в (2), будет имеет вид Х„= (.41'о+ Хо) шоб т, где А = (ХоЬ+с) шоо(гп. (8) УПРАЖНЕНИЯ 1. (10) В примере (3) показана ситуация, когда Х4 = Хо, так что последовательность начииастся сначала. Приводите пример линейной коигруоитной последовательности ирн оп = 10, лля которой число Хо никогда снова не появится. 2.
(Мг0) Покажите, что если а и т взаимно простые, то Хо всегда покоится в периоде. 3. [М10) Объясните, почему последовательность имеет определенные недостатки н, вероятно, ие очень случайна, если а и ш — не взаимно простые числа. Поэтому следует выбирать а и т так, чтобы они были взаимно простыми.
4. (11) Докажите формулу (б). 5. (М00] Соотношение (6) справедливо прн в > О. Если это возможно, получите формулы для Х„+ь в терминах Х„для ввзуицвгвельнмх значений х. 3.2.1.1. Выбор модуля. Первая задача, которую мы рассмотрим, — нахождение хороших значений параметров, определяющих линейную конгруэнтную последовательность. Сначала выясним, как правильно выбрать число т.
Необходимо, чтобы т было довольно большим, так как период не может иметь болыпе т элементов. (Даже если мы намерены генерировать только случайные нули и единицы, не следует брать т = 2, ибо тогда последовательность в лучшем случае будет иметь вид ...,0,1,0,1,0,1,...! Методы получения случайных нулей и единиц из линейной конгруэнтной последовательности обсуждаются в разделе 3.4.) Другой фактор, который оказывает влияние на выбор т, — скорость генерирования: нужно подобрать значение т так, чтобы (аХ„+ с) шог(т вычислялось быстро.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
