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