Метод БВЕ

Метод БВЕ — это метод быстрого суммирования специального вида рядов. Он был построен в 1990 Е.А. Карацубой^{[1] [2]} и назван БВЕ — Быстрого Вычисления Е-функций — потому, что позволяет вычислять быстро Зигелевские $E$-функции, и в частности, $e^x$.

Зигель назвал "E -функциями" класс функций,"похожих на экспоненциальную". К ним принадлежат такие высшие трансцендентные функции как гипергеометрические, сферические, цилиндрические функции и т.д.

С помощью БВЕ можно доказать следующую теорему

Теорема. Пусть $y=f(x)$ --- простейшая трансцендентная функция, т.е. экспоненциальная функция или тригонометрическая функция, или элементарная алгебраическая функция, или их суперпозиция, или обратная им функция или суперпозиция обратных функций. Тогда

$s_f(n) = O(M(n)\log^2n).$

Здесь $s_f(n)$ есть сложность вычисления (битовая) функции $f(x)$ с точностью до $n$ знаков, $M(n)$ --- сложность умножения двух $n$-значных чисел.

Алгоритмы, основанные на БВЕ включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант $e$, $\pi$, постоянной Эйлера $\gamma$, постоянных Апери^[3] и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций ^[4], сферических функций, цилиндрических функций^[5] и т.д. для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента^{[6] [7]}, дзета-функции Гурвица для целого аргумента и алгебраических значений параметра^[8], а также таких специальных интегралов^[9], как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и т.д. при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно

$s_{f}(n)= O(M(n)\log^2 n).$

В настоящее время только метод БВЕ даёт возможность быстро вычислять значения функций из класса высших трансцендентных функций^[10], некоторые специальные интегралы математической физики и такие классические константы, как константы Эйлера, Каталана^[11] и Апери. Дополнительным преимуществом метода БВЕ является возможность распараллеливания основанных на БВЕ алгоритмов.

БВЕ-вычисление классических констант

Для быстрого вычисления константы $\pi$ можно воспользоваться формулой Эйлера

$\frac{\pi}{4} = \arctan \frac12 + \arctan \frac13,$

и применить БВЕ к суммированию рядов Тейлора для

$\arctan \frac12 = \frac{1}{1*2} - \frac{1}{3*2^3}+ \dots + \frac{(-1)^{r-1}}{(2r-1)2^{2r-1}} + R_1 ,$

$\arctan \frac13 = \frac{1}{1*3} - \frac{1}{3*3^3}+ \dots + \frac{(-1)^{r-1}}{(2r-1)3^{2r-1}} + R_2 ,$

с остаточными членами $R_1,$ $R_2,$ для которых справедливы оценки

$|R_1| \leq \frac45\frac{1}{2r+1}\frac{1}{2^{2r+1}};$

$|R_2| \leq \frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}};$

и при

$r = n,$

$4(|R_1|+|R_2|) \ < \ 2^{-n}.$

Чтобы вычислить $\pi$ посредством БВЕ, можно использовать также другие приближения^[12] Во всех случаях сложность

$s_{\pi} = O(M(n)\log^2 n) .$

Чтобы вычислить постоянную Эйлера гамма с точностью до $n$ знаков, нужно просуммировать с помощью БВЕ два ряда. А именно, при

$m=6n, \quad k = n, \quad k \geq 1,$

$\gamma = - \log n \sum_{r=0}^{12n} \frac{(-1)^rn^{r+1}}{(r+1)!} + \sum_{r=0}^{12n} \frac{(-1)^rn^{r+1}}{(r+1)!(r+1)} + O(2^{-n}) .$

При этом

$s_{\gamma} = O(M(n)\log^2 n) .$ Для быстрого вычисления константы $\gamma$ можно также применить метод БВЕ к другому приближению ^[13]

БВЕ-вычисление некоторых степенных рядов

С помощью БВЕ можно вычислить быстро следующие два вида рядов:

$f_1 = f_1(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}z^j ,$

$f_2 = f_2(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}\frac{z^j}{j!} ,$

при условии, что $a(j) , \quad b(j)$ --- целые числа, $|a(j)|+|b(j)| \leq (Cj)^K; \quad |z| \ < \ 1; \quad K$ и $C$ есть константы, и $z$ есть алгебраическое число.

Сложность вычисления этих рядов $s_{f_1}(n)= O\left(M(n)\log^2n \right),$

$s_{f_2}(n)= O\left(M(n)\log n \right).$

Детали БВЕ на примере быстрого вычисления константы $e$

Для вычисления константы $e$ возьмём $m = 2^k, \quad k \geq 1$, членов ряда Тейлора для $e,$

$e = 1 + \frac{1}{1!} + \frac{1}{2!} + \dots + \frac{1}{(m-1)!} + R_m.$ При этом выбираем $m$ так, чтобы для остатка $R_m$ выполнялось неравенство $R_m \leq 2^{-n-1}$. Это будет, например, когда $m\geq \frac{4n}{\log n}$. Таким образом, возьмем $m=2^k$ таким, что натуральное число $k$ определяется неравенствами:

$2^k \geq \frac{4n}{\log n} > 2^{k-1}.$

Будем вычислять сумму

$S = 1 + \frac{1}{1!} + \frac{1}{2!} + \dots + \frac{1}{(m-1)!} = \sum_{j=0}^{m-1}\frac{1}{(m-1-j)!} ,$

за $k$ шагов следующего процесса.

Шаг 1. Объединяя слагаемые $S$ последовательно попарно и вынося за скобки "очевидный" общий множитель, получаем

$S = \left(\frac{1}{(m-1)!} + \frac{1}{(m-2)!}\right) + \left(\frac{1}{(m-3)!} + \frac{1}{(m-4)!}\right) + \dots$

$= \frac{1}{(m-1)!}(1+m-1) + \frac{1}{(m-3)!}(1+m-3) + \dots .$

Будем вычислять только целые значения выражений, стоящих в скобках, т.е. значения

$m , m-2 , m-4 , \dots .$

Таким образом, на первом шаге сумма $S$ преобразуется к виду

$S = S(1) = \sum_{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}\alpha_{m_1-j}(1) ,$

$m_1 = \frac m2 , m = 2^k , k \geq 1 .$

На первом шаге вычисляется только $\frac m2$ целых чисел вида

$\alpha_{m_1-j}(1) = m-2j , \quad j = 0 , 1 , \dots , m_1 - 1 ,$

Далее мы действуем аналогично: объединяя на каждом шаге слагаемые суммы $S$ последовательно попарно, мы выносим за скобки "очевидный" общий множитель и вычисляем только целые значения выражений в скобках. Пусть сделано $i$ шагов такого процесса.

Шаг $i+1$ ($i+1 \leq k$).

$S = S(i+1) = \sum_{j=0}^{m_{i+1}-1}\frac{1}{(m-1-2^{i+1}j)!} \alpha_{m_{i+1}-j}(i+1) ,$

$m_{i+1} = \frac{m_i}{2} = \frac{m}{2^{i+1}} ,$

мы вычисляем только $\frac{m}{2^{i+1}}$ целых чисел вида

$\alpha_{m_{i+1}-j}(i+1) = \alpha_{m_i-2j}(i) + \alpha_{m_i-(2j+1)}(i)\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!} ,$

$j = 0 , 1 , \dots , \quad m_{i+1} - 1 , \quad m = 2^k , \quad k \geq i+1 .$

Здесь $\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!}$ есть произведение $2^i$ целых чисел.

И т.д.

Последний, $k$ -й шаг. Вычисляем одно целое значение $\alpha_1(k)$, вычисляем, пользуясь вышеописанным быстрым алгоритмом, значение $(m-1)!$, и производим одно деление целого числа $\alpha_1(k)$ на число $(m-1)!$ с точностью до $n$ знаков. Получившийся результат и есть сумма $S$, или константа $e$ с точностью до $2^{-n}$. Сложность всех вычислений есть

$O\left(M(m)\log^2 m\right) = O\left(M(n)\log n\right) .$

Ссылки

1. ↑ Е.А.Карацуба, Быстрое вычисление трансцендентных функций. Проблемы передачи информации, т.27, N 4 (1991).
2. ↑ D.W. Lozier and F.W.J. Olver, Numerical Evaluation of Special Functions. Mathematics of Computation 1943-1993: A Half -Century of Computational Mathematics, W.Gautschi,eds., Proc. Sympos. Applied Mathematics, AMS, Vol.48 (1994).
3. ↑ Е.А.Карацуба, Быстрое вычисление $\zeta(3)$. Проблемы передачи информации, т.29, N 1 (1993).
4. ↑ Ekatharine A. Karatsuba, Fast evaluation of hypergeometric function by FEE. Computational Methods and Function Theory (CMFT'97), N.Papamichael, St.Ruscheweyh and E.B.Saff, eds., World Sc.Pub. (1999)
5. ↑ Catherine A. Karatsuba, Fast evaluation of Bessel functions. Integral Transforms and Special Functions, Vol.1, N4 (1993)
6. ↑ Е.А. Карацуба, Быстрое вычисление дзета-функции Римана $\zeta(s)$ для целых значений аргумента $s$. Проблемы передачи информации, т.31, N 4 (1995).
7. ↑ J.M. Borwein, D.M. Bradley and R.E. Crandall, Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math., Vol. 121 ,N 1-2 (2000).
8. ↑ Е.А.Карацуба, Быстрое вычисление дзета-функции Гурвица и $L$-рядов Дирихле. Проблемы передачи информации, т.34, N 4 (1998).
9. ↑ E.A. Karatsuba, Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W.Kramer,J.W.von Gudenberg,eds.(2001).
10. ↑ E. Bach, The complexity of number-theoretic constants. Info. Proc. Letters, N 62 (1997).
11. ↑ E.A. Karatsuba, Fast computation of $\zeta(3)$ and of some special integrals ,using the polylogarithms, the Ramanujan formula and it's generalization. J. of Numerical Mathematics BIT, Vol. 41, N 4 (2001).
12. ↑ D.H. Bailey, P.B. Borwein and S. Plouffe, On the rapid computation of various polylogarithmic constants. Math. Comp.,Vol. 66 (1997).
13. ↑ R.P. Brent and E.M. McMillan, Some new algorithms for high-precision computation of Euler's constant. Math. Comp., Vol.34 (1980).

См. также

• Быстрые алгоритмы
• АГС метод Гаусса
• Сложность вычисления (битовая)

Внешние источники

http://www.ccas.ru/personal/karatsuba/alg.htm