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

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

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

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

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

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

Разложение в цепную дробь

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

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

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

$\dots$

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

$\dots$

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

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

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

Подходящие дроби

Подходящие дроби для золотого сечения

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

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

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

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

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

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

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

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

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

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

(1)

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

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

Отсюда следует, что

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

Приближение вещественных чисел рациональными

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

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

Следствия:

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

Примеры

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

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

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

Свойства золотого сечения

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

$\Phi =[1;1,1,1,\dots ].$

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

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

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

Свойства и примеры

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

  $9/4=[2;3,1]=[2;4].$

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

Например:

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

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

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

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

Открытые проблемы

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

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

а тангенс угла в 1 радиан — в виде

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

У числа $\pi$ простой закономерности не видно:

$\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 ]$

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

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

Приложения цепных дробей

Теория календаря

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

${\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 лет) пропагандировал немецкий астроном Иоганн фон Медлер (1864 год), однако большого интереса он не вызвал.

Теория музыки

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

Решение сравнений первой степени

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

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

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

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

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

или

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

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

Другие приложения

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

Вариации и обобщения

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

$[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 }}}}}}.$

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

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

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

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

При этом

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

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

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

${\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 }}}}}}}}}}}}$

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

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

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

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

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

Историческая справка

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

Книга Катальди

В V веке индийский математик Ариабхата применял аналогичный «метод измельчения» для решения неопределённых уравнений первой и второй степени. С помощью этой же техники было, вероятно, получено известное приближение для числа $\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.