Русская Википедия:Метод БВЕ
Метод БВЕ (быстрого вычисления E-функций) — метод быстрого суммирования специального вида рядов. Построен в 1990 году Е. А. Карацубой[1][2]. Позволяет вычислять быстро зигелевские E-функции, и в частности, <math>e^x</math>.
Зигель назвал «E-функциями» класс функций, «похожих на экспоненциальные». Этому классу принадлежат такие высшие трансцендентные функции как гипергеометрические, сферические, цилиндрические функции и так далее.
Теорема
С помощью БВЕ можно доказать следующую теорему
- Теорема.
Пусть <math>y=f(x)</math> — простейшая трансцендентная функция, то есть экспоненциальная функция или тригонометрическая функция, или элементарная алгебраическая функция, или их суперпозиция, или обратная им функция или суперпозиция обратных функций. Тогда
<math>s_f(n) = O(M(n)\log^2n).</math>
Здесь <math>s_f(n)</math> есть сложность вычисления (битовая) функции <math>f(x)</math> с точностью до <math>n</math> знаков, <math>M(n)</math> — сложность умножения двух <math>n</math>-значных чисел.
Алгоритмы, основанные на БВЕ, включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант <math>e</math>, <math>\pi</math>, постоянной Эйлера <math>\gamma</math>, постоянных Апери[3] и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций[4], сферических функций, цилиндрических функций[5] и так далее для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента[6][7], дзета-функции Гурвица для целого аргумента и алгебраических значений параметра[8], а также таких специальных интегралов[9], как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и так далее при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно <math>s_{f}(n)=O(M(n)\log^2 n).</math>
В настоящее время только метод БВЕ даёт возможность быстро вычислять значения функций из класса высших трансцендентных функций[10], некоторые специальные интегралы математической физики и такие классические константы, как константы Эйлера, Каталана[11] и Апери. Дополнительным преимуществом метода БВЕ является возможность распараллеливания основанных на БВЕ алгоритмов.
БВЕ-вычисление классических констант
Для быстрого вычисления константы <math>\pi</math> можно воспользоваться формулой Эйлера <math>\frac{\pi}{4} = \mathrm{arctg}\frac12 + \mathrm{arctg}\frac13,</math> и применить БВЕ к суммированию рядов Тейлора для
<math>\mathrm{arctg}\frac12 = \frac{1}{1\cdot 2} - \frac{1}{3\cdot 2^3}+ \ldots + \frac{(-1)^{r-1}}{(2r-1)2^{2r-1}} + R_1,</math>
<math>\mathrm{arctg}\frac13 = \frac{1}{1\cdot 3} - \frac{1}{3\cdot 3^3}+ \ldots + \frac{(-1)^{r-1}}{(2r-1)3^{2r-1}} + R_2,</math>
с остаточными членами <math>R_1,\ R_2,</math> для которых справедливы оценки
<math>|R_1| \leqslant \frac45\frac{1}{2r+1}\frac{1}{2^{2r+1}};</math>
<math>|R_2| \leqslant \frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}};</math>
и при
<math>r = n,</math>
<math>4(|R_1|+|R_2|) \ < \ 2^{-n}.</math>
Чтобы вычислить <math>\pi</math> посредством БВЕ, можно использовать также другие приближения[12]. Во всех случаях сложность
<math>s_{\pi} = O(M(n)\log^2 n).</math>
Чтобы вычислить постоянную Эйлера <math>\gamma</math> с точностью до <math>n</math> знаков, нужно просуммировать с помощью БВЕ два ряда. А именно, при <math>m=6n,\ k = n,\ k \geqslant 1,</math>
<math>\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}).</math>
При этом
<math>s_{\gamma} = O(M(n)\log^2 n).</math>
Для быстрого вычисления константы <math>\gamma</math> можно также применить метод БВЕ к другому приближению[13]
БВЕ-вычисление некоторых степенных рядов
С помощью БВЕ можно вычислить быстро следующие два вида рядов:
<math>f_1 = f_1(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}z^j,</math>
<math>f_2 = f_2(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}\frac{z^j}{j!},</math>
при условии, что <math>a(j),\ b(j)</math> — целые числа, <math>|a(j)|+|b(j)| \leqslant (Cj)^K;\ |z| < 1;\ K</math> и <math>C</math> есть константы, и <math>z</math> есть алгебраическое число.
Сложность вычисления этих рядов
<math>s_{f_1}(n)=O\left(M(n)\log^2n \right),</math>
<math>s_{f_2}(n)=O\left(M(n)\log n \right).</math>
Детали БВЕ на примере быстрого вычисления константы <math>e</math>
Для вычисления константы <math>e</math> возьмём <math>m = 2^k,\quad k \geqslant 1</math>, членов ряда Тейлора для <math>e,</math>
<math>e = 1 + \frac{1}{1!} + \frac{1}{2!} + \ldots + \frac{1}{(m-1)!} + R_m.</math>
При этом выбираем <math>m</math> так, чтобы для остатка <math>R_m</math> выполнялось неравенство <math>R_m \leqslant 2^{-n-1}</math>. Это будет, например, когда <math>m\geqslant \frac{4n}{\log n}</math>. Таким образом, возьмем <math>m=2^k</math> таким, что натуральное число <math>k</math> определяется неравенствами:
<math>2^k \geqslant \frac{4n}{\log n} > 2^{k-1}.</math>
Будем вычислять сумму <math>S = 1 + \frac{1}{1!} + \frac{1}{2!} + \ldots + \frac{1}{(m-1)!} = \sum_{j=0}^{m-1}\frac{1}{(m-1-j)!},</math>
за <math>k</math> шагов следующего процесса.
Шаг 1. Объединяя слагаемые <math>S</math> последовательно попарно и вынося за скобки «очевидный» общий множитель, получаем
<math>S = \left(\frac{1}{(m-1)!} + \frac{1}{(m-2)!}\right) + \left(\frac{1}{(m-3)!} + \frac{1}{(m-4)!}\right) + \ldots =</math>
<math>= \frac{1}{(m-1)!}(1+m-1) + \frac{1}{(m-3)!}(1+m-3) + \ldots</math>
Будем вычислять только целые значения выражений, стоящих в скобках, то есть значения <math>m,\ m-2,\ m-4,\ \ldots</math>
Таким образом, на первом шаге сумма <math>S</math> преобразуется к виду
<math>S = S(1) = \sum_{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}\alpha_{m_1-j}(1),</math>
<math>m_1 = \frac m2,\ m = 2^k,\ k \geqslant 1.</math>
На первом шаге вычисляется только <math>\frac m2</math> целых чисел вида
<math>\alpha_{m_1-j}(1) = m-2j,\quad j = 0,\;1,\;\ldots,\;m_1 - 1,</math>
Далее мы действуем аналогично: объединяя на каждом шаге слагаемые суммы <math>S</math> последовательно попарно, мы выносим за скобки «очевидный» общий множитель и вычисляем только целые значения выражений в скобках. Пусть сделано <math>i</math> шагов такого процесса.
Шаг <math>i+1</math> (<math>i+1 \leqslant k</math>).
<math>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),</math>
<math> m_{i+1} = \frac{m_i}{2} = \frac{m}{2^{i+1}},</math>
мы вычисляем только <math>\frac{m}{2^{i+1}}</math> целых чисел вида
<math>\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)!},</math>
<math>j = 0,\;1,\;\ldots,\quad m_{i+1} - 1,\quad m = 2^k,\quad k \geqslant i+1.</math>
Здесь <math>\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!}</math> есть произведение <math>2^i</math> целых чисел.
И так далее.
Последний, <math>k</math>-й шаг. Вычисляем одно целое значение <math>\alpha_1(k)</math>, вычисляем, пользуясь вышеописанным быстрым алгоритмом, значение <math>(m-1)!</math>, и производим одно деление целого числа <math>\alpha_1(k)</math> на число <math>(m-1)!</math> с точностью до <math>n</math> знаков. Получившийся результат и есть сумма <math>S</math>, или константа <math>e</math> с точностью до <math>2^{-n}</math>. Сложность всех вычислений есть
<math>O\left(M(m)\log^2 m\right) = O\left(M(n)\log n\right).</math>
Примечания
Ссылки
- ↑ Карацуба Е. А. Быстрое вычисление трансцендентных функций. Проблемы передачи информации, т. 27, № 4 (1991).
- ↑ Lozier D. W. and Olver F. W. J. 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).
- ↑ Карацуба Е. А. Быстрое вычисление <math>\zeta(3)</math>. Проблемы передачи информации, т. 29, № 1 (1993).
- ↑ Karatsuba Ekatharine A. 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).
- ↑ Karatsuba Catherine A. Fast evaluation of Bessel functions. Integral Transforms and Special Functions, Vol. 1, № 4 (1993).
- ↑ Карацуба Е. А. Быстрое вычисление дзета-функции Римана <math>\zeta(s)</math> для целых значений аргумента <math>s</math>. Проблемы передачи информации, т. 31, № 4 (1995).
- ↑ Borwein J. M., Bradley D. M. and Crandall R. E. Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math., Vol. 121, № 1-2 (2000).
- ↑ Карацуба Е. А. Быстрое вычисление дзета-функции Гурвица и <math>L</math>-рядов Дирихле. Проблемы передачи информации, т. 34, № 4 (1998).
- ↑ Karatsuba E. A. Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W. Kramer, J. W. von Gudenberg, eds. (2001).
- ↑ Bach E. The complexity of number-theoretic constants. Info. Proc. Letters, № 62 (1997).
- ↑ Karatsuba E. A. Fast computation of <math>\zeta(3)</math> and of some special integrals, using the polylogarithms, the Ramanujan formula and it’s generalization. J. of Numerical Mathematics BIT, Vol. 41, № 4 (2001).
- ↑ Bailey D. H., Borwein P. B. and Plouffe S. On the rapid computation of various polylogarithmic constants. Math. Comp., Vol. 66 (1997).
- ↑ Brent R. P. and McMillan E. M. Some new algorithms for high-precision computation of Euler’s constant. Math. Comp., Vol. 34 (1980).
