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

${\ 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 я = 1, \ ldots, п}$

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

Непрерывные дроби обладают рядом замечательных свойств, связанных с алгоритмом Евклида для целых или действительных чисел . Каждое рациональное число ${\ displaystyle p}$/${\ displaystyle q}$имеет два тесно связанных выражения в виде конечной цепной дроби, коэффициенты которой a _i можно определить, применив алгоритм Евклида к . Числовое значение бесконечной цепной дроби иррационально ; он определяется из своей бесконечной последовательности целых чисел как предел последовательности значений для конечных цепных дробей. Каждая конечная цепная дробь последовательности получается с помощью конечного префикса определяющей последовательности целых чисел бесконечной цепной дроби. Более того, каждое иррациональное число является значением уникального${\ displaystyle (p, q)}$${\ displaystyle \ alpha}$бесконечная цепная дробь, коэффициенты которой могут быть найдены с помощью неограниченной версии алгоритма Евклида, применяемого к несоизмеримым значениям и 1. Такой способ выражения действительных чисел (рациональных и иррациональных) называется их представлением в виде непрерывной дроби .${\ displaystyle \ 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]. ^{[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, ...] (последовательность A000012 в 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 {b_ {1}} {a_ {1} + {\ cfrac {b_ {2}} {a_ {2} + {\ cfrac {b_ {3}} {a_ {) 3} + {_ {\ ddots}}}}}}}}}$

где a _i и b _i могут быть любыми комплексными числами. Обычно они должны быть целыми числами. Если b _i = 1 для всех i, выражение называется простой цепной дробью. Если выражение содержит конечное число членов, оно называется конечной цепной дробью. Если выражение содержит бесконечное количество членов, оно называется бесконечной цепной дробью. ^[6]

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

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

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

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

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

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

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

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

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

Вычисление представлений непрерывной дроби [ править ]

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

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

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

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

Обозначения [ править ]

Целые числа и т. Д. Называются коэффициентами или членами непрерывной дроби. ^[2] Можно сокращать непрерывную дробь${\displaystyle a_{0}}$${\displaystyle a_{1}}$

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

в обозначениях Карла Фридриха Гаусса

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

или как

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

или в обозначениях Прингсхайма как

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

или в другом родственном обозначении как

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

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

${\displaystyle x=\left\langle a_{0};a_{1},a_{2},a_{3}\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}].}$

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

Конечные непрерывные дроби [ править ]

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

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

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

Обратных [ править ]

Представления в виде непрерывной дроби положительного рационального числа и его обратной величины идентичны, за исключением сдвига на одну позицию влево или вправо в зависимости от того, является ли число меньше или больше единицы соответственно. Другими словами, числа, представленные символами и, являются обратными.${\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]}$

Бесконечные цепные дроби и подходящие дроби [ править ]

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

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

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

а ₀/1, а ₁ а ₀ + 1/а ₁, а ₂ ( а ₁ а ₀ + 1) + а ₀/а ₂ а ₁ + 1, а ₃ ( а ₂ ( а ₁ а ₀ + 1) + а ₀ ) + ( а ₁ а ₀ + 1)/ а ₃ ( а ₂ а ₁ + 1) + а ₁.

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

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

ч _п = а _н ч _{п - 1} + ч _{п - 2} ,

к _п = _п к _{п - 1} + к _{п - 2} .

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

ч _н/k _n знак равно а _н ч _{п - 1} + ч _{п - 2}/а _н к _{п - 1} + к _{п - 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
k n	1	0	1	1	6	13	32

При использовании вавилонского метода для генерации последовательных приближений квадратного корня из целого числа, если один начинает с наименьшего целого числа в качестве первого приближения, все сгенерированные рациональные числа появляются в списке подходящих дробей для непрерывной дроби. В частности, аппроксиманты появятся в списке подходящих дробей в позициях 0, 1, 3, 7, 15, ...,  2 ^k −1 , ... Например, расширение непрерывной дроби для √ 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
k n	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

Свойства [ править ]

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

Некоторые полезные теоремы [ править ]

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

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

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

${\displaystyle \left[a_{0};a_{1},\,\dots ,a_{n-1},z\right]={\frac {zh_{n-1}+h_{n-2}}{zk_{n-1}+k_{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}}}.}$

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

${\displaystyle k_{n}h_{n-1}-k_{n-1}h_{n}=(-1)^{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}}}$

имеет определитель плюс или минус один и, следовательно, принадлежит к группе унимодулярных матриц .${\displaystyle 2\times 2}$ ${\displaystyle \mathrm {GL} (2,\mathbb {Z} )}$

Теорема 4. Каждая ( ая) сходящаяся дробь ближе к следующей ( ой) сходящейся части, чем любая предыдущая ( ая) сходящаяся. В символах, если принять за th сходящуюся , то${\displaystyle s}$${\displaystyle n}$${\displaystyle r}$${\displaystyle n}$${\displaystyle [a_{0};a_{1},\ldots ,a_{n}]=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: сходящаяся дробь, полученная завершением цепной дроби непосредственно перед большим членом, является близким приближением к пределу цепной дроби.

Полуконвергенты [ править ]

Если

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

где - такое целое число , которые называются полуконвергентами , вторичными подходящими дробями или промежуточными дробями . -St semiconvergent равна медианта из -х одного и сходящихся . Иногда этот термин используется для обозначения того, что быть полуконвергентным исключает возможность быть сходящимся (т. Е. ), А не тем, что сходящийся является своего рода полусходящимся.${\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, 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%

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

«Половина правила» упоминалось выше требует , чтобы при _к четно, половинного термин _к / 2 является допустимым , если и только если | х - [ а ₀  ; a ₁ , ..., a _{k - 1} ] | > | х - [ а ₀  ; a ₁ , ..., a _{k - 1} , a _k / 2] | ^[11] Это эквивалент ^[11] : ^[12]

[ а _к ; a _{k - 1} , ..., a ₁ ]> [ a _k ; а _{к + 1} , ...] .

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

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

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

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

y = [ a ₀ ; a ₁ , a ₂ , ..., a _{k - 1} , b _k , b _{k + 1} , ...]

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

z ( x , y ) = [ a ₀ ; a ₁ , a ₂ , ..., a _{k - 1} , min ( a _k , b _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 = [ a ₀ ; a ₁ , ..., a _{k - 1} , a _k , 1] = [ a ₀ ; a ₁ , ..., a _{k - 1} , a _k + 1]

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

х = [ ₀ ; a ₁ , ..., a _{k - 1} , a _k , 2] и

y = [ a ₀ ; a ₁ , ..., a _{k - 1} , a _k + 2]

Числа 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

Сравнение [ править ]

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

Если такого k нет , но одно расширение короче другого, скажем, x = [ a ₀ ; a ₁ , ..., a _n ] и 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/u ₁ - 7≈ 15,9966 и a ₂ = ⌊ u ₂ ⌋ = 15 , u ₃ =1/у ₂ - 15≈ 1,0034 . Продолжая таким образом, можно определить бесконечную цепную дробь числа π как

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

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

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

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

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

Подводя итог, паттерн${\displaystyle {\text{Numerator}}_{i}={\text{Numerator}}_{(i-1)}\cdot {\text{Quotient}}_{i}+{\text{Numerator}}_{(i-2)}}$${\displaystyle {\text{Denominator}}_{i}={\text{Denominator}}_{(i-1)}\cdot {\text{Quotient}}_{i}+{\text{Denominator}}_{(i-2)}}$

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

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

3/1 + 1/1 × 7 - 1/7 × 106 + 1/106 × 113 - ...

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

Обобщенная непрерывная дробь [ править ]

Обобщенная цепная дробь - это выражение вида

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

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

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

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

или же

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

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

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

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

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

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

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

Приведенная выше непрерывная дробь, состоящая из кубов, использует серию Нилаканта и эксплойт Леонарда Эйлера. ^[15]${\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, φ - одно из самых "сложных" действительных чисел для аппроксимации рациональными числами. Теорема Гурвица ^[16] утверждает, что любое иррациональное число 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для π . Также можно показать, что каждое действительное число видаа + б ф/c + 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 ) является модифицированной или гиперболической функцией Бесселя первого рода, мы можем определить функцию на рациональных числахп/q к

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

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

Типичные непрерывные дроби [ править ]

Большинство иррациональных чисел не имеют никакого периодического или регулярного поведения в разложении их цепной дроби. Тем не менее, Хинчины доказали , что для почти всех действительных чисел х , то _я (для я = 1, 2, 3, ... ) обладает свойством поразительным: их средние геометрическим стремятся к постоянная (известному как постоянная Хинчиной , K ≈ 2.6854520010 ... ) независимо от значения x . Поль Леви показал, что корень n- й степени знаменателя числа n-я сходящаяся дробь разложения почти всех действительных чисел приближается к асимптотическому пределу, приблизительно 3,27582, который известен как константа Леви . Теорема Лохса утверждает, что n- я сходящаяся дробь разложения почти всех действительных чисел определяет число со средней точностью чуть более n десятичных знаков.

Приложения [ править ]

Квадратные корни [ править ]

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

Личность

${\displaystyle {\sqrt {x}}=1+{\frac {x-1}{1+{\sqrt {x}}}}}$

( 1 )

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

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

( 2 )

Уравнение Пелла [ править ]

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

Динамические системы [ править ]

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

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

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

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

Сетевые приложения [ править ]

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

Примеры рациональных и иррациональных чисел [ править ]