AOP_Tom2 (1021737), страница 197
Текст из файла (страница 197)
См. также А, %. Ва)апсху)с, Н. Р. Вгепз, Сошразегь апс) Магб. 14 (1987), 233. 40. Пусть т = !8 гпах((и(, (и(). По индукции можно показать, чго после выполнения в раз на шаге КЗ операции с с- с+1 получим (и( < 2 ' Ы 'У~, (а( < 2 Ы»'11~ Поэтому в < 2сп. Если шаг К2 выполняется ! раз, палучизс ! < в + 2, так как в увеличивается каждый раз, но не на перволс и последнем шагах (См. РЕБ1 '83 (Ног!!с-Но!!апб, 1983), 145-154.] Примечание. Егли и = 1, а = 3 2" — 1 и Л > 2. получаем т = Л + 2, в = 21с, 1 = Л + 4. При и = и и а = 2иг г в последовательности из = 3, ис = 1, иг»с ппп((Зиг — 16и, с(, (5и — 16иг с() палУчаем в = 21+ 2, г = 21+ 3 и (эмпнРнчески) т ф/Ь Может ли г в пределе быть больше, чем 2т/фу 41.
Учитывая, что (а" — 1) шоб (а" — 1) = а" ""в '1 (см. соотношение 4,3.2 — (20) ), для всех положительных целых чисел а найдем в общем случае боб(а — 1, а" — 1) = авсщ"»Ю — 1. 42. Для всех 1с = 1,2, 3,... вычитаем Л-й столбец из 2йч З)с-, 45-го столбца и т, д. В результате получим треугольную матрицу с элементами хь на главной диагонали, где т = хв. Отсюда следует, что х = сг(пс), так что определитель равен сс(1)св(2)... ср(п). [В общем случае точно так можно доказать, что дчя произвольной функции / »определитель Смита", в котором (г,у)-й элемент есть /(Зоб(г,/)), равен ]][» с 2 зс(т/с1)/(а). Слс. Ь.
Е. П!сйьоп, Н!ьсагу об гЬе ТЛеогу оГ НашЬесь 1 (СаспеЕбе 1пьк о1 Жввй!пбгоп, 1919), 122 †1.] РАЗДЕЛ 4.5.3 1. Время выполнения примерно равно 19.02Т+6, что чуть меньше, чем для программы 4.5.2А. 2. ) К„(хс,хг,...,х»-г,х») К»-г(хцхг,,х»-г)~ К г(хг,...,х с,х ) К -г(хг,,х -с) / 3. Кп(х),,х„). 4. По индукции или путем вычисления определителя в упр.
2. 5. Когда положительны все х, то 93 в (9) также положительны и Ч +) > Чп — ). Следовательно, выражение (9) представляет собой знакопеременный ряд с убывающими членами, сходящийся тогда и только тогда, когда Чп9„+) -) оо. По индукции, если все числа х больше е, то Чп > (1 + 4/2) "с, где с выбиРаетсЯ достаточно малым, чтобы неРавенство выполнялось для и = 1 и 2.
Но если хп = 1/2", то Ч„< 2 — 1/2". 8. Достаточно доказать, что А) = В). Иэ того факта, что 0 < //х),..., х // < 1, когда х),...,хп — положительные целые числа, следует, что В) = (1/Л) = А). 7. Только 12...п и п...21. (Переменная хз появляется точно в РзР» з членах, следовательно, х) и х могут быть переставлены только с х) и х . Если х) и х„не затрагиваются перестановкой, то по индукции следует, что остаются нетронутыми и хг, Хп-1 ) 8.
Доказываемое равенство эквивалентно равенству К г(А, ),...,Аг) — ХКп )(4 ),...,А)) 1 К -)(А,,Аг) — ХК (Ап,, 4)) Х и в силу (б) эквивалентно К -)(Аг, °, Ап) + Х)Кп-г(Аг, °,А — )) Кп(.4),, А,)) + Х„К„1(А1,..., Ап-1) 9. (а) ПО ОПРЕдЕЛЕИИЮ. (Ь, д) ДОКаэЫВаЕМ дпя П пп 1, ЗатЕИ ПрИМЕНяЕМ (а), ЧтабЫ ПОЛУ- чить результат в общем случае, (с) Доказываем при и = к+1, а затем снова применяем (а). 10.
Если Аа > О, то Ва = О, В) = Аа, Вг = А), Вз = Аг, В» = Аз, Вз = А4, гл = 5, Если Аа = О, то Ва = А), В) = Аг, Вг = Аз, Вз = А», т = 3, Если Аа = -1 и А) = 1, то Ва = — (Аз+ 2), В) = 1, Вг = Аз — 1, Вз = А4, и) = 3. Если Аа = -1 и А) > 1, то Ва = — 2, В) — — 1, Вг = А) — 2, Вз = Аг, В4 = Аз, Вз = А4. т = 5. Если Аа < — 1, то Ва = -1, В) = 1, Вг = -Аа — 2, Вз = 1 В» = А) — 1, Вз = Аг, Ва = Аз, В) = А», п) = 7 (В действительности последние три случая включают в себя еще восемь подслучаев если какое-либо из чисел В оказывается равным нулю, то следует выполнить "стягивание" в соответствии с правилом (с) упр. 9, Например, если Аа = — 1 и А) = Аз = 1, то фактически имеем Ва = -(Аг + 2), В) = А» + 17 т = 1.
Когда Аа = -2 и А) = 1, нужно выполнить двойное стягивание.) 11. Пусть Ч = К (А),...,А ), Ч'„= Кп(В,,...,В ), Р, = Лп+)(Аа,,А»], Р К п)(Ва,...,В ). Учитывая уравнения (5) и (11), получаем Х = (Р +Р -1Л )/(Ч +Чп-)Хп)) 1 = (Р' +Р' — )1 )/(Ч +Ч)-1У )~ поэтому в силу тождества (8), если Х = Уп, утверждаемая зависимость имеет место.
Обратно, если Х = (ЧУ+ с)/(вУ+ г) и (Чг — гз( = 1, можно считать, что в > О, и иидукцией по з показать, что частичные частные для Х и У в конечном счете совпадают. Согласно упр. 9, ()1) при з = 0 результат очевиден. Для з > 0 положим Ч = аз + з', где 0 < з' < з. Тогда Х = а + 1/Из)'+ г)/(з'у + г — аФ)); поскольку з(г — ог) — гз' = зг — )Ч и з' < з, по предположению индукции и в силу упр. 10 частичные частные для Х и У совпадут. [Х ))е Ма)Ь. Ригеэ ег Аррб 15 (1850), 153 — 155. При внимательном изучении данного доказательства иэ того факта, что в упр. 10 число гл всегда нечетио, становится ясно, что Л, = Уп тогда и только тогда, когда Х = (ЧУ + г)/(зУ + г), где Ч) — гз ы ( — 1) 12.
(а) Так как У„Упт) — — Р— (/~~, известно, что Р— 17~ „) кратно У„+); следовательно, по индукции Х = ()ГР— П,)/У„где П и Ъп — целые числа. (Эамечание. Основанный иа таком процессе алгоритм используется во многих приложениях для целочисленного решения квадратных уравнений.
(См., например, Н. Вачепрогц ТЬе Н~8Ьег АгйЬшес)с (1.опбоп: НпгсЫпаап, 1952); ««5 1. 1еЪецпе, Тор1сэ 1п 1«ишЬег ТЬеогу (Неаб1пб, Маш. Абпбвоп-'«Чез1еу, 1956); см. также раздел 4.5.4.) Согласно упр. 1.2.4-35 имеем А э~ (((э/В] + У„)/Ъ«ы], где Ъ'+з > О, и А»ы = (('1«/Р]+1+ Г/ )/Ъ»ы], где Р'чч < О. Следовательно, такой алгоритм выполняется только для положительных целых чисел («/В]. Более тога, тождество 1' э~ = А (17 -~ — (7 ) + р« ~ позволяет при определении р э~ исключить операцию деления.] (Ь] Пусть У = ( — «/Р— (7)/г', У = (-ъ/ — К )/1' . Заменив в доказательстве (а) ~/В на -«/Р, видим, что сформулированное тождество выполняется.
Имеем У = (р /15+ р.— )/(9-/1"-+9-- ), где элементы р„и д„определены в п, (с) настоящего упражнения, Следовательно, У. = ( — д /9 -~)(У вЂ” Р»/9»)/(У вЂ” Р -~/9 -~) Но согласно (12) р» ~/д„~ и р«/д очень близки к Х; учитывая, что Х ф 1', величины 1' — р„/д» и У вЂ” р„~/д„~ для всех больших значений и будут иметь тот же знак, что и У вЂ” Х. Это доказывает, что 1' < 0 для всех больших значений я. Следовательно, 0 < Х„< Л вЂ” У'„= 2~/В/$'„в Ъ» должно быть положительным.
Так как Х > О, то и К, < чгВ. Значит, г«< 2«/Р, поскольку 1г«< А 1г» < з/В+ Г/» Наконец покажем, что У„> О. Поскольку Х» < 1, то П» > «/В-И», так что достаточно рассмотреть случай, когда К, > «/В. Тогда (7 = А»р'„— У„~ > )㻠— К,-~ > ь/Р— К,-п а это, как уже установлено, величина положительная. Замечание. В повторяющемся цикле имеем «/Р+ У~ = А ~» + (~/ — (7 ~) > 1»; отсюда ((э/+У» ы )/Р» ы] = (А + ~ + р~/(чВ+ В )] = А«ы = Ц «/В+ Ь', )/««ы]. Другими словами, А»э~ определено значениями (7,«; и 1г» н величину (У,. ь;) можно определить черезеепреемника(Р ««,'г ~) в периоде.
Фактическиизприведенныхвыше рассуждений следует, что когда 0 < 1' < «/В+ У и О < К, < «/В, то 0 < И «~ < «/В+ (Г„т~ и О < К,«~ < ~/В. Более того, если пара (У «и И «~) следует за парой ((7, р«), для которой 0 < г" < т/В+ У' и 0 < В' < ~/В, то Г/' = (7 и р« = 'е'„. Таким образом, (У„, \г„) будет частью цикла тогда и только тогда, когда О < р«< «/В + Р и О < Р < ~Р, ( ) )'»э1 Х у (9 Л р»)(Ч»~ р») (с» вХ вЂ” р, в)(9»-ь1' — р -ь) Для доказанного тождества имеется сопряженное тождество Ир р»-~ + Г/(р.ч.— + р -~9 ) + (((7' — Р)Я4»ч — = (-1)" б'» (д) ЕСЛИ Х„ = Лы дпя НЕКОтОрОГО и Э1 щ, тО Х вЂ” ИррацИОНаЛЬНОЕ ЧИСЛО, удОВЛЕтВО- ряющее квадратному уравнению (9«Х-р )/(д ~Х вЂ” р„-!) = (9»Х — р»)/(д ~-~Х-р «-)) История идеи, изложенной в этом упражнении, восходит к Джайадеву из Индии (не позднее 1073 г.).
(См. К. 8. 8Ьп1с!а, Салйа 5 (1954), 1-20; С.-О. Бе!еп(пэ, Няйопа МагЬ. 2 (1975), 167-184.) Некоторые из аспектов этих идей обнаружены также в Японии и датируются не позднее 1750 года. (См. У. М1Ьаш1, ТЬе Реге1ортепг оГ МазЬегпайсв )и СЬ1па апо,/арап (1913), 223 — 229.) Однако основные принципы теории цепных дробей применительно к квадратным уравнениям разработаны Эйлером [№г1 Сопппепп Асад. Яс1 Рессор. 11 (1765), 28-66] и Дш ранжем ]НИ. Асаб.
ЯсЬ 24 (Вег11п, 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, 1, 3//, т > О (см. упр. 16). Обратите внимание на некоторую закономерность в полученном выражении. (БсЬпНеп г!ег рЬуз.-оЬоп. Сезе!!зсЬай гн КошйяЬегб 32 (1891), 59 — 62.) Гурвиц также изложил в Ъуегге!1аЬгззсЬг!й бег Хаспг1огзсЬепбеп Севе!!асЬаЕс ш 2йг!сЬ 41 (1896) „ЗпЬе!Ьапб П, 34-б4, 12, способ умножения на произвольное положительное целое число. 15.
(Эта процедура обрабатывает значения четырех целых чисел (.4, В, С, Р), которые имеют инвариантный смысл: "все, что осталось выполнить,— вывести цепную дробь вида (Ау + В)/(Ср+ Р)> где у---чнсло, которое будет введено".) Сначала присвоим ! е — Ь +- О, (А, В, С, Р) г — (а, Ь, с, И); затем введем хз и будем присваивать (.4., В, С, Р) е(Ах! + В, А, Сх, + Р, С), ! +- ! + 1 один или более раз, пока знак числа С + Р не станет равным знаку числа С (Когда 2 > 1 н ввод не закончен, выполняется неравенство 1 < у < оо, а когда знак числа С + Р равен знаку числа С, то известно, что (Ау+ В)/(Су+ Р) лежит между (А+ В)/(С+ Р) и Л/С.) Теперь приступаем к выполнению основного шага. Если точно между числами (А + В)/(С + Р) и А/С нет ни одного целого числа, то выводим Хь г — ш!п([А/С), [(А + В)/(С -!- Р))) н присваиваем (А,В,С,Р) г — (С, Р, А — ЛьС,  — ЛгР), Ь г- Ь Ч- 1; в противном случае вводим х, и присваиваем (.4,В,С,.Р) г — (Ах! + В, Л, Сх, + Р, С), ! ! — у -!- 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
