унимодулярную матрицу U, такую, что (ni,..., п»)!/ = (О,..., О, d), где d - gcd(ni,..., п). (Приведенный перед равенством 4.5.2-(14) алгоритм безоговорочно определил такую матрицу и.) Построим новую цепочку полиномов с входными значениями i/i, j/s-i следующим образом: сначала вычислим х - {xi,..., х,) = U{yi,..., ys~i,-0/d), затем продолжим вычисления с предполагаемой цепочкой полиномов для Vx. Когда достигнем шага i цепочки, получим = (щ,..., Па)х+Р = О, значит, можно просто положить А; = О, а не выполнять умножение. Затем вычисляем Vx и добавляем постоянный вектор wfi/d к результату, где w - наибольший правый столбец VU. Пусть W - s - 1 остальных столбцов VU. Новая цепочка полиномов вычисляет Vx + wfi/d = VU{yi,-.., j/s-i, -P/d) + wfi/d = W(j/i, • • • I J/s-i) с < - 1 умножениями. Однако столбцы W являются Z-независимыми согласно п. (а); следовательно, < - 1 > s - 1 по индукции по s и получаем t> s.

(c) Пусть Xj = О для t - S значений которых нет в Z-независимых столбцах. С пoю-щью любой цепочки для Vx вычисляем Vx для матрицы V, применив результаты п. (Ь).

(d) Al = ж - у, Аг = Al + Ai, Аз = Аг + ж, А4 = (1/6) х Аз, А5 = А4 + А4, Ае = As + у (= ж + у/3), Аг = Аб - Al, Xs = АГ + А4 (= ж/2 + у). Но для {ж/2 + у, ж + у/2} необходимы два умножения, поскольку столбцы (( j Z-независимы. [Journa/of Information Processing 1 (1978), 125-129.]

РАЗДЕЛ 4.7

1. Найдите первый не равный нулю коэффициент Vm, как в (4), и разделите U(z) и V{z) на 2™ (сдвигая коэффициенты на m мест влево). Отношение будет степенным рядом тогда и только тогда, когда Uo = = Um-i = 0.

2. Имеем Vo+HVn=VoUn-{VoWo){\-Vn}-{ViWl){V--Vn-l)-----(VoW-MV).

Тогда можно начать с замены {Uj,Vj) на {VUj,V VJ) для j >1, затем присвоить W„ ч-Un - Efc=o WkVn-k для n > О и наконец заменить Wj на Wj/o J - О- Подобная техника возможна в сочетании с другими алгоритмами данного раздела.

3. Да. Если а = О, то легко доказать индукцией, что Wi - W2 = - 0. Когда а = 1, найдем, что Wn = Vn согласно тождеству

[~l~)vkVn-k=VnVo.

4. Если W{z) = e, то W{z) = V{z)W(z); находим Wo = е»

Если W{z) = lnV{z), toVhW. меняются ролями. Значит, когда Vo = 1, устанавливается правило: Wo=OviWn = Vn + "Zklik/n - l)VkWn-k для n > 1.

[Используя упр. 6, коэффициент Wn для логарифма можно вычислить за O(nlogn) операций. Р. П. Брент (R. Р. Brent) заметил, что exp{V{z)) также можно вычислить асимптотически с такой же скоростью, применяя метод Ньютона к /(ж) = 1пж - У(г). Следовательно, обычное возведение в степень (1 + Viz))" = exp(aln(l + V{z))) также можно выполнить за O(nlogn) операций. См. Analytic Computational Complexity, edited by J. F. Traub (New York: Academic Press, 1975), 172-176.]

5. Получится начальный степенной ряд. Это можно использовать в качестве критерия алгоритма обращения.

е. (ж) = ж 4-ж(1 - xV{z)) (см. алгоритм 4.3.3R). Затем, когда Wo, Wn-i известны,

основная идея заключается во вводе Vn, .. •, V2N-1, вычислении {Wo Н-----h Wn-iz") х

(Vo-\-----\-V2N-1z} - 1 + До2Н-----hRN-iz"" +0{z") и использовании равенства

Wn + --- + W2n-iz- = -{Wo + --- + Wn-iz-){Ro + ---+Rn-iz~) + 0{z). [JVumer. Math. 22 (1974), 341-348; данный алгоритм, по существу, впервые опубликован в работе М. Sieveking, Computing 10 (1972), 153-156.] Заметим, что общие затраты на вычисление N коэффициентов равняются 0(iV log JV) арифметическим операциям, если использовать "быстрое" умножение полиномов (см. упр. 4.6.4-57).

7. Wn = (™*)/п, когда п = (т - l)ifc 4- 1; иначе -О (см. упр. 2.3.4.4-11).

8. G1. Ввести Gi и Vi; присвоить п ч- 1, t/o <- 1/Vi; вывести Wi = GiUo.

G2. Увеличить n на 1. Если п > N, работа алгоритма окончена; иначе - ввести Vn и Gn

G3. Присвоить f/fc ч- {Uk-Ej=i Uk-jVj+i)/Vi для А: = О, 1, ..., п-2 (в таком порядке),

затем присвоить Un-i <--ЕГ=2 kUn-kVkjVi.

G4. Вывести Wn = Ek=i kUn-kGk/n и возвратиться к шагу G2.

(Время работы алгоритма - порядка N; таким образом, оно увеличилось только относительно порядка N.)

Замечание. Алгоритмы Т и N определяют У(С/(г)), алгоритм данного упражнения определяет G{V\z)), что не одно и то же. Безусловно, все результаты можно получить, выполнив операцию обращения, а затем - композиции (упр. 11), но полезно иметь для каждого случая более прямой алгоритм.

9. п = 1 п = 2 п = 3 п = 4 п = 5

Tin 1 1 2 5 14

Tin 12 5 14

Tin 13 9

Г4„ 1 4

Пп 1

10. С помощью (9) получаем у" = x{l+aix+a2X+ -У" = x{l+cix+C2xA----) изатем

обращаем последние ряды. (См. замечание, следующее после уравнения 1.2.11.3-(11).)

11. Присвоить сначала Wo Uo, а затем - (Г*, Wk) (Vit, 0) для 1 < к < N. После этого для п = 1, 2, ..., JV выполнить следующие операции: присвоить сначала Wj <- Wj + UnTj для n<j<N,a затем -Tj ч- Tj-iVi + + TnVj~n для j = JV, JV - 1, ..., n -f-1.

Здесь вместо T{z) стоит V{z). Можно построить интерактивный алгоритм степенных рядов для этой задачи, аналогичный алгоритму Т, но потребуется около ячеек для хранения данных. Для выполнения данного упражнения также существует интерактивный алгоритм, которому необходимо только 0(JV) ячеек: можно предположить, что Vl = 1, если Uk заменить на UkV и Vk заменить на Vk/Vi для всех к. Тогда с помощью алгоритма L можно обратить V{z) и использовать его выходные данные в качестве входных данных в алгоритм упр. 8 с Gi = t/i, Сг = {2 и т. д. Тогда вычислим U{V~\z)) - Uo. (См. также упр. 20.)

Брент и Кунг построили несколько асимптотически быстрых алгоритмов. Например, можно вычислить и{х) для X = V{z) с помощью варианта алгоритма, который предложен в упр. 4.6.4-42(с), выполнив около 2\/N умножений в цепочке с M{N) или около Л змноже-ний параметров с количеством операций, равным JV, где M{N) - число операций, необходимых для умножения степенных рядов порядка N. Следовательно, общее число операций равно 0{VNM{N) + N) = O(N). Еще более быстрый метод может быть основан на тождестве U{Vo{z) + z"Viiz)) = U{Vo{z)) + z"U{Vo{z))Vi(z) + z"U"{Vo(z))Vi(zf/2l + -- , включающем около JV/m членов, из которых выбираем m й: у/N/log л. Для вычисления первых членов U{Vo{z)) потребуется 0(mJV(log JV)) операций, если использовать метод.

отчасти подобный рассмотренному в упр. 4.6.4-43. Так как перейти от [/<°(Vb(z)) к (7(=+i)(Vo(2)) можно за 0{NlogN) операций, выполнив дифференцирование и деление на Vo{z), то полностью процедура будет содержать OimNilogN) + (N/m) N log N) = 0{N log Nf/ операций. [JACM 25 (1978), 581-595.]

Когда полином имеет целые коэффициенты, состоящие из т двоичных разрядов, данный алгоритм включает приблизительно N1+ умножений чисел, содержащих {Nlgm) двоичных разрядов. Таким образом, общее время работы алгоритма больше N. Альтернативный подход с асимптотическим временем счета 0{N) развит в работе Р. Ritzmann, Theoretical Сотр. Sci. 44 (1986), 1-16. Композиция может выполняться быстрее по модулю малого простого числа р (см. упр. 26).

12. Деление полиномов тривиально, кроме случая, когда m > n > 1. В последнем случае уравнение и{х) = q{x)v{x) + г{х) эквивалентно уравнению U{z) = Q{z)V{z) + z~"R{z), где U{x) = x"u(x-i), ¥{х) = x"w(x-i), Q{x) = x"-"g(x-) и R{x) = x"-V(x-i) - "обратные" полиномы от u, t;, g и г.

Чтобы найти g(x) и r{x), вычислим первые m - n -f-1 коэффициентов степенного ряда lJ{z)IV{z) = И/(г) 4-0(г"-"+), затем вычислим степенной ряд U{z) - V{z)W{z), который

имеет вид z"""r(z), где T{z) = Го + T\z Л----. Заметим, что Г,- = О для всех j > п,

следовательно, Q{z) = W{z) и R{z) = T{z) удовлетворяют требованиям.

13. Используем упр. 4.6.1-3 с и(г) = и v{z) = Wo + + Ожидаемые аппроксимации - это значения V3{z)/v2{z), полученные, конечно, с помощью алгоритма. Из упр. 4.6.1-26 следует, что не существует дополнительных возможностей со взаимно простыми числителем и знаменателем. Если каждое Wt-целое, то алгоритм 4.6.1С, примененный ко всем целым числам, будет обладать требуемыми свойствами.

Замечание. Те, кого интересует более полная информация, могут обратиться к книге Claude Brezinski, History of Continued Fractions and Fade Approximants (Berlin: Springer, 1991). Случай, когда = 2n 4- 1 и deg(«;i) = deg(«;2) = n, в частности, представляет интерес, поскольку он эквивалентен так называемой системе Теплица. Асимптотически быстрые методы для систем Теплица рассмотрены в работе Bini and Pan, Poiynomiai and iVfatrix Computations 1 (Boston: Birkhauser, 1994), §2.5. Метод, предложенный в этом упражнении, можно обобщить на произвольную рациональную интерполяцию вида W(z) = p{z)/q{z) (по модулю {z - z\)... (z - Zn)), где z, необязательно должны быть различны. Таким образом, можно точно определить значения W{z) и несколько их производных в нескольких точках (см. работу Richard Р. Brent, Fred G. Gustavson, and David Y. Y. Yun, J. Algorithms 1 (1980), 259-295).

14. Если U{z) - z + Ukz 4- • • • и V{z) = z* 4- Vlt+iZ*" 4- • , находим, что разность V{U{z)) - и {z)V{z) равна Ej>x z~j{UkVk+j - Uk+j + (полином включает только Uk,..., Uk+j-i, Vk+i,..., Vk+j-i)). Следовательно, V(z) определен единственным образом, если задан U{z), как и U{z), для заданных V{z) и Uk.

Решение зависит от двух вспомогательных алгоритмов; первый из них позволяет решить уравнение V{z 4- z*[/(z)) = (1 4- z-W{z))V{z) 4- 2*"5(г) 4- 0(z*-+") для

V{z) = Vo 4- Viz 4----4- Vn-iz"~, где U{z), W{z), S{z) и n заданы. Если n = 1, положим

Vo = -S{0)/W{0) или выберем Vo произвольно, когда S(0) = W{0) = 0. Перейдем от n к 2n. Пусть

V{z + zUiz)) = (14- z-W{z))V{z) 4- z>-S{z) - z-+"R{z) + 0(z=-+2"), 1 4- z-Wiz) = {z/{z 4- z*t/(z)))"(l 4- z-Wiz)) 4- 0(z*-+"), S{z) = (z/iz 4- zU{z)))Riz) + 0(z")