*4.7. ОПЕРАЦИИ СО СТЕПЕННЫМИ РЯДАМИ

Если ЗАДАНЫ два степенных ряда

U{z) = Uo + UiZ + U2z + -, V{z) = Vo + Viz + V2Z + --- (1)

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

Безусловно, только конечное число членов можно представлять и хранить в компьютере. В таком случае уместно спросить: "Какая арифметика степенных рядов возможна на компьютерах, и, если возможна, чем она от:к1чается от арифметики полиномов?". Ответ таков: "Мы работаем только с первыми Л коэффициентами степенных рядов, где Л - параметр, который, в принципе, может быть произвольно большим. Вместо обычной арифметики полиномов мы, по существу, используем арифметику по модулю z, что часто приводит к различным точкам зрения. К тому же отдельные операции наподобие "обращения" можно выполнять со степенными рядами, но не с полиномами, так как полиномы не замкнуты относительно этих операций".

Операции со степенными рядами находят много применений в численном анализе, но, возможно, наиболее важным является нахождение асимптотического разложения (как видно из раздела 1.2.11.3) или вычисление некоторых величин, определяемых производящими функциями. Именно последние, а не арифметика с плавающей точкой, делают их удобными для точного вычисления коэффициентов. Все алгоритмы данного раздела, кроме очевидных исключений, можно выполнять только с использованием рациональных операций. Таким образом, методы из раздела 4.5.1 можно будет применять для получения точных результатов, когда потребуется.

Вычисление W{z) = U{z) ± V{z), конечно, тривиально, поскольку Wn - [z"] W{z) - UnVn для n = О, 1, 2, .... Так же легко вычислить коэффициенты W{z) = UizViz), воспользовавшись хорошо известным правилом свертки

Wn = Y. = 0" + C/i Уп-1 + • + UnVo. (2)

fc=0

Отношение Wz) = U{z)lV{z), когда Vo ф О, можно получить, если поменять местами С/ и W в (2). Таким образом, получим правило

fc=0

= (f/„ - WoVn -W,Vn-i-----Wn-iV,)IVo. (3)

Это рекуррентное соотношение для Wk позволяет легко последовательно вычислить Wq, Wi, W2, не вводя С/„ и V„ до вычисления Wn-i- Алгоритм с такими свойствами, оперирующий степенными рядами, обычно называют интерактивным {online). С его помощью можно определить N коэффициентов Ио, Wi, Wn-i, не зная заранее Л. Значит, можно, в принципе, выполнять алгоритм, как угодно

долго, и полиостью вычислять степенные ряды. Можно также выполнять интерактивный алгоритм до тех пор, пока не будет соблюдено любое требуемое условие. (Противоположность "online" - "offline" ("автономный").)

Если коэффициенты Uk ч Vk - целые, а Wk - не целые, рекуррентное соотношение (3) включает вычисления с дробями. Этого можно избежать, если воспользоваться полностью целочисленным подходом, предложенным в упр. 2.

Рассмотрим операцию вычисления W{z) = (z)", где а-"произвольная" степень. Например, можно вычислить квадратный корень из V{z) при а = или найти V{z)~° либо даже V{zy. Если Vm - первый не равный нулю коэффициент V{z), получаем

Viz) = VmZ"4l + iVm+l/Vm)z + (V+z/Kn) + •••),

F(Z)- = 1С ""(1 + iVm+l/Vm)z + iVm+2/Vm)z + •)"•

Это выражение будет степенным рядом тогда и только тогда, когда am - неотрицательное целое число. Из (4) следует, что задачу вычисления произвольных степеней можно свести к случаю, когда Vq = I, т. е. к вычислению коэффициентов:

Wiz) = il + Viz + V2Z+ V3Z+ )". (5)

Очевидно, что Wo = 1 = 1.

Естественным методом нахождения коэффициентов выражения (5) является использование биномиальной теоремы 1.2.9-(19) или (если а - положительное целое число) методов из раздела 4.6.3. Но Леонард Эйлер открыл более простой и более эффективный метод получения степеней степенных рядов [Introductio in Analysin Iniinitorum 1 (1748), §76]: если W{z) = V{z)°, то, дифференцируя, получим

Wi + 2W2Z + SWsz + ... = Wiz) = aViz)~V{z); (6)

следовательно,

Wiz)Viz) = aWiz)V{z). (7)

Составив уравнение для коэффициентов при в (7), получим, что

"kWkVn-k = - f)WkVn-k, (8)

fc=0 »:=0

а это дает удобное правило вычислений, справедливое для всех п > 1: а+1

= {{a+l-n)ViWn-i + i2a+2-n)V2Wr,-2 + + naVnWo)/п. (9)

Из соотношения (9) можно получить простой интерактивный алгоритм для последовательного определения Wi, W2, ..., используя приблизительно 2п умножений для вычисления п-го коэффициента. Отметим особый случай, когда а = -1; (9) становится частным случаем (3) при [/(z) = Vq = 1.

Аналогичные методы можно использовать для образования f{V{z)), когда / - любая функция, удовлетворяющая простому дифференциальному уравнению (см., например, упр. 4). Для решения дифференциальных уравнений часто используется сравнительно прямой "метод степенных рядов". Он приводится почти во всех учебниках по дифференциальным уравнениям.

Обращение рядов. Возможно, наиболее интересным преобразованием степенных рядов является обращение рядов. Это преобразование позволяет решить уравнение

z = t + V2t + V3t + V4t + (10)

относительно t, т. е. получить коэффициенты степенного ряда

t = z + W2Z + \¥зг + + . (11)

Известны особо интересные способы выполнения такого обращения. Можно сказать, что "классический" метод основан на замечательной формуле обращения Лагранжа [Memoires Acad. Royade des Sciences et Belles-Lettres de Berlin 24 (1768), 251-326], устанавливающей, что

Wn = [t"-i](l +Fit+ + •••)""• (12)

Например, имеем (1 - t)~ = (4) + {l)t + {)t + , тоща, пятый коэффициент, W5, обращения z = t - t равен {\)/5 = 14. Это проверяется с помощью формулы перечисления бинарных деревьев, приведенной в разделе 2.3.4.4.

В соотношении (12), которое имеет простое алгоритмическое доказательство (см. упр. 16), показано, что можно обратить ряд (10), если последовательно вычислять отрицательные степени (1 + Уг* + Уз* + •)"" ДЛя п = 1, 2, 3, Непосредственное применение этой идеи должно привести к интерактивному алгоритму обращения, который использует около N/2 умножений для вычисления N коэффициентов, но соотношение (9) предоставляет возможность работать только с первыми п коэффициентами (1-ьУг*+Уз*Н-)~" получаемыми интерактивным алгоритмом, которому требуется лишь около Л/6 умножений.

Алгоритм L {Обращение степенного ряда методом Лагранжа). В этом интерактивном алгоритме (рис. 17) вводится значение У„ из (10) и выводится значение Wn из (11) для п = 2, 3, 4, N. (Нет необходимости заранее знать точное число N; алгоритм можно завершить в соответствии с любым критерием.) L1. [Инициализация.] Присвоить п <- l,Uo 1. (Соотношение

(1 -t- V2t + Уз* -f • •)~" = fo + f/it -t- • + f/„- it"- -t- 0(t") (13) сохраняется на все время работы алгоритма.) L2. [Ввод Vn] Увеличить п на 1. Если п > N, работа алгоритма завершается, иначе - ввести следующий коэффициент У„.

L3. [Деление.] Присвоить Uk Uk - Uk-iV2-----UiVk - UoVk+i для = 1, 2, ...,

n - 2 (в таком порядке); затем присвоить

Un-i -2[/„ гУ2 - 3[/„ зУз-----(п - l)f/iy„ i - nUoVn.

(в результате получаем U{z), деленное на V{z)/z, см. (3) и (9).) L4. [Вывод Wn] Вывести Un-i/n, которое равно Wn, и возвратиться к шагу L2.