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

${\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}}$ — натуральные числа (положительные целые) . При этом числа ${\displaystyle a_{0},a_{1},a_{2},a_{3},\dots }$ называются неполными частными или элементами цепной дроби .

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

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

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

Любое вещественное число ${\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}}}.}$

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

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

Следствия :

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 }$ является одним из самых «плохо» приближаемых чисел. Точнее, теорема Гурвица утверждает, что любое действительное число ${\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 и т. д.) в пределе достигают этой границы , удерживая расстояние на почти точно ${\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).}$ В дальнейшем было показано, что любое вещественное число может быть представлено в виде суммы трёх чисел из класса ${\displaystyle F(3)}$ и в виде суммы четырёх чисел из класса ${\displaystyle F(2)}$ . Количество требуемых слагаемых в этой теореме не может быть уменьшено — для представления некоторых чисел указанным образом меньшего количества слагаемых недостаточно .

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

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

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

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

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

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

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

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

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

При разработке солнечного календаря необходимо найти рациональное приближение для числа дней в году , которое равно 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 лет ) пропагандировал немецкий астроном Иоганн фон Медлер (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 равных полутонов .

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

Рассмотрим сравнение : ${\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)}$ ( константа Апери )
• Решение в целых числах уравнения Пелля : ${\displaystyle \;x^{2}-ny^{2}=1\;}$ и других уравнений диофантова анализа
• Определение заведомо трансцендентного числа (см. теорема Лиувилля )
• Алгоритмы факторизации SQUFOF и .
• Характеристика ортогональных многочленов
• Характеристика устойчивых многочленов

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

Ряд источников дают обобщённое определение непрерывной дроби, допуская для числителей в её звеньях не только 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 }}}}}}.}$

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

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

${\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}$ , называется непрерывной дробью Хирцебруха .

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

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

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

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

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

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

Античные математики умели представлять отношения несоизмеримых величин в виде цепочки последовательных подходящих отношений, получая эту цепочку с помощью алгоритма Евклида . По-видимому, именно таким путём Архимед получил приближение ${\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. — (Математика. Новое в зарубежной науке).
• Гладковский С. Н. . — Незлобная, 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 ; (1992). Continued fractions with applications (engelsk). North-Holland Elsevier Science Publishers. ISBN 0444892656 .