AOP_Tom2 (1021737), страница 112
Текст из файла (страница 112)
Если предположить, что выполняется приближенное равенство (54), получим следуюшую формулу: Т„т ~1пп — ~ — ) +1.47, 12!п27 Л(с~)1 г1п (55) где Л(И) — функция фон Мангольдта, определяемая правилами 1пр, если и = р", где р — простое число и г ) 1; Л(п) = 0 в противном случае. (56) (См. упр. 27.) Например, 121п2 7 !п2 !п2 !п5 !п55 Т|ос- (!и 100 — — — — — — — — „) + 1.47 .э 2 4 5 25/ и (0.843)(4,605 — 0.347 — 0.173 — 0,322 — 0,064) + 1.47 4. 59; точное значение Тшв равно 4.56. т.
е. С должно приближенно равняться величине ((12 !и 2)/лт) 1пЮ. Этв константа (12 !и 2)/л~ = 0.842765913... полностью согласуется с эмпирической формулой (50), полученной ранее, так что есть веские основания полагать, что формула Можно также оценить среднее количество шагов деления в случае, когда оба числа и и с равномерно распределены в интервале между 1 и Х, вычислив (57) В предположении справедливости формулы (55) в упр. 29 показано, что эта сумма имеет вид 12!п2 !и Х+ 0(1), (58) а эмпирические расчеты, выполненные с теми же числами, которые использовались при выводе соотношения 4.5.2-(65), хорошо согласуются с формулой 12!п2 )пХ+ 0.06. (59) 12!п2 г„= — !Пп+ С+ 0(п '~в ы), я (60) где С вЂ” 1.4670780794 есть постоянная 6!п2 — 2 1 — (31п2+47 — 24л з~'(2) — 2) — —; кз 2' (61) см. О.
Е. КппгЬ, Сошри!егв апд МаСЛ, ибсЛ Арр!!с. 2 (1976), 137 — 139. Таким образом, утверждение (50) полностью доказано. Используя формулу (60), Грэхэм Х. Нортон Конечно, пока мы ничего не доказали о поведении Т„и г„в общем случае. До сих пор рассматривались только возможные обстоятельства, прн которых должны быть верны определенные формулы. К счастью, сейчас уже можно применить методику строгого доказательства, которая основана на тщательном анализе, выполненном рядом математиков. Впервые главный член (12!и 2)/лз в формулах, приведенных выше, был получен независимо Джоном Д. Диксоном (ЛоЬп В. П!хоп) и Гансом А. Хайльбронном (Наив А.
Не!!Ьгопп). Диксон [У. ХпшЬег ТЛеогу 2 (1970), 414-422) развил теорию распределений Р„(х), чтобы показать, что индивидуальные частичные отношения являютси в определенном смысле независимыми одно от другого, и доказал, что для любого положительного с выполняется соотношение [Т(т, и) — [(12 !и 2)/х~) 1и и ~ < (!и п)0~~!+', но не для значений гп и и ехр(-с(с)(!ойХ)'~з) Хз в интервале 1 < пт < и < Х, где с(с) > О.
Совсем иной подход к этой проблеме, при котором вместо непрерывных переменных рассматриваются только целые числа, предложил Хайльброни. В основу его идеи, излагаемой в несколько модифицированном виде в упр. ЗЗ и 34, положен тот факт, что величину г„можно определенным образом связать с числом способов представления и, Кроме того, в его работе ХшпЬег ТЛеогу апс! Апа!уз!з, еб!Фее Ьу Рап! Титан (Ке~ч Уогк: Р!епцш, 1969), 87 — 96, показано, что распределение индивидуальных частичных отношений 1, 2, ..., которое рассматривалось выше, в действительности применимо ко всему множеству частичных отношений, принадлежащих дробям с заданным знаменателем.
Это более точная форма теоремы Е. Через несколько лет Дж. В. Портер (3. %. Роггег) [Ма!Леша!!!га 22 (1975), 20-28) получил еще более точный результат. Он установил, что (Сгайаш Н. ?логсоп) [Х ВушЬо!!с Сошрпгас!оп 10 (1990), 53-58] продолжил вычисления упр. 29, чтобы доказать, что эмпирическая константа 0.06 в формуле (59) в действительности равна 6!п2 — (3 )и 2+ 4? — 12я ~'(2) — 3) — 1 0.0653514259.... (62) Г. Э. Коллинз (С.
Е. Со!!!пз), применив классические алгоритмы выполнения арифметических операций, показал в ЯСОМР 3 (1974), 1 — 10, что среднее время выполнения алгоритма Евклида при оперировании числами многократной точности равно (1 + )ой(шах(и, а)/йсг!(и, о)) ) [ой шш(и, о). (63) Резюме. Мы обнаружили, что наихудший случай алгоритма Евклида имеет место, когда входные числа и и о связаны с числами Фибоначчи (теорема Е), а число шагав деления при 0 < с <?Ч никогда не превышает величины [4.8!ойга !Ч вЂ” 0.32). Мы определили частоту появления различных частичных отношений, показав, к примеру, что приблизительно в 41% случаев на шаге деления получается [и/о) = 1 (теорема Е). Наконец, в теоремах Хайльбронна и Портера доказывается, что среднее число Тл шагов деления при о = и приблизительно равно ((12!п2)/яг) !пп ш 1.9405!ой,оп, если не учитывать корректирующий член, основанный на делителях числа п, как следует из уравнения (55).
ЯНАХ 5 гАХ л- гА. 11 2Р и — с<а? В1Ч Ч гХ л- гАХпюй ю 2Н ЫА Ч гА+- е. ЮХИХ 13 Выполнена, если гХ = О. $ 1.ВХ О гХ +- и. ЛИР 2Р 1Н БТХ Ч и< — гХ ВОН Ч гА +- и — а. СИРА Ч 2. [МЯ1) Вычислите произведение матриц 3. [МЯ1) Чему равен определитель О ... Π— 1 хг 1 О О -1 хг 1 -1 ' 1 О О ... -1 хл с$ег 4. [МЯО) Докажите тождество (8). УПРАЖНЕНИЯ ° 1. [Я0) Так как частное [и/а) равно единице более чем в 40% времени выполнения алгоритма 4.5.2А, на некоторых компьютерах мажет оказаться выгодным проверить агат случай и запретить выполнение операции деления, когда частное равно единице. Является лн следующая И1Х-программа, реализующая алгоритм Евклида, более эффективной, чем программа 4.5.2А? б. [ВМВО] Пусть хз, хз, — последовательность вещественных чисел и каждое из них больше некоторого положительного числа е.
Докажите, что существует бесконечная цепная дробь //хг,хм // = 11щ„-~ //хы...,х„//. Покажите также, что //хыхз,...// необязательно существует, если предположить только, что х„> О для всех 1, б. [МЯЗ] Докажите, что разложение числа в правильную цепную дробь едккстоекко в следующем смысле. Если Вы Вз,, — положительные целые числа, то бесконечная цепная дробь //Вы Вз, // есть иррациональное число Х, расположенное между О и 1, разложение которого в правильную цепную дробь имеет элементы А„= В„лля всех и > 1.
Если же Вз,, Вгр — положительные целые числа, причем В > 1, тп правильная цепная дробь для чнгза Х = //Вы ..,, В // имеет элелгенты А„= В„для 1 < к < гп. Т. [МЯО] Найдите все перестановки р(1)р(2)... р(п) целых чисел (1, 2,..., и», таких, что К (хм хе,, хр) = Кр(хжм, хжзр ..,, х 00) является тождеством для всех хы хг, ..., х„. й. [МЯО] Покажите, что есзи при разложении в правильную цепную дробь числа Х определено Х„, то — 1/Х = //А,..., Ап — Х//. 9. [МВ1] Покажите, что цепные дроби удовлетворяют следующим тождествам: а) //хы.,.,х // = //хз,.,.,ха+ //хам„...,х„////, 1 < к < и; Ь) //О,хыхз,...,х // = хз +//хз,,х„//, и > 1; с) //хь...;хе кхыО,хьеьхььз,..., х„//ы//хп..., хь-ьха + хьчпхэез,,хр//, 1< К<к; <~) 1 //х! хз ~хе// — //1,х1 1,хз,...,хп// и > 1.
10. (МЯВ] Из результата упр. б следует, что любое иррациональное число Х единственным образом разложимо в правильную цепную дробь вида Х = Ао + //Лы Аз, Аз, //, где Ао — целое число и Лз, Лз, Лз, — положительные целые числа. Покажите, что если Х имеет такое представление, то разложение числа 1/Х в правильную цепную дробь имеет вид 1/Х = Во+//Вз, ",В,Аз, Ае," // для соответствующих целых чисел Во, Вз, ..., В . (Наибопее интересен, безусловно, случай, когда Ао < 0 ) Обьясните, как лгожно выразить все В через Аа, Аы Лз, Аз н Ао 11. [МЯО] (Ж.-Л.
Серре (В.-А. Яеггег), 1850.) Пусть Х = Ае+ //АыАз,Аз,Ац // и У = Ва+//Вы Вз, Вз, В», .., // — представления в виде правильных цепных дробей двух вещественных чисел Х и У в смысле упр. 10. Покажите, что эти представления "эвентуально согласовюзы" в том смысле, что А эь = В„еь для некоторых т и к и для всех /г > О тогда и только тогда, когда для некоторых целых чисел о, г, з, 1 выполняется Х = (ОУ+ г)/(эУ+1) при ]01 — гз] = 1. (Эта теорема является аналогом представлений цепными дробями простого результата, заключающегося в том, что представления целых чисел Х и У в десятичной системе счисления в конечном счете совпадают тогда и только тогда, когда для некоторых целых чисел о, г и э выполняется равенство Х = (10Р У + г)/10*.) ь 12. [МВО] Кеобрапзкчкак иррациональностью называют число вида (т/Р— П)/1'", где Р, (1 и У вЂ” целые числа, удовлетворяющие условиям Р > О, У ЗЬ О, и Р не есть полный квадрат.
Без потери общности можно предположить, что У является делителем числа Р— 1Г~, в противном случае это число можно переписать в виде (~/РУз — (1]У[)/()г[1г]) а) Докажите, что разложение в правильную цепную дробь (в смысле упр. 10) квадратичной иррациональности Х = (~/Р— (/)/У получается по следующнл~ формулам: 1'е = 1', Ао = [Х], Уо = Р+АоУ: У.„= (Р— и.')/У., А.„= [( /Р+ и„)/У„„], и. = А.+ У. - Р. Ь) Докажите, что для всех и > 1У, где Х некоторое целое число, зависящее от Х, выполняются неравенства О < П < гГР, О < У < Зо'гг. Следовательно, представление квадратичной иррациональности правильной цепной дробью в конечном счете периодично.
[Указание. Покажите, что (- И вЂ” 57)/У = Ае+ //Аы, А, -У /(г/сг+ П )//, и, используя равенство (5), докажите, что при больших значениях и величина (з/З+ Ь'„)/~4 положительна.] с) Положилг р„= К„ь~(Ае,Аг,...,А„) и д„= К„(Ам.,.,А„). Докажите тождество г 2П +((Пг П)/р) г ( ц чг1; 6) Докажите, что представление иррационального числа Х правильной цепной дробью в конечном счете периодично тогда и только тогда, когда число Х есть квадратичнан иррациональность (Это утверждение относительно цепной дроби является аналогом утверждения о толг, что разложение вещественного числа Х в десятичную дробь в конечном счете периодично тогда и только тогда, когда Л рационально.) 13. ]М40] (Ж. Лагранж, 1767.) Пусть /(х) = а х" + - - + ао; а ) Π— полипом с целочисленными коэффициентами, у которого нет рациональных корней и имеется точно один вещественный корень 5 ) 1.
Разработайте компьютерную программу для нахождение примерно первой тысячи частичных отношений числа 5 с помощью следующего алгоритма (который включает в себн только сложение). Е1. Присвоить А+- 1. Й2. Для 6 = О, 1, ..., и — 1 (в, таком порядке) и У = и — 1, ..., 6 (в таком порядке) присвоить аг с — агьг + а,. (На этом шаго функция /(х) заменяется функцией д(х) = /(х+ 1), полиномом, корни которого на единицу меньше корней полинома /.) ЕЗ. Если а + а„г + + ае < О, то присвоить А е- А+ 1 и возвратиться к шагу Ь2.
Е4. Вынести А (которое является значением слел54ощего частичного отношения). Заменить коэффициенты (а„,а п,аа) на ( — ае, -ап, -а„) и возвратиться к шагу Ы. (На этом шаге выполняется залгена /(х) полиномом, корни которого обратны корням полинома /.) Например, начав с /(х) = хз — 2, алгоритм выведет сначала "1" (заменив /(х) на х — Зх — Зх — 1), затем — "3" (заменив /(х) на 16х — бх — бх — 1) и т. д. г г г 14. ]МОЯ] (А. Гурвиц (А. Нвгпйз), 1691.) Покажите, что при помощи следующих правил можно найти разложение в цепную дробь числа 2Х, если известны частичные отношения числа Х: 2//2а,Ь,с,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
