AOP_Tom2 (1021737), страница 198
Текст из файла (страница 198)
Основной шаг может повторяться бесконечно. Однако, если в некоторый момент окажется, что введено последнее число хг, юпоритм немедленно переключится на вывод цепной дроби для (Ах! + В)/(Сх + Р). используя алгоритм Евклида, и остановит работу. Решение требуемого примера приводится в следующей таблице, в которой матрица (и с) начинается с верхнего левого угла. Затем происходит сдвиг на единицу вправо в л для ввода и на единицу вниз для вывода.
М. Мендес Франс (М. Мепбев ггапсе) показал, что количество выводимых частных на одно вволимое частное асимптотически ограничено значениями 1/г и г, где г = 2[Ц[аЫ вЂ” Ьс[)/2)+1 и Ь вЂ” функция, определенная в упр. 38; зта граница — наилучшая из возможных. [Тор(сз ш Хитбег ТЬеогу, еб!сей Ьу Р. Тпгап, Со!!опша Ма!Ь. Яос.,Уапое Во!уа! 13 (1975), 183 — 194.] Госпер (Соврет) показал также, что вышеприведенный алгоритм вычисления цепных дробей для х и у может быть обобщен на случай вычисления цепных дробей для (аху + Вх + Су + И)/(Аху + Вх ч- Су + Р) (в частности, для вычисления цепных дробей для сумм и произведений) [М1Т А1 ЬаЬогагогу Мешо 239 (геЬгпвгу, 29, 1972), НасЬ 10Ц.
16. по индукции нетрудно доказатгь что / (з) = а/(2п -~- 1) ч- 0(гз) — нечетная функция, представимая в некоторой окрестности начала координат в виде сходящегося степенного ряда, н что она удовлетворяет указанному дифференциальному уравнению. Поэтому /е(а) = //а +/з(з)// = = //з ',Зз ',,(2п+1)з '+/ .,~(з)//. Остается доказать, что!ип„~ //г ~, Зз ~,...,(2п+ 1)з '// = /о(г). [Фактически Эйлер в возрасте 24 лет получил разложении в цепные дроби для гораздо более общих диффе- ренциальных уравнений вида /„(») = а» + Ь/„(»)»'" + с/ (»)с, но он не потрудился доказать сходимость, поскольку в 18 веке было вполне достаточно формальных выкладок и интуиции.) Для доказательства этого предельного уравнения имеется несколько способов.
Прежде всего, полагаа /„(») = 2 с а„ь», можно доказать из УРавнениЯ с (2и+ 1)а„! + (2и+ 3)а и» + (2и+ 5)асм» + = 1 — (а !»+асс» + а„с» + ), что ( — 1) а„Сз„+,! есть сумма членов вида сс/(2н + 1)вы(2и + Ьс!)... (2и + Ьь!), где с! и Ь! — положительные целые числа, не зависящие от и. Например, имеем — а„с = 4/(2и-1-1) (2и+3)(2и+5)(2и+7)+ 1/(2и+ 1) (2и+3).
(2и+7). Поэтому (ас„!Нь) < (а„ь~ и (/„(»)! < сап)») для (»~ < я/2. такая равномерная оценка для /„(») делает доказательство сходимости очень простым. При внимательном анализе этого доказательства обнаруживается, что степенной ряд для /„(») фактически сходится при (»( < ссз/2п + 1/2; поэтому вместе с ростом и особые точки функции /„(») все больше и больше удаляются от начала координат и цепная дробь фактически представляет разложение функции сапЬ» на всей комплексной плоскости.
Другое доказательство дает дополнительную информацию иного плана. Если поло. жить 72и — )сз»" (и+ Ь)!»" А.с(») = и! Е ~ ) — = Е = и! »" 2ЕО(и + 1, — и;; — 1/»), ) Ь! = Ь.( - Ь)( ь=е ь>а то (и+ й — 1)! ((4и+ 2)Ь+ (и+ 1 — И)(и — Ь)) /с! (и + 1 — Ь)! с>е = (4и+ 2)А„(») +» А„с(»). По индукции получаем, что /1 3 2и — 1') А„(2») + Ас( — 2») г-ь!»- К ! »' ' » '- (- )- 3 2и — 11 А (2») — А (-2») 2"э!»" Следовательно // ! 3, (2 1) с// А„(2») — А,( — 2») А„(2») + А„( — 2») и требуется показать, что это отношение стремится к Сапй». В силу уравнений 1.2.9-(11) и 1.2.6- (24) имеем 'с(-)-"т' (Е( )(' ')(- )') = Е(н ")"-" Поэтому (и + /с) ' »ь с*А (-») — А„(») = Ве(») = (-1)" »сюю ~ ьйе Далее, имеем (ес' — 1)(А (2»)-!-А ( — 2»)) — (с!*+ 1)(А (2») — А ( — 2»)) = 2В (2»); отсюда (А (2») + А ( — 2»))(ез* + 1) Итак, для рассматриваемой разности получена точная формула.
При ]2г] < 1 множитель е ' + 1 отличен от нуля, ]Н (2х)] < е и!/(2п+ 1)! и ]А"(2х)+А"( 2х)]> и С( ) ( и ) ( и ) ( и ) ") (2п)! 7 1 1 1 1 2 (2п)! > — 1 — — — — — —— и! 1 4 16 64 / 3 и! Таким образом, сходимость очень быстрая даже для комплексных значений з. Для перехода от этой цепной дроби к цепной дроби для е' можно воспользоваться равенством сапЬ з и 1 — 2/(ез' + 1). После несложных выкладок получим представление (ез' + 1)/2 в виде цепной дроби. Правило Гурвица дает разложение в цепную дробь функции е * + 1, из которого остается вычесть единицу.
Для нечетных п е !" = //1, 3тп+ ]и/2], (12гл+ б)п, (Зт+ 2)п+ (и/2], 1//, т > О, Еще одно доказательство было предложено К. С. Дэвисом (С. Я. Па лз) и опубликовано в журнале Х ЪоЫоп Ма!Ь. Яос, 20 (1945), 194 — 198. Впервые разложение числа е в цепную дробь было получеяо эмпирически Роджером Коутсом (Набег Со!ее), РЬ!?озоуЬ!са? Т1алэасболз 29 (1714), 5-45, Ргороюйоп 1, ЯсЬо!ппп 3. Эйлер прокомментировал эти результаты в письме Гольдбаху (Со16ЬасЬ) от 25 ноября 1731 года ]Соггеэропс(апсе Ма!Лета!!опе ег РЬуэ!ппе, ес(!!ед Ьу Р.
Н. Рпэз, 1 (Яп РесегзЬигб, 1843), 56-60], а также опубликовал более подробное описание этих результатов в Соп!!пепсагб Аеас!. Яс!, Ре!горо?!галю 9 (1?37), 98- 137; 11 (1739), 32 — 81. 17. (Ь) //х! — 1, 1, хз — 2, 1, хз — 2, 1, ..., 1, хз„! — 2, 1, т! — 1// ]Примечание. Отрицательные параметры могут быть исключены из коитинуантов при помощи тождества К,ее+! (х!,..., х, — х, р,..., р!) — ( 1) Км+е+2(х! ° ° хм-!, хе! — 1, 1,х 1, — у !..., у!), нз которого после повторного применения можно получить Кч+п+! (х!,, тм, -*, ре,..., р!) = — К + +з(х!,...,х,х — 1,1,х — 2,1,9„— 1,9„„,,9,) Похожее тождество встречается в упр.
41.] (с) 1 + //1, 1, 3, 1, 5, 1,... // = 1 + //2т + 1, 1//, т > О. 18. Поскольку в силу тождеств (5) и (8) выполняется К (а!,аз,,а ) //а!,аз,...,а,х// = К,„! (аз,..., ае!) + ( — 1) ~/(Кэ- ! (а !,..., ае!-!) + К, (а !, аг,..., ае!) х), будет выполиятьсл и Км(аг,аз,...,а ~)//а!,аз,...,а,х!,а!,аз,,а~,хз,а!,аз,...,а~,хз,а!,. // = К !(аз,...,а ) + //( — 1)~(С+ Ах!),С+ Ах!,( — 1) (С+ Ахз),... //, где А = К (а!,аз,...,а ) и С = К !(аз,,а ) + К !(а!,...,ам !). Соответственно в силу (6) искомая разность равна (К, !(аз,...,а ) — Ке! !(а!,,а !))/К, (а!,аю,ае). ]Случай, когда т = 2, рассматривался Эйлером в Сопппепсагй Асас1. Яс!.
Ресгоробсалю 9 (1737), 98-137, 124-26.] 19. Сумма для 1 < 5 < Х равна !об!((1 + х)(Х + 1)/(!!+ 1 + х)). 20. Пусть Н = ЯО, д(х) = (1+ х)С'(х), Ь(х) = (1+ х)Н'(х). Тогда из (37) следует, что Ь(х+ 1)/(х + 2) — И(х)/(х+ 1) = — (1+ х) 'д(1/(1+ х))/(1+ 1/(1+ х)). 21. у(х) = с/(сх + 1)э + (2 — с)/((с — 1)х+ 1), (Хх(х) = 1/(х+ с)э. При с < 1 минимум функции»о(х)/(Х»о(х) достигается в точке х = О и 2<~ < 2.
Если с >»5, минимум достигается в точке х = 1 и <»1~. Когда с 1.31266, значения функции при х = 0 и х = 1 почти одинаковы и минимум > 3.2; получены границы: (0.29)"!о < ХХ" »о < (0.31)" »о. Улучшение оценок границ произошло за счет хорошо подобранных линейных комбинаций в формуле Тд(х) = Х.'а>/(х т с,) 23. Основное тождество Н'„(х) = (Н (х) — Н„(О))/х + ухН'„'(д„(х)) для д (х), значения которого изменяются от О до х, получим, используя ннтерполяционную формулу из упр 4.6.4-15 длн хо = О, х~ — — х, хо = х + < и полагая, чта о -» О.
Функция Н„в этом тождестве имеет непрерывную вторую производную. Следовательно, в этом случае Н„'(х) = О(2 "). 24. оо. [А. Хинчнн, в Сошроо. Май. 1 (1935), 361-382, доказал, что эта сумма Аг+. +А„ первых и частичных отношений вещественнога числа Х будет равна примерно и 18 и почти для всех Х В упр. 35 показывается, чта для рациональных чисел Х ситуация будет иной.] 25.
Всякое объединение интервалов можно зш»исеть как объединение непересекающихся интервалов, поскольку имеем ()»>, Х» = 0»>»(Х» ! Д, <» Хо), а это есть объединение непересекаюгцихся множеств Х» '! (),«» Х» каждое из которых может быть выражено в виде конечного числа непересекающихся интервалов. Поэтому можно, пронумеровав каким-либо образом фунхциональные числа отрезка [О ..
1], взять Т = 0Х», где ջ— некоторый интервал длиной о/2", содержащий !о-е рациональное число. В этом случае И(2) < о, ио ]х О Р„] = и для всех п 28. Цепные дроби //Ам, А»//, которые появляются при представлении наших чисел,— это именно те дроби, для которых А~ > 1, А, > 1, а Н~(Ан Ам, А~) есть делитель числа и. Поэтому (6) завершает доказательство.
[Замечание. Если т~/и = //Ан.,., А»// и то/и = //Ан..., А~//, где т~ и гпэ взаимно просты с и, то т~то ш х1 (па модулю и). Это и есть условие, определиющее рассматриваемое соответствие. В случае, когда А~ — — 1, согласно (46) имеет место аналогичная симметрия.] 27. Сначала докажем результат для п = р', а затем — для п = то, где числа г и о взаимно просты. Альтернативный путь — использовать формулу из следующего упражнения.
28. (а) Левая часть — мультиплнкативная функция (см. упр. 1.2.4-31). Она легко вычисляется, когда п является степенью простого числа. (с) С учетам (а) имеем !бормдлд обращения Мебиуса (Моб»ио/: если /(п) = ~<1„9(д), то д(п) = 3" !од(п/д)/(д). 29. Сумма приближенно равна (((12!п2)/я ) !п)у1)/1д — ~ о>~й(д)/д» + 1,47; здесь Х о>, й(д)/до сходится к постоянному значению — ~'(2)/6(2), в то время как согласно приближению Стнрлинга !п Х! = 1У 1и Н вЂ” Н+ О(1об г»'). 30. Предлагаемая модификация алгоритма влияет на вычисления только в том случае, когда при выполнении следующего шага деления немодифицированным алгоритмам получается частное, равное 1.
В таком случае этот следующий шаг деления будет пропущен модифицированным алгоритмом. Вероятность того, что данный шаг деления будет пропущен, равна вероятности того, чта А» = 1 и что этому частному предшествует четное число частных, равных 1. Учитывая условия симметрии, получаем, что это есть вероятность того, что А» = 1 н что оо ннм следует четное число частных, равных 1. Последнее имеет место тогда и только тогда, когда Х»» >»! — 1 = 0.618..., где»!в отношение золотого сечения: действительно, А» = 1 и А»л» > 1 тогда и только тогда, когда л л <Х»» <1:А»=А»э»=А»»з=1иА» л>1тогдаитолькотогда,когда» <Х»» < —, и т. д.
Таким образом, экономится приблизительно Р» л(1) — Е»»(й — 1) 1 — 184 0.306 шагов деления. Среднее число шагов деления в случае, когда с = и и и взаимно просто с и, приблизительно равно ((12!а»1)/;гэ) 1п и. К. Вален (К. луаЫеп) в работе Сге!!е 115 (1895), 221-233, рассл»атривал все алгоритмы, которые прн я»»лоде ~ 0 на каждой итерации заменяют значения (и,е) значениями (о, (хи) пюд с). Для и з. и существует ровно о таких алгоритмов, и они могут быть представлены в виде бинарного дерева с с ветвями. Самые мелкие ветви дерева будут формироваться, если на каждой итерации выбирать самые маленькие остатки — это соответствует наименьшему возможному числу итераций выполнения всех таких алгоритмов определения наибольшего общего делителя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
