AOP_Tom2 (1021737), страница 225
Текст из файла (страница 225)
8 с О> = 77>, Сз = (7о и т. д. Тогда вычислим (7(14 '!' ' (о)) — Ц>. (См. также упр. 20.) Брент и Кунг построили нескачько асимптотически Г>ыстрых алгоритмов. Например, можно вычислить Г/(х) для х = И(х) с помощью варианта алгоритма, который предложен в упр. 4.6.4-42(с), выполнив около 2 /Х умножений в цепочке с М(Х) или окало Х умножений параметров с количеством операций, равным Х. где ЛГ(Х) - — число операций, необходимых для умножения степенных рядов порядка Х С чедавательно, общее чис >о операций равно О(э/ХХМ(Х) + Хэ) = 0(Х~). Еще более быстрый метод может бь>ть основан иа тождестве 0(1о(х)+о'"1>(х)) = Г>($о(о)).1-з'"Г>' (1о(о))1>(с)+ о 0 (1о(с))1'>(с) /2!+ включающем около Х/ис членов, иэ которых выбираем т ж;/>У/!а8 Х Для вычисления первых членов Ц1'о(з)) потребуется 0(шХ(!обХ) ) операций, если использовать метод отчасти подобный рассмотренному в упр.
4.6.4 — 43. Так как перейти от !7И!(Уе(г)) к (7 а ~(Уо(г)) можно за О(!У!ой!У) операций, выполнив дифференцирование и деление на Уе(х), то полностью процедура будет содержать 0(т!т(!о8!У) + (!У/т) Ф!обА) = О(Х!ой%)~7~ операций. [»АСМ 25 (1978), 581 — 595.) Когда полипом имеет целые коэффициенты, состоящие из т двоичных разрядов, данный алгоритм включает приблизительно Ж~!г+' умножений чисел, содержащих (Х!8т) двоичных разрядов. Таким образом, общее время работы алгоритма больше !У Г . ы» Альтернативный подход с асимптотическим временем счета 0(А'™) развит в работе Р. Ейггпапп, ТЬеогебса! Сошр. Яс!.
44 (1986), 1-16. Композиция может выполняться быстрее по модулю малого простого числа р (см. упр. 26). 12. Деление полиномов тривиально, кроме случая, когда т > и > 1. В последнем случае уравнение и(х) = 9(г)с(г) + г(г) эквивалентно уравнению (7(») = О(г)У(г) + г "~'Н(х), где (7(г) = х и(х ~), !7(х) = х"е(х '), 0(г) = х "д(г ~) и Я(г) = г" 'г(г ')— "обратные" полиномы от и, и, о и г. Чтобы найти 9(х) и г(г), вычислим первые т — и+ 1 коэффициентов степенного ряда (7(»)/У (х) = И' (х) + О(г~ "~'), затеи вычислим степенной ряд 5Г(х) — У(г) И~(г), который имеет вид х "+'Т(г), где Т(г) = Те+ Т~г+ ., Заметим, что Т, = 0 для всех 1' > и, следовательно, !»(х) = и'(г) и й(х) = т(г) удовлетворяют требованиям. 13.
Используем упр. 4.6.1-3 с и(г) = г~ и п(г) = И'а+ + И"я-гх~ '. Ожидаемые аппроксимации — это значения оз(х)/ог(х), полученные, конечно, с помощью алгоритма. Из упр. 4.6.1-26 следует, что не существует дополнительных возможностей со взаимно простыми числителем и знаменателем.
Если каждое И'; — целое, то алгоритм 4.6.1С, примененный ко всем целым числам, будет обладать требуемыми свойствами. Замечание. Те, кого интересует более полная информация, могут обратиться к книге С!аиде Вгег!пзк1, Н!егогу ог" Сопгшпе4 Ггасболз апс! Ране Арргох!тангэ (Вег!ш: Брппбег, 1991). Случай, когда Ф = 2и+ 1 и с1еб(ьп) = бей(шг) = и, в частности, представляет интерес, поскольку он эквивалентен так называемой системе Теплица.
Асимптотически быстрые методы для систем Теплица рассмотрены в работе В!ш апб Рап, Ро!упоппа! ап4 Магг!х Сошрпгас!опз 1 (Воз!оп: В!гкпапзег, 1994), 52.5, Метод, предложенный в этом упражнении, можно обобщить на произвольную рациональную интерполяцию вида И'(г) эз р(г)/з(г) (по модулю (х — г~) (» — хя)), где г, необязательно должны быть различны.
Такии образом, можно точно определить значения И'(г) и несколько их производных в нескольких точках (см. работу Е!сЬап! Р, Вгепс, Ггеб С. Спшагэоп, апс! Палб У. 'г'. Упп, Х А!8оп»Ьшз 1 (1980), 259-295). 14. Если О(г) = г ч- 5Г»хь + . и У(г) = г" + 1~+,хьы +, находим, что разность У((/(г)) !" (»)У(х) равна ~,й, г "+" '/(И,1»~.! — (7».ь! + (полином включает только (7ы,5ГХ+г-и Уьеп..., ! ь+т ~)). Следовательно, 1 (») определен единственным образом, егли задан О(»), как и су(»), для заданных У(г) и сгь.
Решение зависит от двух вспомогательных алгоритмов, первый из них позволяет решить уравнение У(г + г»1/(г)) = (1 + хь 'И'(г))У(г) + гь '5(г) + 0(гь 'е") для !' (») = !'е + У~» + + У„- ~г" ', где Цх), И."(г), 5(г) и и заданы. Если и = 1, положим !'е = -Я(0)/И'(О) или выберем Уе произвольно, когда 5(0) = И'(О) = О.
Перейдем от и к 2и. Пусть 1~(г + г !7(х)) = (1 + г И' (г))У(г) + х 5(г) — х Л(х) + О(г ), 1+ » И (г) = (г/(х+ » 57(х))) (1+ г И'(г)) +0(х ), 5(г) = (г/(г+ г" (7(х)))" п(х) + О(г") и пусть У(г) = У, + Уз+,г+ + Узз-зг" ' удовлетворяет уравнению У(г+г (/(г)) = (1+г" 'И«(г))У(г)+г" 'Я(г)+0(г +"). С помощью второго алгоритма решаем И'(г)(/(г) + «7/'(г) = У(г) + О(«") для Цг) = По+ (7«г+ + 17„-зг" ', где У(г), И'(г) и и заданы. Если и = 1, та положим 0« = У(0)/И'(О) или выберем Ц«произвольно для случая, когда У(0) = И'(0) = О. Перейдем от и к 2и.
Пусть И'(г) 1/(г) + «0'(г) = У(г) — г"В(г) + 0(гз") и пусть с7(г) = 0 + + 0« «г" ' — решение уравнения (и+ И'(г))1/(г) + «17~(г) = В(г) + 0(г"). Применив обозначения (27), первый алгоритм можно использовать для решения уравнения У[7/(г)) = (7'(г)(г/(/(г)) У(г) с любой требуемой точностью. Положим У(г) = г" У(«). Чтобы найти Р(г), предположим, что У(Р(г)) = Р'(г) У(г) + 0(гы '« "). Данное уравнение справедливо для и = 1, когда Р(г) = г + аг~ н и — произвольное.
Можно перейти от и к 2и, полагая, что у(Р(г)) = Р'(г)у(г)+гзз '+" В(г)+0(гз" 'т~"), и заменяя Р(«) на Р(з) + «э+" Р(г), где второй алгоритм используется для нахождения полинома Р(г), такого, что (Л+ и — «У'(Р(г))/У(г))Р(г) + гР'(г) = (г /У(г))В(г) + О(г"). 1б. Из дифференциального уравнения (/'(г)/17(г) = 1/гз следует, что (7(г)' з = г' "+с для некоторой постоянной с.
Таким образом, находим, что (7«"«(г) = г/(1+ сиг' з) кцз Аналогично решаем (27) для произвольного У(г): если И" (г) = 1/1'(г), то И'(1760(г)) = И'(г) + ис для некоторого с. 16. Нужно показать, что [С"] 1"+'((и+1)В«+,(1)/У(Ф) — иВ'„(«)/У(1) "+') = О. Это следует из равенства(и+1)Вз+,(С)/У(С)" — иВ«(1)/У(1)"~ = з«(В«(г)/У(1)"+~), Поэтому получаем и '[1"-'] В[(1) С"/У(1)" = (и — Ц '[1"- ] ВЫ«)г"-'/У(1)" ' = = Ум[1 ] В'„(1)1/т (1) = [1] В„(1)/У« = И'„. 17. Соберем коэффициенты при х'р . Из формулы свертки следует, что ['~ )е„1«+ > и Яз [")аз«в<„з>, а это эквивалентно равенству [г"] У(г)+ =2 з([г ]1'(г)')([г" [ У(г) ), являющемуся частным случаем (2).
Замечание. Название "степеноидз введено И. Ф. Стеффенсеном (3 г. Бге17епвеп), который первым из многих авторов изучил удивителъные свойства этих патиномов [Асса Ма«Лешайса 73 (1941), ЗЗЗ-Збб]. Обзор литературы и дальнейшее обсуждение предмета можно найти в следующих нескольких упражнениях, а также в статье П. Е. Кпи«Л, ТЛе Ма«Лен«айса Юонгла! 2 (1992), 67 — 78. Одним из результатов, полученных в этой статье, является асимптотическая формула У„(х) = е~™( —,",)" (1 — 1'зр + 0(у ) + 0(х ')), если У~ = 1, и «У (з) = у и р = и/х ограничены, когда х -о оа и и -о «ю.
18. Имеем У(х) = 2 х"и! [г"]У(г)"/Л! = и! [г"]е*гц«, Поэтому У (х)/х = (и — 1)! [г" ']У'(г) е*' М1, когда и ) О. Равенство можно получить, если приравнять коэффициенты прн г" ' в равенстве У'(г) ебтг«ЩЮ = У'(г) е*ЩЮе" 19. Согласно полиномнальной теореме 1.2.6-(42) имеем и! „, 7 а« аз з эз з апм — [г 1~ г+ г + г + ) « '1 И ~) 3) з,+гш+ "+зз = з,,з«,...,з„>о Эти коэффициенты появляются также в формуле Арбогаста (упр.
1.2.5-21). Эти члены уравнения можно привести в ссютветствие с множеством разбиений, как объясняется в ответе к данному упражнению. Рекуррентная формула ч Гп — 11 овь = ~~ . /езе1 -удь-0 ~-~, -1! позволяет вычислить столбец /с по столбцам 1 и и — 1; она легко интерпретируется в терминах разбиений (1,..., и), поскольку существует (".,'] способов включения элемента и в подмножество размера /. Несколько первых строк матрицы имеют следующий вид. з бе, е« е 15е~ е«+ 10«] ез ез Зще« еа 4е~ез + Зезэ е«бегаю + 10е«вз 4 10о~ е«в, з з 20.
[«"] И«(«) = 2„,([«](У(«)")([«"] г(«)1), следовательно, щ„ь = (и!/10) ~„1((й!/1!)и ь) х ((1!/и!) о„, ), [Е. 3аЬайпзЬу, Сотр«ез Нелс(из Асаф Ясб Рапи 224 (1947), 323-324 ] 21. (а) Если У(«) = пИ'(6«), получим п„ь = ф [«"] (оИ'(8(«))" = пьВ ш„ь; в частности, если б'(«) = !'! 0(«) = — И'( — «), то и„ь = ( — 1)" ~щ„ь. Значит, согласно упр. 20 2 ь и ьщ и 2',„е„ьил соответствуют функции «. (Ь) [Решение И. Ге«сель (1«а Сеззе!).] Данное тождество фактически эквивалентно формуле обращения Лагранжа: имеем щ„ь = ( — 1)" ~и„ь = (-1)" а][«"]И! '!(«)~, и согласно упр. 16 коэффициент при «" в !Л '!(«)" равен и ' [1" '] ке"+~ '/!«(1)".
С другой стороны, определим е1 кд 40 Это ( — к) — "ь [«" "] (!г(«)/«)) ", в свою очередь, равно (-1)" ь(н — 1) (й Ч- 1)й [«"-'] «"+"-'/И(«)" 22. (а) Если И(«) = В! 1(«) и И'(«) = И1э1(«), то И'(«) = !'(«И («)е) = (/(«И'(«)в !«(«И («)э) ) = (у(«И«(«) "эе) — ев]14«( )- — / * [ — (о] -ч — */ С( ~-*/ где «/а --положительное целое число. Ыы получили результат для бесконечного множества о. Этого достаточно.
гак как коэффициенты (/! 1(«)* — полиномы от а. Выше уже рассматривались частные случаи данного результата (в упр. 1.2.6 — 25 и 2.3.4.4 — 29). Одно запоминающееся следствие указания — это случай, когда и = — 1: И'(«) = «С(«) тогда и только тогда, когда И«(«) = «/(/ («) . (с!) Если Се = 1 и \' («) — степеноид для И(«) = 1и 1Г(«), то, как уже было доказано, «1'„(«+по)/(«+ пи) — степеноид для !и (у!~1(«). Значит, можно вставить данный степеноид в первое тождество, заменяя р на у — оп во второй формуле. (Отметим разницу между данным законом и подобными формулами (/!0(«) = С(«), И"йз!(«) = 11!"и!(«), которые применяются в итерации.) (Ь) В!~1(«) — производящая функция для бинарных деревьев, 2.3.4.4 — (12), равная И'(«)/«, в примере « = 1 — 1~, который следует за алгоритмом Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
