Непрерывная дробь

Непрерывная дробь (или цепная дробь) — это конечное или бесконечное математическое выражение вида

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\cdots ]=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\ldots }}}}}},}$

где ${\displaystyle a_{0}}$ есть целое число, а все остальные ${\displaystyle a_{n}}$ — натуральные числа (положительные целые)^[1]. При этом числа ${\displaystyle a_{0},a_{1},a_{2},a_{3},\dots }$ называются неполными частными или элементами цепной дроби^[2].

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

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

Любое вещественное число ${\displaystyle x}$ может быть представлено (конечной или бесконечной, периодической или непериодической) цепной дробью ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\ldots ]}$, где

${\displaystyle a_{0}=\lfloor x\rfloor ,\quad x_{0}=x-a_{0},}$

${\displaystyle a_{1}=\left\lfloor {\frac {1}{x_{0}}}\right\rfloor ,\quad x_{1}={\frac {1}{x_{0}}}-a_{1},}$

${\displaystyle \dots }$

${\displaystyle a_{n}=\left\lfloor {\frac {1}{x_{n-1}}}\right\rfloor ,\quad x_{n}={\frac {1}{x_{n-1}}}-a_{n},}$

${\displaystyle \dots }$

где ${\displaystyle \lfloor x\rfloor }$ обозначает целую часть числа ${\displaystyle x}$.

Для рационального числа ${\displaystyle x}$ это разложение оборвётся по достижении нулевого ${\displaystyle x_{n}}$ для некоторого ${\displaystyle n}$. В этом случае ${\displaystyle x}$ представляется конечной цепной дробью ${\displaystyle x=[a_{0};a_{1},\ldots ,a_{n}]}$. Эффективным алгоритмом для преобразования обычной дроби в цепную является алгоритм Евклида. Представление рационального числа в виде непрерывной дроби неоднозначно: если приведённый здесь алгоритм даёт непрерывную дробь ${\displaystyle [\dots ,a_{n}]}$, то непрерывная дробь ${\displaystyle [\dots ,a_{n}-1,1]}$ соответствует тому же самому числу.

Для иррационального ${\displaystyle x}$ все величины ${\displaystyle x_{n}}$ будут ненулевыми и процесс разложения можно продолжать бесконечно. В этом случае ${\displaystyle x}$ представляется бесконечной цепной дробью ${\displaystyle x=[a_{0};a_{1},a_{2},a_{3},\ldots ]}$. Если последовательность ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\ldots ]}$ состоит из бесконечно повторяющегося набора одних и тех же чисел (периода), то цепная дробь называется периодической. Число представляется бесконечной периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью, то есть иррациональным корнем квадратного уравнения с целыми коэффициентами.

n-й («энной») подходящей дробью для цепной дроби ${\displaystyle x=[a_{0};a_{1},a_{2},a_{3},\ldots ]}$ называется конечная цепная дробь ${\displaystyle [a_{0};a_{1},\ldots ,a_{n}]}$, значение которой есть некоторое рациональное число ${\displaystyle p_{n}/q_{n}}$. Подходящие дроби с чётными номерами образуют возрастающую последовательность, предел которой равен ${\displaystyle x}$. Аналогично, подходящие дроби с нечётными номерами образуют убывающую последовательность, предел которой также равен ${\displaystyle x}$. Таким образом, значение цепной дроби всегда находится между значениями соседних подходящих дробей.

Эйлер вывел рекуррентные формулы для вычисления числителей и знаменателей подходящих дробей:

${\displaystyle p_{-1}=1,\quad p_{0}=a_{0},\quad p_{n}=a_{n}p_{n-1}+p_{n-2};}$

${\displaystyle q_{-1}=0,\quad q_{0}=1,\quad q_{n}=a_{n}q_{n-1}+q_{n-2}.}$

Таким образом, величины ${\displaystyle p_{n}}$ и ${\displaystyle q_{n}}$ являются полиномами от ${\displaystyle a_{0},a_{1},\dots ,a_{n}}$, называемыми континуантами:

${\displaystyle p_{n}=K_{n+1}(a_{0},a_{1},\dots ,a_{n}),}$

${\displaystyle q_{n}=K_{n}(a_{1},a_{2},\dots ,a_{n}).}$

Последовательности как числителей ${\displaystyle \{p_{n}\}}$, так и знаменателей ${\displaystyle \{q_{n}\}}$ подходящих дробей являются строго возрастающими.

Числители и знаменатели соседних подходящих дробей связаны соотношением

${\displaystyle p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}.}$

(1)

Подходящие дроби, как видно из этого соотношения, всегда несократимы. Перепишем соотношение в виде

${\displaystyle {\frac {p_{n}}{q_{n}}}-{\frac {p_{n-1}}{q_{n-1}}}={\frac {(-1)^{n-1}}{q_{n-1}q_{n}}}.}$

Отсюда следует^[3], что

${\displaystyle \left|x-{\frac {p_{n-1}}{q_{n-1}}}\right|<{\frac {1}{q_{n-1}q_{n}}}<{\frac {1}{q_{n-1}^{2}}}.}$

Цепные дроби позволяют эффективно находить хорошие рациональные приближения вещественных чисел. А именно, если вещественное число ${\displaystyle x}$ разложить в цепную дробь, то её подходящие дроби будут удовлетворять неравенству

${\displaystyle \left|x-{\frac {p_{n}}{q_{n}}}\right|<{\frac {1}{q_{n}^{2}}}.}$

Следствия^[4]:

1. Подходящая дробь ${\displaystyle p_{n}/q_{n}}$ является наилучшим приближением исходного числа среди всех дробей, знаменатель которых не превосходит ${\displaystyle q_{n}.}$
2. Мера иррациональности любого иррационального числа не меньше 2.

Разложим число ${\displaystyle \pi =3{,}14159265\dots }$ в непрерывную дробь и подсчитаем его подходящие дроби:

${\displaystyle 3,\ {\frac {22}{7}},\ {\frac {333}{106}},\ {\frac {355}{113}},\ {\frac {103993}{33102}},\ \dots }$

Вторая подходящая дробь ${\displaystyle 22/7}$ — это известное архимедово приближение. Четвёртая подходящая дробь ${\displaystyle 355/113}$ была впервые получена в Древнем Китае.

Ниже приведено разложение золотого сечения:

${\displaystyle \Phi =[1;1,1,1,\dots ].}$

Интересный результат, который следует из того, что выражение непрерывной дроби для ${\displaystyle \Phi }$ не использует чисел, больших 1, состоит в том, что ${\displaystyle \Phi }$ является одним из самых «плохо» приближаемых чисел. Точнее, теорема Гурвица^[5] утверждает, что любое действительное число ${\displaystyle r}$ может быть приближено дробью ${\displaystyle m/n}$ так, что

${\displaystyle \left|r-{\frac {m}{n}}\right|<{\frac {1}{n^{2}{\sqrt {5}}}}.}$

Хотя практически все действительные числа ${\displaystyle r}$ имеют бесконечно много приближений ${\displaystyle m/n}$, которые находятся на значительно меньшем расстоянии от ${\displaystyle r}$, чем эта верхняя граница, приближения для ${\displaystyle \Phi }$ (то есть чи́сла 5/3, 8/5, 13/8, 21/13 и т. д.) в пределе достигают этой границы^[6], удерживая расстояние на почти точно ${\displaystyle 1/(n^{2}{\sqrt {5}})}$ от ${\displaystyle \Phi }$, тем самым никогда не создавая столь хорошие приближения как, к примеру, 355/113 для π. Можно показать, что этим свойством обладает любое действительное число вида ${\displaystyle (a+b\Phi )/(c+d\Phi )}$, где ${\displaystyle a,b,c}$ и ${\displaystyle d}$ являются целыми числами, причём ${\displaystyle ad-bc=\pm 1}$; а также, что все остальные действительные числа могут быть приближены намного лучше.

• Любое рациональное число может быть представлено в виде конечной цепной дроби двумя способами, например:

  ${\displaystyle 9/4=[2;3,1]=[2;4].}$

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

Например:

${\displaystyle {\sqrt {2}}=[1;2,2,2,2,\dots ],}$

${\displaystyle {\sqrt {42}}=[6;2,12,2,12,2,12\dots ],}$

золотое сечение ${\displaystyle \Phi =[1;1,1,1,\dots ].}$

• Теорема Гаусса — Кузьмина: почти для всех (кроме множества меры нуль) вещественных чисел распределение элементов соответствующих им цепных дробей подчиняется статистике Гаусса — Кузьмина; в частности, существует среднее геометрическое всех элементов, и оно равно постоянной Хинчина.
• Теорема Маршалла Холла. Если в разложении числа ${\displaystyle x}$ в непрерывную дробь, начиная со второго элемента не встречаются числа большие ${\displaystyle n}$, то говорят, что число ${\displaystyle x}$ относится к классу ${\displaystyle F(n)}$. Любое вещественное число может быть представлено в виде суммы двух чисел из класса ${\displaystyle F(4)}$ и в виде произведения двух чисел из класса ${\displaystyle F(4).}$^[7] В дальнейшем было показано, что любое вещественное число может быть представлено в виде суммы трёх чисел из класса ${\displaystyle F(3)}$ и в виде суммы четырёх чисел из класса ${\displaystyle F(2)}$. Количество требуемых слагаемых в этой теореме не может быть уменьшено — для представления некоторых чисел указанным образом меньшего количества слагаемых недостаточно^[8][9].

Предпринимались попытки найти закономерности в разложениях в непрерывную дробь кубических иррациональностей^[10], а также других алгебраических чисел степени, большей 2, и трансцендентных чисел^[11]. Для некоторых трансцендентных чисел можно найти простую закономерность. Например, основание натурального логарифма представимо в виде^[12]

${\displaystyle e=[2;1,2,1,1,4,1,1,6,1,1,8,\ldots ,1,1,2n-2,1,1,2n,\ldots ],}$

а тангенс угла в 1 радиан — в виде^[13]

${\displaystyle \operatorname {tg} 1=[1;1,1,3,1,5,1,7,\ldots ,1,2n+1,1,2n+3,\ldots ].}$

У числа ${\displaystyle \pi }$ простой закономерности не видно^[14]:

${\displaystyle \pi =[3;7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,2,1,1,15,\dots ]}$

Однако для обобщённой непрерывной дроби (см. ниже раздел Вариации и обобщения) прослеживается ясная закономерность.

Неизвестно, ограничены ли сверху неполные частные разложения таких чисел, как ${\displaystyle {\sqrt[{3}]{2}}}$ или ${\displaystyle \pi }$^[11][15].

При разработке солнечного календаря необходимо найти рациональное приближение для числа дней в году, которое равно 365,2421988… Подсчитаем подходящие дроби для дробной части этого числа:

${\displaystyle {\frac {1}{4}};\ {\frac {7}{29}};\ {\frac {8}{33}};\ {\frac {31}{128}};\ {\frac {132}{545}}\cdots }$

Первая дробь означает, что раз в 4 года надо добавлять лишний день; этот принцип лёг в основу юлианского календаря. При этом ошибка в 1 день накапливается за 128 лет. Второе значение (7/29) никогда не использовалось, поскольку оно мало отличается от следующего, гораздо более точного. Третья дробь (8/33), то есть 8 високосных лет за период в 33 года, была предложена Омаром Хайямом в XI веке и положила начало персидскому календарю, в котором ошибка в день накапливается за 4500 лет (в григорианском — за 3280 лет). Очень точный вариант с четвёртой дробью (31/128, ошибка в сутки накапливается только за 100000 лет^[16]) пропагандировал немецкий астроном Иоганн фон Медлер (1864 год), однако большого интереса он не вызвал.

В теории музыки при построении равномерно темперированного строя требуют, чтобы интервал октавы ${\displaystyle 2:1}$ делился на ${\displaystyle n}$ равных частей, и при этом интервал из ${\displaystyle m}$ таких частей был по возможности близок к интервалу квинты ${\displaystyle 3:2}$. Эти требования приводят к задаче отыскания рационального приближения для ${\displaystyle \log _{2}1{,}5\approx 0{,}585}$. Третья подходящая дробь ${\displaystyle 3/5}$ даёт равномерно темперированную пентатонику. Четвёртая подходящая дробь ${\displaystyle 7/12}$ приводит к классическому делению октавы на 12 равных полутонов^[17].

Рассмотрим сравнение: ${\displaystyle ax\equiv b{\pmod {m}}}$, где ${\displaystyle a,\ b}$ известны, причём можно считать, что ${\displaystyle a}$ взаимно просто с ${\displaystyle m}$. Надо найти ${\displaystyle x}$.

Разложим ${\displaystyle {\frac {m}{a}}}$ в непрерывную дробь. Она будет конечной, и последняя подходящая дробь ${\displaystyle {\frac {p_{n}}{q_{n}}}={\frac {m}{a}}}$. Подставим в формулу (1):

${\displaystyle mq_{n-1}-ap_{n-1}=(-1)^{n-1}.}$

Отсюда вытекает:

${\displaystyle ap_{n-1}\equiv (-1)^{n}{\pmod {m}},}$

или

${\displaystyle \ a(-1)^{n}p_{n-1}\equiv 1{\pmod {m}}.}$

Вывод: класс вычетов ${\displaystyle x\equiv (-1)^{n}p_{n-1}b{\pmod {m}}}$ является решением исходного сравнения.

• Доказательство иррациональности чисел. Например, с помощью цепных дробей была доказана иррациональность значения дзета-функции Римана ${\displaystyle \zeta (3)}$ (константа Апери)
• Решение в целых числах уравнения Пелля^[18]: ${\displaystyle \;x^{2}-ny^{2}=1\;}$ и других уравнений диофантова анализа
• Определение заведомо трансцендентного числа (см. теорема Лиувилля)
• Алгоритмы факторизации SQUFOF и CFRAC.
• Характеристика ортогональных многочленов
• Характеристика устойчивых многочленов

Ряд источников дают обобщённое определение непрерывной дроби, допуская для числителей в её звеньях не только 1, но и другие целые (в некоторых источниках допускаются даже комплексные) числа^[1]:

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ]=a_{0}+{\cfrac {b_{1}}{a_{1}+{\cfrac {b_{2}}{a_{2}+{\cfrac {b_{3}}{a_{3}+\ldots }}}}}}.}$

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

Для обобщённых непрерывных дробей формулы Эйлера имеют вид^[19]:

${\displaystyle p_{-1}=1,\quad p_{0}=a_{0},\quad p_{n}=a_{n}p_{n-1}+b_{n}p_{n-2};}$

${\displaystyle q_{-1}=0,\quad q_{0}=1,\quad q_{n}=a_{n}q_{n-1}+b_{n}q_{n-2}.}$

При этом

${\displaystyle p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}b_{1}b_{2}\dots b_{n}.}$

Частный случай, в котором все ${\displaystyle b_{n}=-1}$, называется непрерывной дробью Хирцебруха^[20].

Выше было сказано, что разложение числа ${\displaystyle \pi }$ в классическую непрерывную дробь не содержит видимой закономерности. Для обобщённой же непрерывной дроби имеет место формула Браункера^[21]:

${\displaystyle {\frac {\pi }{4}}={\cfrac {1}{1+{\cfrac {1^{2}}{2+{\cfrac {3^{2}}{2+{\cfrac {5^{2}}{2+{\cfrac {7^{2}}{2+{\cfrac {9^{2}}{2+\ddots }}}}}}}}}}}}}$

Другое направление обобщения состоит в построении и применении аппарата непрерывных дробей не для чисел, а для многочленов — используется тот факт, что делимость многочленов по своим свойствам близка к делимости целых чисел^[22]. Всякий многочлен или дробно-рациональная функция может быть разложена в непрерывную дробь^[23]:

${\displaystyle {\cfrac {b_{1}}{a_{1}+{\cfrac {b_{2}x}{a_{2}+{\cfrac {b_{3}x}{a_{3}+\ldots }}}}}}.}$

Пример: получим разложение для функции ${\displaystyle f(x)={\frac {1-x}{1-5x+6x^{2}}}}$:

${\displaystyle f(x)={\cfrac {1}{1-{\cfrac {4x}{1-{\cfrac {2x}{-4+6x}}}}}}.}$

Можно установить соответствие между непрерывными дробями и углами на решётках на плоскости. В связи с этим существуют различные варианты «многомерных непрерывных дробей»^[24].

Античные математики умели представлять отношения несоизмеримых величин в виде цепочки последовательных подходящих отношений, получая эту цепочку с помощью алгоритма Евклида. По-видимому, именно таким путём Архимед получил приближение ${\displaystyle {\sqrt {3}}\approx {\frac {1351}{780}}}$ — это 12-я подходящая дробь для ${\displaystyle {\sqrt {3}}}$ или одна треть от 4-й подходящей дроби для ${\displaystyle {\sqrt {27}}}$.

В V веке индийский математик Ариабхата применял аналогичный «метод измельчения» для решения неопределённых уравнений первой и второй степени. С помощью этой же техники было, вероятно, получено известное приближение для числа ${\displaystyle \pi }$ (355/113). В XVI веке Рафаэль Бомбелли извлекал с помощью цепных дробей квадратные корни (см. его алгоритм).

Начало современной теории цепных дробей положил в 1613 году Пьетро Антонио Катальди. Он отметил основное их свойство (положение между подходящими дробями) и ввёл обозначение, напоминающее современное. Позднее его теорию расширил Джон Валлис, который и предложил термин «непрерывная дробь». Эквивалентный термин «цепная дробь» появился в конце XVIII века.

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

В XVIII веке теорию цепных дробей в общих чертах завершили Леонард Эйлер и Жозеф Луи Лагранж.

• Алгоритм Евклида
• Континуанта
• Несократимая дробь
• Разложение Энгеля
• Числа Фибоначчи

• Арнольд В. И. Цепные дроби. — М.: МЦНМО, 2000. — Т. 14. — 40 с. — (Библиотека «Математическое просвещение»).
• Бескин Н. М. Цепные дроби // Квант. — 1970. — Т. 1. — С. 16—26,62.
• Бескин Н. М. Бесконечные цепные дроби // Квант. — 1970. — Т. 8. — С. 10—20.
• Боднар Д. И. Ветвящиеся цепные дроби. — К.: Наука, 1986. — 174 с.
• Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. — 384 с.
• Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — 180 с.
• Вычисления в алгебре и теории чисел / Пер. с англ. Э. Г. Белаги, под ред. Б. Б. Венкова и Д. К. Фаддеева. — М.: Мир, 1976. — (Математика. Новое в зарубежной науке).
• Гладковский С. Н. Анализ условно-периодических цепных дробей, ч. 1. — Незлобная, 2009. — 138 с.
• Демидович Б. П., Марон И. А. Основы вычислительной математики. — Изд. 2-е. — М.: Физматлит, 1963. — С. 53—73. — 660 с.
• Депман И. Я. История арифметики. Пособие для учителей. — Изд.второе. — М.: Просвещение, 1965. — С. 253—254.
• Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — М.: Наука, 1965.
• Сизый С. В. Лекции по теории чисел. — Екатеринбург: Уральский государственный университет им. А. М. Горького, 1999.
• Скоробогатько В. Я. Теория ветвящихся цепных дробей и её применение в вычислительной математике. — М.: Наука, 1983. — 312 с.
• Хинчин А. Я. Цепные дроби. — М.: ГИФМЛ, 1960.
• Хованский А. Н. Приложение цепных дробей и их обобщений к вопросам приближенного анализа. — М.: Гостехиздат, 1956. — 204 с.
• Brezinski C. History of continued fractions and Padé approximants. NY: Springer, 1980.
• Karpenkov O. Geometry of Continued Fractions. — Springer, 2013. — ISBN 978-3-642-39367-9.
• Lorentzen, Lisa; Waadeland, Haakon (1992). Continued fractions with applications (engelsk). North-Holland Elsevier Science Publishers. ISBN 0444892656.