ПРОГРАММИРОВАНИЕ, 2008, № 4, с. 3-7
— КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ОБ ОПОРНОМ СУММИРОВАНИИ*
© 2008 г. С. А. Абрамов1, М. Петковшек2
1 Вычислительный Центр им. A.A. Дородницына РАН 119991 Москва, ул. Вавилова, 40 2 Отделение математики факультета математики и физики Университет г. Любляны Ядранска 19, SI-1000 Любляна, Словения E-mail: abramov@ccas.ru, marko.petkovsek@fmf.uni-lj.si Поступила в редакцию 10.09.2007 г.
Рассматривается суммирование последовательных значений <p(v), <р(v + 1), . . ., <p{w) мероморфной функции p(z), где v,w Е Предполагается, что p(z) удовлетворяет линейному разностному уравнению Ь(у) = 0 с полиномиальными коэффициентами, и что для L существует суммирующий оператор (если такой оператор существует, то он может быть найден алгоритмом аккуратного суммирования или, в случае ord L = 1, алгоритмом Госпера). Вводится понятие опорного суммирования, охватывающего и тот случай, когда p(z) имеет полюсы в множестве Z.
1. ВВЕДЕНИЕ
Эта заметка ставит целью изложение в простой форме результатов статьи [1], касающихся так называемого опорного суммирования. Речь идет о возможности корректного использования дискретной формулы Ньютона-Лейбница для определенного суммирования после успешного построения суммирующего оператора с помощью алгоритма аккуратного суммирования [2] или алгоритма Госпера [3]. В детальных доказательствах, проведенных в [1], привлекается значительное число довольно абстрактных понятий. Потребовалось сформулировать и доказать также целый ряд вспомогательных утверждений. Это сделало статью [1] сложной для чтения. Вместе с тем можно допустить, что основные результаты статьи [1] представляют для компьютерной алгебры определенный практический интерес, и краткое изложение этих результатов без их сложных доказательств в этом смысле может быть полезным.
* Работа выполнена при частичной поддержке РФФИ, грант 07-01-00482-а, и MZT RS, грант J2-8549.
Ниже основные результаты статьи [1] даются в простых формулировках и иллюстрируются примерами. Доказательства могут быть найдены в [1].
2. СУММИРУЮЩИЕ ОПЕРАТОРЫ
Пусть Е - оператор сдвига: Е(/(к)) = /(&+ + 1) для последовательности /(к), к Е Ъ, и Е((р(г)) = <~р{г+1) для аналитической функции, г £ С. Пусть
Ь = а(1(к)Е(1 +■ ■■ + а1(к)Е + а0(к) е С(к)[Е].
Мы говорим, что оператор В, £ С(к)[Е] есть суммирующий оператор для Ь, если
(Е - 1)фК = 1 + МфЬ (1)
при некотором М 6 С(к)[Е]. Не нанося ущерба общности, мы можем предполагать, что огс! В, = = огс! Ь — 1 = с1 — 1:
К = г(1_1{к)Ед-1 + --- + г1{к)Е + г0{к) е С(к)[Е].
3. ДИСКРЕТНАЯ ФОРМУЛА НЬЮТОНА-ЛЕЙБНИЦА
Если суммирующий оператор существует, то он может быть найден алгоритмом аккуратного
суммирования [4] или, когда (I = 1, алгоритмом Госпера [3]. На первый взгляд, в том случае, когда В, £ С(к)[Е] существует, уравнение (1) дает возможность использовать дискретную формулу Ньютона-Лейбница (ДФНЛ)
ги — 1
£/(ао = </И-</И
к=у
для всех целых V < т и для любой последовательности / такой, что £(/) = 0, беря при этом д = Д(/). Казалось бы, мы можем применить обе части равенства (Е — 1)0Д = 1 + МфЬ к /:
и, положив д = Д(/), а также приняв во внимание, что £(/) = 0, вывести, что (Е — 1)д = /, или
(/(Л+1)-(/(*) = /(Л),
откуда
•ш —1 ги — 1
£/(*) = !>(*+ !)-*(*)) =
= - д{ы - 1) + д(т - 1)-
= дЫ - д(у)
(телескопический эффект).
Но было показано, что, если В, имеет коэффициенты, являющиеся рациональными функциями, у которых есть полюсы в то эта формула может давать неправильный результат (пример приводится ниже). Многие компьютерные реализации алгоритмов суммирования страдают этим недостатком.
Пример 1. Рассмотрим последовательность
(V)
№ = -
к равенству
ги — 1
4 к
которая удовлетворяет уравнению первого порядка 2(к + 1)(к-2)/(к + 1)-(2к-1)(к-1)/(к) =
2к(к + 1)
= 0. Алгоритм Госпера дает л[к) = —--,
ГЪ - 2
при этом последовательность /(к) определена для всех к £ Но применение ДФНЛ приводит
= ди/и - д(о)до) =
к=О
11}
(т - 2)4Ш
которое оказывается неправильным, коль ско-
( 2к-3\
ро мы предполагаем, что значение I I
равно 1 при к = 0 и равно —1 при к = 1 (как принято в комбинаторике). Правая часть дает верное значение суммы из левой части только при т = 1.
4. ОПОРНОЕ СУММИРОВАНИЕ
Предположим, что Ь применяется к аналитическим функциям, и
I = ай{г)Ел+-- ■ + а1{г)Е + а0{г) £ <ВД[Я]. (2)
Будем рассматривать суммирующий оператор (если он существует) в виде
К = гл_1{г)Е'1-1 + --- + г1{г)Е + г0{г) £ <ВД[Я].
Пусть <~р{г) - мероморфное решение уравнения Ь(у) = 0.
Оказывается, что, если <~р{г) не имеет полюсов в 2, то и не имеет полюсов в и мы можем использовать ДФНЛ для суммирования значений (р(к) при к = V, V + 1,..., т. То неприятное явление, которое обнаружено в примере 1, не может возникнуть в том случае, когда элементы суммируемой последовательности являются значениями (р(к), к £ аналитической функции <р(г), удовлетворяющей в комплексной плоскости С тому же самому разностному уравнению с полиномиальными коэффициентами, что и исходная последовательность в целых точках.
Сказанное следует из более сильного утверждения. Оказывается, что, даже если <~р{г) имеет полюсы в то, тем не менее, суммирование может быть в определенном смысле выполнено корректным образом. Для любого к £ Ъ функция <~р{г) может быть разложена в ряд Лорана
ф) = сКрк(г - к)Рк + сКрк+1{г - к)^+1 + ...
с рь £ 1 и Ск}Рк ф 0. Если Ь(<р) = 0, то в множестве всех рк, к £ существует минимальный элемент р. Это р мы назовем глубиной <~р(г) и обозначим через С свяжем после-
довательность /(к) такую, что /(к) = сь,Рк, если рк = р,ж /(к) = 0 в противном случае. Последовательность /(к) мы назовем опорой функции <~р(г) и обозначим ее через
Иллюстрацией служит следующий простой пример. Хорошо известно, что Г (г) имеет конечные значения для г = 1, 2,... и имеет простые полюсы для г = 0, —1, —2,... Мы получаем:
ск^ЦГ) = -1,
ОБ ОПОРНОМ СУММИРОВАНИИ Пример 1
что значение
(продолжение). Предположим, 2к - 3 4
к
определено как
Г (2* - 2)
lim . . . . , Г(г+ 1)Г(г - 2)'
(3)
что является естественным обобщением формулы
(2к — 3)!
2к-3
I *
на все к £ Z. Пусть
Ф) =
I к\(к — 3)! Г (2* - 2)
Y(z + l)Y(z-2)4z
bott(r)(к) =
(-1)
к+1
(-А-1)!'
если к > 0, если к < 0.
Если же мы рассмотрим Г (z) только в полуплоскости Re z > 0, то глубина функции будет равна 0, а ее опорой будет последовательность
т = (к~ 1)!, к = 1,2,...
Предложение 1. Пусть L(ip) = 0. Тогда L(bot%)) = 0.
Предложение 2. Пусть L(ip) = 0 и R - суммирующий оператор для L. Тогда depth (ср) = = depth (Д(<усз)).
Теорема 1 (об опорном суммировании). Пусть L(ip(z)) = 0 и R - суммирующий оператор для L. Пусть ф(г) = R(<~p(z)). Тогда при любых v < w справедлива формула опорного суммирования
w — l
Y^ bott(¥>)(&) = ЪоИ(ф)(т) - ЪоИ(ф)(у).
k=v
В частности, если <р не имеет полюсов в Z (т.е. depth> 0), то функция ф(г) не имеет полюсов в Z, и дискретная формула Ньютона-Лейбнииа
W— 1
<f (к) = ф(гг) - ф(у)
k=v
2z(z + 1)
Предел (3) существует для всех к £ Z, и depth((f) = 0. Теперь ДФНЛ дает правильный результат
Г(2к - 2)
W— 1
2w(w+ 1)Г(2ги - 2) (w - 2)T(w + 1)Г(ги - 2)4W '
w = 1,2,...
Вначале мы предполагали, что значением ( 2к - 3 '
I к ,
гда к = 1 (как принято в комбинаторике). Но
является 1, когда к = 0, и — 1, ко-
Г(2г-2) =1 *4*оГ(г+1)Г(г-2) 2Г
lim
Z
lim
Г(2г-2) 1
1Г(г + 1)Г(г-2) 2Г
справедлива для всех v < w.
В этом примере проступает конфликт между
комбинаторным и аналитическим определения-(р\
ми символа
V ч )
Пример 2. Функция <~р(г) = гГ(г + 1) удовлетворяет уравнению Ь(у) = 0, где Ь = гЕ—
~(г + 1)2. Мы имеем Е= -, ог<Ш = 0, ф(г) = = К(<~р)(г) = Т(г + 1). Очевидно, <~р(г) принимает конечные значения для г = 0,1,... и имеет
Z
простые полюсы при г = — 1, — 2,... Получаем: = = — 1 и
Ъои((р)(к) =
ЪоИ(ф)(к) =
' (-1 )к+1к (-к- 1)!' О,
(-1)
к+1
(-*- 1)1 О,
если к < О,
если к > О,
если /г < О, если к > 0.
Опорное суммирование дает
гю — 1 £
(-1)г
(-1)г
У^ к ■ к\ = ио\ —
VI.
к=у
где Ь = (г + 2)Е — г. Мы имеем: = —г—
— 1 и ф(г) = Д(^г) =--. Легко видеть, что
= = — 1 и
ЪоИ((р)(к) = ■ Ьо Ы(ф)(к) =
1, если к = 0,
— 1, если /г = — 1,
0 иначе,
— 1, если к = 0,
0 иначе.
Простая проверка показывает, что для любых
V < ги
¿;(-*-1)! (-то - 1)! (—V — 1)!
для любых V < т < 0; последнее равенство эквивалентно равенству
к (^Я ~ ^^ " ^2)!
для любых 1 < V < т.
Если мы рассмотрим <~р(г) в полуплоскости 11е г > 0, то = = 0, и мы бу-
дем иметь
ги — 1
]Г кТ(к + 1) = Т(ш + 1) -Г(и + 1)
к=у
для всех 0 < V < ги, или, что то же самое,
ги — 1
•ш —1
^ Ъои((р)(к) = Ьои(^)(то) - Ъои(ф)(у).
к=у
Если мы рассматриваем <~р(г) только в полуплоскости 11е,г > 0, то = = 0, и мы имеем:
У 1 _ 1 1
^ к (к + 1) ~ ю + V
при 1 < V < 1Ю.
Пример 4. Для оператора второго порядка
Ь= (г-3)(г-2)(г+1 )Е2--(г - 3)(г2 - 2г - 1)Е - (г - 2)2
существует суммирующии оператор первого порядка
Я = гЕ +
1
Уравнение вида Ь(у) = 0, где Ь имеет вид (2), всегда имеет ненулевое решение, мероморф-ное в С. Это следует из следующего результата ное решение такого вида. По нашей теореме
г - 3
Из теоремы 2 следует, что уравнение Ь(у) = 0 имеет решения, голоморфные в полуплоскости 11е г > 2. Обозначим через <~р(г) произволь-
М. Баркату и Ж.-П. Рамиса:
Теорема 2 [5]. Пусть Ь имеет вид (2), где ао(г) - ненулевой полином. Пусть константа с £ К такова, что вещественная часть любого из корней полинома ао(г) не превосходит с. Тогда уравнение Ь(у) = 0 имеет решение, голоморфное (т.е. аналитическое и не имеющее особенностей) в полуплоскости 11е г > с.
5. ДОПОЛНИТЕЛЬНЫЕ ПРИМЕРЫ
Пример 3. Рациональная функция <~р(г) = = —-—удовлетворяет уравнению Ь(у) = 0,
ДФНЛ должна давать правильный результат при 3 < V < т, несмотря на то, что один из коэффициентов оператора Я имеет полюс в г = 3.
Мы можем найти значения <~р(г) и ф(г) = = К(<~р)(г) при г = 3. Алгоритм из [2] дает
ф) = (4^(5) - 2^(4))(г- 3) + 0((г - З)2), г 3,
откуда <¿>(3) = 0, ф(3) = ¥'(4) + 4<^(5). Это значение ф(3) может использоваться в ДФНЛ при 3 = V < т:
ги — 1
У^ <р{к) = ги<р(ги + 1
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.