Простая цепная дробь

Простая или правильная непрерывная дробь — это непрерывная дробь, в которой числители равны единице, а знаменатели построены из последовательности целых чисел. Последовательность может быть конечной или бесконечной, что приводит к конечной (или конечной ) непрерывной дроби, например${\displaystyle \{a_{i}\}}$

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{n}}}}}}}}}}$

или бесконечная цепная дробь вроде

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots }}}}}}}$

Обычно такая непрерывная дробь получается посредством итеративного процесса представления числа в виде суммы его целой части и обратной величины другого числа, затем записи этого другого числа в виде суммы его целой части и другой обратной величины и т. д. В конечном случае итерация/ рекурсия останавливается после конечного числа шагов путем использования целого числа вместо другой непрерывной дроби. Напротив, бесконечная непрерывная дробь является бесконечным выражением . В любом случае все целые числа в последовательности, кроме первого, должны быть положительными . Целые числа называются коэффициентами или членами непрерывной дроби. ^[1]${\displaystyle a_{i}}$

Простые непрерывные дроби обладают рядом замечательных свойств, связанных с алгоритмом Евклида для целых или действительных чисел . Каждое рациональное число ⁠${\displaystyle p}$/${\displaystyle д}$⁠ имеет два тесно связанных выражения в виде конечной цепной дроби, коэффициенты которой a _i можно определить, применив алгоритм Евклида к . Числовое значение бесконечной цепной дроби иррационально ; оно определяется из ее бесконечной последовательности целых чисел как предел последовательности значений для конечных цепных дробей. Каждая конечная цепная дробь последовательности получается с помощью конечного префикса определяющей последовательности целых чисел бесконечной цепной дроби. Более того, каждое иррациональное число является значением уникальной бесконечной правильной цепной дроби, коэффициенты которой можно найти с помощью неконечной версии алгоритма Евклида, примененной к несоизмеримым значениям и 1. Этот способ выражения действительных чисел (рациональных и иррациональных) называется их представлением в виде цепной дроби .${\displaystyle (п,д)}$${\displaystyle \альфа}$${\displaystyle \альфа}$

Рассмотрим, например, рациональное число ⁠415/93⁠ , что составляет около 4,4624. В первом приближении начнем с 4, что является целой частью ; ⁠415/93⁠ = 4 + ⁠43/93⁠ . Дробная часть является обратной величиной ⁠93/43⁠ что составляет около 2,1628. Используйте целую часть, 2, как приближение для обратной величины, чтобы получить второе приближение 4 + ⁠1/2⁠ = 4,5. Теперь, ⁠93/43⁠ = 2 + ⁠7/43⁠ ; оставшаяся дробная часть, ⁠7/43⁠ , является обратной величиной ⁠43/7⁠ , и ⁠43/7⁠ составляет около 6,1429. Используйте 6 как приближение для этого, чтобы получить 2 + ⁠1/6⁠ как приближение для ⁠93/43⁠ и 4 + ⁠1/2 + ⁠1/6⁠⁠ , около 4,4615, как третье приближение. Далее, ⁠43/7⁠ = 6 + ⁠1/7⁠ . Наконец, дробная часть, ⁠1/7⁠ , является обратной величиной 7, поэтому ее приближение в этой схеме, 7, является точным ( ⁠7/1⁠ = 7 + ⁠0/1⁠ ) ​​и производит точное выражениедля ⁠$${\displaystyle 4+{\cfrac {1}{2+{\cfrac {1}{6+{\cfrac {1}{7}}}}}}}$$415/93⁠ .

Это выражение называется представлением цепной дроби ⁠415/93⁠ . Это можно представить сокращенной записью ⁠415/93⁠ = [4; 2, 6, 7]. (Принято заменять только первую запятую точкой с запятой, чтобы указать, что предыдущее число является целой частью.) В некоторых старых учебниках используются все запятые в кортеже ( n + 1) , например, [4, 2, 6, 7]. ^{[2] [3]}

Если начальное число рационально, то этот процесс точно параллелен алгоритму Евклида , примененному к числителю и знаменателю числа. В частности, он должен завершиться и произвести конечное представление числа в виде цепной дроби. Последовательность целых чисел, которая встречается в этом представлении, является последовательностью последовательных частных, вычисленных алгоритмом Евклида. Если начальное число иррационально , то процесс продолжается бесконечно. Это производит последовательность приближений, все из которых являются рациональными числами, и они сходятся к начальному числу как к пределу. Это (бесконечное) представление числа в виде цепной дроби. Примерами представлений иррациональных чисел в виде цепной дроби являются:

• √ 19 = [4;2,1,3,1,2,8,2,1,3,1,2,8,...] (последовательность A010124 в OEIS ). Шаблон повторяется бесконечно с периодом 6.
• e = [2;1,2,1,1,4,1,1,6,1,1,8,...](последовательностьA003417вOEIS). Шаблон повторяется бесконечно с периодом 3, за исключением того, что 2 добавляется к одному из членов в каждом цикле.
• π = [3;7,15,1,292,1,1,1,2,1,3,1,...] (последовательность A001203 в OEIS ). В этом представлении не было обнаружено никаких закономерностей.
• Φ = [1;1,1,1,1,1,1,1,1,1,1,1,1,...] (последовательность A000012 в OEIS ). Золотое сечение , иррациональное число, которое «наиболее трудно» аппроксимировать рационально (см. § Свойство золотого сечения φ ниже) .
• γ = [0;1,1,2,1,2,1,4,3,13,5,1,...] (последовательность A002852 в OEIS ). Константа Эйлера–Маскерони , которая, как ожидается, но не известно, является иррациональной, и чья непрерывная дробь не имеет очевидной закономерности.

Цепные дроби, в некотором смысле, являются более «математически естественными» представлениями действительных чисел , чем другие представления, такие как десятичные представления , и обладают несколькими желательными свойствами:

• Представление непрерывной дроби для действительного числа конечно тогда и только тогда, когда оно является рациональным числом. Напротив, десятичное представление рационального числа может быть конечным, например ⁠137/1600⁠ = 0,085625 , или бесконечность с повторяющимся циклом, например ⁠4/27⁠ = 0,148148148148...
• Каждое рациональное число имеет по существу единственное представление в виде простой цепной дроби. Каждое рациональное число может быть представлено ровно двумя способами, так как [ a ₀ ; a ₁ ,... a _{n −1} , a _n ] = [ a ₀ ; a ₁ ,... a _{n −1} ,( a _n −1),1] . Обычно в качестве канонического представления выбирается первое, более короткое .
• Представление иррационального числа в виде простой цепной дроби уникально. (Однако возможны дополнительные представления при использовании обобщенных цепных дробей; см. ниже.)
• Действительные числа, непрерывная дробь которых в конечном итоге повторяется, являются в точности квадратными иррациональными числами . ^[4] Например, повторяющаяся непрерывная дробь [1;1,1,1,...] является золотым сечением , а повторяющаяся непрерывная дробь [1;2,2,2,...] является квадратным корнем из 2. Напротив, десятичные представления квадратичных иррациональных чисел, по-видимому, случайны . Квадратные корни всех (положительных) целых чисел, которые не являются точными квадратами, являются квадратными иррациональными числами и, следовательно, являются уникальными периодическими непрерывными дробями.
• Последовательные приближения, полученные при нахождении представления числа в виде цепной дроби, то есть путем усечения представления цепной дроби, являются в определенном смысле (описанном ниже) «наилучшими возможными».

Цепная дробь в канонической форме — это выражение вида

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\vphantom {\cfrac {1}{1}}}{_{\ddots }}}}}}}}}$

где a _i — целые числа, называемые коэффициентами или членами цепной дроби. ^[1]

Когда выражение содержит конечное число членов, оно называется конечной цепной дробью. Когда выражение содержит бесконечное число членов, оно называется бесконечной цепной дробью. ^[5] Когда члены в конечном итоге повторяются с некоторой точки, цепная дробь называется периодической . ^[4]

Таким образом, все нижеследующее иллюстрирует допустимые конечные простые цепные дроби:

Примеры конечных простых цепных дробей

Формула	Числовой	Замечания
${\displaystyle \ а_{0}}$	${\displaystyle \ 2}$	Все целые числа являются вырожденным случаем
${\displaystyle \ a_{0}+{\cfrac {1}{a_{1}}}}$	${\displaystyle \ 2+{\cfrac {1}{3}}}$	Простейшая возможная дробная форма
${\displaystyle \ a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}}}}}}$	${\displaystyle \ -3+{\cfrac {1}{2+{\cfrac {1}{18}}}}}$	Первое целое число может быть отрицательным
${\displaystyle \ a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}}}}}}}}$	${\displaystyle \ {\cfrac {1}{15+{\cfrac {1}{1+{\cfrac {1}{102}}}}}}}$	Первое целое число может быть равно нулю

Для простых цепных дробей вида

${\displaystyle r=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\vphantom {\cfrac {1}{1}}}{_{\ddots }}}}}}}}}$

этот термин можно рассчитать с помощью следующей рекурсивной формулы:${\displaystyle а_{н}}$

${\displaystyle a_{n}=\left\lfloor {\frac {N_{n}}{N_{n+1}}}\right\rfloor }$

где и${\displaystyle N_{n+1}=N_{n-1}{\bmod {N}}_{n}}$${\displaystyle {\begin{cases}N_{0}=r,\\N_{1}=1,\end{cases}}}$

из чего можно понять, что последовательность останавливается, если .${\displaystyle a_{n}}$${\displaystyle N_{n+1}=0}$

Рассмотрим цепную дробь, выраженную как

${\displaystyle x=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{a_{4}}}}}}}}}}$

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

Готфрид Лейбниц иногда использовал обозначение ^[6]

${\displaystyle {\begin{aligned}x=a_{0}+{\dfrac {1}{a_{1}}}{{} \atop +}\\[28mu]\ \end{aligned}}\!{\begin{aligned}{\dfrac {1}{a_{2}}}{{} \atop +}\\[2mu]\ \end{aligned}}\!{\begin{aligned}{\dfrac {1}{a_{3}}}{{} \atop +}\end{aligned}}\!{\begin{aligned}\\[2mu]{\dfrac {1}{a_{4}}},\end{aligned}}}$

и позже эта же идея была развита еще дальше с вложенными дробными чертами, нарисованными выровненными, например, Альфредом Прингсхаймом как

${\displaystyle x=a_{0}+{{} \atop {{\big |}\!}}\!{\frac {1}{\,a_{1}}}\!{{\!{\big |}} \atop {}}+{{} \atop {{\big |}\!}}\!{\frac {1}{\,a_{2}}}\!{{\!{\big |}} \atop {}}+{{} \atop {{\big |}\!}}\!{\frac {1}{\,a_{3}}}\!{{\!{\big |}} \atop {}}+{{} \atop {{\big |}\!}}\!{\frac {1}{\,a_{4}}}\!{{\!{\big |}} \atop {}},}$

или в более общих обозначениях как ^[7]

${\displaystyle x=a_{0}+{1 \over a_{1}+}\,{1 \over a_{2}+}\,{1 \over a_{3}+}\,{1 \over a_{4}}}$

или

${\displaystyle x=a_{0}+{1 \over a_{1}}{{} \atop +}{1 \over a_{2}}{{} \atop +}{1 \over a_{3}}{{} \atop +}{1 \over a_{4}}.}$

Карл Фридрих Гаусс использовал обозначение, напоминающее обозначение суммирования ,

${\displaystyle x=a_{0}+{\underset {i=1}{\overset {4}{\mathrm {K} }}}~{\frac {1}{a_{i}}},}$

или в случаях, когда числитель всегда равен 1, вообще убирали дробные черты, записывая в виде списка

${\displaystyle x=[a_{0};a_{1},a_{2},a_{3},a_{4}].}$

Иногда в нотации в стиле списка вместо этого используются угловые скобки,

${\displaystyle x=\left\langle a_{0};a_{1},a_{2},a_{3},a_{4}\right\rangle .}$

Точка с запятой в квадратных и угловых скобках иногда заменяется запятой. ^{[2] [3]}

Можно также определить бесконечные простые цепные дроби как пределы :

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\,\ldots \,]=\lim _{n\to \infty }\,[a_{0};a_{1},a_{2},\,\ldots ,a_{n}].}$

Этот предел существует для любого выбора и положительных целых чисел . ^{[8] [9]}${\displaystyle a_{0}}$${\displaystyle a_{1},a_{2},\ldots }$

Рассмотрим действительное число ⁠ ⁠${\displaystyle r}$ . Пусть и пусть ⁠ ⁠ . Когда ⁠ ⁠ , представление в виде непрерывной дроби равно ⁠ ⁠ , где — представление в виде непрерывной дроби ⁠ ⁠ . Когда ⁠ ⁠ , то — целая часть , а — дробная часть ⁠ ⁠ .${\displaystyle i=\lfloor r\rfloor }$${\displaystyle f=r-i}$${\displaystyle f\neq 0}$${\displaystyle r}$${\displaystyle [i;a_{1},a_{2},\ldots ]}$${\displaystyle [a_{1};a_{2},\ldots ]}$${\displaystyle 1/f}$${\displaystyle r\geq 0}$${\displaystyle i}$${\displaystyle r}$${\displaystyle f}$${\displaystyle r}$

Чтобы вычислить представление числа в виде непрерывной дроби , запишите основание числа . Вычтите это значение из . Если разность равна 0, остановитесь; в противном случае найдите обратную величину разности и повторите. Процедура остановится только в том случае, если является рациональным. Этот процесс можно эффективно реализовать с помощью алгоритма Евклида, когда число является рациональным.${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$

В таблице ниже показана реализация этой процедуры для числа ⁠ ⁠${\displaystyle 3.245=649/200}$ :

Шаг	Реальное число	Целая часть	Дробная часть	Упрощенный	Обратная величина f
1	${\displaystyle r={\frac {649}{200}}}$	${\displaystyle i=3}$	${\displaystyle f={\frac {649}{200}}-3}$	${\displaystyle ={\frac {49}{200}}}$	${\displaystyle {\frac {1}{f}}={\frac {200}{49}}}$
2	${\displaystyle r={\frac {200}{49}}}$	${\displaystyle i=4}$	${\displaystyle f={\frac {200}{49}}-4}$	${\displaystyle ={\frac {4}{49}}}$	${\displaystyle {\frac {1}{f}}={\frac {49}{4}}}$
3	${\displaystyle r={\frac {49}{4}}}$	${\displaystyle i=12}$	${\displaystyle f={\frac {49}{4}}-12}$	${\displaystyle ={\frac {1}{4}}}$	${\displaystyle {\frac {1}{f}}={\frac {4}{1}}}$
4	${\displaystyle r=4}$	${\displaystyle i=4}$	${\displaystyle f=4-4}$	${\displaystyle =0}$	ОСТАНАВЛИВАТЬСЯ

Цепная дробь для ⁠ ⁠${\displaystyle 3.245}$ имеет вид или, в развернутом виде:${\displaystyle [3;4,12,4],}$

$${\displaystyle {\frac {649}{200}}=3+{\cfrac {1}{4+{\cfrac {1}{12+{\cfrac {1}{4}}}}}}.}$$

Представления непрерывной дроби положительного рационального числа и его обратной величины идентичны, за исключением сдвига на одну позицию влево или вправо в зависимости от того, меньше или больше единицы число. Другими словами, числа, представленные и являются обратными.${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{n}]}$${\displaystyle [0;a_{0},a_{1},\ldots ,a_{n}]}$

Например, если это целое число, а затем${\displaystyle a}$${\displaystyle x<1}$

${\displaystyle x=0+{\frac {1}{a+{\frac {1}{b}}}}}$и .${\displaystyle {\frac {1}{x}}=a+{\frac {1}{b}}}$

Если тогда${\displaystyle x>1}$

${\displaystyle x=a+{\frac {1}{b}}}$и .${\displaystyle {\frac {1}{x}}=0+{\frac {1}{a+{\frac {1}{b}}}}}$

Последнее число, образующее остаток цепной дроби, одинаково для обоих чисел и его обратной величины.${\displaystyle x}$

Например,

${\displaystyle 2.25={\frac {9}{4}}=[2;4]}$и .${\displaystyle {\frac {1}{2.25}}={\frac {4}{9}}=[0;2,4]}$

Каждая конечная цепная дробь представляет собой рациональное число , и каждое рациональное число может быть представлено двумя различными способами в виде конечной цепной дроби с условиями, что первый коэффициент является целым числом, а другие коэффициенты являются положительными целыми числами. Эти два представления совпадают, за исключением их конечных членов. В более длинном представлении конечный член в цепной дроби равен 1; более короткое представление отбрасывает конечную 1, но увеличивает новый конечный член на 1. Поэтому конечный элемент в коротком представлении всегда больше 1, если он присутствует. В символах:

[ а ₀ ; а ₁ , а ₂ , ..., а _{n − 1} , а _n , 1] = [ а ₀ ; а ₁ , а ₂ , ..., а _{n − 1} , а _n + 1] .

[ а ₀ ; 1] = [ а ₀ + 1] .

Каждая бесконечная цепная дробь иррациональна , и каждое иррациональное число можно представить в виде бесконечной цепной дроби только одним способом.

Представление бесконечной цепной дроби для иррационального числа полезно, потому что его начальные сегменты обеспечивают рациональные приближения к числу. Эти рациональные числа называются сходящимися дробями цепной дроби. ^{[10] [11]} Чем больше член в цепной дроби, тем ближе соответствующая сходящаяся дробь к приближаемому иррациональному числу. Числа, такие как π, иногда имеют большие члены в своей цепной дроби, что позволяет легко приближать их рациональными числами. Другие числа, такие как e, имеют только маленькие члены в начале своей цепной дроби, что затрудняет их рациональное приближение. Золотое сечение Φ имеет члены, равные 1 везде — наименьшие возможные значения — что делает Φ самым трудным числом для рационального приближения. В этом смысле, следовательно, это «самое иррациональное» из всех иррациональных чисел. Четные сходящиеся дроби меньше исходного числа, в то время как нечетные — больше.

Для непрерывной дроби [ a ₀ ; a ₁ , a ₂ , ...] первые четыре подходящие дроби (пронумерованные от 0 до 3) равны

${\displaystyle {\frac {a_{0}}{1}},\,{\frac {a_{1}a_{0}+1}{a_{1}}},\,{\frac {a_{2}(a_{1}a_{0}+1)+a_{0}}{a_{2}a_{1}+1}},\,{\frac {a_{3}{\bigl (}a_{2}(a_{1}a_{0}+1)+a_{0}{\bigr )}+(a_{1}a_{0}+1)}{a_{3}(a_{2}a_{1}+1)+a_{1}}}.}$

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

Если найдены последовательные подходящие дроби с числителями h ₁ , h ₂ , ... и знаменателями k ₁ , k ₂ , ..., то соответствующее рекурсивное отношение представляет собой отношение гауссовых скобок :

${\displaystyle {\begin{aligned}h_{n}&=a_{n}h_{n-1}+h_{n-2},\\[3mu]k_{n}&=a_{n}k_{n-1}+k_{n-2}.\end{aligned}}}$

Последовательные подходящие дроби определяются по формуле

${\displaystyle {\frac {h_{n}}{k_{n}}}={\frac {a_{n}h_{n-1}+h_{n-2}}{a_{n}k_{n-1}+k_{n-2}}}.}$

Таким образом, чтобы включить новый член в рациональное приближение, необходимы только два предыдущих конвергента. Начальные "конвергенты" (требуемые для первых двух членов) - это ⁰ ⁄ ₁ и ¹ ⁄ ₀ . Например, вот конвергенты для [0;1,5,2,2].

н	−2	−1	0	1	2	3	4
а н			0	1	5	2	2
ч н	0	1	0	1	5	11	27
к н	1	0	1	1	6	13	32

При использовании вавилонского метода для генерации последовательных приближений к квадратному корню целого числа, если начать с наименьшего целого числа в качестве первого приближения, все сгенерированные рациональные числа появятся в списке конвергентов для цепной дроби. В частности, аппроксиманты появятся в списке конвергентов в позициях 0, 1, 3, 7, 15, ... ,  2 ^k −1 , ... Например, расширение цепной дроби для равно [1; 1, 2, 1, 2, 1, 2, 1, 2, ...] . Сравнивая конвергенты с аппроксимантами, полученными с помощью вавилонского метода:${\displaystyle {\sqrt {3}}}$

н	−2	−1	0	1	2	3	4	5	6	7
а н			1	1	2	1	2	1	2	1
ч н	0	1	1	2	5	7	19	26	71	97
к н	1	0	1	1	3	4	11	15	41	56

х ₀ = 1 = ⁠1/1⁠

х ₁ = ⁠1/2⁠ (1 + ⁠3/1⁠ ) ​​= ⁠2/1⁠ = 2

х ₂ = ⁠1/2⁠ (2 + ⁠3/2⁠ ) ​​= ⁠7/4⁠

х ₃ = ⁠1/2⁠ ( ⁠7/4⁠ + ⁠3/⁠7/4⁠⁠ ) ​​= ⁠97/56⁠

Пространство Бэра — это топологическое пространство на бесконечных последовательностях натуральных чисел. Бесконечная цепная дробь обеспечивает гомеоморфизм из пространства Бэра в пространство иррациональных действительных чисел (с топологией подпространства, унаследованной от обычной топологии на действительных числах). Бесконечная цепная дробь также обеспечивает отображение между квадратичными иррациональными числами и двоично-рациональными числами , а также из других иррациональных чисел в множество бесконечных строк двоичных чисел (т. е. множество Кантора ); это отображение называется функцией вопросительного знака Минковского . Отображение имеет интересные самоподобные фрактальные свойства; они задаются модулярной группой , которая является подгруппой преобразований Мёбиуса, имеющих целые значения в преобразовании. Грубо говоря, подходящие дроби можно считать преобразованиями Мёбиуса, действующими на (гиперболической) верхней полуплоскости ; это и приводит к фрактальной самосимметрии.

Предельное распределение вероятностей коэффициентов в разложении непрерывной дроби случайной величины, равномерно распределенной в (0, 1), называется распределением Гаусса–Кузьмина .

Если — бесконечная последовательность положительных целых чисел, то рекурсивно определим последовательности и :${\displaystyle \ a_{0}\ ,}$ ${\displaystyle a_{1}\ ,}$ ${\displaystyle a_{2}\ ,}$ ${\displaystyle \ \ldots \ }$${\displaystyle \ h_{n}\ }$${\displaystyle \ k_{n}\ }$

${\displaystyle h_{n}=a_{n}\ h_{n-1}+h_{n-2}\ ,}$			${\displaystyle h_{-1}=1\ ,}$		${\displaystyle h_{-2}=0\ ;}$
${\displaystyle k_{n}=a_{n}\ k_{n-1}+k_{n-2}\ ,}$			${\displaystyle k_{-1}=0\ ,}$		${\displaystyle k_{-2}=1~.}$

Теорема 1. Для любого положительного действительного числа${\displaystyle \ x\ }$

${\displaystyle \left[\ a_{0};\ a_{1},\ \dots ,a_{n-1},x\ \right]={\frac {x\ h_{n-1}+h_{n-2}}{\ x\ k_{n-1}+k_{n-2}\ }},\quad \left[\ a_{0};\ a_{1},\ \dots ,a_{n-1}+x\ \right]={\frac {h_{n-1}+xh_{n-2}}{\ k_{n-1}+xk_{n-2}\ }}}$

Теорема 2. Подходящие дроби определяются формулой${\displaystyle \ [\ a_{0}\ ;}$ ${\displaystyle a_{1}\ ,}$ ${\displaystyle a_{2}\ ,}$ ${\displaystyle \ldots \ ]\ }$

${\displaystyle \left[\ a_{0};\ a_{1},\ \dots ,a_{n}\ \right]={\frac {h_{n}}{\ k_{n}\ }}~.}$

или в матричной форме,$${\displaystyle {\begin{bmatrix}h_{n}&h_{n-1}\\k_{n}&k_{n-1}\end{bmatrix}}={\begin{bmatrix}a_{0}&1\\1&0\end{bmatrix}}\cdots {\begin{bmatrix}a_{n}&1\\1&0\end{bmatrix}}}$$

Теорема 3. Если -я подходящая дробь к цепной дроби равна, то${\displaystyle \ n}$${\displaystyle \ {\frac {h_{n}}{k_{n}}}\ ,}$

${\displaystyle k_{n}\ h_{n-1}-k_{n-1}\ h_{n}=(-1)^{n}\ ,}$

или эквивалентно

${\displaystyle {\frac {h_{n}}{\ k_{n}\ }}-{\frac {h_{n-1}}{\ k_{n-1}\ }}={\frac {(-1)^{n+1}}{\ k_{n-1}\ k_{n}\ }}~.}$

Следствие 1: Каждая сходящаяся дробь находится в своих наименьших членах (так как если бы и имели нетривиальный общий делитель, то они делились бы, что невозможно).${\displaystyle \ h_{n}\ }$${\displaystyle \ k_{n}\ }$${\displaystyle \ k_{n}\ h_{n-1}-k_{n-1}\ h_{n}\ ,}$

Следствие 2: Разность между последовательными сходящимися дробями представляет собой дробь, числитель которой равен единице:

${\displaystyle {\frac {h_{n}}{k_{n}}}-{\frac {h_{n-1}}{k_{n-1}}}={\frac {\ h_{n}\ k_{n-1}-k_{n}\ h_{n-1}\ }{\ k_{n}\ k_{n-1}\ }}={\frac {(-1)^{n+1}}{\ k_{n}\ k_{n-1}\ }}~.}$

Следствие 3: Цепная дробь эквивалентна ряду чередующихся членов:

${\displaystyle a_{0}+\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{\ k_{n}\ k_{n+1}\ }}~.}$

Следствие 4: Матрица

${\displaystyle {\begin{bmatrix}h_{n}&h_{n-1}\\k_{n}&k_{n-1}\end{bmatrix}}={\begin{bmatrix}a_{0}&1\\1&0\end{bmatrix}}\cdots {\begin{bmatrix}a_{n}&1\\1&0\end{bmatrix}}}$

имеет определитель и, таким образом, принадлежит к группе унимодулярных матриц${\displaystyle (-1)^{n+1}}$${\displaystyle \ 2\times 2\ }$ ${\displaystyle \ \mathrm {GL} (2,\mathbb {Z} )~.}$

Следствие 5: Матрица имеет определитель , или, что то же самое, это означает, что нечетные члены монотонно убывают, а четные члены монотонно возрастают.$${\displaystyle {\begin{bmatrix}h_{n}&h_{n-2}\\k_{n}&k_{n-2}\end{bmatrix}}={\begin{bmatrix}h_{n-1}&h_{n-2}\\k_{n-1}&k_{n-2}\end{bmatrix}}{\begin{bmatrix}a_{n}&0\\1&1\end{bmatrix}}}$$${\displaystyle (-1)^{n}a_{n}}$$${\displaystyle {\frac {h_{n}}{\ k_{n}\ }}-{\frac {h_{n-2}}{\ k_{n-2}\ }}={\frac {(-1)^{n}}{\ k_{n-2}\ k_{n}\ }}a_{n}}$$

Следствие 6: Последовательность знаменателя удовлетворяет рекуррентному соотношению и растет по крайней мере так же быстро, как последовательность Фибоначчи , которая сама растет подобно , где — золотое сечение .${\displaystyle k_{0},k_{1},k_{2},\dots }$${\displaystyle k_{-1}=0,k_{0}=1,k_{n}=k_{n-1}a_{n}+k_{n-2}}$${\displaystyle O(\phi ^{n})}$${\displaystyle \phi =1.618\dots }$

Теорема 4. Каждая ( th) сходящаяся дробь ближе к последующей ( th) сходящейся дроби, чем любая предыдущая ( th) сходящаяся дробь. В символах, если th сходящаяся дробь берется как то${\displaystyle \ s}$${\displaystyle \ n}$${\displaystyle \ r}$${\displaystyle \ n}$${\displaystyle \ \left[\ a_{0};\ a_{1},\ \ldots ,\ a_{n}\ \right]=x_{n}\ ,}$

${\displaystyle \left|\ x_{r}-x_{n}\ \right|>\left|\ x_{s}-x_{n}\ \right|}$

для всех${\displaystyle \ r<s<n~.}$

Следствие 1: Четные подходящие дроби (до th) непрерывно увеличиваются, но всегда меньше${\displaystyle \ n}$${\displaystyle \ x_{n}~.}$

Следствие 2: Нечетные подходящие дроби (до th) непрерывно убывают, но всегда больше${\displaystyle \ n}$${\displaystyle \ x_{n}~.}$

Теорема 5.

${\displaystyle {\frac {1}{\ k_{n}\ (k_{n+1}+k_{n})\ }}<\left|\ x-{\frac {h_{n}}{\ k_{n}\ }}\ \right|<{\frac {1}{\ k_{n}\ k_{n+1}\ }}~.}$

Следствие 1: Подходящая дробь находится ближе к пределу цепной дроби, чем любая дробь, знаменатель которой меньше знаменателя подходящей дроби.

Следствие 2: Конвергенция, полученная путем прекращения цепной дроби непосредственно перед большим членом, является близким приближением к пределу цепной дроби.

Теорема 6: Рассмотрим множество всех открытых интервалов с конечными точками . Обозначим его как . Любое открытое подмножество из является несвязным объединением множеств из .${\displaystyle [0;a_{1},\dots ,a_{n}],[0;a_{1},\dots ,a_{n}+1]}$${\displaystyle {\mathcal {C}}}$${\displaystyle [0,1]\setminus \mathbb {Q} }$${\displaystyle {\mathcal {C}}}$

Следствие: Бесконечная цепная дробь обеспечивает гомеоморфизм из пространства Бэра в .${\displaystyle [0,1]\setminus \mathbb {Q} }$

Если

${\displaystyle {\frac {h_{n-1}}{k_{n-1}}},{\frac {h_{n}}{k_{n}}}}$

являются последовательными сходящимися дробями, то любые дроби вида

${\displaystyle {\frac {h_{n-1}+mh_{n}}{k_{n-1}+mk_{n}}},}$

где — целое число, такое что , называются полусходящимися дробями , вторичными сходящимися дробями или промежуточными дробями . -я полусходящаяся дробь равна медиане -й дроби и сходящейся дроби . Иногда этот термин означает, что полусходящаяся дробь исключает возможность быть сходящейся дробью (т. е. ), а не то, что сходящаяся дробь является разновидностью полусходящейся дроби.${\displaystyle m}$${\displaystyle 0\leq m\leq a_{n+1}}$${\displaystyle (m+1)}$${\displaystyle m}$${\displaystyle {\tfrac {h_{n}}{k_{n}}}}$${\displaystyle 0<m<a_{n+1}}$

Отсюда следует, что полусходящиеся дроби представляют собой монотонную последовательность дробей между сходящимися дробями (соответствующими ) и (соответствующими ). Последовательные полусходящиеся дроби и удовлетворяют свойству .${\displaystyle {\tfrac {h_{n-1}}{k_{n-1}}}}$${\displaystyle m=0}$${\displaystyle {\tfrac {h_{n+1}}{k_{n+1}}}}$${\displaystyle m=a_{n+1}}$${\displaystyle {\tfrac {a}{b}}}$${\displaystyle {\tfrac {c}{d}}}$${\displaystyle ad-bc=\pm 1}$

Если рациональное приближение к действительному числу таково, что его значение меньше, чем у любого приближения с меньшим знаменателем, то является полусходящимся дробным разложением . Обратное, однако, неверно.${\displaystyle {\tfrac {p}{q}}}$${\displaystyle x}$${\displaystyle \left|x-{\tfrac {p}{q}}\right|}$${\displaystyle {\tfrac {p}{q}}}$${\displaystyle x}$

Можно определить наилучшее рациональное приближение к действительному числу x как рациональное число ⁠н/г⁠ , d > 0 , которая ближе к x, чем любое приближение с меньшим или равным знаменателем. Простая непрерывная дробь для x может быть использована для генерации всех лучших рациональных приближений для x, применяя эти три правила:

1. Сократите цепную дробь и уменьшите ее последний член на выбранную величину (возможно, на ноль).
2. Сокращенный срок не может быть меньше половины первоначального значения.
3. Если конечный член четный, то половина его значения допустима только в том случае, если соответствующая полусходящаяся дробь лучше предыдущей сходящейся дроби. (См. ниже.)

Например, 0,84375 имеет непрерывную дробь [0;1,5,2,2]. Вот все ее лучшие рациональные приближения.

Продолженная дробь	[0;1]	[0;1,3]	[0;1,4]	[0;1,5]	[0;1,5,2]	[0;1,5,2,1]	[0;1,5,2,2]
Рациональное приближение	1	⁠3/4⁠	⁠4/5⁠	⁠5/6⁠	⁠11/13⁠	⁠16/19⁠	⁠27/32⁠
Десятичный эквивалент	1	0,75	0.8	~0,83333	~0,84615	~0,84211	0,84375
Ошибка	+18,519%	−11,111%	−5,1852%	−1,2346%	+0,28490%	−0,19493%	0%

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

Упомянутое выше «правило половины» требует, чтобы при четном a _k деление пополам члена a _k /2 было допустимо тогда и только тогда, когда | x − [ a ₀  ; a ₁ , ..., a _{k − 1} ]| > | x − [ a ₀  ; a ₁ , ..., a _{k − 1} , a _k /2]| ^[12] Это эквивалентно ^[12] следующему: Shoemake (1995).

[ ak _; ak _{− 1} ,..., ak1 ] _> [ ak; ak ₊ 1 _{, ...} ] .

Конвергенты к x являются «наилучшими приближениями» в гораздо более сильном смысле, чем тот, который определен выше. А именно, n / d является конвергентом для x тогда и только тогда, когда | dx − n | имеет наименьшее значение среди аналогичных выражений для всех рациональных приближений m / c с c ≤ d ; то есть, мы имеем | dx − n | < | cx − m |, пока c < d . (Заметим также, что | d _k x − n _k | → 0 при k → ∞ .)

Рациональное число, попадающее в интервал ( x ,  y ) для 0 < x < y , можно найти с помощью непрерывных дробей для x и y . Когда и x, и y иррациональны и

x ₌ [ a0 ; a1 , a2 _, ..., ak − _{1 , ak} , ak + _{1 ,} ... _]

у ₌ [ а0 ; а1 , а2 ,... , _ак − _{1 , бк} , _бк + _{1 ,} ... ]

где x и y имеют одинаковые разложения в цепную дробь вплоть до a _{k −1} , рациональное число, которое попадает в интервал ( x ,  y ), задается конечной цепной дробью,

z ( x , y ) ₌ [ a ₀ ; a ₁ , a ₂ , ..., ak _{− 1} , min( a _k , b _k ) + 1]

Это рациональное число будет наилучшим в том смысле, что никакое другое рациональное число в ( x ,  y ) не будет иметь меньший числитель или меньший знаменатель. ^{[13] [14]}

Если x рационально, то у него будет два представления в виде конечных цепных дробей , x 1 _и x 2 _, и аналогично рациональное число  y будет иметь два представления, y ₁ и y ₂ . Коэффициенты за последним в любом из этих представлений следует интерпретировать как +∞ ; и наилучшим рациональным числом будет одно из z ( x ₁ ,  y ₁ ) , z ( x ₁ ,  y ₂ ) , z ( x ₂ ,  y ₁ ) или z ( x ₂ ,  y ₂ ) .

Например, десятичное представление 3,1416 может быть округлено от любого числа в интервале [3,14155, 3,14165) . Представления непрерывных дробей 3,14155 и 3,14165 следующие:

3,14155 = [3; 7, 15, 2, 7, 1, 4, 1, 1] = [3; 7, 15, 2, 7, 1, 4, 2]

3,14165 = [3; 7, 16, 1, 3, 4, 2, 3, 1] = [3; 7, 16, 1, 3, 4, 2, 4]

и лучшее рациональное из этих двух —

[3; 7, 16] = ⁠355/113⁠ = 3,1415929....

Таким образом, ⁠355/113⁠ является наилучшим рациональным числом, соответствующим округленному десятичному числу 3,1416, в том смысле, что никакое другое рациональное число, округленное до 3,1416, не будет иметь меньший числитель или меньший знаменатель.

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

z = [ a ₀ ; a _{1 ,} ..., ak _{− 1} , ak _, 1] = [ a ₀ ; a ₁ , ..., ak _{− 1} , ak ₊ 1] = ⁠п _к/д _к⁠

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

x = [ a ₀ ; a ₁ , ..., _ak − ₁ , ak _, 2] = ⁠2 п _к - п _к-1/2 q _k - q _k-1⁠ и

у знак равно [ а ₀ ; а ₁ , ..., а _{k - 1} , а _k + 2] знак равно ⁠п _к + п _к-1/q _к + q _к-1⁠

Числа x и y образуются путем увеличения последнего коэффициента в двух представлениях для z . Это тот случай, когда x < y , когда k четное, и x > y , когда k нечетное.

Например, число ⁠355/113⁠ имеет представление в виде непрерывной дроби

⁠355/113⁠ = [3; 7, 15, 1] ​​= [3; 7, 16]

и таким образом ⁠355/113⁠ является сходящимся дробью любого числа строго между

[3; 7, 15, 2]	=	⁠688/219⁠ ≈ 3.1415525
[3; 7, 17]	=	⁠377/120⁠ ≈ 3.1416667

В своем труде Essai sur la théorie des nombres (1798) Адриен-Мари Лежандр выводит необходимое и достаточное условие для того, чтобы рациональное число было сходящимся дробным числом заданного действительного числа. ^[15] Следствие этого критерия, часто называемого теоремой Лежандра в рамках изучения непрерывных дробей, заключается в следующем: ^[16]

Теорема . Если α — действительное число, а p , q — положительные целые числа, такие, что , то p / q — подходящая дробь цепной дроби α .${\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}}$

Эта теорема лежит в основе атаки Винера , полиномиального по времени использования криптографического протокола RSA , который может возникнуть при необдуманном выборе открытого и закрытого ключей (в частности, эта атака успешна, если простые множители открытого ключа n = pq удовлетворяют p < q < 2 p , а закрытый ключ d меньше (1/3) n ^1/4 ). ^[18]

Рассмотрим x = [ a ₀ ; a ₁ , ...] и y = [ b ₀ ; b ₁ , ...] . Если k — наименьший индекс, для которого a _k не равно b _k, то x < y , если (−1) ^k ( a _k − b _k ) < 0 и y < x в противном случае.

Если такого k нет , но одно расширение короче другого, скажем, x = [ a ₀ ; a ₁ , ..., _an ] и y = [ b ₀ ; b ₁ , ..., b _n , b _{n + 1} , ...] с a _i = b _i для 0 ≤ i ≤ n , то x < y, если n четное, и y < x, если n нечетное.

Чтобы вычислить конвергенты числа π, мы можем положить a ₀ = ⌊ π ⌋ = 3 , определить u ₁ = ⁠1/π − 3⁠ ≈ 7,0625 и a ₁ = ⌊ u ₁ ⌋ = 7 , u ₂ = ⁠1/и ₁ − 7⁠ ≈ 15,9966 и a ₂ = ⌊ u ₂ ⌋ = 15 , u ₃ = ⁠1/и ₂ − 15⁠ ≈ 1,0034 . Продолжая таким образом, можно определить бесконечную цепную дробь числа π как

[3;7,15,1,292,1,1,...] (последовательность A001203 в OEIS ).

Четвертая подходящая дробь числа π равна [3;7,15,1] = ⁠355/113⁠ = 3,14159292035..., иногда называемое Милю , что довольно близко к истинному значению числа π .

Предположим, что найденные частные, как и выше, [3;7,15,1]. Ниже приведено правило, по которому мы можем сразу записать сходящиеся дроби, которые получаются из этих частных, не развивая цепную дробь.

Первое частное, предположительно деленное на единицу, даст первую дробь, которая будет слишком мала, а именно, ⁠3/1⁠ . Тогда, умножив числитель и знаменатель этой дроби на второе частное и прибавив к числителю единицу, получим вторую дробь, ⁠22/7⁠ , что будет слишком большим. Умножая подобным образом числитель и знаменатель этой дроби на третье частное и прибавляя к числителю числитель предыдущей дроби, а к знаменателю знаменатель предыдущей дроби, мы получим третью дробь, которая будет слишком маленькой. Таким образом, третье частное равно 15, мы имеем для нашего числителя (22 × 15 = 330) + 3 = 333 , а для нашего знаменателя (7 × 15 = 105) + 1 = 106 . Третья подходящая дробь, таким образом, равна ⁠333/106⁠ . Мы продолжаем таким же образом для четвертого сходящегося дроби. Четвертое частное равно 1, мы говорим, что 333 умножить на 1 равно 333, и это плюс 22, числитель предыдущей дроби, равно 355; аналогично, 106 умножить на 1 равно 106, и это плюс 7 равно 113. Таким образом, используя четыре частных [3;7,15,1], мы получаем четыре дроби:

⁠3/1⁠ , ⁠22/7⁠ , ⁠333/106⁠ , ⁠355/113⁠ , ....

Подводя итог, можно сказать, что картина такова:${\displaystyle {\text{Numerator}}_{i}={\text{Numerator}}_{(i-1)}\cdot {\text{Quotient}}_{i}+{\text{Numerator}}_{(i-2)}}$${\displaystyle {\text{Denominator}}_{i}={\text{Denominator}}_{(i-1)}\cdot {\text{Quotient}}_{i}+{\text{Denominator}}_{(i-2)}}$

Эти сходящиеся дроби попеременно меньше и больше истинного значения π и приближаются все ближе и ближе к π . Разница между данной сходящейся дробью и π меньше, чем обратная величина произведения знаменателей этой сходящейся дроби и следующей сходящейся дроби. Например, дробь ⁠22/7⁠ больше π , но ⁠22/7⁠ − π меньше ⁠1/7 × 106⁠  =  ⁠1/742⁠ (на самом деле, ⁠22/7⁠ − π — это чуть больше, чем ⁠1/791⁠ = ⁠1/7 × 113⁠ ).

Демонстрация вышеизложенных свойств выводится из того факта, что если мы ищем разность между одной из сходящихся дробей и следующей, смежной с ней, то мы получим дробь, числитель которой всегда равен единице, а знаменатель — произведению двух знаменателей. Таким образом, разность между ⁠22/7⁠ и ⁠3/1⁠ есть ⁠1/7⁠ , в избытке; между ⁠333/106⁠ и ⁠22/7⁠ , ⁠1/742⁠ , в дефиците; между ⁠355/113⁠ и ⁠333/106⁠ , ⁠1/11978⁠ , в избытке; и так далее. Результатом является то, что, используя этот ряд разностей, мы можем выразить другим и очень простым способом дроби, с которыми мы здесь имеем дело, посредством второго ряда дробей, числители которых все являются единицей, а знаменатели последовательно являются произведением каждых двух соседних знаменателей. Вместо дробей, написанных выше, мы имеем, таким образом, ряд:

⁠3/1⁠ + ⁠1/1 × 7⁠ − ⁠1/7 × 106⁠ + ⁠1/106 × 113⁠ − ...

Первый член, как мы видим, — это первая дробь; первый и второй вместе дают вторую дробь, ⁠22/7⁠ ; первое, второе и третье дают третью дробь ⁠333/106⁠ , и так далее с остальными; в результате весь ряд эквивалентен исходному значению.

Непростая цепная дробь — это выражение вида

${\displaystyle x=b_{0}+{\cfrac {a_{1}}{b_{1}+{\cfrac {a_{2}}{b_{2}+{\cfrac {a_{3}}{b_{3}+{\cfrac {a_{4}}{b_{4}+\ddots \,}}}}}}}}}$

где a _n ( n > 0) — частичные числители, b _n — частичные знаменатели, а старший член b ₀ называется целой частью цепной дроби.

Чтобы проиллюстрировать использование непростых цепных дробей, рассмотрим следующий пример. Последовательность частичных знаменателей простой цепной дроби π не показывает никакой очевидной закономерности:

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

или

${\displaystyle \pi =3+{\cfrac {1}{7+{\cfrac {1}{15+{\cfrac {1}{1+{\cfrac {1}{292+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{2+{\cfrac {1}{1+{\cfrac {1}{3+{\cfrac {1}{1+\ddots }}}}}}}}}}}}}}}}}}}}}}}$

Однако несколько непростых цепных дробей для π имеют совершенно регулярную структуру, например:

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

${\displaystyle \displaystyle \pi =2+{\cfrac {2}{1+{\cfrac {1}{1/2+{\cfrac {1}{1/3+{\cfrac {1}{1/4+\ddots }}}}}}}}=2+{\cfrac {2}{1+{\cfrac {1\cdot 2}{1+{\cfrac {2\cdot 3}{1+{\cfrac {3\cdot 4}{1+\ddots }}}}}}}}}$

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

Первые два из них являются частными случаями функции арктангенса с π = 4 arctan (1), а четвертый и пятый могут быть выведены с использованием произведения Уоллиса . ^{[19] [20]}

${\displaystyle \pi =3+{\cfrac {1}{6+{\cfrac {1^{3}+2^{3}}{6\cdot 1^{2}+1^{2}{\cfrac {1^{3}+2^{3}+3^{3}+4^{3}}{6\cdot 2^{2}+2^{2}{\cfrac {1^{3}+2^{3}+3^{3}+4^{3}+5^{3}+6^{3}}{6\cdot 3^{2}+3^{2}{\cfrac {1^{3}+2^{3}+3^{3}+4^{3}+5^{3}+6^{3}+7^{3}+8^{3}}{6\cdot 4^{2}+\ddots }}}}}}}}}}}$