AOP_Tom2 (1021737), страница 111
Текст из файла (страница 111)
1). Однако вероятность того, что вещественные числа являются рациональными, .равна нулю (почти все числа являются иррациональными), так что эти результаты непосредственно к алгоритму Евклида неприменимы. Прежде чем применять теорему %' для решения задачи, необходимо преодолеть некоторые технические затруднения. Рассмотрим следующий результат, основанный на элементарной теории меры. Лемма М. Пусть Ее, Ез,..., Ем вм...
— попарно непересекающиеся подынтервалы, содержащиеся в интервале [О .. 1), н пусть Х= ДЕь ь>е К = [0..1) ~(ХО.Т). Предположим, что К имеет меру нуль. Пусть Р„означает множество (О/и, 1/и, ..., (и — 1)/и), Тогда (45) Здесь р(Х) — мера Лебега множества Х, т. е. Я.>, 1епкеЬ(Еь), а ~ХГ1 Р„~ обозначает число элементов множества Х П Р„. Доказательство.
Пусть Хн = () <в<и Ее и Тм = () <в<и Ее. Для заданного е > 0 найдем Х, достаточно большое, чтобы выполнялось соотношение р(Хн) + р(Тн) > 1 — е, и положим ид(Е) — 1 < [Е 11 Р„[ < ир(Е) + 1. Пусть теперь г„= [Хн гз Р„[, в„= [,Тм О Р„[, 1„= [Кн еэ Ря[; тогда гп+ве+Е» = и' ир(?и) — Ю < г„< гер(Хн) + Х; ип(Яд) — Ю < в < ип(Тн) + Ж. Значит, б" 1в' г„г„+ С„ д(Х) — — — < р(Хн)- — « —" " и и и и ве М Х =1- — '" <1-д(.ун)+ — «р(Х)+ — +' и и и Это неравенство справедливо для всех и и для любого е; следовательно, 1пп г„/и = р(Х).
в — >се В упр. 25 показано, что лемма М нетривиальна в том отношении, что для справедливости формулы (45) необходимо принимать квкие-то довольно ограничивающиее предположения. К,,=КОДЕ, О[)Е. е>Ф в>у Ясно, что если Š— любой из интервалов (а ..6), [а.,'6), (а..Ь) и [а ..6], то р(Е) = 6 †Распределение частичных отношений. Объединив теорему дд' и лемму М, докажем теперь несколько фундаментальных свойств, касающихся алгоритма Евклида.
Теорема Е. Пусть и и й — положительные целые числа; пусть также р»(а,п) вероятность того, что (й + 1)-е частное А»е» в алгоритме Евклида равно а, когда с = и и и выбирается случайно. Тогда 1пп р»(а,п) = г»(-) — Г»( — ), 1 1 где Г»(х) — функция распределения (22). Доказательство. Множество Т всех Х в [0..1), для которых А»~.1 = а, есть объединение непересекающихся интервалов, как и множество,7 всех Х, для которых А»+» ~ а. Поэтому применима лемма М, причем множество а. — множество всех Л, для которых А»е» не определено. Далее, Е»(1/а) — Г»(1/(а + 1)) есть вероятность того, что 1/(а + 1) < Х» < 1/а, а это не что иное, как д(Х), т.
е. вероятность того, что А»+~ = а. Из теорем Е и»д' следует, что частное, равное а, встречается с вероятностью !8(1+1/а) — 18(1+ 1/(а+ 1)) = 18((а+ 1) /((а+1) — 1)). Так, частное. 1 встречается примерно в 18(4) = 41.504% случаев; частное 2 встречается примерно в )8(д) = 16.993% случаев; частное 3 встречается примерно в 18(Я) = 9.311% случаев; частное 4 встречается примерно в 18(д») = 5.889% случаев. В действительности, если алгоритм Евклида формирует частные Ам Ад, ..., Ам приведенное доказательство гарантирует такое поведение только для тех А», 1» которых мал по сравнению с». На значения Ад и А, д, ...
это доказательство не распространяется. Однако можно показать экспериментально, что распределение последнего ряда А, м Ад д,... частных, по существу, такое же, как и первого ряда. Рассмотрим, например, разложение в правильную цепную дробь ряд правильных дробей со знаменателем, равным 29. гв //29// дд //3 1 1 1 2// д //1 1 14// гв // 1,3 7// д = //14,2// д =//3,4,2// Я = //1,1,4,3// Я =//1,3,1,5// зд //9 1 2// 1д //2 1 9// ы //1 1 2 2 2// »4 //1 4 1 4// ф = //7,4// — = //2, 1, 1, 1,3// Ц = //1, 1, 1, 1,1,3// ~ге — — //1,6,4// —,', = //5,1,4// —,", = //2,2,2,2// Я = //1,1, 1,9// —,", = //1,8,1,2// дд = //4~ 1~5// дд = //214~3// Б = //1,2,4,2// .щ — // 1, 13~2// дд / 4 7// дд // 2~ 14// дд // 1 2 1 1 1 2// дд // 1 28// В этой таблице следует обратить внимание на несколько моментов.
а) Как указывалось ранее, последнее частное всегда равно 2 или более. Далее, имеем очевидное тождество //хм..., х„м х„+ 1// = //хм.,хь-» хь 1//, (46) показывающее, каким образом связаны цепные дроби, в которых последнее частное равно единице, с правильными цепными дробями. Ь) Имеется простая связь значений, расположенных в правых столбцах, со зна- чениями, расположенными в левых столбцах.
Видит ли читатель эту связь7 Она заключается вот в чем: 1 — //хмхг,...,х„// = //1,х1 — 1, хг, ..., х„//; (47) см. упр. 9. с) Мелинду левыми н правыми числами в первых двух столбцах наблюдается симметрия: если встречается //Ам Аг,..., Аг//, то встречается также //Ам..., Аг, Аг//. Так происходит всегда (см.
упр. 26). д) Если исследовать все частные в таблице, то обнаружится, что всего их имеется 96 и нз них $ = 40.6% равны 1, гг = 21.9% равны 2, ггг = 8.3% равны 3. Эти данные хорошо согласуются с приведенными выше значениями вероятностей. х1нсно шагов деления. Вернемся теперь к исходной проблеме и исследуем вели- чину ҄— среднее число шагов деления при и = и (см. формулу (19)). Приведем отдельные значения Т„.
102 103 104 105 4.6 5.3 4.7 4.6 9999 10000 10001 8.6 8.3 9.1 99999 100000 100001 10.7 10.3 11.0 95 96 97 98 99 100 101 5.0 4.4 5.3 4.8 4.7 4.6 5.3 996 997 998 999 1000 1001 6.5 7.3 7.0 6.8 6.4 6.7 49998 49999 50000 50001 9.8 10.6 9.7 10.0 и и = Т„= и= Т„= т„= — ~ Т(гп, и). 1 ю(п) (48) 7».3.» Отсюда следует, что (49) Обратите внимание на некоторую неустойчивость поведения.
Если п простое, то соответствующее ему значение Т„ больше соседних значений. И это значение соответственно меньше соседних, если и содержит много делителей. (В приведенном списке числа 97, 101, 103, 997 и 49999 †прост числа; 10001 = 73 137; 49998 = 2 3 . 13 . 641; 50001 = 3 7.2381; 99999 = 3 3 41 271 и 100001 = 11 9091.) Нетрудно понять причину такого поведения. Если йсб(и,и) = 6, то алгоритм Евклида выполняет операции с числами и и и так же, как и с числами и/г1 н и/г1. Поэтому, когда число и = и имеет несколько делителей, существует много способов выбора такого и, для которого п ведет себя так, как будто его значение меньше значения, которое есть на самом деле, Соответственно рассмотрим другую величину, т„, которая является средним числам шагов делении, для случая, когда и = и и и есть число, взаимно простое с н.
Тогда Ниже приводится таблица значений т„для тех же значений и, которые были рас- смотрены выше. и = ть тя = Очевидно, что т„ведет себя значительно лучше, чем Т„, и оно должно значительно легче поддаваться анализу. При внимательном изучении таблицы значений т„ прн малых и обнаруживается ряд серьезных отклонений, например тьв —— тпм и твв = тню Но по мере роста числа и значения т„становятся вполне нормальными, как зто видно в приведенной выше таблице., и не указывают ни на какую особую зависимость от свойств рвзложимости на простые множители числа и. Если построить график значений т„как функций )пп по приведенным выше данным, то окажется, что эти значения расположены очень близко к прямой линии: (50) т„0.
843 1п и + 1. 47. Это свойство будет учтено чуть позже, при исследовании процесса формирования правильной цепной дроби. Учитывая выражение (15), для алгоритма Евклида получаем 1о г1 1) — ~ Па (7! Ь~ т По поскольку (7~+~ = Ъы Далее, если П = 17в и 1т = Ъв взаимно просты и если имеется 1 шагов деления, то Х.Х,...Х,, = 1Уи. (51) 1и Хс + 1и Л~ + .
+ )и Х~ ~ = — 1п М. Так как известно распределение величин Хо, Х~„Хю ..., это уравнение можно использовать для оценки величины с=тр; ) =т(, у) — 1. Возвращаясь к формулам, приведенным перед теоремой %, находим, что среднее значение величпны!и Л'„в случае, когда Лв — вещественное число, равномерно распределенное в интервале [0..1), равно 1 г~ )и х Р„"(х) Их = / 1п х ~„(х) Их/(1+ х), о о (52) где У„(х) определено в уравнении (33). Отсюда, рассуждая так же, как и ранее (см.
упр. 23), получаем ~„(х) = — + О(2 "). 1 1п 2 (53) 95 96 97 98 99 100 101 5.4 5.3 5.3 5.6 5.2 5.2 5.4 996 997 998 999 1000 1001 7.2 7.3 7.3 7.3 7.3 7.4 49998 49999 50000 50001 10.59 10.58 10.57 10.59 Полагая (7 = % и Ъ' = гп < Ю, найдем, что 102 103 104 105 5.3 5.4 5.3 5.6 9999 10000 10001 9.21 9.21 9.22 99999 100000 100001 11.170 11.172 11.172 Следовательно, среднее значение величины !и Х„очень хорошо аппроксимируется величиной 1 / !пх 1 /~ ие" г!х = — — пи !п2,/о 1+х !п2,/о 1+е " 1 Гс" = — — ~ (-1) + / ие "Ни !п2 ь>1 1 / 1 1 1 1 = — (1- -+-- — + — — ) !п2(, 4 9 16 25 1 1 1 1 1 1 (1+ + + — г( + + + )) 2!п2( 4 9 ) 1 1 1 = -яэ/(12!п2). Поэтому в силу (51) следует ожидать, что приближенная формула будет иметь вид — 1~~/(12! 2) - — ! Л!, 12!п2 гь я~ э !пи+ 1.47 лэ (54) описывает истинное поведение т„ при и -> аа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
