для всех п. Кроме того, можно даже воспользоваться (20), чтобы определить £7" для нецелых значений п. Например, "полуитерация" J l -это такая функция, что f/I/l ( (г)) = U{z). (Существуют две такие функции J/t/J, полученные в результате использования у/й и -л/й в качестве значения и/" в (20).)

Мы получили простые соотношения в (20), которые, начиная с V и и, определяют и. Но на практике обычно применяется другой метод: начиная с некоторой заданной функции U, найти такие V и и, чтобы выполнялось (19), т. е. чтобы

V{U{z)) = uV{z). (21)

Такая функция V называется функцией Шредера JJ, поскольку она была введена Эрнстом Шредером (Ernst Schroder, Math. Annalen 3 (1871), 296-322). Рассмотрим задачу нахождения функции Шредера V{z) = z + V2z + • заданного степенного

ряда и = Uiz + UiZ Н----. Очевидно, что u = Ui, если выполняется (21).

Подставив в (21) и = Ui и собрав коэффициенты при г, придем к последовательности уравнений, начинающихся с

UtV + ZUlUV + 2C/1C/3F2 + UlV + C/4 = C/1F4

и т. д. Ясно, что не существует решения, когда [/ = О (кроме тривиального случая, когда f/2 = = • = 0), но существует единственное решение, если Ui не является корнем из единицы. Можно предположить, что произойдет что-нибудь забавное, когда Ui = 1, так как из (20) видно, что U\z) = z, если функция Шредера в этом случае существует. Предположим на минуту, что Ui не равно нулю и не равно корню из единицы. Тогда функция Шредера существует и возникает следующий вопрос: "Как ее вычислить, не прилагая слишком много усилий?".

Следующая процедура предложена Р. П. Брентом (R. Р. Brent) и Ж. Ф. Траубом (J. F. Traub). Уравнение (21) приводит к подобной подзадаче, но более сложного вида. Таким образом, мы поставили более общую задачу, подзадача которой имеет такой же вид. Попытаемся найти V{z) = Уо + Viz Н-----h Vn-iz"~, такое, что

V{U{z)) = W{z)V{z) + S{z) + 0(2"), (22)

где U{z), W{z), S{z) и n заданы, n - степень двойки и J7(0) = 0. Для n = 1 просто положим Уо = 5(0)/(1 - W{0)) с Уо = 1, если S{0) = О и W{0) = 1. Кроме того, возможен переход от п к 2п: сначала найдем R{z), такое, что

V{U{z)) = W{z)V{z) + S{z) - zR{z) + 0(2"), (23)

затем вычислим

W{z) = W{z) {zlU{z)Y + 0(2"), S{z) = R{z) (2/C/(2))" + 0(2") (24)

и найдем V{z) = У„ + Vn+iz H-----h У2п-1.г"", такое, что

V {U{z)) = W{z)V{z) + S{z) + 0(2"). (25)

Следовательно, функция V*{z) = У(2) + z"V{z) удовлетворяет У* {U{z)) = Wiz)V*{z) + S{z) + 0(2"),

что и требовалось.

Время работы данной процедуры Г(п) удовлетворяет соотношению

Г(2п) = 2Г(п) + С{п), (26)

где С{п) - время вычисления R{z), W{z) и S{z). Функция С(п) отнимает основное время при вычислении V{U(z)) по модулю z" порядок роста С(п) предположительно больше, чем п+; следовательно, решение Г(п) рекуррентного соотношения (26) будет иметь порядок С(п). Например, если С(п) = сп, получим Г(п) и сп

или, если С{п) равно 0(п logп), с помощью "быстрой" композиции получим Г(п) = 0(п log п)3/2.

Процедура не работает, когда W{0) = 1 и 5(0) ф О, поэтому необходимо исследовать, когда это происходит. Легко доказать индукцией по п, что решение (22) согласно методу Брента-Трауба влечет рассмотрение точно п подзадач, в которых коэффициенты V{z) правой части уравнения принимают соответствующие значения W{z){z/U{z)) +0{z"-) для О < j < п в некотором порядке. Если И(0) = Ui hUi - не корень из единицы, получаем И(0) = 1 только тогда, когда j = 1; в этом случае процедура не работает, если (22) не имеет решения для п = 2.

Следовательно, функцию Шредера для U можно найти, решая уравнение (22) для п = 2, 4, 8, 16, .. .с W{z) = ill и S{z) = О, всякий раз, когда Ui не равно нулю и не является корнем из единицы.

Если Ui = 1, функция Шредера не существует, кроме случая, когда U{z) - z. Однако Брент и Трауб сумели найти быстрый метод вычисления ?7"](2), даже когда (/1 = 1, благодаря использованию функции V(z), такой, что

V{V{z)) = V\z)V{z). (27)

Если обе функции (г] и lJ(z) удовлетворяют (27) для тех же V, легко проверить, что их композиция U{U{z)) также удовлетворяет (27); следовательно, все итерации U{z) являются решениями (27). Предположим, вьшолняется равенство U{z) =

z + Ukz + f/4+iz*+ -I----, где к > 2 и Uk ф 0. Тогда можно показать, что существует

единственный степенной ряд вида V{z) = z + Vk+iz + 14+2*+ + • • •, который Здовлетворяет (27). Значит, если задана такая функция V{z) и если заданы к > 2 и Uk, существует единственный ряд вида U{z) = z + Ukz + (7fc+iz*-+ Н----, удовлетворяющий (27). Требуемая итерация U\z) является единственным степенным рядом P{z), удовлетворяющим

V{P{z))=P4z)V{z), (28)

где P{z) = z + nUkZ* Н----. Обе функции, V{z) и P{z), можно найти с помощью

подходящих алгоритмов (см. упр. 14).

Если Ux-к-й корень из единицы, не равный 1, то такой же метод можно применить к функции (7*!(г) = z + и U\z) можно найти из U{z), произведя 1{к) операций композиции (см. раздел 4.6.3). Можно также рассмотреть случай,

когда Ux - 0: если U{z) = Uk z + f/fc+iz*+ Н----, где > 2 и О, то идея состоит

в том, чтобы найти решение уравнения ((/(г)) = UkV{zY. Тогда

C/W(z) = 1/1-1] (C/f"->(-V(z)="). (29)

и наконец, если U{z) = Uo + Uiz н----, где Uo ф О, пусть а- "неподвижная точка",

такая, что U(а) = а, и пусть

U{z) = С/(а + 2) - а = zUipt) + zU"{a)l2\ + • • . (30)

Тогда f/I"l(2) = i/I"5(2 - а) + а. Детали можно найти в работе Brent and Traub, SICOMP 9 (1980), 54-66. Функция V из (27), по существу, рассмотрена в книге М. Kuczma, Functional Equations in a Single Variable (Warsaw: PWN-Polish Scientific, 1968), лемма 9.4, и, безусловно, Э. Жаботинским (Е. Jabotinsky) на несколько лет раньше (см. упр. 23).

Алгебраические функции. Коэффициенты каждого степенного ряда W{z), удовлетворяющего общему уравнению вида

An{z)W{zr + + Ai{z)W{z) + Ao{z) = О, (31)

где каждое Ai{z) - полином, можно эффективно вычислить методом, предложенным в работе Н. Т. Kung and J. F. Traub, JACM 25 (1978), 245-260. См. также работу Д. В. Чудновского и Г. В. Чудновского (D. V. Chudnovsky and G. V. Chud-novsky, J. Complexity 2 (1986), 271-294; 3 (1987), 1-25).

УПРАЖНЕНИЯ

1. [MIO] в разделе объяснено, как разделить {7(г) на У(г), когда Уо # 0. Как произвести деление, когда Vo = О?

2. [20] Когда коэффициенты U(z) и V{z) -целые и Уо 5 О, найдите рекуррентное соотношение для целых YgWri, где Wn определено в (3). Как можно этим воспользоваться для деления степенных рядов?

3. [М15] Будет ли правильным результат, приведенный в формуле (9), когда а = О и когда а = 1?

> 4. [НМ23] Покажите, что простая модификация (9) может быть использована для вычисления е, когда Уо = О, и In У(г), когда Уо = 1-

5. [МОО] Что произойдет, если степенной ряд обратить дважды, т. е. если выходные значения алгоритма L или Т обратить снова?

6. [М21] (X. Т. Кунг (Н. Т. Kung).) Примените метод Ньютона к вычислению W{z) = 1/У(г), когда У(0) ф О, определив корень в виде степенного ряда уравнения /(ж) = О, где fix) = х--Viz).

7. [М23] Воспользовавшись формулой обращения Лагранжа (12), найдите простое выражение для коэффициента Wn в обращении z - t -t".

*- 8. [М25] Для W{z) = Wiz + W2Z + Wzz + = Git + Gat + dt + = G(t), где г = Fit + Vit + Vit H----и Fi 51 0, Лагранж доказал, что

Wn = C?(t)/(yi + Fat + Уз* + •••)"

(Соотношение (12) является частным случаем предыдущего, когда Gi = Fi = 1, G2 = G3 = • • =0.) Расширьте алгоритм L таким образом, чтобы для данной более общей Ситуации он вычислял коэффициенты W\, W2, ... без значительного увеличения времени работы алгоритма.

9. [11] Используя алгоритм Т, найдите значения Тт.п как первые пять коэффициентов обращения z = t - .