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

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

$[a_0;a_1,a_2,a_3,\cdots ]=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\dots }}},$

где $a_0$ есть целое число, а все остальные $a_n$ — натуральные числа (положительные целые). При этом числа $a_0,a_1,a_2,a_3,\dots$ называются неполными частными или элементами цепной дробиШаблон:Sfn.

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

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

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

Любое вещественное число $x$ может быть представлено (конечной или бесконечной, периодической или непериодической) цепной дробью $[a_0;a_1,a_2,a_3,\dots ]$, где

$a_0=\lfloor x\rfloor ,x_0=x-a_0,$

$a_1=\lfloor \frac{1}{x_0}\rfloor ,x_1=\frac{1}{x_0}-a_1,$

$\dots$

$a_n=\lfloor \frac{1}{x_{n-1}}\rfloor ,x_n=\frac{1}{x_{n-1}}-a_n,$

$\dots$

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

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

Для иррационального $x$ все величины $x_n$ будут ненулевыми и процесс разложения можно продолжать бесконечно. В этом случае $x$ представляется бесконечной цепной дробью $x=[a_0;a_1,a_2,a_3,\dots ]$. Если последовательность $[a_0;a_1,a_2,a_3,\dots ]$ состоит из бесконечно повторяющегося набора одних и тех же чисел (периода), то цепная дробь называется периодической. Число представляется бесконечной периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью, то есть иррациональным корнем квадратного уравнения с целыми коэффициентами.

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

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

n-й («энной») подходящей дробью для цепной дроби $x=[a_0;a_1,a_2,a_3,\dots ]$ называется конечная цепная дробь $[a_0;a_1,\dots ,a_n]$, значение которой есть некоторое рациональное число $p_n/q_n$. Подходящие дроби с чётными номерами образуют возрастающую последовательность, предел которой равен $x$. Аналогично, подходящие дроби с нечётными номерами образуют убывающую последовательность, предел которой также равен $x$. Таким образом, значение цепной дроби всегда находится между значениями соседних подходящих дробей.

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

$p_{-1}=1,p_0=a_0,p_n=a_n{p}_{n-1}+p_{n-2};$

$q_{-1}=0,q_0=1,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\}$ подходящих дробей являются строго возрастающими.

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

$\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{(-1{)}^{n-1}}{q_{n-1}{q}_n}.$

Отсюда следуетШаблон:Sfn, что

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

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

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

$|x-\frac{p_n}{q_n}|<\frac{1}{q_n^2}.$

СледствияШаблон:Sfn:

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$ была впервые получена в Древнем Китае.

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

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

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

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

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

Хотя практически все действительные числа $r$ имеют бесконечно много приближений $m/n$, которые находятся на значительно меньшем расстоянии от $r$, чем эта верхняя граница, приближения для $\mathrm{\Phi }$ (то есть чи́сла 5/3, 8/5, 13/8, 21/13 и т. д.) в пределе достигают этой границыШаблон:Sfn, удерживая расстояние на почти точно $1/(n^2\sqrt{5})$ от $\mathrm{\Phi }$, тем самым никогда не создавая столь хорошие приближения как, к примеру, 355/113 для π. Можно показать, что этим свойством обладает любое действительное число вида $(a+b\mathrm{\Phi })/(c+d\mathrm{\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 ],$

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

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

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

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

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

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

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

У числа $\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(\mathrm{mod}m)$, где $a,b$ известны, причём можно считать, что $a$ взаимно просто с $m$. Надо найти $x$.

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

$m{q}_{n-1}-a{p}_{n-1}=(-1{)}^{n-1}.$

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

$a{p}_{n-1}\equiv (-1{)}^n(\mathrm{mod}m),$

или

$a(-1{)}^n{p}_{n-1}\equiv 1(\mathrm{mod}m).$

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

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

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

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

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

$[a_0;a_1,a_2,a_3,\dots ]=a_0+\frac{b_1}{a_1+\frac{b_2}{a_2+\frac{b_3}{a_3+\dots }}}.$

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

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

$p_{-1}=1,p_0=a_0,p_n=a_n{p}_{n-1}+b_n{p}_{n-2};$

$q_{-1}=0,q_0=1,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}=\frac{1}{1+\frac{1^2}{2+\frac{3^2}{2+\frac{5^2}{2+\frac{7^2}{2+\frac{9^2}{2+\ddots }}}}}}$

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

$\frac{b_1}{a_1+\frac{b_{2}x}{a_2+\frac{b_{3}x}{a_3+\dots }}}.$

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Хованский А. Н. Приложение цепных дробей и их обобщений к вопросам приближенного анализа. — М.: Гостехиздат, 1956. — 204 с.
• Brezinski C. History of continued fractions and Padé approximants. NY: Springer, 1980.
• Шаблон:Публикация
• Lorentzen, Lisa; Waadeland, Haakon (1992). Continued fractions with applications (engelsk). North-Holland Elsevier Science Publishers. ISBN 0444892656.