Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 89
Текст из файла (страница 89)
Может лн 1 в пределе быть больше, чем 2т/42 41. Учитывая, что (а" — 1) шос) (а' — 1) = а" ~'~ п1 (см, соотношение 4.3.2-(20)), для эсе положительных целмх чисел а найдем в общем случае йсб(ам — 1, а" — 1) = азпе!"'эй — 1, 42. Для всех й = 1,2,3,... вычитаем й-й столбец иэ 2йч 35-, 45-го стспбца н т, д. В результате получим треугольную матрицу с элементами г» на главной диагонали, где т = Я„хю Отсюда следует, что х = 1р(ш), так что определитель равен Р(Ц1р(2)... д(а). [В ОбщЕМ СЛуЧаЕ ТОЧНО таК Мажиа дОКаЗатъ, Чта дЛя ПрОИЗВОЛЬНОй фуиКШ»н / паирсдслитель Смита", в котором (1,Я-й элемент есть /(йсс((з,у)), равен Пп, ~э! д(т/11)/(й). См. Ь.
Е. Р»сизов, ВЗэгогу о/гйе Тйеогу ог" Хпшбегэ 1 (Си!пей(е 1пзз. о1 1ЧвэЫпйсоп, 1919), 122-123.[ РАЗДЕЛ 4.8.3 1. Время выполнения примерно равно 19.02Т+6, что чуть меньше, чем лчя программы 4.5.2А. 2. (...-,'и) К„(хз,х»,. ° ° ~хп-»,х ) йп-1(х1~хз, ° ~хп-1)~ Кп-1(хз,...
~ хп 1, хп) Кп-з(хз ... )х !) / 8 Кп(хм...,хь). 4. По нндукпии или путем вычисления определителя в упр. 2. б. Когда положительны все х, то 9; в (9) также положительны и йз+з > ч -ь Следовательно, выражение (9) представляет собой знакопеременный ряд с убывающими членами, сходящийся тогда и только тогда, когда 8„9„+, з оо. По индукции, если все числа х больше е, то о„> (1+ е/2)" с, где с выбирается достаточно малым, чтобы неравенство выполнялось для и = 1 н 2. Но если хк м 1/2", то йз < 2 — 1/2". 8. Достаточно доказать, что А1 = Вь Из того факта, что 0 < //хм, х„// < 1, когда хм..., х„— положительные целые числа, следует, что В1 = (1/Х) = Аь У. Только 12...н и п...21.
(Переменная хз появляется точно в РзР -з членах, следовательно, х1 и х могут быть переставлены только с х1 н х,. Если хз и х„не затрагиваются перестановкой, то по индукпни следует, что остаются нетронутыми и хз, ...,х -и) 8. Доказываемое рагзенство эквивалентно равенству К„з(А з,...,Аз) — ХК„з(А м...,Аз) 1 Ки-з(Аз ° ° ° ~Аз) ХКл(Аз~ °,Аз) Хв и в силу (6) зквивалеитно Х Кв-з(Аз, А ) +ХзК -з(Аз,,Ав-з) К„(А,,А„) + Х„К„,(Ап..., А„з) 9. (а) По определению. (Ь,б) Доказываем для и ж 1, затем применяем (а), чтобы получить результат в общем случае. (с) Доказываем при и = 8+ 1, а затем снова применяем (а). 10* Если Ае > О, то Ве = О, Вз = Ае, Вз Ам Вз = Аз, Вз = Аз, Вз - -Аз, пз = 5, Если Ао ж О, то Ве = Ам В1 = Аз, Вз = Аз, Вз = Ам щ = 3.
Если Ае = -1 н Аз - -1, то Во = -(Аз+2), Вз =1, Вз = Аз — 1, Вз ж Аз, пз = 3. Если Ао = -1 и Аз > 1, то Ве = -2, Вз = 1, Вз = Аз — 2, Вз ы Аз, Вз = Аз, Вз = Аз, зп = 5. Если Ао < -1, то Во = -1 Вз = 1 Вз м -Ао — 2 Вз ~ 1, Вз = Аз — 1, Вз = Аз, Вз = Аз, Вт = Аз, гл = 7. «В действительности последние три случая включают в себя еще восемь подслучаев: если какое-либо из чисел В оказывается равным нулю, то следует выполнить "стягивание" в соответствии с правилом (с) упр. 9. Например, если Ао = — 1 и Аз -- Аз -- 1, то фактически имеем Во = -(Аз + 2), Вз = Аз + 1гщ ы 1. Когда Ае = -2 и Аз = 1, нужно выполнить двойное стягивание.) 11. Пусть Оп Ке(АЬ...,Ав), д« = Кз(Вм...,Вз), рп = Кем(Ао,...,Аа), рп К тз(Ва,..., Вз). Учитывая уравнения (5) н (11), получаем Х=(Р +Р,Х )/(9 +9,Х ), У=(Р'„+Р'„,У)/И„'+Д'„,У); повгому в силу тождества (8), если Х, = Уз, утверждаемая зависимость имеет место.
Обратно, если Х = (дУ+ г)/(зУ+ 1) и ) о1 — гз! ы 1, можно считать, что з > О, и индукпией по з показать, что частичные частные для Х и У в конечном счете совпадают. Согласно упр. 9, (8) при з = 0 результат очевиден. Для з > 0 положим д = аз + з', где 0 < з' < з. Тогда Х = а + 1/((зУ + 1)/(з'У + г — о1)), поскольку з(г — ас) — зз' = зг — 19 и з' < з, по предположению инлукпни и в силу упр. 10 частичные частные для Х и У совпалут.
[Х с(е Мазй. Рогзн щ Аррй 16 (1850), 153-155. При внимательном изучении данного доказательства нз того факта, что в упр. 10 число зп всегда нечетно, становится ясно, что Х = Уз тогда и только тогда, когда Х = (дУ+ г)/(зУ+1), где 81 — гз = (-1) 12. (а) Так как У У +, = Р— Пз, известно, что Р— 1Я+з кратно У„+П следовательно, по индукции Х„= (з/Рл — У„)/Ую где П и 1'„— целые числа. [Замечанвз. Основанный на таком пропессе алгоритм используется во многих приложениях для целочисленного решения квадратных уравнений. (См., например, Н. Ратепрогц ТЬе Н)бЬег АгйЬщебс (1;оптов; НпссЬ1пвоп, 1952); Ч~. 1. Ье«'ецве, Тор/св 1п НпшЬег ТЬеогу (Иещ)(пб, Маевс Аббюоп-'««Ья1еу, 1956), см, также раздел 4.5.4.) Согласно упр.
1,2.4-35 имеем А +~ = Щ«/Р] + К,)/У»+~], где 1»+~ > О, н А»+« = '1((«/Р]+ 1+ (/ )/У»+~], где У»»«< О. Следовательно, такой алгоритм выполняется только для положительных целых чисеа '1«/Р]. Более того, тождество У»т~ = А»((7»-~ — (7») + У»-~ позволЯет пРи опРеделении У»+ ~ исключить операцию деления.) (Ь) Пусть У = (-«/Р-(/)/г', У, = (-«ГР— К»)/Ъ». Заменив в доказательстве (а) «/Р на -«/Р, видим, что сФормулированное тон«лестно выполняется. Имеем 1'= (р./У.
+р.- )/(д./1'+д — ), где элементы р„и д„определены в п. (с) настоящего упражнения. Следовательно, У = (-д /д - )(1 — р»/д )/(У вЂ” р,- /д,- ) Но согласно (12) р ~/д„-~ и р„/д„очень близки к Х; учитывая, что Х ЭЬ У, величины У вЂ” р„/д„н У вЂ” р ~/д «для всех больших значений и будут иметь тот же знак, что и У вЂ” Х. Это доказывает, что У» < О для всех больших значений и. Следовательно, 0 < Х„< Մ— У„= 2«ГР/У„и У„должно быть положительным. Так как Х„> О, то н (7„< «/Р. Значит, У» < 2«/Р, поскольку У» < А„У» < «/Р+ К„ Наконец покажем, что 0'„> О. Поскольку Л"„< 1, то К„> «/Р-Ъ', так что достаточно рассмотреть случай, когда У» > «/ь).
Тогда К, = А»У» — (/»-~ > У» — (/»-~ > «/Р— (7» а зто, как уже установлено, величина положительная. Замечание. В повторяющемся цикле имеем «/Р + К, = А 1" + («/Р— К «) > Ъ'„; отсюда ((«/+(7»т~)/У»~ «] = ] 4» ~ ~+ У»/(«/Р+(/»)] = А»~ 1 = '1(«/Р+(7 )/У»е!] Другими словами, А»~ы определено значениями К, », и 1'„~.п величину (К». У» ) можно определить через ее преемника ((7»+и \'»„.«) в периоде. Фактически нз приведенных выше рассуждений сведует, что когда 0 < 1' < «/Р + К н 0 < К„ < «/Р, то 0 < У„+« < «/Р + (7 +~ и О < (7»+«< «/Р.
Более того, если пара Щ+и У» ы) следует за парой (17', Ъ"), для которой О < 1" < «/Р + (7' и 0 < (7' < «/Р, то (/' = (7 и У' = У . Таким образом, (К, У») буде« частью цикла тогда н только тогда, когда 0 < У» < «/Р+ К, н 0 < К, < «/Р. -Ъ"».„~ (д Л вЂ” р )(д»У — р ) (с) —, = ջӻ— (д -~Х вЂ” р -~)(д — ~У - р»-~) Для доказанного тождества имеется сопряженное тождество Ур»р.- + (/(р.д — + р — д.) + ((К' — Р)/У)д»д.- = (-1)"К' (б) Есви Х = Х для некоторого а ~ щ, то Х вЂ” иррапионвльное число, удовлетворяющее квадратномууравнению(д„Х-р„)/(д ~Х-р»-~) = (д, Х-р„)/(д„, ~Х-р ~).
История иден, изложенной в этом упражнении, восходит к Джайадеву из Индии (не позднее 1073 г.). (См. К. 8. ЗЬвМа, Сапйа 5 (1954), 1-20: С.-О. Бе)епщв, Насог!а Маей, 2 (1975), 167-184.) Некоторые нз аспектов этих идей обнаружены также в Японии и датируются не позднее 1750 года. (См. У. М1Ьапп', ТЬе Реке)ортепг о/ Магйетабсв )п СЫпа апд,)арап (1913), 223-229.) Однако основные принципы теории цепных дробей применительно к квадратным уравнениям разработаны Эйлером (г1ог( Сапщепк Асад. ос( Ресгор. 11 (1765), 28-66] и Лагранжем [НЫ.
Асаб. Зс). 24 (Вег!ш, 1768), 111-180]. 14. Как н в упр. 9, достаточно проверить указанные тождества для случая, когда с есть последнее частичное отношение, а зта проверка выполняется просто. Применив правило Гурвица, получаем 2/е = //1,2,1,2,0,1,1,1,1,1,0,2,3,2,0,1,1,3,1,1,0,2,5,...//.
Перейдя к обратной величине и отбросив нули, как в упр. 9, получаем е/2ы1+//2,2щ+1,3,1, 2т+1,, //, т>0 (см. упр. 16). Обратите внимание на некоторую закономерность в полученном выражения. (Ясйгй)ев г)ег рЬуи.-бйоп. С»не()эсЬа(г гв КашйВЬегб 32 (1891), 59 — 62.) Гурвиц также нзложнл в Ъьег»е!(ВЬгмсЬг!Я»(ег Ь!агиг(огэсЬев»(еп Севе!(ыЬа(1 !и Ебг»сЬ 41 (1896), ЛпЬе!Ьав»1 П, 34-64, 82, способ умноження на произвольное положительное целое число. 18.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
