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

«Повторяющаяся дробь» перенаправляется сюда. Не путать с повторением десятичной дроби .

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

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

В математике непрерывная дробь — это выражение, полученное посредством итерационного процесса представления числа как суммы его целой части и обратной величины другого числа, а затем записи этого другого числа как суммы его целой части и другой обратной дроби, и так на. В конечной цепной дроби (или завершающейся цепной дроби ) итерация/ рекурсия завершается после конечного числа шагов путем использования целого числа вместо другой цепной дроби. Напротив, бесконечная цепная дробь является бесконечным выражением . В любом случае все целые числа в последовательности, кроме первого, должны быть положительными . Целые числа $a_{i}$ называются коэффициентами или членами цепной дроби.

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

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

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

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

Рассмотрим, например, рациональное число 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 ) и 4 дает точное выражение + 1 / 2 + 1 / 6 + 1/7 ​ ​ за 415 / 93 .

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

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

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

Основная формула

( Обобщенная ) цепная дробь представляет собой выражение вида

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

где a _i и b _i могут быть любыми комплексными числами.

Когда b _i = 1 для всех i, выражение называется простой цепной дробью.Когда выражение содержит конечное число членов, оно называется конечной цепной дробью.Когда выражение содержит бесконечное количество членов, оно называется бесконечной цепной дробью. Когда с какого-то момента члены со временем повторяются, выражение называется периодической цепной дробью .

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

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

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

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

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

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

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

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

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

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

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

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

Найдите простую цепную дробь для $3.245={\frac {649}{200}}$

Шаг	Настоящий Число	Целое число часть	Дробный часть	Упрощенный	Взаимный выключенный ​
1	$r={\frac {649}{200}}$	$i=3$	$f={\frac {649}{200}}-3$	$={\frac {49}{200}}$	${\frac {1}{f}}={\frac {200}{49}}$
2	$r={\frac {200}{49}}$	$i=4$	$f={\frac {200}{49}}-4$	$={\frac {4}{49}}$	${\frac {1}{f}}={\frac {49}{4}}$
3	$r={\frac {49}{4}}$	$i=12$	$f={\frac {49}{4}}-12$	$={\frac {1}{4}}$	${\frac {1}{f}}={\frac {4}{1}}$
4	$r=4$	$i=4$	$f=4-4$	$=0$	ОСТАНАВЛИВАТЬСЯ
Форма непрерывной дроби для $3.245={\frac {649}{200}}=[3;4,12,4]$ = 3 + 1 / 4 + 1 / 12 + 1 / 4

Обозначения

Целые числа $a_{0}$, $a_{1}$ и т. д., называются коэффициентами или членами цепной дроби. Поскольку непрерывная дробь, такая как

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

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

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

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

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

$x=a_{0}+{\frac {\ \ 1\ \mid }{\mid \,a_{1}}}+{\frac {\ \ 1\,\mid }{\mid \,a_{2}}}+{\frac {\ \ 1\,\mid }{\mid \,a_{3}}}+{\frac {\ \ 1\,\mid }{\mid \,a_{4}}},$

или в более распространенных связанных обозначениях, таких как

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

или

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

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

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

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

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

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

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

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

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

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

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

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

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

[ а ₀ ; а ₁ , а ₂ , ..., а _{п - 1} , а _п , 1] знак равно [ а ₀ ; а ₁ , а ₂ , ..., а _{п - 1} , а _п + 1] .

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

Взаимные обязательства

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

Например, если $a$ является целым числом и $x<1$ затем

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

Если $x>1$ затем

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

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

Например,

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

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

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

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

Представление бесконечной цепной дроби для иррационального числа полезно, поскольку его начальные сегменты обеспечивают рациональные приближения к числу. Эти рациональные числа называются подходящими дробями цепной дроби. Чем больше член цепной дроби, тем ближе соответствующая подходящая дробь к аппроксимируемому иррациональному числу. Числа типа π иногда содержат большие члены в своей цепной дроби, что позволяет легко аппроксимировать их рациональными числами. Другие числа, такие как e, имеют лишь небольшие члены в начале своей непрерывной дроби, что затрудняет их рациональное приближение. Золотое сечение Φ повсюду имеет члены, равные 1 – наименьшие возможные значения – что делает Φ самым трудным для рационального приближения числом. Следовательно, в этом смысле это «самое иррациональное» из всех иррациональных чисел. Четные подходящие числа меньше исходного числа, а нечетные - больше.

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

${\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 ₂ , ..., то соответствующее рекурсивное отношение - это соотношение гауссовских скобок :

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

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

${\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. ^к −1 , ... Например, разложение цепной дроби для ${\sqrt {3}}$ есть [1; 1, 2, 1, 2, 1, 2, 1, 2, ...] . Сравнение подходящих чисел с аппроксимантами, полученными на основе вавилонского метода:

н	−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), является распределение Гаусса–Кузьмина .

полезные

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

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

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

$\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. Подходящие $\ [\ a_{0}\ ;$ $a_{1}\ ,$ $a_{2}\ ,$ $\ldots \ ]\$ даны

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

или в матричной форме,

$${\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. Если $\ n$сходящаяся к цепной дроби есть $\ {\frac {h_{n}}{k_{n}}}\ ,$ затем

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

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

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

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

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

${\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: Цепная дробь эквивалентна серии чередующихся членов:

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

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

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

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

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

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

имеет определитель $(-1)^{n}a_{n}$или, что то же самое,

$${\frac {h_{n}}{\ k_{n}\ }}-{\frac {h_{n-2}}{\ k_{n-2}\ }}={\frac {(-1)^{n}}{\ k_{n-2}\ k_{n}\ }}a_{n}$$

это означает, что нечетные члены монотонно уменьшаются, а четные монотонно увеличиваются.

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

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

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

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

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

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

Теорема 5.

${\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: Рассмотрим множество всех открытых интервалов с концами $[0;a_{1},\dots ,a_{n}],[0;a_{1},\dots ,a_{n}+1]$. Обозначим это как ${\mathcal {C}}$. Любое открытое подмножество $[0,1]\setminus \mathbb {Q}$ представляет собой непересекающееся объединение множеств из ${\mathcal {C}}$.

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

Полуконвергенты

Если

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

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

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

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

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

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

приближения

См. Также: Диофантово приближение и аппроксимация Паде.

Можно выбрать наилучшее рациональное приближение действительного числа x как рациональное число. n / d , 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%

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

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

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

[ К _​ ; а _{k - 1} , ..., а ₁ ] > [ а _k ; до _{k + 1} , ...] .

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

Лучшее рациональное решение в пределах интервала

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

х = [ до ₀ ; а ₁ , а ₂ , ..., а _{k - 1} , а _k , а _{k + 1} , ...]

у знак равно [ а ₀ ; а ₁ , а ₂ , ..., а _{k - 1} , б _k , б _{k + 1} , ...]

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

z ( Икс , y ) знак равно [ а ₀ ; а ₁ , а ₂ , ..., а _{k - 1} , min( а _k , б _k ) + 1]

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

Если x является рациональным, он будет иметь два представления цепной дроби, которые являются конечными , x ₁ и x ₂ , и аналогично рациональный 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 = [ и ₀ ; а ₁ , ..., а _{k - 1} , а _k , 1] знак равно [ а ₀ ; и ₁ , ..., и _{k − 1} , и _k + 1] = пк _​ / дк _​

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

х = [ до ₀ ; а ₁ , ..., а _{k - 1} , а _k , 2] знак равно 2 п _к - п _к-1 / 2 q _к - q _к-1 и

у = [ до ₀ ; а ₁ , ..., а _{k - 1} , а _k + 2] = пк _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 theorie des nombres» (1798) Адриен-Мари Лежандр выводит необходимое и достаточное условие того, что рациональное число сходится к непрерывной дроби данного действительного числа. Следствием этого критерия, часто называемого теоремой Лежандра при изучении цепных дробей, является следующее:

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

show Доказательство

Proof. We follow the proof given in An Introduction to the Theory of Numbers by G. H. Hardy and E. M. Wright. Suppose α, p, q are such that $\left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}$, and assume that α > p/q. Then we may write $\alpha -{\frac {p}{q}}={\frac {\theta }{q^{2}}}$, where 0 < θ < 1/2. We write p/q as a finite continued fraction [a0; a1, ..., an], where due to the fact that each rational number has two distinct representations as finite continued fractions differing in length by one (namely, one where an = 1 and one where an ≠ 1), we may choose n to be even. (In the case where α < p/q, we would choose n to be odd.) Let p0/q0, ..., pn/qn = p/q be the convergents of this continued fraction expansion. Set $\omega :={\frac {1}{\theta }}-{\frac {q_{n-1}}{q_{n}}}$, so that $\theta ={\frac {q_{n}}{q_{n-1}+\omega q_{n}}}$ and thus, $$\alpha ={\frac {p}{q}}+{\frac {\theta }{q^{2}}}={\frac {p_{n}}{q_{n}}}+{\frac {1}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {(p_{n}q_{n-1}+1)+\omega p_{n}q_{n}}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {p_{n-1}q_{n}+\omega p_{n}q_{n}}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {p_{n-1}+\omega p_{n}}{q_{n-1}+\omega q_{n}}},$$ where we have used the fact that pn-1 qn - pn qn-1 = (-1)n and that n is even. Now, this equation implies that α = [a0; a1, ..., an, ω]. Since the fact that 0 < θ < 1/2 implies that ω > 1, we conclude that the continued fraction expansion of α must be [a0; a1, ..., an, b0, b1, ...], where [b0; b1, ...] is the continued fraction expansion of ω, and therefore that pn/qn = p/q is a convergent of the continued fraction of α.

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

Сравнение

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

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

Разложение числа π и его

Чтобы вычислить подходящие числа π, мы можем положить a ₀ = ⌊ π ⌋ = 3 , определить u ₁ = 1 / π − 3 ≈ 7,0625 и а ₁ знак равно ⌊ ты ₁ ⌋ знак равно 7 , ты ₂ = 1 / ты ₁ - 7 ≈ 15,9966 и а ₂ знак равно ⌊ ты ₂ ⌋ знак равно 15 , ты ₃ = 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 будет генерировать непрерывные дробные разложения числа Пи.

Подводя итог, шаблон такой ${\text{Numerator}}_{i}={\text{Numerator}}_{(i-1)}\cdot {\text{Quotient}}_{i}+{\text{Numerator}}_{(i-2)}$${\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 ; и так далее с остальными в результате вся серия эквивалентна исходному значению.

Обобщенная цепная дробь

Основная статья: Обобщенная цепная дробь

Обобщенная цепная дробь является выражением вида

$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 ₀ называется целой частью цепной дроби.

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

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

или

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

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

$\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 \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 \pi =2+{\cfrac {4}{3+{\cfrac {1\cdot 3}{4+{\cfrac {3\cdot 5}{4+{\cfrac {5\cdot 7}{4+\ddots }}}}}}}}$

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

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

Непрерывная фракция $\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, φ является одним из самых «трудных» действительных чисел для аппроксимации рациональными числами. Теорема Гурвица утверждает, что любое иррациональное число k можно аппроксимировать бесконечным числом рациональных м / н с

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

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

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

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

$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 :

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

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

$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 :

$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 ]\,\!.$

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

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

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

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

со специальным случаем для n = 1 :

$\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 ) — модифицированная или гиперболическая функция Бесселя первого рода, мы можем определить функцию на рациональных числах п / к по

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

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

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

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

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

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

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

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

Среднее арифметическое расходится: $\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=1}^{n}a_{k}=+\infty$, и поэтому коэффициенты становятся сколь угодно большими: $\limsup _{n}a_{n}=+\infty$. В частности, это означает, что почти все числа хорошо аппроксимируются в том смысле, что

$$\liminf _{n\to \infty }\left|x-{\frac {p_{n}}{q_{n}}}\right|q_{n}^{2}=0$$

Хинчин доказал, что геометрическое a i _{среднее} стремится к константе (известной как константа Хинчина ):

$$\lim _{n\rightarrow \infty }\left(a_{1}a_{2}...a_{n}\right)^{1/n}=K_{0}=2.6854520010\dots$$

Поль Леви доказал, что корень n-й степени знаменателя n- й подходящей дроби сходится к постоянной Леви.

$$\lim _{n\rightarrow \infty }q_{n}^{1/n}=e^{\pi ^{2}/(12\ln 2)}=3.2758\ldots$$

Теорема Лоха утверждает, что подходящие дроби сходятся экспоненциально со скоростью

$$\lim _{n\to \infty }{\frac {1}{n}}\ln \left|x-{\frac {p_{n}}{q_{n}}}\right|=-{\frac {\pi ^{2}}{6\ln 2}}$$

Приложения

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

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

Личность

${\sqrt {x}}=1+{\frac {x-1}{1+{\sqrt {x}}}}$ ( 1 )

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

${\sqrt {x}}=1+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\ddots }}}}}}}$ ( 2 )

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

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

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

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

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

Собственные значения и собственные векторы

Алгоритм Ланцоша использует разложение непрерывной дроби для итеративной аппроксимации собственных значений и собственных векторов большой разреженной матрицы.

Сетевые приложения

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

Примеры рациональных и иррациональных чисел

Число	р	0	1	2	3	4	5	6	7	8	9	10
123	и р	123
	день	123
12.3	и р	12	3	3
	день	12	37 / 3	123 / 10
1.23	и р	1	4	2	1	7
	день	1	5 / 4	11 / 9	16 / 13	123 / 100
0.123	и р	0	8	7	1	2	5
	день	0	1 / 8	7 / 57	8 / 65	23 / 187	123 / 1 000
Φ = ${\frac {1+{\sqrt {5}}}{2}}$	и р	1	1	1	1	1	1	1	1	1	1	1
	день	1	2	3 / 2	5 / 3	8 / 5	13 / 8	21 / 13	34 / 21	55 / 34	89 / 55	144 / 89
- Φ = $-{\frac {1+{\sqrt {5}}}{2}}$	и р	-2	2	1	1	1	1	1	1	1	1	1
	день	-2	- 3 / 2	- 5 / 3	- 8 / 5	- 13 / 8	- 21 / 13	- 34 / 21	- 55 / 34	- 89 / 55	- 144 / 89	- 233 / 144
${\sqrt {2}}$	и р	1	2	2	2	2	2	2	2	2	2	2
	день	1	3 / 2	7 / 5	17 / 12	41 / 29	99 / 70	239 / 169	577 / 408	1 393 / 985	3 363 / 2 378	8 119 / 5 741
${\frac {1}{\sqrt {2}}}$	и р	0	1	2	2	2	2	2	2	2	2	2
	день	0	1	2 / 3	5 / 7	12 / 17	29 / 41	70 / 99	169 / 239	408 / 577	985 / 1 393	2 378 / 3 363
${\sqrt {3}}$	и р	1	1	2	1	2	1	2	1	2	1	2
	день	1	2	5 / 3	7 / 4	19 / 11	26 / 15	71 / 41	97 / 56	265 / 153	362 / 209	989 / 571
${\frac {1}{\sqrt {3}}}$	и р	0	1	1	2	1	2	1	2	1	2	1
	день	0	1	1 / 2	3 / 5	4 / 7	11 / 19	15 / 26	41 / 71	56 / 97	153 / 265	209 / 362
${\frac {\sqrt {3}}{2}}$	и р	0	1	6	2	6	2	6	2	6	2	6
	день	0	1	6 / 7	13 / 15	84 / 97	181 / 209	1 170 / 1 351	2 521 / 2 911	16 296 / 18 817	35 113 / 40 545	226 974 / 262 087
${\sqrt[{3}]{2}}$	и р	1	3	1	5	1	1	4	1	1	8	1
	день	1	4 / 3	5 / 4	29 / 23	34 / 27	63 / 50	286 / 227	349 / 277	635 / 504	5 429 / 4 309	6 064 / 4 813
и	и р	2	1	2	1	1	4	1	1	6	1	1
	день	2	3	8 / 3	11 / 4	19 / 7	87 / 32	106 / 39	193 / 71	1 264 / 465	1 457 / 536	2 721 / 1 001
п	и р	3	7	15	1	292	1	1	1	2	1	3
	день	3	22 / 7	333 / 106	355 / 113	103 993 / 33 102	104 348 / 33 215	208 341 / 66 317	312 689 / 99 532	833 719 / 265 381	1 146 408 / 364 913	4 272 943 / 1 360 120
Число	р	0	1	2	3	4	5	6	7	8	9	10

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

История

• 300 г. до н.э. «Элементы Евклида» содержат алгоритм определения наибольшего общего делителя , современная версия которого генерирует непрерывную дробь как последовательность частных последовательных евклидовых делений , которые встречаются в ней.
• 499 Арьябхатия содержит решение неопределенных уравнений с использованием цепных дробей.
• 1572 Рафаэль Бомбелли , L'Algebra Opera – метод извлечения квадратных корней, связанный с цепными дробями.
• 1613 Пьетро Катальди , Трактат об очень коротком способе нахождения квадратного корня из чисел – первые обозначения цепных дробей.

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

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

См. также

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

Ссылки

• Афифи, Хайтам; Ору, Себастьян; Карл, Хольгер (апрель 2018 г.). «MARVELO: внедрение беспроводной виртуальной сети для наложения графиков с циклами». Конференция IEEE по беспроводной связи и сетям 2018 года (WCNC) . IEEE. стр. 1–6. arXiv : 1712.06676 . дои : 10.1109/WCNC.2018.8377194 . ISBN  978-1-5386-1734-2 . S2CID   13447977 .

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

• Чен, Чен-Фан; Ши, Леанг-Сан (1969). «Продолжение обращения дробей по алгоритму Рауса». IEEE Транс. Теория цепей . 16 (2): 197–202. дои : 10.1109/TCT.1969.1082925 .

• Коллинз, Даррен К. (2001). «Продолжительные дроби» (PDF) . Математический журнал бакалавриата Массачусетского технологического института . Архивировано из оригинала (PDF) 20 ноября 2001 г.

• Кайт, А.; Бревик Петерсен, В.; Вердонк, Б.; Вааделанд, Х.; Джонс, ВБ (2008). Справочник цепных дробей для специальных функций . Спрингер Верлаг. ISBN  978-1-4020-6948-2 .

• Британская энциклопедия (2013). «Цепная дробь – математика» . Проверено 26 апреля 2022 г.

• Эйлер, Леонард (1748). «E101 – Введение в анализ infinitorum, том 1» . Архив Эйлера . Проверено 26 апреля 2022 г.

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

• Грэгг, Уильям Б. (1974). «Матричные интерпретации и приложения алгоритма цепной дроби» . Роки Маунтин Дж. Математика . 4 (2): 213. doi : 10.1216/RMJ-1974-4-2-213 . S2CID   121378061 .

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

• Хайлерманн, JBH (1846 г.). «О превращении рядов в цепные дроби» . Журнал чистой и прикладной математики . 33 : 174–188.

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

• Хинчин, А.Я. (1964) [Первоначально опубликовано на русском языке, 1935]. Продолжительные дроби . Издательство Чикагского университета . ISBN  0-486-69630-8 .

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

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

• Мартин, Ричард М. (декабрь 2004 г.). Электронная структура: основная теория и практические методы . Издательство Кембриджского университета. дои : 10.1017/CBO9780511805769 . ISBN  9780511805769 .

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

• Перрон, Оскар (1950). Учение о цепных дробях . Нью-Йорк, штат Нью-Йорк: Издательство Челси.

• Петтофреззо, Энтони Дж.; Биркит, Дональд Р. (декабрь 1970 г.). Элементы теории чисел . Энглвудские скалы: Прентис-холл . ISBN  9780132683005 .

• Ригер, Георг Иоганн (1982). «Новый подход к действительным числам (на основе цепных дробей)» (PDF) . Трактаты Брауншвейгского научного общества . 33 :205-217. Архивировано (PDF) из оригинала 10 декабря 2020 г.

• Рокетт, Эндрю М.; Сюс, Питер (1992). Продолжительные дроби . Мировая научная пресса. ISBN  981-02-1047-7 .

• Джулиано Ромео: Цепные дроби в области p-адических чисел», Bul. AMS, v61(2), (апрель 2024 г.), стр. 343–371.

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

• Шайнерман, Эд; Пикетт, Томас Дж.; Коулман, Энн (2008). «Еще одна непрерывная дробь для π». Американский математический ежемесячник . 115 (10): 930–933. дои : 10.1080/00029890.2008.11920610 . JSTOR   27642639 . S2CID   11914017 .

• Шумейк, Кен (1995). «I.4: Рациональное приближение» . В Паэте, Алан В. (ред.). Graphics Gems V (версия IBM) . Сан-Диего, Калифорния: Academic Press. стр. 25–31. ISBN  0-12-543455-3 .

• Зибек, Х. (1846). «О периодических цепных дробях» . Журнал чистой и прикладной математики . 33 :68-70.

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

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

• Уолл, Хьюберт Стэнли (1948). Аналитическая теория цепных дробей . компании Д. Ван Ностранда, Inc. ISBN  0-8284-0207-8 .

• Вайсштейн, Эрик Вольфганг (2022). MathWorld (ред.). «Периодическая непрерывная дробь» . Проверено 26 апреля 2022 г.

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

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

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