Журнал вычислительной математики и математической физики, 2022, T. 62, № 10, стр. 1587-1614

1. ВВЕДЕНИЕ

Преобразование числовых последовательностей с целью ускорения их сходимости берет свое начало, вероятно, с работ Эйлера. Один из наиболее известных (и популярных) алгоритмов ускорения сходимости – это как раз метод Эйлера. Другой не менее известный метод, который преобразует (медленно) сходящуюся последовательность в расходящийся асимптотический ряд, – это формула Эйлера–Маклорена. Эта формула также может рассматриваться как ускоритель сходимости.

Ускорение сходимости последовательностей широко применяется как при решении практических задач, так и при разработке более совершенных численных методов. Медленно сходящиеся или расходящиеся ряды часто являются решениями сложных прикладных задач, поэтому ускорение их сходимости может быть единственным способом получить содержательную информацию о решении.

В последние годы этот раздел численного анализа интенсивно развивается, что во многом связано с развитием систем компьютерной алгебры (CAS). Теперь вычисления можно проводить с очень высокой точностью в плавающей арифметике или в рациональной арифметике на обычном компьютере, что устраняет ряд ограничений, ранее казавшихся принципиальными.

В то же время численные методы, и особенно высокоточные вычисления, в последнее время находят все большее применение в теории чисел.

Разумеется, применение методов, традиционно относящихся к численному анализу, в теории чисел не является чем-то новым. Как известно, Эйлер, Гаусс и другие великие математики были также виртуозными вычислителями.

Например, решение Базельской проблемы Эйлер начинал как раз с ускорения сходимости этого ряда и получения точной численной оценки величины $\zeta (2) = {{\pi }^{2}}{\text{/}}6$. Весьма вероятно, что Эйлер угадал решение этой задачи до того, как он дал доказательство.

В настоящее время суммирование рядов с высокой точностью (см. [1]), вычисление квадратур с десятками или даже сотнями десятичных разрядов и т.п., часто используются в теории чисел для проверки некоторых гипотез и тождеств (см. [2]).

Один из классических разделов теории чисел – это доказательство иррациональности некоторых фундаментальных постоянных, где скорость сходимости последовательностей рациональных чисел играет ключевую роль. На этом фоне отсутствие (насколько нам известно) приложений классических алгоритмов ускорения сходимости последовательностей к доказательствам иррациональности является пробелом, который необходимо восполнить.

В данной статье мы дадим выборочный обзор некоторых весьма эффективных алгоритмов ускорения сходимости “двойного применения”, а также ряд примеров их приложения. С одной стороны, эти алгоритмы весьма эффективны в численном анализе, ориентированном на высокоточные вычисления. С другой стороны, применение рациональной арифметики в этих алгоритмах позволяет, в принципе, получить строгие доказательства иррациональности некоторых фундаментальных постоянных. В частности, мы покажем, что для констант $\log 2$, $\zeta (2)$ и $\zeta (3)$ доказательства иррациональности могут быть получены довольно простыми средствами.

2. УСКОРЕНИЕ СХОДИМОСТИ В СМЫСЛЕ ДИРИХЛЕ

Преобразование последовательностей мы будем понимать как применение или конструирование некоторого алгоритма, преобразующего данную последовательность рациональных чисел в другую такую последовательность, которая сходится (вообще говоря) быстрее исходной. Либо то же, но преобразующее расходящийся ряд в сходящийся.

Существует множество таких алгоритмов, применимых к различным задачам, от классического метода Эйлера до современных методов суммирования типа метода Левина (см. обзор [3]).

Весьма похожие задачи возникают в аналитической теории чисел при доказательстве иррациональности некоторых фундаментальных констант. Например, известно, что ключевым моментом в доказательстве иррациональности числа $\zeta (3)$ было построение быстро сходящейся числовой последовательности (и цепной дроби), найденной Апери (см. [4], [5]).

С тех пор как Апери дал свое весьма неожиданное для современников доказательство иррациональности числа $\zeta (3)$ (а также и $\zeta (2)$ тем же методом, см. [5]), попытки развить данный успех можно охарактеризовать как конструирование все более быстро сходящихся рациональных приближений для нужных констант с помощью все более изощренных средств.

Однако схожесть задач “ускорения сходимости” в этих столь далеких разделах математики является чисто внешней, что объясняет, почему классические алгоритмы ускорения сходимости, широко применяемые в численном анализе, не нашли (насколько нам известно) приложений в теории чисел.

Хотя сам термин “ускорение сходимости” применяется в теории чисел, однако он понимается обычно как конструирование специальной быстро сходящейся последовательности для конкретного случая. Ярким примером такого специализированного ускорения является построение цепной дроби Апери из цепной дроби Эйлера в результате серии преобразований Бауэра–Муира (см. [6]).

В отличие от обычно понимаемой скорости сходимости как, скажем, количества членов ряда, которые требуется просуммировать,чтобы получить желаемый результат, скорость сходимости в теории чисел понимается в смысле Дирихле, т.е. в смыcле наилучшего диофантова приближения. Иными словами, последовательность рациональных чисел $\{ p{\text{/}}q\} $ хорошо приближает вещественное число $x$, если $\left| {p - q{\kern 1pt} x} \right|$ стремится к нулю. Поскольку знаменатели $q$ в такой последовательности не ограничены (иначе $x$ рационально), то необходимо, чтобы скорость сходимости измерялась величиной знаменателя $q$. Например,

В этом случае число $x$ должно быть иррациональным, так как в противном случае, т.е. $x = a{\text{/}}b$, $a,b \in \mathbb{N}{\kern 1pt} $, получим последовательность натуральных чисел $\left| {pb - qa} \right|$, которая стремится к нулю.

Таким образом, алгоритм ускорения сходимости может быть весьма хорош в обычном практическом смысле и совершенно непригоден для ускорения сходимости в смысле Дирихле. Покажем это на примере классического алгоритма Айткена и константы Эйлера–Гомпертца (см. [7]).

Константа Эйлера–Гомпертца выражается, например, как

где $\operatorname{Ei} (\,)$ – это интегральная экспонента.

Метод Айткена, как известно, точен на последовательностях $s(n)$, которые сходятся как геометрические. Поэтому данный метод имеет весьма ограниченное применение. Однако итерационный метод Айткена (см. [8], [9]) является весьма мощным ускорителем сходимости, применимым также к расходящимся рядам. Последний дается рекуррентным соотношением

Последовательность $A(n,1)$, $n = 1,2, \ldots $, соответствует обычному методу Айткена.

Как мы увидим, все имеющиеся (нелинейные) ускорители сходимости даются похожими рекуррентными схемами.

Последовательность $s(n)$ для константы Эйлера–Гомпертца имеет вид

т.е. данная последовательность быстро расходится. Тем не менее, так называемая диагональная (так как таблица традиционно строится в виде ромба) последовательность {$A(0,n)$, $n = 1,2, \ldots $} весьма быстро сходится к $\delta $. Например, $\left| {A(0,8) - \delta } \right|{{ < 10}^{{ - 9}}}$. Следующая диагональ $A(1,n)$ сходится к $\delta $ еще быстрее. Однако $A(0,8)$ выражается дробью, суммарное количество цифр в которой равно 10 206.

В дополнение к (1) приведем два классических (и довольно малоизвестных) критерия иррациональности, которые также служат контрпримерами для двух, казалось бы, самоочевидных вещей: дроби $\{ p{\text{/}}q\} $ в доказательстве иррациональности должны быть неприводимы; быстрее сходящаяся последовательность лучше, чем более медленно сходящаяся.

В критерии (1) мы не упомянули, что дроби $\{ p{\text{/}}q\} $ неприводимы, т.е. $p$ и $q$ взаимно просты. Очевидно, что критерий (1) можно легко нарушить, если брать приводимые последовательности дробей $\{ p{\text{/}}q\} $.

Однако, во-первых, последовательности целых чисел $p$ и $q$ могут генерироваться отдельно (хотя и, возможно, по одной рекуррентной формуле). Поэтому критерий (1) следует проверять для приведенной последовательности $\{ p{\text{/}}q\} $, а она может быть неизвестна.

Во-вторых, современные CAS автоматически приводят дроби к наименьшему знаменателю, но только если $p$ и $q$ не слишком велики.

Классический (слегка обобщенный) критерий иррациональности Бруна (см. [10]) состоит в следующем.

Пусть дана (a) возрастающая (или (b) убывающая) ограниченная последовательность рациональных чисел

где ${{q}_{n}} < {{q}_{{n + 1}}}$, $n \geqslant 1$. Тогда эта последовательность имеет предел, т.е. ${{p}_{n}}{\text{/}}{{q}_{n}} \to B$, $n \to \infty $. Пусть последовательность является (a) убывающей (или (b) возрастающей). Тогда число $B$ иррационально.

Данный критерий (сформулированный в [10] для случая (a)), по оценке самого Бруна, имеет весьма ограниченное применение. Однако он дает пример того, что приведение дробей может нарушить критерий иррациональности.

Рассмотрим последовательность

которая стремится к числу ${\mathbf{e}}$, но для которой критерий Бруна очевидно нарушается. Однако, если взять приводимую последовательность где $\Gamma (\,)$ – это обычная и неполная Гамма-функции, то, как показал еще сам Брун (см. [10]), критерий иррациональности Бруна выполнен.

Заметим также, что ряд (4) является разложением Энгеля для числа ${\mathbf{e}}$ (см. [11]), поэтому автоматически сходится к иррациональному числу.

На самом деле критерий Бруна оказывается значительно более вездесущим, чем это можно заключить по (весьма скудной) литературе об этом критерии. Справедлива следующая

Теорема. Пусть даны произвольное иррациональное число $0 < B < 1$ и его разложение в обыкновенную цепную дробь. Тогда последовательности (a) четных и (b) нечетных подходящих дробей удовлетворяют критерию Бруна (a) и (b) соответственно.

Доказательство. Любое иррациональное число $0 < B < 1$ однозначно раскладывается в обыкновенную цепную дробь по алгоритму Евклида:

Как известно, числители ${{p}_{n}}$ и знаменатели ${{q}_{n}}$ подходящих дробей удовлетворяют рекуррентным соотношениям

а последовательности $\{ {{p}_{{2{\kern 1pt} n}}}{\text{/}}{{q}_{{2{\kern 1pt} n}}}\} $ и $\{ {{p}_{{2{\kern 1pt} n - 1}}}{\text{/}}{{q}_{{2{\kern 1pt} n - 1}}}\} $ являются соответственно возрастающей и убывающей.

Критерии Бруна (a) и (b) для этих последовательностей записываются как

Утверждение теоремы следует из следующих тождеств:

На самом деле это не два тождества, а одно, что видно, если подставить туда $n = m{\text{/}}2$. Тогда получим

и еще такое же равенство, где $m \to m - 1$.

Последнее тождество тривиально проверяется заменой ${{p}_{{m + 3}}}$, ${{q}_{{m + 3}}}$, ${{p}_{{m + 1}}}$, ${{q}_{{m + 1}}}$ по их рекуррентным формулам. Что и требовалось доказать.

Ряд (4) для числа ${\mathbf{e}}$ можно преобразовать в цепную дробь Эйлера, т.е. эквивалентную цепную дробь, подходящие дроби которой равны частичным суммам $s(n)$ в (4):

Сходимость этой цепной дроби можно ускорить стандартными средствами, например, четным сжатием. Эта дробь имеет вид и сходится вдвое быстрее предыдущей.

Из первой дроби сразу видна иррациональность числа ${\mathbf{e}}$ по классическому критерию (Ламберта–)Лежандра (см. [12, p. 289–296]), так как частные дроби (или звенья в русскоязычной литературе) $\left| {{{a}_{n}}{\text{/}}{{b}_{n}}} \right| < 1$. Однако вторая более быстро сходящаяся дробь не удовлетворяет этому критерию.

В более общем виде критерий Лежандра известен как теорема Титце (см. [13, p. 252]) и формулируется следующим образом.

Пусть все частные числители ${{a}_{n}}$ и знаменатели ${{b}_{n}}$ в цепной дроби

являются целыми числами. И пусть, начиная с некоторого индекса $n$, Тогда цепная дробь сходится, и число $C$ иррационально, за исключением случая, когда начиная с некоторого индекса $n$, В последнем случае дробь либо несущественно расходится, либо $C$ рационально.

Таким образом, преобразование последовательности рациональных чисел для доказательства иррациональности ее предела не следует понимать как непременно ускорение ее сходимости. Пример с числом ${\mathbf{e}}$ показывает, что растяжение цепной дроби, т.е. замедление ее сходимости, может привести к успеху.

В заключение этого раздела приведем один курьезный случай, который служит иллюстрацией малоизвестности данного выше критерия.

На с. 226 книги [14] автор приводит со ссылкой на Лагерра две цепные дроби для константы Эйлера–Гомпертца (которая там равна $F(1)$):

Из второй дроби следует иррациональность константы Эйлера–Гомпертца по критерию Лежандра. Однако, к сожалению, вторая дробь ошибочна. Там следует заменить $2 \to 1{\text{/}}2$, $3 \to 1{\text{/}}3$ и т.д. Тогда будет правильно, но не будет критерия иррациональности.

3. ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Линейные преобразования последовательностей можно выразить в виде линейного оператора на множестве числовых последовательностей. Такие преобразования появились значительно раньше нелинейных, и они до сих пор пользуются большой популярностью. Мы не будем давать здесь исторического обзора и сравнительного анализа их эффективности, что можно найти в специализированной литературе, а сосредоточимся на некоторых из них, которые, по нашему мнению, могут найти применение в теории чисел.

Наиболее известным преобразованием последовательностей является метод Эйлера. Мы изложим обобщение этого метода и его эффективную реализацию в CAS.

Метод Эйлера обычно выводят в учебниках с помощью так называемого Umbral Calculus, т.е. путем формального манипулирования разностными операторами. Однако вывод этого метода с точки зрения комбинаторного преобразования последовательностей выглядит более прозрачным.

Пусть последовательности $\{ {{a}_{n}}\} $ и $\{ {{b}_{n}}\} $, $n \in \mathbb{N}{{{\kern 1pt} }_{0}}$, являются биномиальными преобразованиями друг друга, т.е.

где $C(n,m)$ – биномиальный коэффициент. И пусть $A(x)$ и $B(x)$ являются их соответствующими формальными производящими функциями, т.е. тогда справедливо тождество понимаемое как формальное преобразование степенных рядов.

Доказательство очевидно. Тождество (7) является инволюцией, так же как и биномиальное преобразование. Оба легко проверяются с помощью формальных манипуляций.

Если теперь подставить $x = - 1$ в уравнение (7), то получим классический ускоритель сходимости Эйлера

который справедлив для любых числовых последовательностей $\{ {{a}_{n}}\} $ и $\{ {{b}_{n}}\} $, $n \in \mathbb{N}{{{\kern 1pt} }_{0}}$, для которых хотя бы один из этих рядов сходится.

Иногда встречающееся в литературе утверждение, что метод Эйлера может преобразовать расходящийся ряд в сходящийся, справедливо только для исходно сходящегося степенного ряда для его суммирования, возможно, за пределами его круга сходимости, т.е. метод Эйлера не может просуммировать всюду расходящийся асимптотический ряд, что видно из инволюции (7).

Метод Эйлера можно обобщить, введя в уравнения произвольный числовой параметр $p$. Для этого в уравнении (7), записанном в виде рядов, нужно подставить ${{a}_{n}} \to {{a}_{n}}{\kern 1pt} {{( - p)}^{n}}$, затем $x \to x{\text{/}}p$, затем $x = - 1$. В результате получим

Например, формула Лейбница для числа $\pi $ принимает вид

где $F()$ – гипергеометрическая функция. Для $p = 1$ эта формула принимает вид Этот ряд, как легко проверить, сходится значительно быстрее исходного.

Существует эффективная имплементация метода Эйлера, которая носит название преобразования ван Вингардена (van Wijngaarden). Однако для параметризованного метода Эйлера такое преобразование неизвестно. Приведем это обобщение.

Рассмотрим последовательности частичных сумм

Предполагается, что последовательность $e(n)$ стремится к тому же пределу, что и $s(n)$, но быстрее (хотя это не факт). Рассмотрим рекуррентное соотношение Тогда Доказательство можно получить с помощью математической индукции.

Заметим, что диагональные последовательности $V(k,n)$, $n \in \mathbb{N}{{{\kern 1pt} }_{0}}$, для $k \geqslant 0$ стремятся (вообще говоря) к тому же пределу и, возможно, еще быстрее (что справедливо для ряда Лейбница).

Закончим рассмотрение метода Эйлера тем, что выведем одно ранее (вероятно) неизвестное комбинаторное тождество.

Тождество (8) на самом деле не зависит от $p$. Поэтому продифференцируем его по $p$ и упростим. В результате получим тождество

справедливое (если ряды сходятся) для любого числа $p$ и любой последовательности $\{ {{a}_{n}}\} $. Это тождество, разумеется, также можно дифференцировать.

Другой весьма популярный линейный метод ускорения сходимости – это экстраполяция Ричардсона (см. [3]). Мы изложим его в форме (предложенной Невиллем в [15]), удобной для реализации в CAS.

Пусть дана последовательность $s(n)$, сходимость которой требуется ускорить. Выбирается монотонная последовательность $t(n) \to 0$, $n \to \infty $, которая моделирует скорость сходимости $s(n)$. Последовательность $t(n)$ можно рассматривать как условное “время”, которое измеряет близость величины $s(n)$ к своему пределу в зависимости от близости величины $t(n)$ к нулю. Рассмотрим рекуррентное соотношение

Последнюю формулу легко модифицировать так, чтобы $t(n) \to \infty $.

Пусть, например, $s(n) = P(t(n))$, где $P(x) = {{a}_{m}}{\kern 1pt} {{x}^{m}} + \cdots + {{a}_{1}}{\kern 1pt} x + {{a}_{0}}$ – полином степени $m$. Тогда, как легко проверить, для любой последовательности $t(n)$, $R(n,k) \equiv {{a}_{0}}$ при $k \geqslant m$ и $n \in \mathbb{N}{\kern 1pt} $.

Иными словами, метод Ричардсона точен на полиномиальных последовательностях в указанном смысле. Поэтому, если последовательность $s(n)$ хорошо приближается такими последовательностями, и если удачно подобрать время $t(n)$, то последовательности $R(n,m)$, $n,m \in \mathbb{N}{\kern 1pt} $, могут весьма быстро сходиться.

Рассмотрим, например, последовательности частичных сумм для ряда Лейбница

где суммирование ведется до $2{\kern 1pt} n$, так как исходный ряд знакопеременный. Тогда

Метод Ричардсона, как и другие методы, рассмотренные ниже, весьма чувствителен к выбору времени $t(n)$, т.е. вспомогательной последовательности. Это относится как к скорости сходимости в обычном смысле, так и к скорости сходимости в смысле Дирихле. Никаких правил выбора $t(n)$, насколько нам известно, не существует.

Приведем пример, показывающий чувствительность метода Ричардсона к выбору вспомогательной последовательности $t(n)$.

Последовательность $H(n) - \ln n$, $n \to \infty $, стремится к константе Эйлера $\gamma $, где $H(n)$ – гармоническое число. Поэтому и $H({{n}^{2}}) - 2\ln n \to \gamma $. Таким образом, получаем последовательность рациональных чисел $2{\kern 1pt} H(n) - H({{n}^{2}}) = \gamma + O(1{\text{/}}n)$. На самом деле удобнее взять последовательность

Исходя из данной асимптотической оценки, возьмем $t(n) = 1{\text{/}}{{n}^{2}}$. Тогда получим где числитель и знаменатель числа $R(1,10)$ состоят из 74 цифр.

Теперь возьмем время $t(n) = 1{\text{/}}n{\text{/}}(n + 1)$, которое имеет примерно ту же асимптотику. Тогда получим

где числитель и знаменатель числа $R(1,10)$ состоят из 72 цифр.

Такую же точность аппроксимации можно получить в плавающей арифметике для исходной последовательности $H(n) - \ln n$ или, что лучше, для $H(n) - \ln (n + 1{\text{/}}2)$.

Метод Ричардсона, по-видимому, также не может просуммировать всюду расходящийся асимптотический ряд, хотя строгое доказательство этого, вероятно, отсутствует.

Рассмотрим два метода преобразования последовательностей, которые в некотором смысле дополняют друг друга.

Метод Эйлера–Маклорена (см. [16, p. 518]) суммирования рядов весьма эффективен в численном анализе, хотя он переводит (вообще говоря) сходящиеся ряды в расходящиеся асимптотические. Например,

где $B(n)$ – числа Бернулли, и равенстро следует понимать в асимптотическом смысле.

Аналогичные формулы выражают значения $\zeta (n)$, $n = 2,3, \ldots $, в виде асимптотических разложений полигамма функций (см. [17]).

Расходящиеся асимптотические ряды, полученные с помощью формулы Эйлера–Маклорена, могут быть отправлены на вторичную переработку и преобразованы в сходящиеся (см. ниже).

Напомним, что числа Стирлинга первого и второго рода, ${{S}_{1}}(n,m)$, ${{S}_{2}}(n,m)$, определяются следующими тождествами:

где есть символ Почхаммера (или восходящий факториал).

Один из (малоизвестных) способов преобразовать расходящийся ряд в сходящийся – это классическое факториальное преобразование (см. [18], [19]). Дадим его в более удобной форме.

Пусть последовательности $\{ {{a}_{n}}\} $ и $\{ {{b}_{n}}\} $, $n \in \mathbb{N}{{{\kern 1pt} }_{0}}$, являются преобразованиями Стирлинга друг друга, т.е.

Тогда справедливо тождество которое следует понимать в асимптотическом смысле, т.е. обе части (13) имеют одно и то же асимптотическое разложение в правой полуплоскости.

Тождество (13) можно обобщить так же, как мы это сделали с преобразованием Эйлера, т.е. ввести в него произвольный параметр $p$.

Формула (13) преобразует (вообще говоря) расходящийся асимптотический ряд слева в (13) в (вообще говоря) сходящийся ряд в некоторой полуплоскости $R < {\text{Re}}(x)$, $0 \leqslant R < \infty $ (см. [18], [19]). Таким образом, формула (13) является в некотором роде альтернативой теории моментов Стилтьеса, которая обосновывает преобразование асимптотических рядов в сходящиеся цепные дроби и Паде-аппроксимации (см. [20]).

Ряд примеров суммирования расходящихся рядов с помощью факториального преобразования (13) можно найти в [17]. Приведем пример для константы Эйлера–Гомпертца. Асимптотический ряд для нее имеет вид

Эйлер, как известно, просуммировал этот ряд с помощью преобразования в цепную дробь (см. [21]).

Возьмем $x = 1$ в (13) и (14). Тогда получим

Теперь нужно доказать, что ряд справа в (15) сходится, причем к константе $\delta $. Рассмотрим вспомогательный ряд

С помощью энциклопедии целых последовательностей [22] получаем Поэтому $f(1) = \delta $. Заметим также, что последний интеграл можно получить с помощью замен переменных из определения $\delta $ в (2).

Формула (13) является переформулировкой ($x \to 1{\text{/}}x$) факториального преобразования, рассмотренного в [17]. Приведем другое, как мы полагаем, более удобное преобразование расходящихся асимптотических рядов в сходящиеся.

Пусть последовательности $\{ {{a}_{n}}\} $ и $\{ {{b}_{n}}\} $, $n \in \mathbb{N}{{{\kern 1pt} }_{0}}$, являются преобразованиями типа Стирлинга друг друга, т.е. ${{a}_{0}} = {{b}_{0}}$, и

Тот факт, что эти преобразования инволютивны, как и традиционные преобразования Стирлинга, легко проверяется. Тогда справедливо асимптотическое тождество которое следует понимать так же, как и тождество (13), т.е. обе части (17) имеют одно и то же асимптотическое разложение при $0 < x \to \infty $.

Тождество (17) не эквивалентно формуле (13), хотя доказывается сходным образом (см. [17]). Насколько нам известно, формула (17), как и данные выше преобразования типа Стирлинга, ранее не публиковались. Формула (17) удобна тем, что при подстановке $x = 1$ в ее правую часть получим тейлоровские коэффициенты некоторой экспоненциальной производящей функции (так как ${{(1)}_{n}} = n!$, $n \in {{\mathbb{N}}_{0}}$).

Применим формулу (17) к асимптотическому ряду (14) для константы Эйлера–Гомпертца. Имеем ${{a}_{n}} = ( - {{1)}^{n}}{\kern 1pt} n!$, $n \in {\kern 1pt} \;{{\mathbb{N}}_{0}}$, и

Положим $x = 1$ в (17), тогда получим Теперь нужно доказать, что ряд в (18) сходится, причем к константе $\delta $. Рассмотрим вспомогательный ряд С помощью энциклопедии целых последовательностей [22] получаем Поэтому $\mathop {\lim }\nolimits_{z \nearrow 1} f(z) = \delta $. Последнее тождество можно также вывести интегрированием по частям тождества (16).

Применим преобразование (17) для вычисления константы Эйлера по формуле (11). Для этого более удобно взять второй комплект чисел Бернулли, в котором $B(1) = 1{\text{/}}2$, а не $B(1) = - 1{\text{/}}2$. Напомним, что первый комплект чисел Бернулли – это значения $B(n) = {{B}_{n}}(0)$, а второй – это значения $B(n) = {{B}_{n}}(1)$, где ${{B}_{n}}(x)$ – полиномы Бернулли. Эти два комплекта являются биномиальными преобразованиями друг друга.

Подставим $n = 1$ в (11), тогда получим тождество (полученное Эйлером)

Последнее равенство является своего рода “слепком” с хорошо известного асимптотического тождества

где $\psi (x) = (\ln \Gamma (x)){\kern 1pt} '$ – это дигамма-функция.

Имеем ${{a}_{n}} = B(n){\text{/}}n$, и

Положим $x = 1$ в (17), тогда получим

Теперь нужно доказать, что ряд в (20) сходится, причем к константе Эйлера $\gamma $. Рассмотрим вспомогательный ряд С помощью энциклопедии целых последовательностей [22] получаем Поэтому $\mathop {\lim }\nolimits_{z \nearrow 1} f(z) = \gamma $.

Последнее тождество является обобщением известной формулы для константы $\gamma $ (см. [23]), которая применялась (см. [24]) в ошибочном (см. [25]) доказательстве иррациональности константы Эйлера. Однако в [24] была получена правильная формула для коэффициентов разложения подынтегрального выражения в (21) в степенной ряд. Сравнивая эту формулу с нашим преобразованием, получаем (по-видимому) неизвестное ранее комбинаторное тождество

из которого находим

Пример с суммированием ряда Эйлера (19) для константы $\gamma $ показывает, что формула (17) имеет некоторые преимущества по сравнению с классическим факториальным преобразованием (13), так как мы не смогли получить с помощью последнего что-либо содержательное для константы $\gamma $.

Формулы (13) и (17) вместе с соответствующими преобразованиями Стирлинга могут рассматриваться как простое преобразование асимптотического ряда

Однако для последнего существует гораздо более простое преобразование типа биномиального, т.е. ${{a}_{0}} = {{c}_{0}}$, и что легко проверяется.

Например, если взять в (22) ${{a}_{n}} = ( - {{1)}^{n}}{\text{/}}(n + 1)$ и $x = 1$, то получим

т.е. вариант формулы суммирования Эйлера, с которой мы начали этот раздел.

Приведем одно весьма полезное (но редко используемое) тождество:

которое представляет собой ряд Ньютона, или сумму прямых (при $h > 0$), либо обратных (при $h < 0$) конечных разностей. Здесь $a$ – произвольный вещественный параметр. При конечном суммировании правая часть (23) (rhs(23)) – это интерполяционный полином Ньютона.

При $h \to 0$ формула (23) дает обычный ряд Тейлора в точке $x = a$.

Формула (23) может давать как сходящиеся ряды, т.е. разложения гладкой функции $f(x)$, так и расходящиеся асимптотические ряды.

Приведем  пример использования ряда Ньютона для вычисления константы Эйлера–Гомпертца. Напомним, что

т.е. для $f(x) = {\mathbf{e}}{\kern 1pt} \Gamma (x,1)$ значения $f(x)$ целочисленны при $x \in \mathbb{N}$. Причем они вычисляются по простой рекуррентной формуле $f(n) = (n - 1){\kern 1pt} f(n - 1) + 1$. Так как $f(0) = \delta $, то можно (попытаться) экстраполировать значения $f(n)$ в натуральных числах в число 0, т.е. выразить $\delta $ рядом Ньютона.

Для этого сначала подставим в (23) $h = 1$ (шаг интерполяции) и $a = 1$, а затем $x = 0$. Тогда получим

т.е. мы получили исходный асимптотический ряд для $\delta $.

Теперь возьмем $h = 1$, $a = 2$, а затем $x = 0$. Тогда получим

т.е. мы получили асимптотический ряд для $\delta $, который отличается от исходного отсутствием первых двух членов. Этот, казалось бы, парадоксальный результат объясняется очень просто: что легко проверяется интегрированием по частям.

Таким образом можно получить целую серию новых асимптотических разложений (и цепных дробей) для константы Эйлера–Гомпертца. Например, при $h = 1$, $a = 3$ получим

Однако формула (23) может давать и сходящиеся ряды для константы $\delta $. Возьмем, например, $f(x) = {\mathbf{e}}{\kern 1pt} \Gamma (x,1){\text{/}}\Gamma (x + 1)$. Далее, как и раньше, положим $h = 1$, $a = 1$. Тогда получим

Подстановка $x = 0$ в последнюю формулу дает (после некоторого исследования)

где $L(n,x)$ – полином Лагерра. Напомним, что

Для значений полиномов Лагерра в $x = 1$ существует довольно сложная асимптотическая формула, которую мы опускаем. Из нее следует, что $L(k,1){\text{/}}(k + 1) = O(1{\text{/}}{{k}^{{5/4}}})$, т.е. ряд (24) сходится, хотя и медленно.

Используя рекуррентную формулу для полиномов Лагерра, получаем линейную однородную рекурсию для частичных сумм $s(n)$ ряда (24):

где $s(0) = 1$, $s(1) = 1$, $s(2) = 5{\text{/}}6$. Эта рекурсия может быть преобразована стандартными средствами CAS в линейное ОДУ второго порядка (которое мы опускаем) для производящей функции последовательности $s(n)$. Полученное уравнение интегрируемо, так что имеем

Заметим, что полиномы Лагерра регулярно появляются при исследовании константы Эйлера–Гомпертца (см., например, [26]).

В завершение этого раздела вернемся к функции $f(x) = {\mathbf{e}}{\kern 1pt} \Gamma (x,1)$ с ее рекуррентной формулой $f(n) = (n - 1){\kern 1pt} f(n - 1) + 1$. Эту рекурсию легко записать в виде трехзвенного линейного однородного соотношения, т.е.

Действуя классическим способом, преобразуем эту рекурсию в цепную дробь. Получаем тождество ($n \to x$)

которое, очевидно, можно продолжить неограниченно, и которое справедливо во всей комплексной плоскости. При $x = 0$ левая часть (25) (lhs(25)) равна $1{\text{/}}\delta $, а правая часть (25) (rhs(25)) стремится к этому пределу при $x \to 0$.

Многие известные разложения в цепные дроби получены подобным образом из трехзвенных линейных рекурсий. Кажется очевидным, что полученная таким образом бесконечная цепная дробь (которая сходится по крайней мере при ${\text{Re}}(x) > 0$) дает разложение lhs(25), но это не так.

В самом деле, при $x = n \in \mathbb{N}{\kern 1pt} $, lhs(25) – это рациональное число, а rhs(25) – всегда иррациональное число согласно критерию Лежандра (или Титце, см. [13, p. 252]). Например, при $x = 1$, rhs(25) = $({\mathbf{e}} - 2){\text{/}}({\mathbf{e}} - 1)$, причем сходимость очень быстрая.

Как известно, сходимость и расходимость ряда и представляющей его цепной дроби могут сильно различаться по своим свойствам. Например, степенной ряд может расходиться, а его цепная дробь сходиться (см. [21] для $\delta $). Или цепная дробь может расходиться. Или ряд и его цепная дробь могут сходиться, но иметь разные области сходимости.

Хованский (см. [27, c. 30]) со ссылкой на Перрона (см. [13]) указал, что если ряд и его цепная дробь сходятся, то их сходимость к одному пределу, вообще говоря, не гарантирована, т.е. это открытая проблема.

Но что касается трехзвенных линейных соотношений, то для них существует ряд достаточных условий сходимости бесконечной цепной дроби к нужному пределу (см. [13, p. 289]). Для цепной дроби (25) эти условия, очевидно, не выполнены.

Тем не менее цепные дроби, полученные таким образом, могут давать эффективные рациональные аппроксимации нужных функций, если использовать их как модифицированные цепные дроби (см. [28]), т.е., например, заменить функциональную часть в rhs(25) на ее асимптотику.

4. НЕЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Линейные преобразования последовательностей, рассмотренные в предыдущем разделе, весьма эффективны для ускорения сходимости в обычном смысле. Нам не удалось построить с их помощью пример ускорения сходимости в смысле Дирихле так, чтобы выполнялся критерий (1). Однако это не означает, что такой пример не существует.

В данном разделе мы рассмотрим некоторые нелинейные ускорители сходимости и дадим их эффективную реализацию.

Наиболеее популярным (и разрекламированным) таким ускорителем является метод Левина (см. [29, p. 214]). Если пользователь в CAS вычисляет сумму бесконечного ряда, то система с большой вероятностью будет использовать метод Левина.

Однако сам этот алгоритм реализован в CAS в плавающей арифметике и скрыт от пользователя, а имеющиеся в открытом доступе алгоритмы весьма громоздки и также используют плавающую арифметику.

Поэтому мы дадим простой вариант метода Левина, пригодный для численного экспериментирования в рациональной (и плавающей) арифметике. Это же относится и к другим алгоритмам в этом разделе.

Теоретические основы метода Левина изложены в специализированной литературе (см., например, [30, p. 189]). Пусть дана числовая последовательность $s(n)$, $n \in {{\mathbb{N}}_{0}}$. Выбираются вспомогательная последовательность $\omega (n)$ и параметр $\beta $ (мы используем стандартные обозначения). Строится двумерная таблица $L(n,k) = {{L}_{1}}(n,k){\text{/}}{{L}_{2}}(n,k)$, где

Заметим, что в этой стандартной форме метода Левина общий множитель ${{(\beta + n + k)}^{{k - 1}}}$ в знаменателе сокращается. Он нужен лишь для нормализации вычислений в плавающей арифметике с фиксированной разрядной сеткой. Если же разрядность можно увеличивать или вычисления проводятся в рациональной арифметике, то данный алгоритм можно значительно упростить:

Метод Левина, как и его модификация (см. ниже), попали в разряд нелинейных лишь потому, что вспомогательная последовательность $\omega (n)$ обычно зависит от исходной последовательности, которую требуется просуммировать.

Вспомогательная последовательность $\omega (n)$ и параметр $\beta $ выбираются из чисто эмпирических соображений с учетом имеющейся информации (или гипотез) об асимптотике исходной последовательности. Как и ранее, диагональные последовательности $L(k,n)$ при фиксированном $k$ и $n \in \mathbb{N}$ дают (вообще говоря) хорошие приближения к пределу последовательности $s(n)$.

Основное достоинство метода Левина – это его универсальность. Он может суммировать как монотонные последовательности или знакопеременные сходящиеся ряды, так и знакопеременные расходящиеся ряды. Однако помимо этой последней возможности нам не удалось выявить преимущества данного метода по сравнению даже с методом Ричардсона для ускорения сходимости в обычном смысле.

Что касается ускорения сходимости в смысле Дирихле, то, по нашему мнению, этот метод уступает всем изложенным в этом разделе. Хотя этот вывод основан на ограниченном опыте.

Существует модификация метода Левина (см. [8], [9]). В тех же обозначениях двумерная таблица $U(n,k) = {{U}_{1}}(n,k)/{{U}_{2}}(n,k)$ строится следующим образом:

Здесь степени ${{(\beta + n + k)}^{{k - 1}}}$ и т.п. заменены на символы Почхаммера. Данный алгоритм также можно значительно упростить:

Например, возьмем последовательность (3) для константы Эйлера–Гомпертца. Выберем для нее $\beta = - 1$ и $\omega (n) = ( - {{1)}^{n}}{\kern 1pt} (n + 1)!$. Тогда получим (по явному алгоритму)

причем Заметим, что в этой последовательности рациональных приближений за исключением $n = 8$. Далее, к сожалению, эта закономерность не сохраняется. Здесь и далее num() и den() – это соответственно числитель и знаменатель рационального числа.

Заметим также, что при выбранных начальных данных рекурсивный алгоритм не работает, так как $\beta + n = 0$ при $n = 1$ в знаменателе. Однако это устранимая особенность, и при других параметрах эти алгоритмы эквивалентны.

Перейдем к изложению двух родственных методов, предложенных Винном (Wynn), и которые дополняют друг друга. Это так называемые $\varepsilon $- и $\rho $-алгоритмы. Как и ранее, мы отсылаем читателя к специализированной литературе по теоретическим основам этих методов. Они имеют огромную библиографию (см., например, [30]).

Пусть даны формальный ряд и последовательность его частичных сумм

Для $\varepsilon $-алгоритма положим тогда величины $W(j,n)$ для нечетных $n$ являются вспомогательными, и где $P[n + j,n](s)$ – диагональ Паде-таблицы, т.е. рациональные аппроксимации формального ряда $s$ в виде отношения полиномов степени $n + j$ и $n$ таких, что

Таким образом, $\varepsilon $-алгоритм дает верхнюю часть Паде-таблицы. Данное утверждение – это теорема 1 в [31].

Приведем дополнение к этому утверждению, которое легко проверяется, но отсутствует в литературе (насколько нам известно). При тех же условиях

т.е. $\varepsilon $-алгоритм дает также одну нижнюю диагональ Паде-таблицы.

Величины $W(j,n)$, $j < - 1$, в этом алгоритме не имеют смысла. Однако, если рассмотреть ряд $1{\text{/}}s$, т.е. обратный к $s$, то $\varepsilon $-алгоритм даст также и нижнюю часть Паде-таблицы для $s$.

Применим $\varepsilon $-алгоритм для последовательности (3), т.е. вычислим константу Эйлера–Гомпертца. Численный эксперимент показывает, что все диагональные последовательности $W(j,2{\kern 1pt} n)$, $j \geqslant - 1$, сходятся к этой константе, но медленно. Например,

Однако (относительно) медленно сходящаяся последовательность также может быть полезна, если известна общая формула для ее членов.

Закономерности в последовательности рациональных чисел часто бывают видны, если преобразовать ее в цепную дробь Эйлера (известную еще Д. Бернулли). Пусть дана сходящаяся последовательность $s(n)$. Рассмотрим ее как последовательность $s(n) = {{p}_{n}}{\text{/}}{{q}_{n}}$ подходящих дробей. Вычислим

где ${{p}_{0}} = 0$ и ${{q}_{0}} = 1$. Тогда

Рассмотрим теперь сходящиеся последовательности ${{s}_{k}}(n) = W(k,2{\kern 1pt} n)$, которые получаются по $\varepsilon $-алгоритму для константы Эйлера–Гомпертца.

Для ${{s}_{1}}(n)$ получим в точности цепную дробь (6). Заметим, что это по сути единственная цепная дробь для константы $\delta $, известная в настоящее время. Она приведена в Википедии. Вторая дробь для $\delta $ в Википедии, а также в [7], является ее растяжением. Четное сжатие дроби (6) рассматривалось в [26, (1)]. Ее подходящие дроби выражаются с помощью полиномов Лагерра.

Таким образом, хотя сам $\varepsilon $-алгоритм является существенно нелинейным, полученные последовательности рациональных приближений нужных констант могут выражаться с помощью линейных рекурсий или даже в явном виде.

Дадим еще две цепные дроби для $\delta $, полученные по этому алгоритму.

Последовательность ${{s}_{0}}(n) = W(0,2{\kern 1pt} n)$, т.е. главная диагональ, несколько лучше приближает $\delta $ (и с другим знаком невязки). Цепная дробь для нее (после преобразования к эквивалентной) имеет вид

Для последовательности ${{s}_{2}}(n) = W(2,2{\kern 1pt} n)$ цепная дробь имеет вид

Любопытно, что для данного асимптотического ряда, т.е. для (14), последовательности над- и поддиагональных Паде-аппроксимаций дают один и тот же ряд рациональных приближений, т.е. ${{\left. {W( - 1,2{\kern 1pt} n)} \right|}_{{x = 1}}} = {{\left. {W(1,2{\kern 1pt} n)} \right|}_{{x = 1}}}$, $n \in \mathbb{N}{{{\kern 1pt} }_{0}}$. В общем случае это, разумеется, неверно.

Применим теперь $\varepsilon $-алгоритм для вычисления $\ln 2$ по простейшему ряду:

Для диагональных Паде-аппроксимаций ${{s}_{0}}(n) = W(0,2{\kern 1pt} n)$, $n > 0$, получим причем т.е. мы получили ускорение сходимости в смысле Дирихле так, что критерий (1) выполнен. Это же относится к другим диагональным аппроксимациям.

Однако это пока экспериментальный факт, для доказательства которого необходимо выявить закономерности в этих рядах рациональных чисел.

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

В данном случае эти закономерности лучше наблюдаются в поддиагональной последовательности ${{s}_{{ - 1}}}(n) = W( - 1,2{\kern 1pt} n)$. Для нее получим

причем Цепная дробь для ${{s}_{{ - 1}}}(n)$ (после преобразования к эквивалентной) имеет вид В данной цепной дроби для $n \in \mathbb{N}$т.е. после начального отрезка длины 4 структура дроби “квазипериодична” с периодом 3.

Заметим, что эту же цепную дробь (за исключением начального куска) можно получить другим способом. Рассмотрим ряд

который является обратным к ряду для логарифма, который мы рассматривали. Сравнивая эту формулу с (21), получаем выражение для общего члена этого ряда ${{c}_{k}}$ и последовательности $s(n)$Последовательность $s(n)$ ускорим по $\varepsilon $-алгоритму как ${{s}_{1}}(n) = W(1,2{\kern 1pt} n)$, т.е. возьмем наддиагональную Паде-аппроксимацию. Но при вычислении цепной дроби по формуле (26) будем использовать последовательность $1{\text{/}}{{s}_{1}}(n)$. Поэтому получим ту же дробь для $\ln 2$.

Эти манипуляции понадобились нам для того, чтобы установить связь между $\ln 2$ и константой Эйлера $\gamma $. Согласно изложенному выше,

причем первый из этих рядов знакопеременный, а второй – знакопостоянный.

Иррациональность $\ln 2$, впрочем, следует из обычной цепной дроби для $\ln (1 + x)$. Применение $qd$-алгоритма (см. [30]) (который реализован в современных CAS) дает цепную дробь

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

Данный факт объясняется тем, что цепная дробь, полученная по $qd$-алгоритму, дает (через раз) диагональную и наддиагональную Паде–аппроксимации отрезков степенного ряда. Однако $\varepsilon $-алгоритм значительно проще и обладает большими возможностями.

Перейдем к изложению $\rho $-алгоритма, который обычно используют для ускорения монотонных последовательностей, для которых $\varepsilon $-алгоритм неэффективен. Однако, как мы увидим, $\rho $‑алгоритм работает и для знакопеременных рядов (упоминание чего мы не нашли в литературе).

Пусть дана последовательность $s(n)$ (например, частичных сумм ряда $s$). Выберем последовательность $t(n)$, $n \in \mathbb{N}$, моделирующую скорость сходимости $s(n)$ к своему пределу. Таким образом, рассматриваются сходящиеся ряды или последовательности. Считается, что $\rho $-алгоритм не применим к расходящимся рядам, хотя доказательство этого факта мы не нашли в литературе.

В отличие от метода Ричардсона (см. разд. 3) последовательность $t(n)$ может стремиться к нулю или к другой константе, или к бесконечности, а также быть осциллирующей в случае, если таковой является последовательность $s(n)$.

Построим двумерную таблицу $T(n,k)$, $n,k \in {{\mathbb{N}}_{0}}$, по рекуррентному соотношению

Мы использовали данное обозначение потому, что $\rho $-алгоритм на самом деле идентичен алгоритму Тиле построения интерполяционной рациональной аппроксимации в виде цепной дроби. Мы обнаружили данный факт эмпирически, но он, разумеется, уже известен (см. [32]).

Данное свойство $\rho $-алгоритма сразу показывает его сходство и отличие от метода Ричардсона. В отличие от последнего, $\rho $-алгоритм точен на последовательностях значений рациональных функций (а значит, и полиномиальных).

Однако, в отличие от $\varepsilon $-алгоритма, $\rho $-алгоритм не дает Паде-аппроксимаций отрезков ряда, а строит свои рациональные аппроксимации.

Дадим обобщение алгоритма Тиле для построения интерполирующей цепной дроби.

Выберем значение $p \in \{ - 1,0,1,2, \ldots \} $, которое является параметром. Пусть $s(n) = f(t(n + p))$, т.е. последовательность $s(n)$ является значениями функции $f(x)$ в точках $x = t(n + p)$, $n \in \mathbb{N}{\kern 1pt} $. Положим

Тогда цепная дробь по построению является рациональной функцией и ${{f}_{n}}(x) = f(x)$ в узлах интерполяции $x \in \{ t(p + 1),t(p + 2), \ldots ,t(p + n)\} $.

Таким образом, цепная дробь ${{f}_{n}}(x)$ обрывается в случае, если $f(x)$ является рациональной функцией.

Пусть теперь ${{\lim }_{{n \to \infty }}}t(n) = {{t}_{*}}$, где ${{t}_{*}}$ пока конечно. Тогда бесконечная цепная дробь ${{f}_{\infty }}({{t}_{*}})$ сходится (вообще говоря) к значению $f({{t}_{*}})$. Например, при $t(n) \to 0$ для вычисления ${{a}_{n}}$ и ${{b}_{n}}$ сразу можно положить $x = 0$ и т.п.

Традиционно $\rho $-алгоритм используется при $t(n) \to \infty $, причем монотонно. Обычно берут $t(n) = n$ (что было в оригинальном $\rho $-алгоритме Винна, см. [33]). Так же, как и для $\varepsilon $-алгоритма, вычисляются диагональные последовательности $T(j,2{\kern 1pt} n)$, но здесь $j \geqslant 0$. Величины $T(j,n)$ для нечетных $n$ также являются вспомогательными.

Укажем на эквивалентность данного алгоритма алгоритму Тиле. Можно проверить, что

Однако алгоритм Тиле является значительно более общим, так как $t(n)$ может стремиться к любому пределу, причем цепные дроби ${{f}_{{2{\kern 1pt} n + 1}}}(x)$ также имеют смысл.

Приведем пример применения алгоритма Тиле к осциллирующей последовательности, что для $\rho $-алгоритма считается недопустимым. Возьмем произведение Валлиса

где общий член ${{c}_{n}}$ имеет вид

Заметим, что мы могли бы попарно перемножить соседние члены этого произведения и получить монотонную последовательность (и сходный результат). Но мы возьмем осциллирующую последовательность произведений ${{c}_{n}}$ с узлами интерполяции $t(n) = ( - {{1)}^{n}}{\text{/}}(n + 1)$. Выбор $t(n) = ( - {{1)}^{n}}{\text{/}}n$ здесь был бы крайне неудачным, что априори ниоткуда не следует.

Выберем параметр $p = 0$ и положим $x = 0$ в (27). Тогда для ${{f}_{n}}(0)$ в (28) получим (после преобразования эквивалентности)

где закономерность в частных знаменателях очевидна, а для числителей

Данная цепная дробь лишь немного не дотягивает до критерия Дирихле (1). Имеем

причем

Применим $\rho $-алгоритм для вычисления $\zeta (2)$ по ряду

который, как известно, сходится очень медленно (Базельская проблема).

Возьмем $t(n) = n$ (как в оригинальном алгоритме Винна). Тогда для ${{s}_{0}}(n) = T(0,2{\kern 1pt} n)$ получим

с невязками причем Таким образом, мы получили также ускорение сходимости в смысле Дирихле, т.е. критерий (1) выполнен. Это же относится к другим диагональным аппроксимациям, хотя, например, последовательность ${{s}_{1}}(n) = T(1,2{\kern 1pt} n)$ лучше приближает $\zeta (2)$ численно, но хуже в смысле Дирихле.

Преобразуем теперь последовательность ${{s}_{0}}(n) = T(0,2{\kern 1pt} n)$ в цепную дробь Эйлера по формулам (26). Тогда получим (после преобразования эквивалентности)

где ${{a}_{1}} = 5$, и ${{a}_{n}} = (n - {{1)}^{4}}$, $n > 1$; ${{b}_{n}} = 11{{n}^{2}} - 11{\kern 1pt} n + 3$, $n \geqslant 1$.

На самом деле, мы получили в точности цепную дробь Апери для $\zeta (2)$ (см. [5], [34]). Хотя сам Апери не привел ее в явном виде, и данная цепная дробь не получила широкой известности, но она есть в [5] в виде своих подходящих дробей.

Таким образом, последовательность (30) известна в явном виде (см. [34]). Для удобства читателя приведем готовые формулы. Пусть

где Тогда (30) = $\{ b(n){\text{/}}a(n)\} $, $n \in \mathbb{N}{\kern 1pt} $.

Данный алгоритм также демонстрирует чувствительность к выбору вспомогательной последовательности $t(n)$, что видно на следующем примере.

Применим $\rho $-алгоритм для вычисления $\zeta (3)$ по ряду

с той же последовательностью $t(n) = n$. Тогда получим примерно такой же результат ускорения сходимости численно (т.е. примерно с теми же невязками), что и для $\zeta (2)$, но непригодный в смысле Дирихле.

Возьмем теперь $t(n) = n{\kern 1pt} (n + 1)$. Тогда для ${{s}_{0}}(n) = T(0,2{\kern 1pt} n)$ получим

с невязками причем т.е. мы экспериментально установили иррациональность $\zeta (2)$ и $\zeta (3)$ с помощью классического алгоритма ускорения сходимости.

Заметим, что если взять последовательность $t(n) = {{n}^{2}}$, которая асимптотически почти идентична предыдущей, то получим результат ускорения для $\zeta (3)$ значительно хуже, чем для $t(n) = n$ в численном смысле, и совершенно непригодный в смысле Дирихле. Например,

Данный факт еще раз показывает, что никаких априорных правил для выбора вспомогательной последовательности $t(n)$ пока что не существует, как и исследований в этом направлении.

Преобразуем теперь последовательность ${{s}_{0}}(n) = T(0,2{\kern 1pt} n)$ для $\zeta (3)$ в цепную дробь Эйлера по формулам (26). Тогда получим (после преобразования эквивалентности)

где ${{a}_{1}} = 6$ и ${{a}_{n}} = - {{(n - 1)}^{6}}$, $n > 1$; ${{b}_{n}}4{\kern 1pt} {{n}^{3}} - 51{\kern 1pt} {{n}^{2}} + 27{\kern 1pt} n - 5$, $n \geqslant 1$.

На самом деле, мы получили в точности цепную дробь Апери для $\zeta (3)$ (см. [5], [34]). Ранее эта цепная дробь (как и аналогичная для $\zeta (2)$) выводилась гораздо более извилистым путем. Помимо [5], эта дробь была получена в [6] в результате ускорения сходимости цепной дроби Эйлера для ряда (31) с помощью серии преобразований Бауэра–Муира.

Таким образом, последовательность (32) также известна в явном виде (см. [34]). Для удобства читателя приведем готовые формулы. Пусть

где Тогда (32) = $\{ b(n){\text{/}}a(n)\} $, $n \in \mathbb{N}{\kern 1pt} $.

Заметим, что сам Апери не объяснил, как он пришел к последовательностям (30) и (32) (см. [4]).

Мы попытались также применить найденные аналогии для ускорения сходимости последовательностей

Однако они не работают.

Так, например, можно было ожидать, что выбор $t(n) = n{\kern 1pt} (n + 1){\kern 1pt} (n + 2)$ приведет к успеху для $\zeta (4)$, но это не так. Выбор $t(n) = n$ оказался самым удачным, но только для численного ускорения сходимости. То же для $\zeta (5)$: выбор $t(n) = n{\kern 1pt} (n + 1)$ оказался самым удачным, но непригодным для ускорения сходимости в смысле Дирихле.

По-видимому, между $\zeta (2)$, $\zeta (3)$ и последующими значениями $\zeta (s)$, $s > 3$, существует некий барьер, природа которого пока не ясна.

Это проявляется не только в конструировании быстро сходящихся рациональных приближений для этих констант. Другой пример дают асимптотические разложения полигамма функций (см., например, [17]). Эти разложения можно преобразовать в сходящиеся цепные дроби. При этом для ${{\psi }_{1}}(1) = \zeta (2)$ и ${{\psi }_{2}}(1) = - 2{\kern 1pt} \zeta (3)$ получаются просто устроенные дроби с легко выявляемыми закономерностями (см. [17]). Но для ${{\psi }_{3}}(1)$ и далее не удается получить ничего содержательного.

Асимптотические разложения полигамма функций использовались в [28] для конструирования эффективных рациональных аппроксимаций этих функций. Однако были предъявлены (без объяснения причин) только аппроксимации для ${{\psi }_{1}}(x)$ и ${{\psi }_{2}}(x)$ (см. [28, p. 229]).

По нашему мнению, аппроксимации для ${{\psi }_{3}}(x)$ и далее получаются просто слишком громоздкими и без выявленных закономерностей в их структуре. Поэтому они, вероятно, бесполезны.

Для строгого доказательства иррациональности $\zeta (2)$ и $\zeta (3)$ приведенных результатов, разумеется, недостаточно. Однако в литературе не раз отмечалось, что получение этих приближений являлось ключевым моментом в доказательстве.

Таким образом, для доказательства иррациональности числа необходимо как минимум два ингредиента: последовательность рациональных приближений должна быстро сходиться в смысле Дирихле; и требуется установить закономерности в этой последовательности.

Алгоритм Тиле (он же $\rho $-алгоритм) комбинирует эти условия по принципу “два в одном”.

Закономерности в последовательности рациональных приближений часто видны в цепной дроби, полученной из нее. Однако в отличие от $\varepsilon $-алгоритма для алгоритма Тиле нет нужды использовать цепную дробь Эйлера. Можно сразу строить цепную дробь Тиле по формулам (27).

Дадим пример такой дроби для константы Апери $\zeta (3)$. Для $\zeta (2)$ результаты аналогичны, и мы их опускаем.

Для последовательности (31) возьмем параметр $p = 0$ и узлы интерполяции $t(n) = 1{\text{/}}n{\text{/}}(n + 1)$. Заметим, что выбор $t(n) = 1{\text{/}}{{n}^{2}}$ здесь также был бы крайне неудачным. Поскольку $t(n) \to 0$, то в (27) сразу можно положить $x = 0$. Тогда для ${{f}_{n}}(0)$ в (28) получим (после преобразования эквивалентности)

где ${{a}_{1}} = 3$, ${{a}_{2}} = - 8$ и а также ${{b}_{0}} = 1$, ${{b}_{1}} = 16$ и

Эта дробь обладает аппроксимационными свойствами, которые несколько уступают таковым у цепной дроби Апери, однако вполне достаточными для установления иррациональности $\zeta (3)$. Имеем

причем

Заметим также, что в алгоритме Тиле требуются диагональные последовательности вдвое меньшей длины, чем в обычном $\rho $-алгоритме, так как там величины $T(j,2{\kern 1pt} n - 1)$ являются вспомогательными. Иными словами, нужно сравнивать четное сжатие данной дроби с цепной дробью Апери, и тогда наша дробь сходится быстрее, чем дробь Апери, численно и почти так же в смысле Дирихле.

Наконец, применим алгоритм Тиле к ускорению последовательности (9) с тем же временем $t(n) = 1{\text{/}}n{\text{/}}(n + 1)$. Тогда получим, что цепные дроби ${{f}_{{10}}}(0)$ дают лучшую оценку, чем (10), для $p = 0,1,2, \ldots $. Причем порядок точности увеличивается вместе с $p$. Однако полученные дроби имеют очень большую длину, так что метод Ричардсона здесь более предпочтителен.

В заключение этого раздела отметим, что представленные нами алгоритмы весьма просто реализуемы в современных CAS именно благодаря их рекурсивности.

В некоторых старых учебниках по численному анализу встречаются утверждения, что рекурсии в программах реализуются в виде циклов. Для современных CAS это, конечно, не так. Рекурсии в CAS реализуются в виде внутренних таблиц, которые система строит и пополняет по мере надобности. Так что пользователю нет смысла резервировать память и самому организовывать вычисления. Можно просто обратиться к нужной величине.

5. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ КРИТЕРИЯ БРУНА

Здесь мы рассмотрим некоторые теоретико-числовые модификации приведенных алгоритмов и их приложения (вместе с критерием Бруна) к доказательствам иррациональности.

Как мы видели, некоторые алгоритмы генерируют последовательности рациональных приближений, которые позволяют сразу сделать вывод об иррациональности их предела по критерию (1).

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

С другой стороны, эти алгоритмы могут давать исключительно хорошие рациональные приближения нужных констант, но численно, т.е. в обычном смысле. Иными словами, полученная последовательность непригодна для доказательства иррациональности нужной константы напрямую.

Обыкновенные цепные дроби дают наилучшие рациональные приближения нужной константы, причем в двух смыслах (см. [35]). Но может оказаться, что алгоритм ускорения сходимости дает на каждом шаге $n$ (возможно, с запаздыванием, т.е. начиная с шага $m > 1$) лучшее рациональное приближение численно, чем $n$-я подходящая дробь этой константы. Насколько нам известно, таких замеров скорости сходимости, например, для константы Апери никто не делал.

Смысл данных замечаний поясняет следующая

Лемма 1. Пусть даны произвольное иррациональное число $x > 0$ и его разложение в обыкновенную цепную дробь. И пусть рациональное число $y$ находится между двумя подходящими дробями числа $x$, ${{p}_{n}}{\text{/}}{{q}_{n}}$ и ${{p}_{{n + 1}}}{\text{/}}{{q}_{{n + 1}}}$, $n \in \mathbb{N}{\kern 1pt} $. Тогда подходящие дроби числа $y$ совпадают с таковыми для числа $x$ вплоть до $n$-й включительно.

Доказательство очевидно. Число $x$ можно записать как конечную цепную дробь $x = [{{b}_{0}};{{b}_{1}},{{b}_{2}}, \ldots ,{{b}_{{n + 1}}},r]$, где $0 < r < \infty $ – это некоторое вещественное число. Тогда

поэтому существует рациональное $0 < s < \infty $ такое, что

Лемма 1 доказана.

Очевидным следствием леммы 1 является тот факт, что если последовательность $\{ s(n)\} $ сходится к своему пределу $x$ быстрее, чем последовательность подходящих дробей $\{ {{p}_{n}}{\text{/}}{{q}_{n}}\} $ числа $x$ (которую мы обозначим, как $\{ K(x,n)\} $) (причем быстрее в обычном, численном смысле), то последовательность подходящих дробей $\{ K(s(n),n)\} $ совпадает с таковой для числа $x$, т.е. $K(x,n) = K(s(n),n)$, $n > {\text{const}}$.

Проиллюстрируем это наблюдение на последовательности (4). Возьмем число ${\mathbf{e}} - 2$. Тогда

Предложение. Последовательность $\{ s(n) - 2\} $ $(4)$ сходится к своему пределу ${\mathbf{e}} - 2$ быстрее, чем последовательность его подходящих дробей.

Поэтому, согласно лемме 1, последовательность подходящих дробей числа ${\mathbf{e}} - 2$ (начиная с $n = 4$) можно генерировать прямо по последовательности частичных сумм $\{ s(n) - 2\} $ (4). Разумеется, это пока экспериментальный факт. Мы проверили его до $n = 100$.

Этот пример объясняет, почему существует столько простых доказательств иррациональности числа ${\mathbf{e}}$. Иррациональность этого числа прямо следует из его разложения (4) в указанном нами смысле, так как последовательности подходящих дробей удовлетворяют критериям Бруна (см. теорему в разд. 2).

По-видимому, эта ситуация является типичной, т.е. последовательность подходящих дробей иррационального числа $x$ сходится к своему пределу (вообще говоря) медленнее, чем последовательность частичных сумм ряда Энгеля числа $x$ (см. [11]). Мы проверили это наблюдение для некоторых известных констант.

В то же время легко построить контрпример, например,

Это разложение Энгеля, как можно проверить, сходится заметно медленнее, чем последовательность $\{ K(v,n)\} $.

Заметим, что, во-первых, вычисление любой подходящей дроби рационального числа (например, на компьютере) – это вполне детерминистский процесс, основанный на алгоритме Евклида, и он всегда конечен. Для иррационального числа, т.е. практически для числа, заданного в плавающей арифметике, это всегда не так. Иными словами, мы не можем строго гарантировать правильность всех найденных подходящих дробей, даже если есть возможность увеличивать разрядную сетку.

В рациональной арифметике все эти проблемы со “стохастичностью” не существуют, и вычисления можно считать доказательными.

Во-вторых, само число $x$, иррациональность которого под вопросом, вообще не участвует в данной вычислительной схеме. Число $x$ получается как предел последовательности, которая выглядит как (а значит, и является, см. лемму 2 ниже) последовательность подходящих дробей некоторого числа, которое и есть $x$. Иррациональность при этом автоматически следует из критериев Бруна (см. теорему в разд. 2). Поэтому доказательством иррациональности числа $x$ в данной ситуации было бы доказательство того, что данный процесс не обрывается и не стабилизируется.

Лемма 2. Пусть дана сходящаяся последовательность рациональных чисел $s(n) = {{p}_{n}}{\text{/}}{{q}_{n}}$. Тогда она является $($начиная с некоторого индекса $n)$ последовательностью подходящих дробей своего предела $x$ тогда и только тогда, когда

При этом ${{b}_{n}}$ являются частными знаменателями $($начиная с некоторого индекса $n)$ в разложении числа $x$ в обыкновенную цепную дробь.

Доказательство следует из рекуррентного соотношения (5).

Заметим также, что в условиях леммы 2 цепная дробь Эйлера, вычисленная для этой последовательности по формулам (26), автоматически будет иметь (начиная с некоторого индекса $n$) частные числители ${{a}_{n}} = 1$, что проверяется простой выкладкой.

И, наконец, в случае, если не все ${{b}_{n}}$ в лемме 2 окажутся целыми, эти члены последовательности можно просто опустить. Цепная дробь Эйлера, полученная из этой подпоследовательности по формулам (26), окажется некоторым сжатием обыкновенной цепной дроби числа $x$.

Приведем простой пример, как работают леммы 1 и 2 вместе. Рассмотрим уравнение

корнем которого является ${{x}_{*}} = \sqrt[3]{2}$. Положим ${{x}_{0}} = 1$ и что является методом Ньютона решения нелинейного уравнения $f(x) = 0$.

Метод Ньютона, как известно, имеет квадратичную сходимость. Поэтому последовательность $K({{x}_{n}},n)$ даст подходящие дроби числа $\sqrt[3]{2}$. Однако сходимость оказывается столь быстрой, что значительно проще использовать модификацию метода Ньютона

Тогда получим все подходящие дроби ${{x}_{n}} = K(\sqrt[3]{2},n)$, $n \geqslant 1$, числа $\sqrt[3]{2}$. Частные знаменатели ${{b}_{n}}$, $n \geqslant 3$, получим по лемме 2:

Этот метод генерации подходящих дробей числа $x$ с использованием только рациональной арифметики и с сертификатом качества (лемма 2) имеет очевидные преимущества по сравнению с методами генерации подходящих дробей, использующими априорную информацию о числе $x$ и плавающую арифметику.

Как известно, алгебраические иррациональности хуже приближаются рациональными числами, чем трансцендентные. Поэтому весьма вероятно, что метод Ньютона в сочетании с леммами 1, 2 дает эффективный способ разложения корней полиномиальных уравнений в обыкновенные цепные дроби. Например, для полинома $f(x) = {{x}^{5}} - 2{\kern 1pt} {{x}^{4}} + 7{\kern 1pt} {{x}^{3}} + 3{\kern 1pt} {{x}^{2}} - 1$, имеющего корень ${{x}_{*}} \approx 0.420232964 \approx 2{\text{/}}5$, получим этим способом все подходящие дроби $K({{x}_{*}},n)$, начиная со второй. В частности, оборвав цепную дробь перед (локально) большим частным знаменателем, получим рациональное приближение

Дадим еще один пример для трансцендентного уравнения. Рассмотрим уравнение

корнем которого является ${{x}_{*}} = \pi {\text{/}}4$. Положим ${{x}_{0}} = 1$ и где и Здесь $P(x,n)$ и $Q(x,n)$ в (34) – это отрезки рядов Тейлора для функций $\cos x - \sin x$ и $\cos x + \sin x$ соответственно. Тогда получим все подходящие дроби ${{x}_{n}} = K(\pi {\text{/}}4,n)$, $n \geqslant 1$, числа $\pi {\text{/}}4$, причем верхние показатели суммирования в (34) не могут быть уменьшены (иначе получим не все подходящие дроби). Частные знаменатели ${{b}_{n}}$, $n \geqslant 3$, получим по лемме 2:

Применим леммы 1, 2 вместе с нашими наблюдениями к некоторым рациональным последовательностям, полученным в предыдущих разделах.

Цепная дробь (29), полученная с помощью алгоритма Тиле из произведения Валлиса, сходится несколько медленнее (в обычном смысле), чем последовательность подходящих дробей числа $\pi {\text{/}}2$. Однако последовательность четных подходящих дробей дроби (29), как оказалось, сходится быстрее, чем это может обеспечить обычная цепная дробь числа $\pi {\text{/}}2$. Поэтому подходящие дроби последней можно генерировать как $K(\pi {\text{/}}2,n) = K({{f}_{{2{\kern 1pt} n}}}(0),n)$, $n \geqslant 1$, где ${{f}_{n}}(0)$ вычисляются по формуле (27).

Последовательность (30), которая совпадает с последовательностью подходящих дробей дроби Апери для числа $\zeta (2)$ (см. [5]), дает все подходящие дроби константы $\zeta (2)$, т.е. $K(\zeta (2),n) = K({{s}_{0}}(n),n)$, $n \geqslant 1$.

Последовательность (32), которая совпадает с последовательностью подходящих дробей дроби Апери для числа $\zeta (3)$ (см. [5]), дает все подходящие дроби константы $\zeta (3)$, начиная со второй, т.е. $K(\zeta (3),n) = K({{s}_{0}}(n),n)$, $n \geqslant 2$.

Для последующих значений $\zeta (\sigma )$, $\sigma > 3$, как было отмечено, не удается получить последовательности рациональных приближений, которые удовлетворяли бы критерию (1). Однако это не означает, что полученные приближения плохи. Напротив, они весьма хороши в обычном, численном смысле.

Как оказалось, для ускорения последовательностей (33) по $\rho $-алгоритму нужно взять

Никакой другой выбор $t(n)$ не давал даже похожих результатов.

Последовательность ${{s}_{0}}(n) = T(0,2{\kern 1pt} n)$ для числа $\zeta (4)$, полученная по $\rho $-алгоритму, дает все подходящие дроби константы $\zeta (4)$, начиная с третьей, т.е. $K(\zeta (4),n) = K({{s}_{0}}(n),n)$, $n \geqslant 3$. При этом диагональные последовательности ${{s}_{k}}(n) = T(k,2{\kern 1pt} n)$, $k > 0$, сходятся быстрее, чем ${{s}_{0}}(n)$, но имеют большую длину (как и для последующих значений $\zeta (s)$).

Подчеркнем, что данный алгоритм корректно определен и не зависит от априорного знания чего-либо о константах $\zeta (s)$.

Для констант $\zeta (5)$, $\zeta (6)$, $\zeta (7)$ мы сгенерировали таким образом все их подходящие дроби (до 100-й включительно), начиная с третьей, по их последовательностям ${{s}_{0}}(n) = T(0,2{\kern 1pt} n)$. За исключением $K({{s}_{0}}(42),42) - K(\zeta (6),42) \approx 0.1670026257 \times {{10}^{{ - 40}}}$.

Для константы $\zeta (8)$ по какой-то причине подходящие дроби получаются только начиная с седьмой. Но для $\zeta (9)$ они получены начиная с четвертой.

Вообще, $\zeta (2{\kern 1pt} n)$, как оказалось, приближаются хуже, чем $\zeta (2{\kern 1pt} n + 1)$, $n \geqslant 1$, что видно уже по приближениям, полученным Апери в [5]. Наши результаты лишь подтверждают эту тенденцию. Вероятно, это как-то связано с тем, что величины $\zeta (2{\kern 1pt} n + 1)$ являются, в каком-то смысле, “более трасцендентными”, чем $\zeta (2{\kern 1pt} n)$.

Наконец, вернемся к ускорению последовательности (9) (см. также 3-й с конца абзац разд. 4). Последовательность ${{s}_{1}}(n) = R(1,n)$ для константы Эйлера $\gamma $, полученная по методу Ричардсона (см. разд. 3), дает все подходящие дроби константы $\gamma $, т.е. $K(\gamma ,n) = K({{s}_{1}}(n),n)$, $n \geqslant 1$. Мы проверили это до $n = 100$. Частные знаменатели ${{b}_{n}}$, $n \geqslant 3$, получим по лемме 2, а ${{b}_{1}} = {{b}_{2}} = 1$ получим из уравнений

т.е. для $n \in \mathbb{N}{\kern 1pt} $При этом

Заметим, что ранее алгоритмы вычисления обыкновенной цепной дроби константы $\gamma $ использовали плавающую арифметику и предварительное вычисление этой константы по другим алгоритмам с очень высокой точностью (см., например, [36]).

Как мы видели, леммы 1, 2 и теорема в разд. 2 прямо указывают на связь скорости сходимости ряда (или последовательности) с иррациональностью его суммы (ее предела). Разумеется, эта связь была отмечена уже давно и многими авторами (см. [37] и ссылки там). Однако это было сделано совершенно в другом контексте.

Так, в [37] был дан “в определенном смысле неулучшаемый” критерий иррациональности суммы ряда

который является переформулировкой критерия Бруна. Этот же критерий можно получить, преобразовав этот ряд в цепную дробь Эйлера и применив критерий Лежандра.

Однако критерий (35) предъявляет очень сильно завышенные требования к скорости сходимости, так как ряд (4) ему, очевидно, не удовлетворяет.

Для константы Эйлера $\gamma $ можно предъявить (в явном виде) последовательность рациональных чисел, которая сходится как угодно быстро. Для этого следует использовать прием, который мы применили в разд. 3 для последовательности (9). Например, для $n \in \mathbb{N}{\kern 1pt} $

Ясно, что так можно получить асимптотику рациональной последовательности $s(n) \to \gamma $, которая будет сильнее любой наперед заданной асимптотики. При этом числители и знаменатели в таких последовательностях известны в явном виде, так как

Таким образом, если удастся получить каким-либо способом априорную оценку скорости сходимости подходящих дробей данного числа, то доказательством его иррациональности было бы предъявление последовательности рациональных чисел, которая сходится заведомо быстрее.