10. [М20] Задано у = ж° + aix°+ + а2Ж°+ + а ф 0. Покажите, как вычислить

коэффициенты в разложении х = у" + Ь2У" + Ьзу° Н----•

* 11. [М25] (Композиция степенных рядов.) Пусть

U{z) = Uo + Uiz + U2Z + --- и V{z) = Viz + V2z + V3Z + ---.

Составьте план алгоритма, который вычисляет первые N коэффициентов U{V{z)).

12. [М20] Найдите связь между делением полиномов и делением степенных рядов. Заданы полиномы и{х) и v{x) степеней тип соответственно над полем. Покажите, как найти полиномы q{x) и г(х), такие, что и{х) = q{x)v{x) + г{х) и deg(r) < п, используя только операции со степенными рядами.

13. [М27] (Аппроксимация рациональных функций) Иногда необходимо найти полиномы, отношения которых имеют такие же начальные члены, как и данные степенные ряды. Например, если W(z) = 1 + z + 3z + 7z то существует четыре различных способа представления W(z) в виде wi(z)/w2(z) + O(z), где wi(z) и W2(z)-полиномы с deg(wi) -t-deg(w2) < 4:

(l+z + 3z + 7z) /l = l+z + Зz + 7z+0z + ,

(3 - 4z + 2z) / (3 - 7z) = 1 + z + 3z + 7z + fz + ,

(l-z)/(l-2z-z) = l + z + 3z + 7z + \7z* + ,

l/(l-z-2z - 2/) = l + z + 3z+ 7z + ISz" + • •.

Рациональные функции такого рода обычно называют аппроксимацией Ладе, так как они широко изучены Г. Е. Паде (Н. Е. Pade) [AnnaJes Scient. de IEcole Normale Superieure (3) 9 (1892), S1-S93; (3) 16 (1899), 395-426].

Покажите, что все аппроксимации Паде W(z) = wi(z)/w2(z) + O(z) с deg(wi) + deg(w2) < N можно получить, применяя обобщенный алгоритм Евклида к полиномам z и Wo + W\Z+--- + Ил 1г-\ и составьте целочисленный алгоритм для случая, когда каждое Wi-целое. [Указание. См. упр. 4.6.1-26.]

14. [НМЗО] Используя (27) и (28), запишите подробно метод вычисления t/"(z) Брента и Трауба, когда U(z) = z+ Uk z Л----.

15. [HM20] Какой вид должна иметь функция U(z), если в (27) V(z) имеет простую форму г*? Какой вывод можно сделать относительно итераций U(z)!

16. [НМ21] Пусть, как в упр 8, W(z) = G(t). "Очевидный" метод нахождения коэффициентов Wi, W2, W3, таков: присвоить п -\ и Rx(t) +- G(t), а затем сохранить соотношение WnV(t) + Wn+iV(t) Н----= Rn(t), неоднократно присваивая Wn [t]Rn(t)IV\,

Rn+i(t)+-Rn(t)/V(t)-Wn,ni-n + l.

Докажите формулу Лагранжа из упр. 8, показав, что

-[t"-]Rk+i(t)t"/V(t) = -[e]Rk(t)t"+/V(t)"- для всех п > 1 и > 1.

17. [М20] Задан степенной ряд V(z) = V\Z + V2z + ViZ Н----. Определим степенную

матрицу V как бесконечную таблицу коэффициентов Vnk = fl[г"]У(г); п-й степеноид

(poweroid) V определяется как Vn(x) = Vno + Vnix Н-----1- Vnnx". Докажите, что степеноид

удовлетворяет общему закону свертки

K.(x-t-y) = Xl(fc)*()"-*(2/)-

(Например, когда V(z) = z, получаем Vn(x) = ж", и это биномиальная теорема. Когда V(z) = ln(l/(l - z)), согласно 1.2.9-(26) получаем v„k - [Д. Следовательно, степеноид

Vn{x) равен ж", и тождество совпадает с результатом, доказанным в упр. 1.2.6-33. Когда

Г"! LfcJ

V{z) = е - 1, получаем V„(x) = {fc}* и данная формула эквивалентна равенству

{;т){,:„]-пж]гл

которого ранее у нас не было. Другие треугольные таблицы коэффициентов, которые возникают в комбинаторной математике и анализе алгоритмов, также оказываются степенными матрицами степенных рядов.)

18. [НМ22] Продолжая упр. 17, докажите, что степеноид также удовлетворяет уравнению

xV„(x + y) = (x + y)("J)Ffc(x)K fc(y).

[Указание. Рассмотрите производную е*".]

19. [М25] Продолжая упр. 17, выразите все числа vnk в терминах чисел vn - vni = п\ V„ первого столбца и найдите простую рекуррентную формулу, которая позволит получить все столбцы из последовательности vi, v2, ... . В частности, покажите, что если все vn - целые, то все vnk также целые.

20. [НМ20] Продолжая упр. 17, предположим, что W{z) - U{V{z)) kUq -0. Докажите, что степенная матрица W равна произведению степенных матриц V kU: wnk = Ylj vnjujk-

> 21. [HM27] Продолжая предыдущее упражнение, предположим, что vi ф О, и пусть W(z) = -г). Назначение данного упражнения - показать, что степенные матрицы V и W "двойственны" одна другой; например, когда V{z) = ln(l/(l - z)), то У~(г) = 1 - е~, W{z) = - 1 и соответствующие степенные матрицы - это хорошо известные треугольники Стирлинга vnk ~ [] и wnk = {}-

a) Докажите, что формула обращения 1.2.6-(47) для чисел Стирлинга обычно выполняется в более общем случае:

Y vnku)km{-l)"~ = Y "nkvkm{-l)"~ = smn . к к

b) Из соотношения v„„-k) = n-[z*] (F(z)/z)"~ для фиксированных к следует, что величина vn(n-k)/Vx является полиномом от п степени < 2к. Поэтому можно определить

v-k)=cxHz]{V{z)zУ

ДЛЯ произвольного а, когда к - неотрицательное целое число, как было определено для чисел Стирлинга в разделе 1.2.6. Докажите, что v..k)-n) = wk. (Это обобщение формулы 1.2.6-(58).)

22. [НМ27] Задан ряд U(z) - Uq + U\z + u2z Н----с Uo ф 0; а-индуцированная функция

C/{"}(z) - это степенной ряд V{z), полностью определенный уравнением

Viz) = U(zV{zr).

a) Докажите, что U°Hz) = Uiz) и t/<">>(z) = П+Цг).

b) Пусть B(z)-простой биномиальный ряд 1 -f- г. Где раньше встречалось B(z)?

c) Докажите, что [г"] {7°}(z) = [z"] г7(г)+"". Указание. Если \¥{г) = z/Uiz)°,

то получим г7">(2) = (1У-Ч(2)/2)1/".

d) Докажите, следовательно, что любой степеноид Vnix) удовлетворяет не только равенствам из упр. 17 и 18, но и равенствам

[х + у)Уп{х + у + па) y/7г\жFfc(ж+fcQ) уУп-к{у+{п-к)а) х + у + па \к) х + ка у+[п - к)а

Уп{х + у)

У - па

, , (п-\\Уи{х-\-ка) Уп-к{у-ка) = ( + y)l[k-l)-rn--у-ка

[Частные случаи включают биномиальную теорему Абеля, формулу 1.2.6-(16) и равенства Рота 1.2.6-(26) и 1.2.6-(30): сумму Торелли, упр. 1.2.6-34.]

23. [НМЗЗ] (Э. Жаботинский.) Продолжая в том же духе, предположим, что {/ = (itnfc) - степенная матрица U{z) = z + Uuz -i----. Пусть Un = Uni = nlUn.

a) Объясните, как вычислить матрицу InU, чтобы степенная матрица t/"(z) равнялась ехр(а In г7) = / + а In {/+ (а In г7)72! + •.

b) Пусть Ink -элемент матрицы In U, находящийся на пересечении строки п и столбца к, и пусть

1п=1пг, L(z) = l2+h+l4 + ---.

Докажите, что Ink = для I < к < п. [Указание. Uz) = z + eL{z)+0{e).]

c) Рассмотрите U°\z) как функцию от а и z и докажите, что

(Следовательно, Ь{г) = {1к/к\)У{г), где У{г) - функция в (27) и (28).)

d) Покажите, что, если uj ф О, числа можно вычислить по рекуррентной формуле

12= U2, ,. ]lkUn+l-k - yJkUnk

к = 2 к=2

Как следует использовать данную рекуррентную формулу, когда U2 = О?

e) Докажите равенство

п-1 ,

En! По П1 Пт-1 , , , -Г / Т~\Т~\--~1-г l*2 • -fcrn I

n j i , l- =2! km\

m=0 fciH-----\-km=n+m-l

ki,...,k„>2

где щ = l + kx +.....!• kj -j.

24. [HM25] Задан степенной ряд U(z) = UiZ + U2Z + где Ui не равно корню из единицы. Пусть U = (Unk) - степенная матрица U{z).

a) Объясните, как вычислить матрицу In С/ таким образом, чтобы степенная матрица U°\z) равнялась ехр(а In t/) = / -Ь а In ?7 + (а In {7)V2! + .

b) Покажите, что если W{z) тождественно не равно нулю и если U{W{z)) = W{U{z)), то W{z) = {/"(г) для некоторого комплексного числа а.

25. [М24] При Uiz) = z + Ukz" + C/fc+iz+i + • • и У{г) = z + V,z + Vi+iz+ + •, где > 2, Z > 2, г7к # О, F, # О и U{Viz)) = У (Uiz)), докажите, что = Z и y{z) = UM{z) для

a = Vk/Uk.

26. [M22] Покажите, что, если U{z) = Uq + Uiz + U2Z • • • и У{г) = ViZ + V2Z +----степенные ряды, все коэффициенты которых равны либо О, либо 1, можно получить первые N коэффициентов U{V{z)) по модулю 2 за 0{N) шагов для любого б > 0.