ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 462, № 2, с. 137-140
= МАТЕМАТИКА =
УДК 517.521.15+519.651.1
БЫСТРЫЕ АППРОКСИМАЦИИ НЕКОТОРЫХ ТЕОРЕТИКО-ЧИСЛОВЫХ КОНСТАНТ
© 2015 г. Е. А. Карацуба
Представлено академиком РАН Ю.И. Журавлевым 17.06.2014 г. Поступило 18.11.2014 г.
БОТ: 10.7868/80869565215140042
На основе применения метода быстрого вычисления трансцендентных функций БВЕ (см. [1—11]) автором были построены быстрые алгоритмы вычисления дзета-констант, т.е. значений дзета-функции Римана ^(у) при целом аргументе у = п, п > 2 (см. [4, 6, 7]). Доказанная сложность вычисления близка к оптимальной. При этом использовалась либо известная эйлерова формула (см. [4]) значений дзета-функции ^(у) при четном аргументе у = 2п с участием коэффициентов Бер-нулли В2п:
,2я - 1 2
Z(2n) =
2n I n П |B2
( 2 n)!
z
k = 0
П + 1
(1)
Bk = 0, Bo = 1;
либо выведенная автором (см. [6, 7]) новая формула для ^(п) при любом целом п, п > 2:
nn
Z( n) = (П-1^ z (-1)i-1(i -1
(2)
i = 1
где
G = Z
ki + к2 + ■■■ + kn = i
k + 2 + ■.. + nkn = n
n!
n (jkj
k,\k2\... k,\и jJ
j = 1
Jj = Sj + 0-2
-N
S = z
i=0
(- 1)iN + 1 z j!
(i + 1)! „(i + 1 )m(j- m)!
m = 0 v 7
lnj - mN,
|0| < 1, r > 4N, N> 2nlog22n, n > 2, 1 < j < n.
С помощью метода БВЕ дзета-константы вычисляются по формулам (1), (2) с точностью 2-N за
O ( M( N) log2 N)
(3)
битовых операций, где Ы(Ы) — близкая к оптимальной сложность произведения двух ^-знач-ных чисел.
С другой стороны, в отличие от (1) формула (2) не дает непосредственного ответа на вопрос об арифметической структуре дзета-констант, так что вопрос об иррациональности значений дзета-функции Римана при любом нечетном аргументе остается открытым. Исключение составляет дзета-константа ^(3), иррациональность которой была доказана Апери (см. [12]). При этом Апери использовал быстро сходящийся к ^(3) знакопеременный ряд рациональных дробей (впервые эта формула была получена Марковым, см. [13]):
z(3) = 2z
(-И
k -1
2 - (2к *
В настоящей работе решается задача построения быстрых аппроксимаций дзета-констант рациональными дробями. Имеет место
Тео р е ма 1. Для любого целого к, к > 1, справедливы следующие соотношения для значений дзета-функции Римана четного и нечетного аргументов:
Z( 2k) = Zk + 2 z
(- 1 )n
(2n\ 2 — n
n=kI Jn m=o"
1 n J
k - 1 D P
z -^f-T-,, (4)
/ ' 2k - 2m - 2
Вычислительный центр им. А.А. Дородницына Российской Академии наук, Москва E-mail: ekar@ccas.ru
Z( 2k + 1) = Zk + 2 z
(2n\ з
k I In m
k - 1 z
d P
mm 2k - 2m - 2 '
(5)
n
30
r
GO
30
где
Р =
т п - q
П I
' 1, -Г, +1(п ~1<)''
^ q Jq + 1т + 1 = 0
т = 1, 2, ..., к - 1; Р0 = 1,
Бт = йт = (-1)т; т = 0, 1, 2, ..., к - 2;
к - ц л 1 2 п + 1
Бк -1 = (-1 )к -111 + -
йк -1 = (-1)
4 2п - У'
к -1 5 4,
1к = 1 + — + — + ... +-1-; к> 2;
22к 32к (к - 1 )2к
= 0,
гк = 1 + -1—. + +... + 1
22к + 1 32 к + 1
(к - 1)
2 к + 1'
к > 2;
^ = 0.
Доказательство. Схема доказательства теоремы такова. Для фиксированного к = г ряды Дирихле для
да да
«2г) = I 1' «2г + 1) = I ^
1 = 11
1 = 1
7
преобразуются и приближаются другими, более быстро сходящимися рядами, которые, в свою очередь, преобразуются и приближаются другими, еще более быстро сходящимися рядами, и этот процесс продолжается до тех пор, пока в качестве приближающего ряда не оказывается легко вычислимый ряд. При этом используются следующие комбинаторные приемы:
1) сдвиг на позицию; при р = 1, 2, 3, ... справедливо соотношение (п = 2г или п = 2г + 1)
I
1=р +
1
1 (1 - р)...(! -1 )/0 + 1 )...0+р) 1
(р + 1 )п -1( 2р + 1)!
да
+1-1-;
, 2 (I - р )■( - 11 (1 + 1 + Р )
2) преобразование рядов; при р = 0, 1, 2, ... справедливо соотношение (п = 2г или п = 2г + 1)
I
1=р + 2
1
(1 - р)...(! -1 )1п (1 + 1)...(!+р) 1
I - 2
1 2 0 - р -1 )(1 - р ).■■(! -1)1п- 2 0 + 1 ).■■(!+р )(1+р + 1)
- I
1 = р + 2
(р + 1) 2
О - р -1)(! - р)...(] -1 )1п (1 + 1).(!+р)(1+р + 1)
3) приближение (при п = 2г) быстросходящего- а также приближение (при п = 2г + 1) быстросхо-ся ряда вида
I-1-
,...2(1 - т).(1 - 1 УО + 1 ).(1 + т)
легко вычислимым рядом с известной суммой
I
1
1 = т + 2
(1 - т - 1)...(!- 1 )(1 + 1)...(! + т + 1)
1
1 _ 2 т + 3__
2 2т + 1 (2т + 2)!,
дящегося ряда вида
да
I
1
(1 - т)...(1 - 1)/(1 + 1 + т)
1 = т + 2Х
легко вычислимым рядом с известной суммой
I
1 = т + 2
1
(1 - т - 1 )...(1 - 1 )1 (1 + 1 )...(1 + т + 1)
1
(2т + 2)(2т + 2)! После N шагов таких преобразований ^(2г) или ^(2г + 1) предстают в виде суммы г быстросходя-щихся рядов, остатки которых представляют собой
q
да
да
да
>
да
БЫСТРЫЕ АППРОКСИМАЦИИ
139
знакопеременные ряды "лейбницевского" типа с монотонно убывающими по абсолютной величине и стремящимися к нулю членами, остатки которых также стремятся к нулю. Таким образом при N ^ +да получаем приближение ^(2г) или ^(2г + 1) посредством г быстросходящихся рядов.
Теорема 1 является обобщением теорем из [14], где содержатся как детальные доказательства, так и обширный список ссылок на работы других авторов, которые занимались построением аппроксимаций дзета-констант рациональными дробями. Отметим, что частные случаи соотношений (4), (5) (для ^(3), С(5) и в неполной форме для С(7)) были получены ранее другими авторами (см. [12, 13, 15]), причем на основе совершенно отличных от представленного подходов. Однако в общем виде эти соотношения прежде найдены не были.
Для того чтобы показать скорость сходимости рядов (4), (5) явно, запишем эти формулы в виде рядов по бета-функциям:
У
(;(2к) = 1к + 21-
(-1 )п 1 в и
п = к
2п
2п
(-1 )п
В (п, 1
С(2к +1) = ~гк + 21
п = к
где, как и раньше,
п - q
Р0 = 1, Рт
2п 2
2п
1
(6)
(7)
= П I (п , )2
q = 1 Л =},+1 +1(п 1'
при т > 1;
Зт +1
Бт = йт = (-1 )т при т < к - 2; Бк
1 = (-1 )к -1( 1 + 1 2 п + 1
4-1 = (-1)
4 2п - 1
к - 15 4,
к -1
Ь = 0, 1к = I — при к > 2;
Ь = 0,
к -1
^ = I
г = 1
к -1
Ь = I
2к
г = 1
Г
- при к> 2,
п
БР
тт 2к- 2т - 2
к - 1
& = I
й Р
-т- т
2к - 2т - 2
причем
11
1^1 < -4- (а 2))
к -1
Ук| < 4 (К 2 ))к -1;
к = 1, 2, 3,
Здесь B(x, у) есть бета-функция, B(x, у) =
= Г(х)Г(у-
, где Г(x) — гамма-функция Эйлера,
Г( х + у)
xГ(x) = Г^ + 1). При этом, при п = 1, 2, 3, ..., 0 < B(п, < 2, и для значения дзета-константы
^(2) справедлива оценка 0 < ^(2) < 1.65.
Формулы (6), (7) показывают, что при фиксированном k, k > 1, ряды (4), (5) сходятся как — ,
22п
т.е. быстро. Однако единственный существующий на настоящий момент метод быстрого суммирования рядов БВЕ (см. [1—11]) можно применить здесь лишь к частному случаю, к случаю вычисления рядов (4), (5) (или (6), (7)) при k = 1. При этом сложность вычисления ^(2) и ^(3) будет иметь оценку (3). Быстрому вычислению суммы рядов (4), (5) с помощью БВЕ при любом целом k
препятствует структура Sk, 5к. Вопрос о построении быстрых алгоритмов для вычисления ^(2^, Z(2k + 1) при k = 2, 3, 4, ... по формулам (4), (5) остается открытым. Таким образом, представленный в [6, 7] метод является пока единственным способом быстрого вычисления дзета-констант ^(п) для любого п, п > 2.
Применяя аналогичную технику и аналогичные комбинаторные приемы можно вывести формулы приближения дзета-констант разнообразными знакопеременными рядами с мульти-факториалами. Рассмотрим самый простой случай с двойными факториалами. Пусть
(2п - 1)!! = 1 ■ 3 ■ 5 ■ ... ■ (2п - 1), (2п - 3)!! = = 1 ■ 3 ■ 5 ■ ... ■ (2п - 3), (4п - 1)!! = 1 ■ 3 ■ 5 ■ . ■ (4п - 1) и пусть (2п - 3)!! = 1, если п = 1.
Теорема 2. Справедливы соотношения
да
П2) = V (-1 )п -1 (((2п - 3 ) ! ! )
^ ' ^ ' ( (4п - 3)!!
п=1
(4п - 3)!! (2п - 1)
((2 п - 1 ) !!) 2 1 (4п - 1)!! 2
= I
иг
=1
2п
2 п
ВI п +
х ВI п +
1 ^К 4 п + 1)
2
4 п - 1
1 3
2,
1
(4п - 2)(2п - 1 )2 4п
(8)
$(3) = 8 I (-1)"-122(п-((п - 1)!)2 х
п=1
+
(2п - 1 )2(4п - 3)!! 4п(4п - 1)!!
== 71
(-1)
п - 1
2п
п=1
В\п^ 3) в(п, 1У+ 1
ч(2п - 1 )2
да
к
зо
к
т
0
да
0
т
т
х
Здесь В(х, у) есть бета-функция, и при п = 1, 2, 3, ...; 0 < В (л, 1) < 2, 0 < в(л, 4) < 4, 0 < В (л, 4) < \.
В [11] была доказана теорема о быстром вычислении константы Каталана О. БВЕ-алгоритм со сложностью (3) использовал быструю аппроксимацию О арифметической суммой двух знакопостоянных рядов с рациональными дробями на основе следующего утверждения.
Теорем а 3. Справедливо соотношение
_ lZ 8 "-1 ( (n - 1) ! ) 3 ( 6 n - 3
G _ 1 Y- v
4 ^ (2n - 1)!! V((4n - 3)m,)2
1
» BIn,
6П - 1 ^ _ У 4^ÍB2(n, !')(6n - 3) -
((4n - 1)!!!! )2) fl 22n +5
- B4 n, 4)( 6n -1 )j.
Здесь (4и - 1)!!!! = 3 ■ 7 ■ 11 ■ ... ■ (4n - 1), (4n - 3)!!!! = = 1 ■ 5 ■ 9 ■ ... ■ (2n - 3).
Следствие 1. Для дзета-константы Z(2) справедливо соотношение
_ 4 v 8 n -1 ( (n - 1) ! )3 ( 6 n - 3
z(2) _ 4 Y о
3 (2n
1 (2n - 1)!! V((4n - 3)!ü!)
+
6n - 1
j _ 1 У ((4n - 1)!!!!)2) 3ntl 2
да Bn,:
..2 n + 3
b2Í n, Л( 6 n - 3) +
+ B2 (n, 4)( 6 n - 1 )j.
(9)
Используя метод доказательства из [11], можно получить разные быстрые приближения дзета-константы ^(2) знакопостоянными рядами с мультифакториалами.
Теорема 4. Справедливо соотношение
да
z(2) _ 3 у-
_ 2^Т -1 ( 3 n - 1 ) ( (n - 1 ) ! ) _
_ 3 Y 3 _
n _ 1
((2n - 1)!!)3
1 V ( 3 n - 1 ) b3(n 1
_ i у : 3 n - 1 :BJ| n
3 Y 22
n _ 1 z
(10)
Поскольку из (1) следует, что Z(2) = — , то, вос-
6
пользовавшись аппроксимациями (5), (8)-(10),
можно построить БВЕ-алгоритмы вычисления со сложностью (3), т.е. со сложностью, близкой к оптимальной, также классической константы я.
Работа выполнена при поддержке РФФИ (грант 13-01-00657).
СПИСОК ЛИТЕРАТУРЫ
1. Карацуба E.A. О быстром вычислении трансцендентных функций // ДАН. 1991. Т. 319. № 2. С. 278-279.
2. Карацуба E.A. Быстрое вычисление трансцендентных функций // Пробл. передачи информации. 1991. Т. 27. № 4. С. 87-110.
3. Карацуба E.A. О новом методе быстрого вычисления трансцендентных функций // УМН. 1991. Т. 46. № 2(278). С. 219-220.
4. Карацуба E.A. Быстрое вычисление Z(3) // Пробл. передачи информации. 1993. Т. 29. № 1. С. 68-73.
5. Karatsuba C.A. Fast Evaluation of Bessel Functions // Integral Transforms and Spec. Fu
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.