Метод БВЕ

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод БВЕ — это метод быстрого суммирования специального вида рядов. Он был построен в 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