Продолженная дробь

Число, представленное как b0+a1/(b1+a2/...)

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

Бесконечная обобщенная цепная дробь определяется последовательностями , для , при этом . ${\displaystyle \{a_{i}\},\{b_{i}\}}$ ${\displaystyle i=0,1,2,\ldots }$ ${\displaystyle a_{0}=0}$

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

Конечная правильная цепная дробь, где — неотрицательное целое число, — целое число, а — положительное целое число, для . ${\displaystyle n}$ ${\displaystyle a_{0}}$ ${\displaystyle a_{i}}$ ${\displaystyle i=1,\ldots ,n}$

Цепная дробь — это математическое выражение , которое можно записать в виде дроби со знаменателем , представляющим собой сумму, содержащую другую простую или цепную дробь. В зависимости от того, заканчивается ли эта итерация простой дробью или нет, цепная дробь является конечной или бесконечной . ^[1]

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

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

Мотивация и обозначения

Рассмотрим, например, рациональное число ⁠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]. ^{[3] [4]}

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

• √ 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] . Обычно в качестве канонического представления выбирается первое, более короткое .
• Представление иррационального числа в виде простой цепной дроби уникально. (Однако возможны дополнительные представления при использовании обобщенных цепных дробей; см. ниже.)
• Действительные числа, непрерывная дробь которых в конечном итоге повторяется, являются в точности квадратными иррациональными числами . ^[5] Например, повторяющаяся непрерывная дробь [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 — целые числа, называемые коэффициентами или членами цепной дроби. ^[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот предел существует для любого выбора и положительных целых чисел . ^{[9] [10]} ${\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}$ :

Цепная дробь для ⁠ ⁠ ${\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] .

Бесконечные цепные дроби и подходящие дроби

Конвергенты, приближающиеся к золотому сечению

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

Представление бесконечной цепной дроби для иррационального числа полезно, потому что его начальные сегменты обеспечивают рациональные приближения к числу. Эти рациональные числа называются сходящимися дробями цепной дроби. ^{[11] [12]} Чем больше член в цепной дроби, тем ближе соответствующая сходящаяся дробь к приближаемому иррациональному числу. Такие числа, как π, иногда имеют большие члены в своей цепной дроби, что позволяет легко приближать их рациональными числами. Другие числа, такие как 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].

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

х ₀ = 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}\ }$

Теорема 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]. Вот все ее лучшие рациональные приближения.

Лучшие рациональные аппроксимации для π (зеленый круг), e (синий ромб), ϕ (розовый продолговатый), (√3)/2 (серый шестиугольник), 1/√2 (красный восьмиугольник) и 1/√3 (оранжевый треугольник), вычисленные из их непрерывных дробных расширений, изображенные в виде наклонов y / x с ошибками относительно их истинных значений (черные штрихи)  

• в
• т
• е

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

Упомянутое выше «правило половины» требует, чтобы при четном a _k деление пополам члена a _k /2 было допустимо тогда и только тогда, когда | x − [ a ₀  ; a ₁ , ..., a _{k − 1} ]| > | x − [ a ₀  ; a ₁ , ..., a _{k − 1} , a _k /2]| ^[13] Это эквивалентно ^[13] следующему: 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 ) не будет иметь меньший числитель или меньший знаменатель. ^{[14] [15]}

Если 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⁠ является конвергентным числом любого числа строго между

Теорема Лежандра о цепных дробях

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

Теорема . Если α — действительное число, а 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 ). ^[19]

Сравнение

Рассмотрим 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⁠ , ....

Следующий код Maple сгенерирует непрерывные дроби числа Пи

Подводя итог, можно сказать, что картина такова: ${\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), а четвертый и пятый могут быть выведены с использованием произведения Уоллиса . ^{[20] [21]}

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

Непрерывная дробь, представленная выше и состоящая из кубов, использует ряд Нилаканты и эксплойт Леонарда Эйлера. ^[22] ${\displaystyle \pi }$

Другие расширения цепных дробей

Периодические непрерывные дроби

Числа с периодическим разложением в непрерывную дробь являются в точности иррациональными решениями квадратных уравнений с рациональными коэффициентами; рациональные решения имеют конечные разложения в непрерывную дробь, как было сказано ранее. Простейшими примерами являются золотое сечение φ = [1;1,1,1,1,1,...] и √ 2 = [1;2,2,2,2,...], в то время как √ 14 = [3;1,2,1,6,1,2,1,6...] и √ 42 = [6;2,12,2,12,2,12...]. Все иррациональные квадратные корни целых чисел имеют специальную форму для периода; симметричную строку, такую ​​как пустая строка (для √ 2 ) или 1,2,1 (для √ 14 ), за которой следует удвоенное ведущее целое число.

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

Поскольку разложение непрерывной дроби для φ не использует никаких целых чисел больше 1, φ является одним из самых «трудных» действительных чисел для аппроксимации рациональными числами. Теорема Гурвица ^[23] утверждает, что любое иррациональное число k может быть аппроксимировано бесконечным множеством рациональных чисел ⁠м/н⁠ с

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

В то время как практически все действительные числа k в конечном итоге будут иметь бесконечно много подходящих дробей ⁠м/н⁠ чье расстояние от k значительно меньше этого предела, подходящие дроби для φ (т.е. числа ⁠5/3⁠ , ⁠8/5⁠ , ⁠13/8⁠ , ⁠21/13⁠ и т. д.) последовательно «следуют границе», сохраняя расстояние почти точно от φ, таким образом, никогда не создавая приближения, даже близко не столь впечатляющего, как, например, ⁠ ${\displaystyle {\scriptstyle {1 \over n^{2}{\sqrt {5}}}}}$355/113⁠ для π . Можно также показать, что каждое действительное число вида ⁠а + б φ/с + d φ⁠ , где a , b , c и d — целые числа, такие что a  d − b  c = ±1 , разделяет это свойство с золотым сечением φ; и что все другие действительные числа могут быть более точно приближены.

Регулярные закономерности в цепных дробях

Хотя в разложении числа π в простую цепную дробь не наблюдается никакой закономерности , для числа e , основания натурального логарифма , она есть :

${\displaystyle e=e^{1}=[2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1,\dots ],}$

что является частным случаем этого общего выражения для положительного целого числа n :

${\displaystyle e^{1/n}=[1;n-1,1,1,3n-1,1,1,5n-1,1,1,7n-1,1,1,\dots ]\,\!.}$

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

${\displaystyle e^{2/n}=\left[1;{\frac {n-1}{2}},6n,{\frac {5n-1}{2}},1,1,{\frac {7n-1}{2}},18n,{\frac {11n-1}{2}},1,1,{\frac {13n-1}{2}},30n,{\frac {17n-1}{2}},1,1,\dots \right]\,\!,}$

с особым случаем для n = 1 :

${\displaystyle e^{2}=[7;2,1,1,3,18,5,1,1,6,30,8,1,1,9,42,11,1,1,12,54,14,1,1\dots ,3k,12k+6,3k+2,1,1\dots ]\,\!.}$

Другие непрерывные дроби этого вида:

${\displaystyle \tanh(1/n)=[0;n,3n,5n,7n,9n,11n,13n,15n,17n,19n,\dots ]}$

где n — положительное целое число; также для целого числа n :

${\displaystyle \tan(1/n)=[0;n-1,1,3n-2,1,5n-2,1,7n-2,1,9n-2,1,\dots ]\,\!,}$

с особым случаем для n = 1 :

${\displaystyle \tan(1)=[1;1,1,3,1,5,1,7,1,9,1,11,1,13,1,15,1,17,1,19,1,\dots ]\,\!.}$

Если I _n ( x ) — модифицированная или гиперболическая функция Бесселя первого рода, мы можем определить функцию на рациональных числах ⁠п/д⁠ по

${\displaystyle S(p/q)={\frac {I_{p/q}(2/q)}{I_{1+p/q}(2/q)}},}$

которая определена для всех рациональных чисел, с p и q в младших членах. Тогда для всех неотрицательных рациональных чисел мы имеем

${\displaystyle S(p/q)=[p+q;p+2q,p+3q,p+4q,\dots ],}$

с аналогичными формулами для отрицательных рациональных чисел; в частности, мы имеем

${\displaystyle S(0)=S(0/1)=[1;2,3,4,5,6,7,\dots ].}$

Многие формулы можно доказать с помощью цепной дроби Гаусса .

Типичные цепные дроби

Большинство иррациональных чисел не имеют периодического или регулярного поведения в их расширении непрерывной дроби. Тем не менее, для почти всех чисел на единичном интервале они имеют одинаковое предельное поведение.

Среднее арифметическое расходится: , и поэтому коэффициенты растут произвольно большими: . В частности, это означает _, что почти все числа хорошо аппроксимируемы, в том смысле, что Хинчин доказал, что геометрическое среднее a i стремится к константе (известной как константа Хинчина ): Поль Леви доказал, что n-й корень из знаменателя n -й подходящей дроби сходится к константе Леви Теорема Лохса утверждает, что подходящие дроби сходятся экспоненциально со скоростью ${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{k=1}^{n}a_{k}=+\infty }$ ${\displaystyle \limsup _{n}a_{n}=+\infty }$ $${\displaystyle \liminf _{n\to \infty }\left|x-{\frac {p_{n}}{q_{n}}}\right|q_{n}^{2}=0}$$ $${\displaystyle \lim _{n\rightarrow \infty }\left(a_{1}a_{2}...a_{n}\right)^{1/n}=K_{0}=2.6854520010\dots }$$ $${\displaystyle \lim _{n\rightarrow \infty }q_{n}^{1/n}=e^{\pi ^{2}/(12\ln 2)}=3.2758\ldots }$$ $${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\ln \left|x-{\frac {p_{n}}{q_{n}}}\right|=-{\frac {\pi ^{2}}{6\ln 2}}}$$

Приложения

Квадратные корни

Обобщенные цепные дроби используются в методе вычисления квадратных корней .

Идентичность

приводит через рекурсию к обобщенной цепной дроби для любого квадратного корня: ^[24]

Уравнение Пелля

Цепные дроби играют существенную роль в решении уравнения Пелля . Например, для положительных целых чисел p и q и неквадратного n верно, что если p ² − nq ² = ±1 , то ⁠п/д⁠ является подходящей дробью правильной непрерывной дроби для √ n . Обратное справедливо, если период правильной непрерывной дроби для √ n равен 1, и в общем случае период описывает, какие подходящие дроби дают решения уравнения Пелля. ^[25]

Динамические системы

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

Оператор обратного сдвига для цепных дробей — это отображение h ( x ) = 1/ x − ⌊1/ x ⌋ , называемое отображением Гаусса , которое отсекает цифры разложения цепной дроби: h ([0; a ₁ , a ₂ , a ₃ , ...]) = [0; a ₂ , a ₃ , ...] . Оператор переноса этого отображения называется оператором Гаусса–Кузмина–Вирсинга . Распределение цифр в цепных дробях задается нулевым собственным вектором этого оператора и называется распределением Гаусса–Кузмина .

История

• 300 г. до н.э. « Начала» Евклида содержат алгоритм нахождения наибольшего общего делителя , современная версия которого генерирует цепную дробь как последовательность частных последовательных евклидовых делений , которые в ней встречаются.
• 499 Ариабхатия содержит решение неопределенных уравнений с использованием цепных дробей
• 1572 Рафаэль Бомбелли , L'Algebra Opera – метод извлечения квадратных корней, связанный с цепными дробями
• 1613 Пьетро Катальди , Trattato del modo brevissimo di trovar la radice Quadra delli numeri – первое обозначение цепных дробей

Катальди представлял цепную дробь как & & & с точками, указывающими, куда следует вводить следующие дроби. ${\displaystyle a_{0}}$ ${\displaystyle {\frac {n_{1}}{d_{1}\cdot }}}$ ${\displaystyle {\frac {n_{2}}{d_{2}\cdot }}}$ ${\displaystyle {\frac {n_{3}}{d_{3}\cdot }}}$

• 1695 Джон Уоллис , Opera Mathematica – введение термина «цепная дробь»
• 1737 Леонард Эйлер , диссертация «De Fractionibus continuis dissertatio » – дал первое на тот момент всеобъемлющее описание свойств непрерывных дробей и включил первое доказательство того, что число e иррационально. ^[26]
• 1748 Эйлер, Введение в анализ бесконечных чисел . Т. I, Глава 18 — доказал эквивалентность определенной формы цепной дроби и обобщенного бесконечного ряда , доказал, что каждое рациональное число может быть записано в виде конечной цепной дроби, и доказал, что цепная дробь иррационального числа бесконечна. ^[27]
• 1761 Иоганн Ламберт – дал первое доказательство иррациональности числа π, используя цепную дробь для tan(x) .
• 1768 Жозеф-Луи Лагранж – дал общее решение уравнения Пелля с использованием цепных дробей, подобных дробям Бомбелли.
• 1770 Лагранж – доказал, что квадратичные иррациональные числа разлагаются в периодические цепные дроби .
• 1813 Карл Фридрих Гаусс , Werke , т. 3, стр. 134–138 – вывел очень общую комплекснозначную цепную дробь с помощью хитрого тождества, включающего гипергеометрическую функцию
• 1892 Анри Паде определил аппроксимацию Паде
• 1972 Билл Госпер – Первые точные алгоритмы для арифметики цепных дробей.

Смотрите также

• Полное частное
• Вычисление непрерывных дробей квадратных корней  – Алгоритмы вычисления квадратных корней
• Египетская дробь  – Конечная сумма отдельных единичных дробей
• Разложение Энгеля  — разложение положительного действительного числа на ряд единичных дробей, каждая из которых является целым кратным следующей.Pages displaying wikidata descriptions as a fallback
• Формула цепной дроби Эйлера  – связывает очень общий бесконечный ряд с бесконечной цепной дробью.
• Бесконечные композиции аналитических функций  – Математическая теория бесконечно итерируемой композиции функций
• Повторяющаяся бинарная операция  – повторное применение операции к последовательности.
• Многогранник Клейна  – Понятие в геометрии чисел
• Математические константы, представленные в виде цепной дроби
• Ограниченные частичные частные  – Аналитические ряды
• Дерево Штерна–Броко  – упорядоченное двоичное дерево рациональных чисел
• Теорема Слешинского–Принсхейма  – Критерий сходимости цепных дробей

Примечания

1. Энциклопедия Британника 2013.
2. Pettofrezzo & Byrkit 1970, стр. 150.
3. Long 1972, стр. 173.
4. Pettofrezzo & Byrkit 1970, стр. 152.
5. Weisstein 2022.
6. Коллинз 2001.
7. Каджори, Флориан (1925). «Лейбниц, мастер-строитель математических обозначений». Isis . 7 (3): 412–429. doi : 10.1086/358328 .
8. Свенсон, Эллен (1999) [1971]. Mathematics into Type (PDF) . Обновлено О'Шоном, Арлин; Шлейер, Антуанеттой (обновленное издание). Американское математическое общество. 2.4.1c "Цепные дроби", стр. 18.
9. Лонг 1972, стр. 183.
10. Петтофреццо и Биркит 1970, стр. 158.
11. Лонг 1972, стр. 177.
12. Петтофреццо и Биркит 1970, стр. 162–163.
13. Thill 2008.
14. Госпер, РВ (1977). «Приложение 2: Арифметика непрерывных дробей».См. «Простейшее промежуточное рациональное», стр. 29–31.
15. Мураками, Хироши (февраль 2015 г.). «Вычисление рациональных чисел в интервале, знаменатель которого наименьший, с использованием интервальной арифметики FP». ACM Communications in Computer Algebra . 48 (3/4): 134–136. doi :10.1145/2733693.2733711.
16. Лежандр, Адриен-Мари (1798). Essai sur la theorie des nombres (на французском языке). Париж: Дюпра. стр. 27–29.
17. Барболози, Доминик; Ягер, Хендрик (1994). «Об одной теореме Лежандра в теории цепных дробей». Journal de Théorie des Nombres de Bordeaux . 6 (1): 81–94. дои : 10.5802/jtnb.106. JSTOR  26273940 – через JSTOR.
18. Харди, Г. Х .; Райт, Э. М. (1938). Введение в теорию чисел . Лондон: Oxford University Press . С. 140–141, 153.
19. Винер, Майкл Дж. (1990). «Криптоанализ коротких секретных экспонент RSA». Труды IEEE по теории информации . 36 (3): 553–558. doi :10.1109/18.54902 – через IEEE.
20. Бандер и Тониен 2017.
21. Шайнерман, Пикетт и Коулман 2008.
22. Фостер 2015.
23. Харди и Райт 2008, Теорема 193.
24. Терстон 2012.
25. Нивен, Цукерман и Монтгомери 1991.
26. Сэндифер 2006.
27. Эйлер 1748.

Ссылки

• Бандер, Мартин В.; Тониен, Джозеф (2017). «Выражения в закрытой форме для двух гармонических непрерывных дробей». The Mathematical Gazette . 101 (552): 439–448. doi :10.1017/mag.2017.125. S2CID  125489697.

• Чэнь, Чэнь-Фань; Ши, Леанг-Сан (1969). «Обращение цепной дроби с помощью алгоритма Рауса». IEEE Trans. Circuit Theory . 16 (2): 197–202. doi :10.1109/TCT.1969.1082925.

• Коллинз, Даррен К. (2001). "Continued Fractions" (PDF) . MIT Undergraduate Journal of Mathematics . Архивировано из оригинала (PDF) 2001-11-20.

• Cuyt, A.; Brevik Petersen, V.; Verdonk, B.; Waadeland, H.; Jones, WB (2008). Справочник по непрерывным дробям для специальных функций . Springer Verlag. ISBN 978-1-4020-6948-2.

• Encyclopaedia Britannica (2013). "Цепная дробь – математика" . Получено 26 апреля 2022 г. .

• Эйлер, Леонард (1748). "E101 – Introductio in analysin infinitorum, том 1". Архив Эйлера . Получено 26 апреля 2022 г.

• Фостер, Тони (22 июня 2015 г.). "Теорема дня: теорема № 203" (PDF) . Робин Уитти. Архивировано (PDF) из оригинала 2013-12-11 . Получено 26 апреля 2022 г. .

• Грэгг, Уильям Б. (1974). «Матричная интерпретация и применение алгоритма непрерывных дробей». Rocky Mountain J. Math . 4 (2): 213. doi : 10.1216/RMJ-1974-4-2-213 . S2CID  121378061.

• Харди, Годфри Х.; Райт, Эдвард М. (декабрь 2008 г.) [1979]. Введение в теорию чисел (6-е изд.). Oxford University Press. ISBN 9780199219865.

• Хайлерманн, JBH (1846 г.). «Ueber die Verwandlung von Reihen в Кеттенбрюхе». Журнал для королевы и математики . 33 : 174–188.

• Джонс, Уильям Б.; Трон, У. Дж. (1980). Непрерывные дроби: аналитическая теория и приложения. Энциклопедия математики и ее приложений . Том 11. Чтение. Массачусетс: Addison-Wesley Publishing Company. ISBN 0-201-13510-8.

• Хинчин, А. Я. (1964) [Первоначально опубликовано на русском языке в 1935 г.]. Continued Fractions . University of Chicago Press . ISBN 0-486-69630-8.

• Лонг, Кэлвин Т. (декабрь 1972 г.). Элементарное введение в теорию чисел (2-е изд.). Лексингтон: DC Heath and Company . ISBN 9780669627039.

• Магнус, Арне (1962). «Цепные дроби, связанные с таблицей Паде». Math. Z . 78 : 361–374. doi :10.1007/BF01195180. S2CID  120535167.

• Нивен, Иван; Цукерман, Герберт С.; Монтгомери, Хью Л. (1991). Введение в теорию чисел (Пятое изд.). Нью-Йорк: Wiley . ISBN 0-471-62546-9.

• Перрон, Оскар (1950). Die Lehre von den Kettenbrüchen . Нью-Йорк, штат Нью-Йорк: Издательство Челси.

• Pettofrezzo, Anthony J.; Byrkit, Donald R. (декабрь 1970 г.). Элементы теории чисел . Englewood Cliffs: Prentice Hall . ISBN 9780132683005.

• Ригер, Георг Иоганн (1982). «Новый подход к действительным числам (на основе цепных дробей)» (PDF) . Abhandlungen der Braunschweigischen Wissenschaftlichen Gesellschaft . 33 : 205–217. Архивировано (PDF) из оригинала 10 декабря 2020 г.

• Rockett, Andrew M.; Szüsz, Peter (1992). Продолжительные дроби . World Scientific Press. ISBN 981-02-1047-7.

• Сэндифер, К. Эдвард (2006). "Глава 32: Кто доказал, что e иррационально?". Как это сделал Эйлер (PDF) . Математическая ассоциация Америки . стр. 185–190. ISBN 978-0-88385-563-8. LCCN  2007927658. Архивировано (PDF) из оригинала 2014-03-19.

• Scheinerman, Ed; Pickett, Thomas J.; Coleman, Ann (2008). «Еще одна непрерывная дробь для π». The American Mathematical Monthly . 115 (10): 930–933. doi :10.1080/00029890.2008.11920610. JSTOR  27642639. S2CID  11914017.

• Shoemake, Ken (1995). "I.4: Рациональная аппроксимация". В Paeth, Alan W. (ред.). Graphics Gems V (версия IBM) . Сан-Диего, Калифорния: Academic Press. стр. 25–31. ISBN 0-12-543455-3.

• Зибек, Х. (1846). «Ueber periodische Kettenbrüche». Журнал для королевы и математики . 33 : 68–70.

• Тилл, М. (2008). «Более точный алгоритм округления рациональных чисел». Computing . 82 (2–3): 189–198. doi :10.1007/s00607-008-0006-7. S2CID  45166490.

• Терстон, Бен (2012). «Оценка квадратных корней, обобщенное выражение непрерывной дроби для каждого квадратного корня». Блог Бена Пола Терстона . Получено 26 апреля 2022 г.

• Уолл, Хьюберт Стэнли (1948). Аналитическая теория непрерывных дробей . D. Van Nostrand Company, Inc. ISBN 0-8284-0207-8.

• Weisstein, Eric Wolfgang (2022). MathWorld (ред.). "Periodic Continued Fraction" . Получено 26 апреля 2022 г. .

Внешние ссылки

• «Цепная дробь», Энциклопедия математики , EMS Press , 2001 [1994]
• Нотт, Рон (2018). "Цепные дроби (доступен онлайн-калькулятор комбинированных цепных дробей)" . Получено 26 апреля 2022 г. .

• В книге Линаса Вепстаса «Цепные дроби и пропуски» (2004) рассматриваются хаотические структуры в цепных дробях.
• Продолжение дробей на дереве Штерна-Броко в cut-the-knot
• Антикитерский механизм I: передаточные числа и непрерывные дроби Архивировано 04.05.2009 на Wayback Machine
• Калькулятор цепных дробей, WIMS.
• Арифметика непрерывных дробей Первая статья Госпера о непрерывных дробях, неопубликованная. Кэшировано в Интернет-архиве Wayback Machine
• Вайсштейн, Эрик В. «Непрерывная дробь». MathWorld .
• «Цепные дроби» Стивена Вольфрама и «Аппроксимации цепными дробями функции тангенса» Майкла Тротта, Демонстрационный проект Вольфрама .
• Последовательность OEIS A133593 («Точная» непрерывная дробь для числа пи)
• Взгляд на «дробную интерполяцию» цепной дроби {1; 1, 1, 1, ...}
• Наилучшее рациональное приближение с помощью цепных дробей
• ПРОДОЛЖЕННЫЕ ДРОБИ от CD Olds