Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 53
Текст из файла (страница 53)
Значит, если задана такая функция 1"(г) и если заданы й > 2 и П», существует единственный ряд аида (»'(г) = г + У»г» ~- У»+»г»+» + ° °, удовлетворяющий (27). Требуемая итерация (»'1"1(г) является единственным степенным рядом Р(г), удовлетворяющим И(Р(г)) = Р'(г)1"(г), (28) где Р(г) = г + иУ» г" +" . Обе функции, И(г) и Р(г), можно найти с помощью подходящих алгоритмов (см. упр. 14). Если Г» — й-й корень из единицы, не равный 1, то такой же метод можно применить к функции 1»'1»1(г) = г + ° н У1»1(г) можно найти из У(г), произведя 1(й) операций композиции (см. раздел 4.6.3). Можно также рассмотреть случай, когда У» — — 0: если П(г) = У» г» + У»+» г" +' +.
-., где к > 2 и 1»» ф. О„то ццея состоит в том, чтобы найти решение уравнения ИЩг)) = Ю~Х(г)». Тогда У1э)( ) 1»1-»1((711»"-»1»1»-111Р( )»") И наконец, если Ь'(г) = 17е + (7~г +, где (7е Ф О, пусть а — "неподвижная точка", такая, что Г(а) = а, н пусть (7(г) = С(а + г) — а = Ю'(а) + г~(уе(а)/21 + (30) Тогда (71"1(г) = (7")(г — а) + ц. Детали можно найти в работе Вгепт апй ТгацЬ, 51СОМР 9 (1930), 54-66. Функция И из (27), по существу, рассмотрена в книге М. Кцсгша, Гипсе!опа! Еппасюпя ш а 3!пб!е "гаг!аЫе (%агзаич РИ'Н-Ро)(зЬ Бс(епг(бс, 1968), лемма 9.4, и, безусловно, Э. Жаботипским (Е. ЛаЬос)пзйу) на несколько лет раньше (см.
упр. 23). Алгебраические функции. Коэффициенты каждого степенного ряда И'(г), удо- влетворяющего общему уравнению вида А„(г)И'(г)" +--. + Аз(г)Иг(г)+ Аз(г) = 0„ (31) где каждое А;(г) — полинам, можно эффективно вычислить методом, предложенным в рабате Н. Т. Кипб апб 2. Р. ТгацЬ, «АСМ 25 (1978), 245-260. См, также работу Д. В, Чудновского и Г. В. Чудновского (В. У. СЬцбпотзЫу апб С. Ъ', СЬш)- пот эйу, Х Сотр!ех!Су 2 (1936), 271-294; 3 (1987), 1-25). УПРАЖНЕНИЯ 1. [М!О) В разделе объяснено, как разделить 1!(г) на И(г), когда Ие ф О.
Как произвести деление, когда !'о = 07 2. [ОО) Когда коэффициенты У(г) и $~(г) — целые и $е зе О, найдите рекуррентное соотношение для целых $'р"'~~И'„„где И определено в (3). Как можно этим воспользоваться для деления степенных радову 3. [М!О) Будет лн правильным результат, приведенный в формуле (9), когда а = О н когда а ш 17 ° 4. [НМЗО) Покажите, что простая модификация (9) может быть использована для вычисления е~ ~'~, когда Ъо = О, н 1в 1'(г), когда Ре = 1.
5. [МОО) Что произойдет, если степенной ряд обратить дважды, т. е. если выходные значения алгоритма 1 нлн Т обратить сновау ь О. [МО!) (Х. Т. Кунг (Н. Т. Кавб).) Примените метод Ньютона к вычислению И'(г) = 1/И(г), когда И(0) зе О, определив корень и воде степенного ряда уравнении у(г) = О, где У(г) = г ' — И(г) 7.
[МОЯ) Воспользовавшись формулой обращения Лагранжа (12), найдите простое выражение для коэффициента И'„в обращении г ж 1 — 1"'. ь 3. [МОО) Для И'(г) = Идя+И'згз+Изг~+ ° = С~1+От!'+Саге+ = С(1), где г = Ю+ 161З + гас~+ . И 16 1Ь О, ЛаГРаиж ДОКаЗад, ЧтО И'„= -[г" ')С'(гИ14+ ЪЪ!+ Ъ~з!'+ ")". (Соотношение (12) является частным случаем предыдущего, когда С~ ж Ъ1 = 1, Сз = Сз = . - -О.) Расширьте алгоритм 1. таким образом, чтобы для данной более общей ситуации он вычисляя коэффициенты И'и И'з, ... без значительного увелнчен1зя времени работы алгоритма. 9. [!!) Используя алгоритм Т, найдите значения Т „как первые пять коэффициентов обращения г ж 1 — Р.
16. [Мйй] Задано у = х'"+а«х ~'+ахх '~х+, о р О. Покажите, как вычислить козффициентыв разлом них=уы +Ьзущ'+Ьзущ + ". ° 11, [Мйб] (Композиция сщененнмх рядов.) Пусть (/(х) = (7о+(7«х+(/зх'+." и 1'(х) = У«х+ Ъзх'+1хзх'+.". Составьте план алгоритма, который вычисляет первые Х коэффициентов (/(И(х)). 12. [М20! Найдите связь между делением поликанов н делением степенных рялов. Запалы полиномы и(х) и и(х) степеней н«и и соответственно над полем. Покажите, как найти полиномы 4(х) и г(х), такие, что н(х) = е(х)о(х) + г(х) и <Фей(г) < н, используя только операции со степенными рядами. 13. [М37] (Аппроксимации рационахьнмх функций) Иногда необходимо найти полииомы, отношения которых имеют такие же начальные члены, как н данные степенные ряды.
Напрнл«ер, если И (х) = 1+ х + Зхх + 7хз .«, то существует четыре различных способа представления ««'(х) в впде вл(х)/юз(х) + О(х ), где ил(х) и юз(х) — полиномы с бей(ю~) + боб(юх) < 4: (1+ х + Зх + 7х ) /1 = 1+ х + Зхх + 7-"' + Ох' + ", (3 — 4х + 2х') / (3 — 7х) = 1+ х+ зхг ) 7хз 4 «эх«4.
(1 — х) / (1 — 2х — хз) = 1 + х+ Зх" + 7хз+ 17х«+ 1 / (1 — х — 2хх — 2хз) = 1 + х + Зхх + 7хз + 15х" + Рациональные функции такого рода обычно назмвают аппроксимацией Паде, так как они широко изучены Г, Е. Паде (Н. Е. Ра«(е) [Алла)ез Ясзепс, де РЕсо)е №гща)е Янрбпеиге (3) 9 (1892), 81-$93; (3) 16 (1899), 395-426!. Покажите, что все аппроксимации Паде И'(х) = ю«(х)/мз(х) + О(хн) с бей(кл) + де8(«ех) < Х можно получить, применяя обобщенный алгоритм Евклида к полиномам хл и Ие+ ИЗх+ . + И'л «х~ ', и составьте целочисленный алгоритм для случая, когда каждое Ж вЂ” целое.
[Указание. См. упр. 4.6.1-26.! ь 14. [НМЯ0] Используя (27) и (28), запишите подробно метод вычисления Пгч(х) Брента и Трауба, когда (/(х) = х+ П«х" + 15. [НМ20] Какой вид должна иметь функция (/(х), если в (27) И(х) имеет простую форму х" 7 Какой вмвод можно сделать относительно итераций (7(х)7 16. [НМ01] Пусть, как в упр З„Иг(х) = О(1). "Очевидный" метод нахождения коэффи- циентов И'и Их, И''з, ... таков: присвоить н +- 1 и В«(Ф) +- О(1), а затем сохранить соот- ношение И'"«Щ) + Их«.««1х(Г)з +" = В.(1), неоднократно присваивая И' «- [С] В«(г)/1'и В«(Г) - В (1)/У(1) —, 1. Докажите формулу Лагранжа нз упр. 8, показав, что -[1" ! В~«+,(Ф) Ф"/И(1)" = — [1"] В«(Ф) 1"+ ЯЯ" для всех и > 1 и й > 1.
и+1 «" 17. [МЯ0] Задан степенной ряд И(х) = 5[в+ гххз+ Ъзхз+ . Определим степенную матрацу И как бесконечную таблицу коэффициентов о„« = $[х"]Цх)~; н-й стененонд (ромегоЫ) 1' определяется как )г (х) = с„о+ е„«х+ + е х". Докажите, что степеноид удовлетворяет общему закону свертки «' (х+у)=~~ ( /"«(х)" -«(у) (Например, когда Ъ'(х) = х, получаем 1«(х) м х", и зто бииомиальная теорема. Когда И(х) = 1п(1/(1 — х)), согласно 1.2.9-(26) получаем е„« = [«].
Следовательно, степеноид з!) Докажите, следовательно, что любой степенонд 1'» (х) удовлетворяет не только равенствам из упр. 17 н 18,но н равенствам (*+ у)!' (х + у + оа) % ! ! х1»(х + йа) р~ — (к+ (и й)а) х+у+на ~~й/ х+йа у+(н — й)а И (х+ р) т гн — 1~ Из(х+йа) Ъ"„з(р — йа) р — па л ~й — 1/ х+!га р-йа ж(х+у), ' [Частные случаи включают биномиальную теорему Абеля, формулу 1.2.6-(16) н равенства Рота 1.2,6-(26) и 1.2.6 — (ЗО): сумму Торелли, упр. 1.2,6-34.] 28. (НМЯЕ] (3. Жаботинский.) Продолжая э том же духе, предположим, что (7 = (и з)— стеленная матрица У(х) = х+ Узз + .
Пусть и„= ию = н! б' . а) Объясните, как вычислить мат*рину 1в 17, чтобы степенная матрица Е !")(з) равнялась ехр(а!пУ) = 1+ а!вП+(а!вУ)з/2!+ Ь) Пусть 1„з — элемент матрицы!и У, находящийся на пересечении строки н и столбца й, и пусть з з» !» =!»м 1(х) =1з — +!з — +!» — + " 2! $! 4! Докажите, что 1„» = („",) 1„+~ з для 1 < й < н. (Указание, У!О(х) = х+еь(з)+0(г~).] с) Рассмотрите У!"!(х) как функцию от а и х и доказкнте, что оа — У! '(з) = Б(х) у У!"!(х) = б((1!"!(х)) . (Следовательно, Цз) = (!»1й!)И(г), где И(х) — Функция в (27) и (28).) з!) Покажите, что, если оз Р' О, числа 1„можно вычислить по рекуррентной формуле «-/п~ 1з = из, ~~ )!зо»зз-з = ~!зо з ° з з 2-Ы з з Как следует использовать данную рекуррентиую формулу, когда оз = 07 е) Докажите равенство «-1 и.
» пе пз н~,-з — —...— 1,1,...1 " — 2 гл! 2 йз! йз! ''' й ! ~в»е з~+ ез»«зт-з »о...,з йз где пз = !+йз+ ° т й — з. 24. (НМ26] Задав степенной'ряд У(х) = Цх+ Узхз + ", где У~ не равно корню из единицы. Пусть У = (и„з) — степенная матрица У(х). а) Объясните, как вычислить матрицу 1п У таким образом, чтобы степенная матрица !!! 1(х) равнялась ехр(а !и У) = 1 + а! в У + (а !а У) ~/2! + Ь) Покажите, что если И (х) тождественно не равно нулю и если У(Иг(з)) = И'(!з(х)), то И (з) = У! !(х) для некоторого комплексного числа а.
26. (ЛЩ] При У(г) = з+17ззз+!7 зз+'+ и !г(з) ы х+!ззз+И+зх'+'+ °, где й > 2, ! > 2, Уз Р О, 16 ф О и Ц(1/(х)) = 1~(У(х)), докажите, что й = ! и И(х) = К»!(х) дзя а = гЯУз. 26. (М22] Покажите, что, если У(х) ж !1е+Узх+Узх~. и И(з) = Изх+Ъюх~+. — степенные ряды, все коэффициенты которых равны либо О, либо 1, мшкно получить первые Ф коэффициентов У(И(х)) по модулю 2 за О(Х'~') шагов для любого с > О, 22.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
