AOP_Tom2 (1021737), страница 174
Текст из файла (страница 174)
]Подготовка к следующей итерации.] Присвоить с +- г, е е — — е; присвоить г +- й — аь, И 1- И, И +- г, присвоить г +- ар+ р', р' е — р, р е- г. Если И > О, возвратиться к шагу П2. 3 По окончании работы этого алгоритма р будет равно истинному значению Ие величины И, так что требуемый ответ — А + В/р. Окончательное значение р' будет равно И', если «< О, иначе р' будет равна Ие — И'. Хороша было бы, чтобы В благодаря подходящей корректировке А не выходило из области 0 < В < Ие.
Поэтому используются только операции с обычной точностью (с двойной точностью выполняются умножение и деление), если Ие — — число, заданное с обычной точностью. 18. Можно моментально увидеть, что формула Б(И; И: с, Ц = ~„„ь((1/lс] — ((/ — «)/И]) (((ИЗ + с)/И) ) определена для всех «> 0 не только тогда, когда й > «.
Записав (//И] — ((1 — «)/И] = 1 + И«1з)) — ((е)) + ~б,е — «д(»=„— ') и выполнив суммирование, получим где со = с шос) с(. Общая сумма будет составлять около 6, когда с( мзлб и когда все дроби и/тп, (а шос) т)/гп, (аЬ шов) т)/т, 6/т, (а' — 1)/т, (а'(а' — 1) шос(т)/т, ((ас1) шос1 т)/т имеют малые частичные отношения. (Заметим, что а — 1 = — 6 + 6 —, как в 2 упр. 3.2.1.3-7.
) 21. Сначала заметим, что основной интеграл точно разлагается следующим образом: Гв вс пт и — В в„= /1 х(их+В) с1х = —, ~ — — — + — ), если х а 13 2 2)' и Г' 1 В а — 1 В в = / х(ах+В) Их = во+ос+ + з„г+ / (ах+В) Их = — — — + — + —. о -Ввв За 2а 4а 2и Поэтому С = (з — ( †') )/(зс — (-') ) = (1 — 6В 4- 6Во)/о. 22. Неравенство в(х) < х выполняется на непересекающихся интервалах [ — '„в .. ~ в), [о в .. о в), ..., ['— ,в .. 1), имеющих общую длину, равную 23. Справедливо з(з(х)) < з(х) < х, когда х находится в [ь в ..
з в) и ах +  — 6 принадлежат интервалам [с: — .. ~: — ) для О < 1 < 6 < а или когда х принадлежит ['— .. 1) 1 в,т-в и ах+В-а принадлежит либо [с: — .. в' —;) для О < / < (аВ), либо [ '„..В). Требуемая вероятность ранна о<в<в< о<с<1 в1 6 ба 2а ао 1 2(а — 1) т. е, -'+(1 — ЗВ+ ЗВо)/ба+ 0(1/а~) для больших а. Заметим, что 1 — ЗВ+ЗВо > -', поэтому В не может быть выбрано так, чтобы сделать данную вероятность близкой к требуемой. 24. Поступите, как в предыдущем упражнении; сумма длин интервалов равна Е 1 /и+С вЂ” 2т а' '(и — 1) а' '(а — 1) 1 о<и«" и,< Чтобы подсчитать среднюю длину, положим рь равным вероятности того, что длина серии > 6.
Тогда среднее равно Эта величина для истияной случайной последовательности равна е — 1, а наше значение равно е — 1 + (е/2 — 1)/а+ О(1/а ). [Замечакие. Тот же результат справедлив для возрасзвющих серий, так как неравенство с/ > Ц,ес выполняется тогда и только тогда, когда 1 — (/„< 1 — б'„+ь Это приводит к предположению, что серии в линейной конгруэитпой последовательности могут быть немного длиннее, чем нужно, поэтому к таким генераторам следует применять критерий моиотоипости.) 23.
х должен прииадлежать интервалу [(6+ а' — В)/а .. (6+;9' — В)/а) для некоторых 6 и также интервалу [и .. В), Пусть Ьо = [оп+  — Д'), йс ж [аД+  — /1~). С учетом граничных условий получим вероятность (Ьс — Ио)(В' — и )/а + шах(0,)3 — (Ьс + и' — В)/а) — гпах(О,п — (Ьо + и' — В)/а). Рис. А-1. Области перестановок для генератора Фнбоначчи. Рис. А-2. Области длин г для генератора Фибоначчи Это равно (43 — а)(!3' — 43') + 4, где )4! < 2(/1' — о!)/а. 25.
См. рис. А — 1. Нераве1штва Н1 < (!3 < 1га и На < (/3 < (11 невозможны; каждое из остальных четырех имеет вероятность 4. 1 27. ~У„= (Г 15!р+ Г„(11). Необходимо, чтобы выполнялись оба следующих неравенства: ГВ 1(/В 4- ГВН1 < 1 и ГВПВ + ГВ+1(11 > 1. Половина единичного квадрата, в которой Ц1 > 5!1, отброшена, как показано на рис. А-2, с различными отмеченными значениями Л. Вероятность для серии длиной Л равна, егли Л = 1, и равна 1/ГВ ! Г341 — 1/ГВ Г34.2, если Л > 1.
Соответствующие вероятности для !лучайной последовательности равны 2Л/(5+ 1)! — 2(Л+ 1)/(Й + 2)!. В приведенной ниже таблице сравниваются пять первых величии. 1 2 3 4 5 1 ! 1 1 2 3 1а 24 3 И 1а 3 12 60 360 1 63 23 2320 Вероятности для последовательности Фибоначчи: Вероятности для случайной последовательности; РАЗДЕЛ 3.3.4 1. Ддя ГЕНЕратОрса С МаКСИМаЛЬНЫМ ПсрИОдОМ 1-П тОЧНОСтв и1 ВСЕГда раВНа П3 И р1 ж 2.
2. Пусть У вЂ” матрица со столбцами, равными У1,..., 1'1. Минимизация У Упри условии, что У ф (О,...,О) и УУ вЂ” вектор-столбец Х, состоящий из целых чисел, равносильна минимизации (\' 'Х) (У 'Х) при условии, что Х вЂ” это вектор-столбец, состоящий иэ целых чисел, не равных нулю. Столбцами У ' являются Н1, ..., К. 3. а ш 2а — 1 и а ги За — 2 (по модулю т). Рассматривая все короткие решения (15), найдем, что ма~ — — 6 и и4~ = 4 для соответствующих векторов (1, -2, 1) и (1, — 1, — 1, 1), за 29, На рис.
А — 3 показаны различные области для общего случая. Область 213 означает, что 1!2 < 531 < 513, ЕСЛИ С!1 И С!а вЫбраны наудачу; область 321 означает, что (/3 < (/2 < 51„ и т. д. Вероятности для 123 и 321 равны -' — и/2 + па/2; вероятности двя всех остальных случаен равны -'+ и/4 — и'/4.
Чтобы все вероятности были равны -', должно выполняться равенство 1 — бп + ба~ = О. (Утверждение этого упражнения установлено в теореме Дж. Н. Франклина (2. Н. ггвпЫш), (см. работу 1. "3. Ггап(4!ш, МайЛ. Сошр. 17 (1953), 28-59, теорема 13); другие результаты статьи Франклина имеют отношение к упр. 22 и 23.) 1 а у=я ! 2 2 1 а у= -хЧ-1 —— 2 2 а у=х-— 2 1 1 а У= 2 2 2 (0, Ц (О, 1 — а) 1 а у =хв 2 2 1 а у=-х-- 2 2 (01 а) (оо) /1 а ) (10) (,2 2 (- ) Рис.
А — 3. Область перестановок для генератора с потенциалом 2, ц = (а — 1)с/т. исключением следующих: т = 2'0, 0 — нечетное, е > 3, а = 2' ' (по модулю 2'), а ш 1 (по модулвз 0) из = "'г = 2' т=З"0, ЗЛ.0, е>2, аш1шЗ' л(помодулюЗ"), а=1(помодулюу), иг — — 2; т=9, а=4или7, из=из=3.
з 4. (а) Единственным выбором для (хмхз) янляетсн -(улизз — Угиы, — Улиш + узиы), и зто равно ш — '(улигз+узаию, -улиш-угаиш) и (О О) (по модулю 1), т е. хз и хз являются целыми числами. (Ь) Когда (хм хз) зе (О О), получим (хзим +язвы) +(хлиш+ хгизз) хг(игг + илз) + гз(иг, -ь игг) ч- 2хзхз(иллигз + и1зизг), а согласно предположению з з з з г г это > (х~ + хз — )хлхз!)(иззл + излз) > иггг + игг. (Заметим, что полученный результат сильнее леммы А, которая утверждает только, что хзг < (из„+ изз)(из~з + иззз)/тз и хгз < (изм + и1з) /тг, где последний может быть > 1. Идея, по существу, является Гауссовским методом приведения двоичной квадратичной формы (см.
Шзци!зй(опез Аг!с)зшее!сш (1 е!рх!3, 1801), 0171).) $. Условия (30) остаются неиэменнылли; следовательно, /л не может быть нулем на шаге 32, когда а и т — взаимно простые числа. Так как /з всегда уменьшается на етом шаге, 32 в конце концов завершится с из + иг > з. Заметим, что рр' < 0 на протяжении всего вычисления. 6. Если иг + ег > э > (и — Л) + (е — р) в предыдущем ответе, пачучим (е — р) > ег. Следовательно, (о — Л) < иг, если 9 = о„то, поскольку Л' = о,Л+и, мы должны получить о ес = 1. Из замечания к упр. 3.3.3-1б следует, что иг = шспедгсс(тг -Ь р„,).
г г г Получим те=тзр,+псгссрг с=агтгрг с+а,рз г+тгесрг с<(о;+1+1/иг)пггрг с< (А+ 1+ 1/А)псгР, с, а спг+Рг, > 2гп,Р, с, откУда и следУет ответ. 7. Докажем, используя условие (19), что юг 11с = 0 для всех Л ~ У тогда и только тогда, когда У) Уь = 0 для всех Л ф /ь Предположим, что Осг 11ь = О для всех Л ф у, и пусть ссг = асУс + . + асИ Тогда Ц (ъ = ас лля всех Л. Следовательно, с/г = а,Уг н У 'г» = а '((гг.1'с,) = 0 для всех Л ~ 1. Аналогично доказывается обратное утверждение. 8. Ясно, что ссс+с < ссс (факт безоговорочно использован в алгоритме 3, так как э не изменяется при возрастании 1).
Для С = 2 это эквивалентно (псрг/х)ссс > (1спрг/л)'с~, т. е. Рг < 4 1/т/яд~с~. Зта гРаница доведена до с 10 ~/с/х длЯ заданных паРаметРов, но для больших сл и фиксированного рг граница (40) лучше. 9. Пусть /(дс,..., ус) = д; Осс((дс,..., ус) = 1 (Осс) — наибольший обсций делитель) и И'— целочисленная матрица с определителем, равным 1, первая строка которой — (дс,, р,). (Последнее доказать по индукции по наименьшей ненулевой величине, занесенной в строку.) Если Х = (хс,..., хс) — вектор-строка, получим ХИс = Х' тогда и только тогда, когда Х = Х'Ис ', а если Иг ' — целочисленная матрица с определителем, равным 1, форма д, определенная ИЧ/, удовлетворяет д(х„...,хс) = /(х'„...,х',), Кроме того, д(1,0с...,о) = д.
Без уменьшения общности предположим, что / = д. Если 5 — любая ортогональная МатрИца, МатрИца СГ5 ОирЕдЕЛяЕт ту жЕ фпрМу, Чтп И Бс, ПОЭтОМу (Х(го)(ХСгз) (Х(/)(Х(г)г. Выберем 5 так, чтобы ее первый столбец был кратным (1~с, а все другие столбцы — любые подходящие векторы. Тогда получим ас О ... 0 аг сс'5 = Пс ас для некоторых ас, аг,, ас и некоторой матрицы и' размера (1 — 1) х (с — 1). Следовательно, /(хс,,хс) = (асяс + + асхс) + Л(хг,...,хс). Из этого следует, что ас = т/д (фактически аг = ((/с (/г)/т/д для 1 < / < «) и что Л вЂ” положительно определенная квадратичная форма, порожденная П, где с1ес сг = (с(ес(сс)/з/д. Индукцией по 1 можно показать, что существуют целые числа (хг,..., хс), для которых выполняется Л(хг хс) < (с)С вЂ” г)Сг)д (У)гцс — И/Всц -1) и для этих целых чисел хс можно выбрать таким образом, что ~к с+(агкг+ +асяс)/ас ~ < р 1 а это эквивалентно (асяс + + асяс) < -'д.
Значит, д < /( ) < сд (с)С~-~)С~)б 1(/)гдс-с)/дсдс-с> и желаемое неравенство пачучается немедленно. [Замечание. Для 1 = 2 это наилучший из возможных результатов. В общем случае из теоремы Зрмита следует, что дс < х'с~(4/3)ц' Пс~/(1/2)!. Из фундаментальной теоремы Минковского (" Каждое 1-мерное выпуклое множество, симметричное относительно начала координат с объемам > 2', содержит не равную нулю точку с целыми координатами") следует, что рс < 2'. Это более точное неравенство, чем то, которое следует из теоремы Эрмита для с > 9. Известен еще более точный результат (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
