| Математические заметки |
|
|
|
|
|
О сложности вычисления “сжатых” степенных рядов Е. А. Карацуба Вычислительный центр им. А. А. Дородницына РАН, г. Москва
Англоязычная версия:
Mathematical Notes, 2023, Volume 114, Issue 1, Pages DOI: https://doi.org/10.1134/S000143462307009X 
Реферативные базы данных:
  1. Введение. Основные определения. Быстрые алгоритмы. Метод БВЕПод “сжатыми” степенными рядами будем иметь в виду ряды вида Такие ряды возникают в разных областях математики и физики. В теории чисел и теории специальных функций такими рядами являются: эйлерова тэта-функция и тэта-ряды Якоби (см.,например, [1]), а также функция, введенная Риманом (см.,например, [2]), Очевидно, что если положить в (2) y=e−πx, можно рассматривать (2) в качестве ряда W2(y).Такие ряды и суммы встречаются в квантовой физике, например, в квантовой оптике (см. [3], [4]). Настоящая статья посвящена проблеме быстрого (или эффективного) вычисления ряда (1) и оценке сложности такого вычисления для аргумента x разной арифметической природы. Под алгоритмом ниже предполагается правило или способ вычисления без формализации этого понятия. Далее считаем, что числа записаны в двоичной системе счисления, знаки которой 0 и 1 называются битами. Определение 1. Запись знаков 0, 1, плюс, минус, скобка; сложение, вычитание и умножение двух битов называется одной элементарной или битовой операцией (далее – просто операцией). Пусть y=f(x) есть вещественная функция вещественного переменного x, a⩽x⩽b, которая на интервале (a,b) удовлетворяет условию Липшица порядка α, 0<α<1, так что при x1,x2∈(a,b): |f(x1)−f(x2)|⩽|x1−x2|α. Пусть n – натуральное число. Определение 2. Вычислить функцию y=f(x) в точке x=x0∈(a,b) с точностью до n знаков, значит найти такое число A, что |f(x0)−A|⩽2−n. Определение 3. Количество операций, достаточное для вычисления функции f(x) в точке x=x0 с точностью до n знаков посредством данного алгоритма, называется сложностью вычисления f(x) в точке x0 и обозначается sf(n)=sf,x0(n). Сложность умножения двух n-значных чисел получила специальное обозначение M(n). Сложность школьного метода умножения оценивается как В 1960 г. (см. [5]–[8]) А. А. Карацуба нашел первый быстрый метод умножения двух n-значных чисел с оценкой сложности открыв тем самым новое направление в математике – быстрые алгоритмы или быстрые вычисления. В зарубежной литературе метод А. А. Карацубы получил несколько наименований, самыми распространенными из которых являются “divide and conquer” и “binary splitting”, а его развитие и усовершенствование привело к созданию новых быстрых алгоритмов, в частности, быстрых алгоритмов умножения с лучшей оценкой сложности (см. [9]–[11]). Далее считаем, что для сложности умножения справедлива оценка Шенхаге–Штрассена (см. [10])Определение 4. Назовем быстрым такой алгоритм вычисления функции f, что для этого алгоритма где C есть константа.Тем самым, сложность какого-либо быстрого алгоритма оценивается следующим образом: для любого ε>0 и n>n1(ε), n→∞.Для быстрого вычисления широкого класса простейших и высших трансцендентных функций автором был построен (см. [12]–[18]) новый метод – метод БВЕ – Быстрого Вычисления Е-функций (о Е-функциях Зигеля см. [19]). Применяя БВЕ, можно вычислить любую элементарную трансцендентную функцию для любого аргумента, классические константы e, π, постоянную Эйлера γ, постоянные Апери и Каталана, такие высшие трансцендентные функции как гамма-функцию Эйлера, гипергеометрические функции, сферические функции, цилиндрические функции и т.д. для алгебраических значений аргумента и параметров, дзета-функцию Римана для целых значений аргумента, дзета-функцию Гурвица для целого аргумента и алгебраических значений параметра, а также такие специальные интегралы, как интеграл вероятности, интегралы Френеля, интегральную экспоненциальную функцию, интегральные синус и косинус и т.д. с оценкой сложности не хуже, чем Метод БВЕ – это метод суммирования рядов специального вида. Рассмотрим степенной ряд f, f=f(z)=∑∞j=0d(j)zj. Пусть R=1/¯limj→∞j√|d(j)| есть радиус сходимости этого ряда. Предположим, что |z|⩽R−δ, 0<δ<R, δ – некоторая константа. Тогда существует такая константа A⩾1, что Поэтому, чтобы вычислить функцию f в точке z с точностью 2−n, достаточно вычислить с точностью 2−n−1 сумму S,Применим к вычислению суммы S метод БВЕ (см. детальное описание в [12]–[18]): т.е., комбинируя на каждом шаге слагаемые S последовательно попарно и вынося за скобки “очевидный” общий множитель, вычисляем на каждом шаге значения выражений в скобках, которые по построению будут целыми числами. Чтобы вычислительная сложность была не слишком большой, вычисляемые на каждом шаге значения “скобок” должны расти не слишком быстро. Например (см. [12]), с помощью БВЕ можно вычислить быстро следующие два вида степенных рядов: при условии, что a(j), b(j) – целые числа, |a(j)|+|b(j)|⩽(K1j)K2, |z|<1, K1, K2 есть константы, и z есть алгебраическое число. Сложность вычисления рядов (4), (5) оценивается так: Структура метода БВЕ допускает распараллеливание БВЕ-алгоритмов.2. Вычисление “сжатых” степенных рядов с помощью БВЕЛегко видеть из (1) и (4), (5), что если числа d(j) таковы, что то при алгебраическом x, |x|<1, “сжатые” ряды (1) являются подмножеством множества рядов (4), (5) и вычисляются методом БВЕ точно так же, как и ряды (4), (5). Единственным отличием является количество слагаемых ряда, которые нужно просуммировать, чтобы получить значение суммы ряда с точностью до n знаков. Для достижения точности 2−n в (4) достаточно взять ∼n членов ряда (4) и потом просуммировать сумму ∼n слагаемых методом БВЕ (см. для деталей [12], [15], [18]). Для достижения точности 2−n в (5) достаточно взять ∼n/logn членов ряда (5) и потом вычислить сумму ∼n/logn слагаемых методом БВЕ (см. для деталей [12]). В то же время, чтобы вычислить ряд (1) с точностью 2−n, достаточно взять r√n, а затем просуммировать сумму ∼r√n слагаемых (точнее, количество суммируемых слагаемых должно равняться первому целому числу, не меньшему, чем ∼r√n, и равному степени двойки) методом БВЕ. Поскольку количество шагов в таком БВЕ алгоритме есть logr√n=1/rlogn, оценки сложности вычисления “сжатых” степенных рядов в этом случае совпадают с оценками (6), и алгоритмы БВЕ вычисления “сжатых” рядов являются быстрыми.С другой стороны, оценка сложности вычисления ”сжатых” рядов вида (2) методом БВЕ будет отличаться от оценок сложности вычисления методом БВЕ рядов (4), (5) с трансцендентным аргументом, поскольку существенно зависит от количества суммируемых слагаемых. В случае рядов (4), (5) оценка сложности вычисления (в общем случае) будет O(n2+ε). В случае “сжатого” степенного ряда с трансцендентным аргументом сложность вычисления методом БВЕ будет для любого ε>0, n→∞. Таким образом (см. выше определение быстрого алгоритма), такие алгоритмы не будут быстрыми.Далее рассмотрим другой способ вычисления изучаемого ряда с трансцендентным аргументом и оценим сложность нового вычисления. Для простоты будем рассматривать “сжатые” степенные ряды (1) с d(j)≡1 ∀j, т.е. такие, как функция ω(x) из (2). 3. Вспомогательные утверждения Доказательство. Легко видеть, что сумма слагаемых с биномиальными коэффициентами, стоящая в скобках в правой части формулы (10) под знаком суммы по m от 1 до k, представляет собой выражение Отсюда имеем Замечание 1. Заметим, что первая формула из (9) – это известная табличная формула (см., например, [20]). Следствие 1. Из леммы 1 следует, что примечательную формулу Фаульхабера от 1631 г. из [21] можно записать в новом виде. Формулу Фаульхабера (сам Иоганн Фаульхабер подсчитал в численном виде 17 первых коэффициентов), с выведенными для любой степени коэффициентами B_j, названными впоследствии в его честь числами Бернулли, Бернулли доказал в следующей форме (см. [22]):
\begin{equation*}
n^{p+1}=(p+1)\sum_{k=1}^nk^p+\frac{p+1}{2}\,n^p +\sum_{j=2}^p\binom{p+1}{j}B_jn^{p+1-j}.
\end{equation*}
\notag
С введенными после Бернулли двумя первыми “числами Бернулли” формула Фаульхабера имеет вид (см., например, [20])
\begin{equation*}
\sum_{k=1}^nk^p=\frac{1}{p+1}\sum_{j=0}^p(-1)^j\binom{p+1}{j}B_jn^{p+1-j}.
\end{equation*}
\notag
Из леммы 1 следует, что формулу Фаульхабера можно записать также в виде “сжатого” степенного ряда
\begin{equation}
\widetilde W_r(x)=\sum_{j=0}^\infty x^{j^r},\qquad |x|<1,\quad r =2,3,\dots,
\end{equation}
\tag{12}
представима в виде произведения
\begin{equation}
S_{r,l}(x)=\bigl(1+x(1+x^{a_2}(1+x^{a_3}(1+\dotsb+x^{a_{l-1}} (1+x^{a_l})\dotsb)))\bigr),
\end{equation}
\tag{13}
где
\begin{equation}
\begin{gathered} \, a_2 =\sum_{m=1}^r(-1)^{m-1}\binom{r}{m}2^{r-m}=2^r-1, \\ a_3=\sum_{m=1}^r(-1)^{m-1}\binom{r}{m}3^{r-m}=3^r-2^r, \\ \dots, \\ a_{l-1} =\sum_{m=1}^r(-1)^{m-1}\binom{r}{m}(l-1)^{r-m}=(l-1)^r -(l-2)^r, \\ a_l =\sum_{m=1}^r(-1)^{m-1}\binom{r}{m}l^{r-m}=l^r-(l-1)^r; \end{gathered}
\end{equation}
\tag{14}
в частности, с учетом того, что l^2-(l-1)^2=2l-1, Доказательство. Пользуясь леммой 1, получаем последовательно значения коэффициентов от a_1=\sum_{m=1}^r(-1)^{m-1}\binom{r}{m}1^{r-m}=1 до a_l=\sum_{m=1}^r(-1)^{m-1}\binom{r}{m}l^{r-m}.
4. Новый алгоритм и сложность вычисления “сжатого” степенного рядаВычислим ряд (12) с точностью 2^{-n}, предположив для простоты, что |x|\leqslant 1/2. В этом случае в сумме (11) достаточно просуммировать l слагаемых, где l – наименьшее целое число такое, что Чтобы вычислить (11) будем вычислять произведение (13).На вычисление значения произведения x^{2^r-1}=x* x^2*x^4*\dotsb*x^{2^{r-2}}*x^{2^{r-1}}, где каждый следующий сомножитель является квадратом предыдущего, достаточно O((2r-1)M(n)) операций (r – фиксированное), для вычисления всех значений x^{3^r-2^r},x^{4^r-3^r},x^{5^r-4^r},\dots,x^{l^r-(l-1)^r} (вычисляем последовательно), с учетом (16) достаточно операций. С предварительно вычисленными значениями
\begin{equation*}
x^{2^r-1},\ x^{3^r-2^r},\ x^{4^r-3^r},\ x^{5^r-4^r}, \ \dots,\ x^{l^r-(l-1)^r}
\end{equation*}
\notag
произведение (13) при условии (16) вычисляется со сложностью Из (17), (18) и (3) следует, что для вычисления с точностью 2^{-n} ряда (12) достаточно операций. Если 1/2<|x|\leqslant a<1, то определив такое k, что a^k< 1/2, или k\geqslant 1/\log_2(1/a), нужно просуммировать не (16) членов ряда (12), а L членов ряда, где L наименьшее целое число такое, что L\geqslant(kn)^{1/r}. Поскольку k является фиксированной постоянной, оценка сложности вычисления не меняется с точностью до констант в O. Тем самым доказана Теорема 1. Сложность вычисления ряда
\begin{equation*}
\widetilde W_r(x)=\sum_{j=0}^\infty x^{j^r},\qquad |x|<1,\quad r =2,3,\dots,
\end{equation*}
\notag
где x – трансцендентное число, есть для любого \varepsilon>0 и n>n_1(\varepsilon), n\to\infty. 5. ЗаключениеПоскольку в теории сложности вычислений до сих пор (июль 2022) не найдено ни одной оценки битовой сложности вычисления снизу (кроме тривиальных), трудно заявлять о существовании (или не существовании) быстрого алгоритма вычисления “сжатого” степенного ряда с трансцендентным аргументом. Однако, то что оценка сложности вычисления такого ряда посредством двух совершенно разных методов оказалась одинаковой по n, n\to\infty, с точностью до констант, стоящих в O, свидетельствует о том, что полученная оценка близка к “естественной” (возможно даже к оптимальной) для вычисления “сжатого” степенного ряда с трансцендентным аргументом. 
Цитирование в формате AMSBIB
\RBibitem{Kar23} |
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|