Очерк о цепных дробях

16

Очерк
о цепных дробях

Кандидат физико-mатематических наук
Ю. В. НЕСТЕРЕНКО,
доктор физико-mатематических наук
Е. М. НИКИШИН

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

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

Календарь, зубчатые колеса и немного истории

Сколько дней в году? Все знают, что в общном году 365 дней, а в высоком — 366 дней. Високосными объявленными годы, номер которых делится на 4, например, 1904, 1908, …, 1980, 1984, …, 1996. Однако годы 1800, 1900, 2100, 2200 не объявляются высокими, а годы 2000, 2400, 2800 будут высокими. Почему?

Механика календаря довольно проста. Земля равномерновращается вокруг своей оси, делая один оборот за сутки. Один круг обращения Земли вокруг Солнца составляет один год и этот год равен 365,24219878… суток. Конечно, можно сказать, что добавка 0,242… суток мала. Оdnako с течение времени она накалливается, если положить год равным 365 суток. В древности, когда знание длительного года в сутках было весма приближенным, накалливаемая ошибка достигла серверных размеров. Так в Риме в 46 г. до н. э. отставание составляет 90 дней!

Чтобы установить закономерность черезования объчных и высоких годов в календаре, нужно выбрать длину цикла $q$ (после которого все периодические повторяется) и число $p$ высоких годов в цикле. Запишем величины года в виде $365+\alpha$, где $\alpha=0,242...$. Натуральные числа $p$ и $q$ нужно подобрать так, чтобы величины

$$\beta = q\alpha - p$$

была по возможности маленькой, в то время как $p$ и $q$ были не очень большими. Собственно говоря, подбору подлежит лишь натуральное $q$, число же $p$ есть близкой к $q\alpha$ целое. Тогда за $q$ лет прошет $365q+p$ суток. Из равенства $365q+p=q(365+\alpha)-\beta$ следует, что за это время Земля сделает

$$q - \frac{\beta}{365+\alpha} \approx q$$

17

оборотов вокруг Солнца. Ошибка в одной сутки набежит лишь за $\frac{1}{\beta}$ таких циклов или же $\frac{q}{\beta}$ лет.

В григорианском календаре, по которым мы живем, в качестве длины цикла взято $q=400$ годам. Из этих лет 303 являются обычными и 97 высокими. Високосными объявляются годы, которые делятся на 4, за исключением тех из них, для которых число сотен тоже делится на 4. Таким образом, средняя дительность года по григорианскому календарю составляет 365,242500 суток,

ошибка в одной сутки набежит примерно за 3300 лет. Эта точность вполне удовлетворительная. Можно было бы достигнуть даже большей точности, взяв $q=128$ и $p=31$, однako устройство календаря 128-летними цикlamами неудобно для использования.

Для нас важно в данной случае возникка ошибка здесь математическая задача: по данному числу $n$ найти $p$ и $q$, по возможности необходиме так чтобы число $\frac{p}{q}$ как можно лучше приближало заданное значение $\omega$ (нужное отношение угловых скоростей). Ясно, что из сообщений экономии следует подбирать $p$ и $q$ по возможности меньше.

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

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

2 «Квант» № 5

менять очень давно. Уже в 1572 году итальянский математик и инженер Р. Бомбелли (1526 ? — 1572) использовал их для вычисления $\sqrt{13}$. Позднее английнин У. Броункер (1620—1684) применил их для уччения числа $n$. Х. Гюйгенс (1629—1695), выдавшийся физик, астроном, математик (изобретатель магнитковых часов), был первым, кто при использовании цепных дробей указал, в каком смысле они дают наилучшую аппроксимацию дейстительного числа. Великий Л. Эйлер (1707—1783) дал обоснование ряда положений теории непрерывных дробей и нашел цепную дробь для числа $e$. Перечислить математиков, внесших свой вклад в эту теорию после работы Эйлера, уже очень трудно из-за их большого числа. Начиная с работы выдавшегося русского математика П. Л. Чебышева (1821—1894), активно развивается теория, имеющая дело с функциональным цепными дробями.

Алгоритм Евклида и разложение числа в цепную дробь

Пусть $p$, $q$ — два натуральных числа. Производление с остатком, найдем

$$p = a_0 q + q_1, \quad 0 < q_1 < q$$

$$q = a_1 q_1 + q_2, \quad 0 < q_2 < q_1$$

$$q_1 = a_2 q_2 + q_3, \quad 0 < q_3 < q_2$$

$$q_{k-2} = a_{k-1} q_{k-1} + q_k, \quad 0 < q_k < q_{k-1}$$

$$q_{k-1} = a_k q_k.$$

Указанный набор дейстий называется алгоритмом Евклида. Можно показать, что полученное число $q_k$ будет наиболее обширным обшим дейстелем чисел $p$, $q$. Нам этот факт не потребуется, поэтому доказательство мы опускаем*).

Из полученных равенств следует

$$\frac{p}{q} = a_0 + \frac{q_1}{q} = a_0 + \frac{1}{a_1 + \frac{q_2}{q_1}} = \dots = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \dots + \frac{1}{a_k}}}.$$

18

К тому же результату приводит и такой процесс. Пусть α — действительное число. Положим
$$\alpha = a_0 + \frac{1}{a_1}, a_0 - \text{целое},$$
где $a_1 > 1$. Если $a_1$ — не целое, то продолжим процесс dalleше. Представим $a_1$ в виде $a_1 = a_1 + \frac{1}{a_2}$, где $a_1$ — целое, положительное и $a_2 > 1$. Таким образом,
$$\alpha = a_0 \frac{1}{a_1 + \frac{1}{a_2}}.$$
Если $a_2$ — не целое, то можно продолжить процесс dalleше. Таким образом, на $k$-м шаге получаем равенство «Многоэтажная» запись дроби (1) очень громоздка, поэтому в дальнейшем мы будем часто пользоваться следующей более компактной специалной записью:
$$\alpha = a_0 + \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_{k-1}} + \frac{1}{a_k},$$
где $a_k > 1$.
Нетрудно доказать, что если $\alpha = \frac{p}{q}$ — рациональное число, то для некоторого $k$ число $a_k$ будет целым.

Ясно также, что если при некотором $k$ получится целое $a_k$, то число $a$ является рациональным. Если же $a$ — irrationalное число, то указанный процесс никакогда не оборвется и возникнет бесконечная цепная (или непрерывная) дробь
$$\alpha = a_0 + \frac{1}{|a_1|} + \frac{1}{|a_2|} + \dots +$$
$$\dots + \frac{1}{|a_{k-1}|} + \frac{1}{|a_k|} + \dots$$
Знак равенства здесь стоит условно, поскольку непонятно, что означает выражение справа. Для того чтобы придать ему смысл, рассмотрим конечные суммы вида
$$\pi_k = a_0 + \frac{1}{a_1 + \dots} + \frac{1}{a_k},$$
которые называются подходящими дробями непрерывной дроби (2). По определению принимают, что права часть равенства (2) представляется собой предел подходящих дробей:
$$\lim_{k \to \infty} \pi_k$$
Сформилируем теперь в виде набора задач те свойства цепных дробей, которые составляют основу их элементарной теории и, в частности, установливают равенство (2).

Основные свойства цепных дробей

1. Пусть $\pi_k = \frac{p_k}{q_k}$ — подходящая дробь цепной дроби (2). Доказите справедливость рекуррентных соотношения:
   $$p_0 = a_0, p_1 = a_0 a_1 + 1, \dots,$$
   $$p_{k+1} = a_{k+1} p_k + p_{k-1}, \dots$$
   $$q_0 = 1, q_1 = a_1, \dots,$$
   $$q_{k+1} = a_{k+1} q_k + q_{k-1}, \dots$$
   для $k = 1, 2, 3, \dots$.
2. Установите следующие соотношения:
   a) $q_n p_{n-1} - p_n q_{n-1} = (-1)^n, n \geqslant 1$;
   b) $q_k p_{k-2} - p_k q_{k-2} = (-1)^{k-1} a_k, k \geqslant 2$;
   c) $\pi_{n-1} - \pi_n = \frac{(-1)^n}{q_n q_{n-1}}, n \geqslant 1$;
   d) $\pi_{k-2} - \pi_k = \frac{(-1)^{k-1} a_k}{q_k q_{k-2}}, k \geqslant 2$.

19

3. Покажите, что дроби $\pi_0, \pi_2, \pi_4, \dots$ монотно возрастают:
   $$\pi_0 < \pi_2 < \pi_4 < \pi_6 < \dots,$$
   а дроби $\pi_1, \pi_3, \dots$ монотно убывают:
   $$\pi_1 > \pi_3 > \pi_5 > \dots$$

4. Пусть числа $a_k$ определяны равенством (1). Докажите соответствие:
   $$\alpha = \frac{p_{k-1}a_k + p_{k-2}}{q_{k-1}a_k + q_{k-2}}, k \geqslant 2.$$

5. Докажите неравенство
   $$\frac{1}{2q_{n+1}} < |q_n\alpha - p_n| \leqslant \frac{1}{q_{n+1}}.$$

6. Докажите, что
   $$\lim_{k \to \infty} \pi_k = \alpha.$$
   Как видно из задачи 1—6, подхождение дроби $\pi_n$ довольно хорошо приближают число $\alpha$. Так, из оценок задачи 5 и неравенства $q_{n+1} < q_n$ следует, что если $\alpha$ — irrationalно, то неравенство
   $$\left| \alpha - \frac{p_n}{q_n} \right| < \frac{1}{q_n^2}$$
   выполняется для всех подхождения дробей $\pi_n = \frac{p_k}{q_k}$ цепной дроби числа $\alpha$.

Числовые примеры

Цепную дробь (2) числа $\alpha$ иногда обозначают $[a_0; a_1, a_2, \dots, a_k, \dots]$. Можно доказать, что для каждой последовательности целых чисел $a_0, a_1, a_2, \dots, (a_0 \geqslant 0$ и $a_j \geqslant 1$ для $j \geqslant 1$) существует единственное положительное число $\alpha$ такое, что
$$\alpha = [a_0; a_1, a_2, \dots].$$
Если последовательность $a_0, a_1, a_2, \dots$ известна, то последовательность подхождения дробей $\pi_k = \frac{p_k}{q_k}$ удовно вычисляется, пользоваться равенствами из задачи 1, заполняя следующую таблицу:

| $a$ | $a_0$ | $a_1$ | $a_2$ | … | $a_{n-1}$ | $a_k$ | $a_{k+1}$ | $a_{k+2}$ | … |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| $p$ | 1 | $a_0$ | $p_1$ | $p_2$ | … | $p_{k-1}$ | $p_k$ | … | … |
| $q$ | 0 | 1 | $q_1$ | $q_2$ | … | $q_{k-1}$ | $q_k$ | … | … |

Пример 1. Найдем разложение в цепную дробь числа $\sqrt{2}$.
Имеем $a_0 = 1$,
$$a_1 = \frac{1}{\sqrt{2} - 1} = \sqrt{2} + 1, \quad a_1 = 2,$$
$$a_2 = \frac{1}{\sqrt{2} - 1} = \sqrt{2} + 1, \quad a_2 = 2.$$
Ясно, что в последовательности $a_j, j = 1, 2, \dots$, все члены равны $\sqrt{2} + 1$, а в последовательности $a_j, j = 1, 2, \dots$, все члены равны 2. Итак,
$$\sqrt{2} = [1; 2, 2, 2, \dots].$$
Вычислим несколько подхождения дробей для $\sqrt{2}$:

| $a$ | 1 | 2 | 2 | 2 | 2 | 2 | 2 | … |
| :— | :— | :— | :— | :— | :— | :— | :— | :— |
| $p$ | 1 | 1 | 3 | 7 | 17 | 41 | 99 | … |
| $q$ | 0 | 1 | 2 | 5 | 12 | 29 | 70 | 169 | … |

Получили последовательность подхождения дробей: $\frac{1}{1}, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \dots$

Из задачи 5 следует, что
$$\left| \sqrt{2} - \frac{99}{70} \right| < \frac{1}{70 \cdot 169} < 10^{-4}.$$
Таким образом, разполяная дробь