AOP_Tom2 (1021737), страница 161
Текст из файла (страница 161)
(24) (25) Следовательно., функция 1 (») = 1~(») +»" Ъ'(») удовлетворяет Ъ" (П(»)) = И"(»)И*(») + 5(») + 0(»'") Такая функции И называется функцией Шредера Г, поскольку она была введена Эрнстом Шредером (Егпэс 3сЬгодег, Ма»Ь. Аппа1еп 3 (1871), 296-322). Рассмотрим задачу нахождения функции Шредера И(») = » + 1»»» + . заданного степенного ряда 17 = П~» + (7»»' + .
Очевидно, что и = (7м если выполняется (21). Подставив в (21) и = Г~ и собрав коэффициенты при», придем к последовательности уравнений, начинающихся с что и требовалось. Время работы данной процедуры Т(п) удовлетворнет соотношению (26) Т(2п) = 2Т(л) + С(л), где С(л) — время вычисления Н(з), И'(г) и Я(г). Функция С(п) отнимает основное время при вычислении \г(17(г)) по модулю сэ", порядок роста С(п) предположительно больше, чем и'+', следовательно, решение Т(л) рекуррентного соотношения (26) будет иметь порядок С(п).
Например, если С(п) = спз, получим Т(п) села илн, если С(л) равно 0(л!оял)з~э, с помощью "быстрой" композиции получим Т(п) = О(п 1обп)зуз. Процедура не работает, когда 1У(0) = 1 и 5(0) ~ О, поэтому необходимо исследовать, когда это происходит. Легко доказать нндукцией по и, что решение (22) согласно методу Брента-Трауба влечет рассмотрение точно л подзадач, в которых коэффициенты У(г) правой части уравнения принимают соответствующие значения 1У(х) (х/(7(х))' + 0(х") для 0 < 7' < л в некотором порядке.
Если И'(0) = Гс и û— не корень из единицы, получаем И'(0) = 1 только тогда, когда 7' = 1; в этом случае процедура не работает, если (22) не имеет решении для л = '2. Следовательно, функцию Шредера для П можно найти, решан уравнение (22) для п = 2, 4, 8, 16, ... с 1У(г) = (7с и 5(х) = О, всякий раз, когда (7с не равно нулю и не является корнем из единицы. Если (7с = 1, функция Шредера не существует, кроме случая, когда Г(г) = ю Однако Брент и Трауб сумели найти быстрый лсетод вычисления У~")(х), даже когда Гс — — 1, благодаря использованию функции У(з), такой, что У((7(х)) = Г'(з)У(з). (27) Если обе функции П(г) и (7(г) удовлетворяют (27) для тех же 1', легко проверить, что их композиция Г(П(г)) также удовлетворяет (27); следовательно, все итерации 17(х) являются решениями (27). Предположим, выполняется равенство Г(з) я+ 17» г» + Г»„сх»+'+ ., где lс > 2 и Г» э» О. Тогда можно показать, что существует единственный степенной ряд вида У(х) = з~ + У».»»х~~~ + У».»эх + + которьсй удовлетворяет (27).
Значит, если задана такая функция У(г) и если заданы )с > 2 и 17», существует единственный ряд вида Г(х) = х + П» х» -» 17»»» з»сы +, удовлетворяющий (27). Требуемая итерация (7(")(в) является единственным степенным рядом Р(х), удовлетворяюшим (26) У(Р(з)) = Р'(х) У(х), где Р(х) = х+ п(7»х» + . Обе функции, У(х) и Р(з), можно найти с помощью подходящих алгоритмов (см. упр. 14). Если Гс — 2с-й корень из единицы, не равный 1, то такой же метод можно применить к функции Г(»~(г) = х+ . и Бй(»)(х) можно найти из 17(х), произведя 1(1с) операций композиции (см.
раздел 4.6.3). Можно также рассмотреть случай, когда 17» — — О.' если 17(х) = (7» в» + Г»+, г~»' + ., где 1с > 2 и Ц,, ф О, то идея состоит в том, чтобы найти решение уравнении Г((7(г)) = П»У(х)». Тогда (29) И наконец, егли Ьг(») = Ьо + Ьг~ » +, где Ь?о ф О, пусть а — "неподвижная точка", такая, что Ьг(а) = а, и пусть ЬЗ(») = Ь?(а + ») — а = »Ь?'(а) + »зСе(п)/2! + (30) Тогда (1("'(») = ЬО("!(» — и) + и.
Детали можно найти в работе Вгепс апг1 ТгапЬ, $1СОМР 9 (1980), 54 — 66. Функция 1? из (27), по существу, рассмотрена в книге М. Кцс»ша, гипс!!опа! ЕОиаиопз !и а $!пк!е Иаг!аЫе (И?агзаэн РИ'Ь?-Ро11эЬ $с!епНйс, 1968), лемма 9.4, н, безусловно, Э. Жаботинскнм (Е. ЗаЬог!пз)су) на несколько лет раньше (см. упр. 23). Алгебраические функции. Коэффициенты каждого степенного ряда И'(»), удо- влетворяющего общему уравнению вида А„(») И'(»)" + + Аг(») И'(») + Ае(») = О, (3Ц где каждое А,(») — полипом, можно эффективно вычислить методом, прелложенным в работе Н. Т. Кцпв апб 3. Р, ТгапЬ, Х4СМ 25 (1978), 245 — 260. См.
также работу Д. В. Чудновского и Г. В. Чудновского (1). У. С1шбпотэ)су апс) С. У. С1шдпотв)су, Х Сотр!ех!Су 2 (1986), 271 — 294; 3 (1987), 1 — 25). УПРАЖНЕНИЯ 1. [М19) В разделе объяснено, как разделить Н(») на И(»), когда 1е ф О. Как произвести деление, когда Ие = О? 2. [99) Когда коэффициенты !?(») и И(») — целые и Иа ~ О, найдите рекуррентное соотношение для целых 1'э"+'И'„, где И' определено в (3).
Как можно этим всспользоваться для деления степенных рядов? в. [м!5[ Будет ли правильным результат, приведенный в формуле (9), когда и = О и когда о = 1'? ь 4. [НМ23[ Покажите, что простая модификация (9) может быть использована для вычисления е ' О1, когда гэ — — О, и !и 'г'(»), когда Ра = 1. 5. [МОО) Что произойдет, если степенной ряд обратить дважды, т. е. если выходные значения алгоритма Ь или Т обратить снова? В. [М91) (Х.
Т. Кунг (Н. Т. КнпВ).) Примените метод Ньютона к вычислению Иг(») = 1/И(»), когда Ъ'(0) ЗЭ О, определив корень в аиде степенного ряда уравнения ((х) = О, где У(*) = * ' — !'(») 7. [МОЯ) Воспользовавшись формулой обращения Лагранжа (12), найдите простое выражение дли коэффициента И' в обращении» = 1 — 1 В. [Мхе) ЛЛ И'(») = И', +И' +И, + = С!+а Р+Сзгз+ = С(1), де » = Ъ~1+ 1 э1з + Из1~ -г и г'~ ф О, Лагранж доказал, что И'„= — [1" '[а'(1)1(И + !'1+ !',1' Ч- .)" . 1 и (Соотношение (12) ЯвлЯетса частным слУчаем пРедыЛУн~его, когда С, = Ъ'~ = 1, Сз = Сз = = 0.) Расширьте алгоритм Ь таким образом, чтобы для данной более общей ситуации он вычислял коэффициенты 1Рм И'м .. без значительного увеличения времени работы элгорнтма.
9. [11) Используя алгоритм Т, найдите значения Тм как первые пять коэффициентов обращения» = ! — 1 . 2 10. [М20] Задано у = х + атхат' + пехот + ., а ф О. Покажите, как вычислить коэффициенты в разложении х = уш + утупят~ + бгугта + ' ь 11. [МЗЗ] (Композиция степенных рядов.) Пусть О(г) = Пт+(?тг+Ог»г+ и 1 (г) = Гтг+ Гггг+ 1»гг+. Составьте план алгоритма, который вычисляет первые ?т' коэффициентов Ц1'(г)). 12.
[М20] Найдите связь между делением полиномов и делением степенных рядов. Заданы полиномы и(х) н и(х) степеней т и тт соответственно над полем. Покажите, как найти полиномы д(х) н г(х), такие, что и(х) = о(х)о(х) + т(х) и Йе8(г) < п, используя только операции со степенными рядами. 13. [М27] (Ааараксимация рациональных функций) Иногда необходимо найти полиномы, отношения которых имеют такие же начальные члены, как и данные степенные ряды. Например, если И'(г) = 1 + г + Згг + 7»г +, то существует четыре различных способа представления И"(г) в виде шт(г)/шг(г) + О(г"), где шт(г) и шг(г) — полиномы с т(еб(шт) + т(е8(шг) < 4: (1+»+3» + 7» )/1 = 1+ »+ 3» + 7» + О»'+-. (3 — 4 + 2»г) / (3 — 7 ) = 1 ч- г -!- 3»г + 7»г + ф ~~ + (1 — г) /(1 — 2» — г ) = 1+ »+ 3»э ч-7»~ + 17»~ + 1/(1 — г — 2»г — 2»г) = 1+ г ч- Зг~+ 7»г+ 15»" + ..
Рациональные функции такого рода обычно называют ааароксиманией Паде, так как они широко изучены Г. Е. Паде (Н. Е. Раде) [Алла!еэ Яшеас. т!е !'Есо!е Хогша!е Яирег!еиге (3) 9 (1892), 81-893; (3) 16 (1899), 395 — 426]. Покажите, что все аппроксимации Паде ру(г) = шт(г)/шг(г) + О(г ) с с(е8(шт) + Йей(шг) < )т' можно получить, применяя обобщенный алгоритм Евклида к полиномам г~ и Ио+ Иттг+ + Итл тг, и составьте целочисленный алгоритм для случая, когда и — 1 каждое Ит, — целое. [Указание.
См, упр, 4.6.1 — 26.] ь 14. [НМ30] Используя (27) и (28), запишите подробно метод вычисления (т'!"!(г) Брента и Трауба, когда У(г) = г+ Уг гг + 18. [НМ20] Какой вид должна иметь функция У(г), если в (27) Г(г) имеет простую форму г ? Какой вывод можно сделать относительно ктераций У(г)? 16. [НМ2!] Пусть, как в упр 8, Ит(г) = О(С). "Очевидный" метод нахождения коэффициентов Вт, Иг, Иг, таков: присвоить п е- 1 и Нт(1) т — О(Г), а затем сохранить соотногаение И' Г(1) + Ит„т~ Г(!) + = Я„(1), неоднократно присваивая Ит„+- [!] На(1)/Гт, Н .н (С) +- На (!)/Г(1) — И', и т- и + 1. Докажите формулу Лагранжа из упр.
8, показав, что -[!" '] Я[т, (!) г"/Г(г)" = — [г") В[(г) С"т'/Г(1)о Ы для всех н > 1 и й > 1. п+1 ь 17. [М20] Задан степенной ряд 1'(г) = 1тг + Ггг + 1гг + . Определим стагаенную матрицу Г как бесконечную таблицу коэффициентов е„г = г][г"]Г(г)"; а-й стаеаеноид (ромеготд) Г определяется как 1'„(х) = и„о + е„тх + + о„„х". Докажите, что степеноид удовлетворяет общему закону свертки Г.(х+ у) = Е~ "Ь'(х) Г.— (у) 1?т / (Например, когда Г(г) = г, получаем Ге(х) = х", и это биномиальнан теорема. Когда Г(г) = (п(1/(1 — г)), согласно 1.2.9 — (26) получаем тт„г = ['„'].
Следовательно, степеноид К,(х) равен х", и тождество совпадает с результатом, доказанным в упр. 1.2.6 — ЗЗ. Когда 1г(х) = е' — 1, получаем 1~,(х) = 2 (")х и данная формула эквивалентна равенству которого ранее у нас не было. Другие треугольные таблицы казффициентов, которые возникают в комбинаторной математике и анализе алгоритмов, такксе оказываются степенными матрицами степенных рядов.) 18. [НМЯ2) Продолжая упр. 17, докажите, что степеноид также удовлетворяет уравнению х1'„(к+ у) = (х+ у) ) 1ь(х) г'„-ь(у).
16 — 1/ [Указание. Рассмотрите производную е Р1.) 16. [М25) Продолжая упр. 17, выразите все числа а„ь в терминах чисел о = и„~ = н! Ъ'„ первого столбца и найдите простую рекуррентную формулу, которая позволит получить все столбцы из последовательности им оз, .... В частности, покажите., что если все и„— целые, то все иьь также целые. 20. [ВМЯЛО) Продолжая упр.
17, предположим, что И'(х) = 17((г(х)) и Пе = О. Докажите, что степенная матрица И' равна произведению степенных матриц 1' и П: ш„ь = ) и„„и ь. ° 21. [НМ27) Продолжая предыдущее упражнение, предположим, что $'~ ЗЬ О, и пусть Иг(з) = — 1ч О(-х). Назначение данного упражнения — показать, что степенные матрицы 1' и И' "двойственны" одна другой; например, когда У(х) = 1п(1/(1 — з)), то И '1(х) = 1 — е *, И'(з) = е' — 1 и соответствующие степенные матрицы — это хорошо известные треугольники Стирлипга и„ь = [„") и ш„ь = (").
а) Докажите, что формула обращения 1.2.6-(47) для чисел Стирлинга обычно выполняется в более общем случае: ) и ешь ( — 1) ж) шньиь ( — 1)" =б ь Ь) Из соотношения ещ„щ = нй[х") (1'(х)/х)" ~ для фиксированных к следует, что величина и„ы Ю/)г," является полиномом ат п степени ( 26. Позтому можно определить а 1 ь1 =а [х ) (г(х)/х) для произвольного о, когда ?г — неотрицательное целое число, как было определено для чисел Стирлинга в разделе 1.2.6.
Докажите, что а1 ьд „~ — — ш„ь. (Это обобщение формулы 1.2 6-(56).) ь 22. [НМЯ7) Задан ряд П(х) = 7?а+1?~х+ П~~~ -~- с Па ЗЬ 0; а-~ндуиир еаннал функция (71 1(з) -- зто степенной ряд У(х), полностью определенный уравнением 1'(з) = П(х?г( )") . а) Докажите, что ГГ1~1(х) = 17(х) и (71~16з1(х) = П1а+Л1(з).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
