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

В математике бесконечная периодическая цепная дробь — это непрерывная дробь , которую можно представить в виде

$x=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\quad \ddots \quad a_{k}+{\cfrac {1}{a_{k+1}+{\cfrac {\ddots }{\quad \ddots \quad a_{k+m-1}+{\cfrac {1}{a_{k+m}+{\cfrac {1}{a_{k+1}+{\cfrac {1}{a_{k+2}+{\ddots }}}}}}}}}}}}}}}}}$

где за начальным блоком [ a ₀ , a ₁ ,... a _k ] из k +1 частичных знаменателей следует блок [ a _{k +1} , a _{k +2} ,... a _{k + m} ] из m частичных знаменателей знаменатели, повторяющиеся до бесконечности . Например, ${\sqrt {2}}$ можно разложить до периодической цепной дроби [1,2,2,2,...].

В данной статье рассматривается только случай периодических правильных цепных дробей . Другими словами, в оставшейся части этой статьи предполагается, что все частичные знаменатели a _i ( i ≥ 1) являются положительными целыми числами. Общий случай, когда частичные знаменатели a _i являются произвольными действительными или комплексными числами, рассматривается в статье « Проблема сходимости» .

Чисто периодические и периодические дроби

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

${\begin{aligned}x&=[a_{0};a_{1},a_{2},\dots ,a_{k},a_{k+1},a_{k+2},\dots ,a_{k+m},a_{k+1},a_{k+2},\dots ,a_{k+m},\dots ]\\&=[a_{0};a_{1},a_{2},\dots ,a_{k},{\overline {a_{k+1},a_{k+2},\dots ,a_{k+m}}}]\end{aligned}}$

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

${\begin{aligned}x&=[a_{0};a_{1},a_{2},\dots ,a_{k},{\dot {a}}_{k+1},a_{k+2},\dots ,{\dot {a}}_{k+m}]\end{aligned}}$

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

Если исходный неповторяющийся блок отсутствует, т. е. если k = -1, a ₀ = a _m и

$x=[{\overline {a_{0};a_{1},a_{2},\dots ,a_{m-1}}}],$

правильная цепная дробь x называется чисто периодической . Например, правильная цепная дробь [1; 1, 1, 1, ...] золотого сечения φ является чисто периодической, тогда как правильная цепная дробь [1; 2, 2, 2, ...] из ${\sqrt {2}}$ является периодическим, но не чисто периодическим.

Как унимодулярные матрицы

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

$x=[0;{\overline {a_{1},a_{2},\dots ,a_{m}}}],$

Фактически это можно записать как

$x={\frac {\alpha x+\beta }{\gamma x+\delta }}$

с $\alpha ,\beta ,\gamma ,\delta$ являются целыми числами и удовлетворяют $\alpha \delta -\beta \gamma =1.$ Явные значения можно получить, написав

$S={\begin{pmatrix}1&0\\1&1\end{pmatrix}}$

что называется «сдвигом», так что

$S^{n}={\begin{pmatrix}1&0\\n&1\end{pmatrix}}$

и аналогично отражение, данное

$T\mapsto {\begin{pmatrix}-1&1\\0&1\end{pmatrix}}$

так что $T^{2}=I$. Обе эти матрицы унимодулярны , произвольные произведения остаются унимодулярными. Тогда, учитывая $x$ как и выше, соответствующая матрица имеет вид

$S^{a_{1}}TS^{a_{2}}T\cdots TS^{a_{m}}={\begin{pmatrix}\alpha &\beta \\\gamma &\delta \end{pmatrix}}$

и у одного есть

$x=[0;{\overline {a_{1},a_{2},\dots ,a_{m}}}]={\frac {\alpha x+\beta }{\gamma x+\delta }}$

как явная форма. Поскольку все элементы матрицы являются целыми числами, эта матрица принадлежит модульной группе $SL(2,\mathbb {Z} ).$

Связь с

Квадратное иррациональное число — это иррациональный действительный корень квадратного уравнения.

$ax^{2}+bx+c=0$

где коэффициенты a , b и c являются целыми числами, дискриминант b а ² − 4 ac , больше нуля. По квадратичной формуле всякую квадратичную иррациональную величину можно записать в виде

$\zeta ={\frac {P+{\sqrt {D}}}{Q}}$

где P , D и Q — целые числа, D > 0 не является полным квадратом (но не обязательно свободным от квадратов), а Q делит величину P ² − D (например (6+ √ 8 )/4). Такое квадратичное иррациональное число также может быть записано в другой форме с квадратным корнем из бесквадратного числа (например, (3+ √ 2 )/2), как объяснено для квадратичных иррациональных чисел .

Рассмотрев полные частные периодических цепных дробей, Эйлер смог доказать, что если x — правильная периодическая цепная дробь, то x — квадратичное иррациональное число. Доказательство простое. Из самой дроби можно составить квадратное уравнение с целыми коэффициентами, которым x должна удовлетворять .

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

Уменьшение количества сурдов

Квадратичный сурд $\zeta ={\frac {P+{\sqrt {D}}}{Q}}$ называется уменьшенным, если $\zeta >1$ и его сопряженное $\eta ={\frac {P-{\sqrt {D}}}{Q}}$удовлетворяет неравенствам $-1<\eta <0$. Например, золотое сечение $\phi =(1+{\sqrt {5}})/2=1.618033...$ является уменьшенным сурдом, поскольку он больше единицы и сопряжен с ним $(1-{\sqrt {5}})/2=-0.618033...$ больше −1 и меньше нуля. С другой стороны, квадратный корень из двух ${\sqrt {2}}=(0+{\sqrt {8}})/2$ больше единицы, но не является уменьшенным сурдом, поскольку его сопряженное $-{\sqrt {2}}=(0-{\sqrt {8}})/2$ меньше −1.

Галуа доказал, что правильная цепная дробь, представляющая квадратичный иррационал ζ, является чисто периодической тогда и только тогда, когда ζ является приведенным иррационом. На самом деле Галуа показал нечто большее. Он также доказал, что если ζ — приведенная квадратичная дробь, а η — ее сопряженная дробь, то цепные дроби для ζ и для (−1/η) являются чисто периодическими, а повторяющийся блок в одной из этих цепных дробей является зеркальным отображением. повторяющегося блока в другом. В символах мы имеем

${\begin{aligned}\zeta &=[{\overline {a_{0};a_{1},a_{2},\dots ,a_{m-1}}}]\\[3pt]{\frac {-1}{\eta }}&=[{\overline {a_{m-1};a_{m-2},a_{m-3},\dots ,a_{0}}}]\,\end{aligned}}$

где ζ — любой приведенный квадратичный иррационал, а η — его сопряженное.

Из этих двух теорем Галуа можно вывести результат, уже известный Лагранжу. Если r > 1 — рациональное число, не являющееся полным квадратом, то

${\sqrt {r}}=[a_{0};{\overline {a_{1},a_{2},\dots ,a_{2},a_{1},2a_{0}}}].$

В частности, если n — любое неквадратное положительное целое число, разложение √ n в правильную цепную дробь содержит повторяющийся блок длины m , в котором первые m − 1 частичных знаменателей образуют палиндромную строку.

Длина повторяющегося блока

Анализируя последовательность комбинаций

${\frac {P_{n}+{\sqrt {D}}}{Q_{n}}}$

которое может возникнуть, когда ζ = ( P + √ D )/ Q разлагается как правильная цепная дробь, Лагранж показал, что наибольший частичный знаменатель a _i в разложении меньше 2 √ D и что длина повторяющегося блока меньше Д. 2

В последнее время более резкие аргументы на основе функции делителя показали, что длина повторяющегося блока для квадратичного иррационального дискриминанта D имеет порядок ${\mathcal {O}}({\sqrt {D}}\ln {D}).$

Каноническая форма и повторение

Следующий итерационный алгоритм можно использовать для получения разложения цепной дроби в канонической форме ( S — любое натуральное число , не являющееся полным квадратом ):

$m_{0}=0\,\!$

$d_{0}=1\,\!$

$a_{0}=\left\lfloor {\sqrt {S}}\right\rfloor \,\!$

$m_{n+1}=d_{n}a_{n}-m_{n}\,\!$

$d_{n+1}={\frac {S-m_{n+1}^{2}}{d_{n}}}\,\!$

$a_{n+1}=\left\lfloor {\frac {{\sqrt {S}}+m_{n+1}}{d_{n+1}}}\right\rfloor =\left\lfloor {\frac {a_{0}+m_{n+1}}{d_{n+1}}}\right\rfloor \!.$

что m _n , d _n и an _{Обратите внимание ,} всегда являются целыми числами.Алгоритм завершает работу, когда этот триплет совпадает с предыдущим.Алгоритм также может завершиться на a _i, когда a _i = 2 a ₀ , что проще реализовать.

С этого момента расширение будет повторяться. Последовательность [ a ₀ ; a ₁ , a ₂ , a ₃ , ...] — разложение цепной дроби:

${\sqrt {S}}=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\,\ddots }}}}}}$

Пример

Чтобы получить √ 114 в виде цепной дроби, начните с m ₀ = 0; д ₀ = 1; и 0 _{= 10 (} 10 ² = 100 и 11 ² = 121 > 114, поэтому выбрано 10).

${\begin{aligned}{\sqrt {114}}&={\frac {{\sqrt {114}}+0}{1}}=10+{\frac {{\sqrt {114}}-10}{1}}=10+{\frac {({\sqrt {114}}-10)({\sqrt {114}}+10)}{{\sqrt {114}}+10}}\\&=10+{\frac {114-100}{{\sqrt {114}}+10}}=10+{\frac {1}{\frac {{\sqrt {114}}+10}{14}}}.\end{aligned}}$

$m_{1}=d_{0}\cdot a_{0}-m_{0}=1\cdot 10-0=10\,.$

$d_{1}={\frac {S-m_{1}^{2}}{d_{0}}}={\frac {114-10^{2}}{1}}=14\,.$

$a_{1}=\left\lfloor {\frac {a_{0}+m_{1}}{d_{1}}}\right\rfloor =\left\lfloor {\frac {10+10}{14}}\right\rfloor =\left\lfloor {\frac {20}{14}}\right\rfloor =1\,.$

Итак, m ₁ = 10; д ₁ = 14; и 1 _{= 1} .

${\frac {{\sqrt {114}}+10}{14}}=1+{\frac {{\sqrt {114}}-4}{14}}=1+{\frac {114-16}{14({\sqrt {114}}+4)}}=1+{\frac {1}{\frac {{\sqrt {114}}+4}{7}}}.$

Далее, m ₂ = 4; д ₂ = 7; и 2 _{= 2} .

${\frac {{\sqrt {114}}+4}{7}}=2+{\frac {{\sqrt {114}}-10}{7}}=2+{\frac {14}{7({\sqrt {114}}+10)}}=2+{\frac {1}{\frac {{\sqrt {114}}+10}{2}}}.$

${\frac {{\sqrt {114}}+10}{2}}=10+{\frac {{\sqrt {114}}-10}{2}}=10+{\frac {14}{2({\sqrt {114}}+10)}}=10+{\frac {1}{\frac {{\sqrt {114}}+10}{7}}}.$

${\frac {{\sqrt {114}}+10}{7}}=2+{\frac {{\sqrt {114}}-4}{7}}=2+{\frac {98}{7({\sqrt {114}}+4)}}=2+{\frac {1}{\frac {{\sqrt {114}}+4}{14}}}.$

${\frac {{\sqrt {114}}+4}{14}}=1+{\frac {{\sqrt {114}}-10}{14}}=1+{\frac {14}{14({\sqrt {114}}+10)}}=1+{\frac {1}{\frac {{\sqrt {114}}+10}{1}}}.$

${\frac {{\sqrt {114}}+10}{1}}=20+{\frac {{\sqrt {114}}-10}{1}}=20+{\frac {14}{{\sqrt {114}}+10}}=20+{\frac {1}{\frac {{\sqrt {114}}+10}{14}}}.$

Теперь вернемся ко второму уравнению выше.

Следовательно, простая цепная дробь для квадратного корня из 114 равна

${\sqrt {114}}=[10;{\overline {1,2,10,2,1,20}}].\,$ (последовательность A010179 в OEIS )

√ 114 примерно равно 10,67707 82520. После одного разложения повторения непрерывная дробь дает рациональную дробь. ${\frac {21194}{1985}}$ десятичное значение которого составляет ок. 10.67707 80856, относительная ошибка0,0000016% или 1,6 частей на 100 000 000.

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

Более быстрый метод — оценить его обобщенную цепную дробь . формулы Из полученной там :

${\begin{aligned}{\sqrt {z}}={\sqrt {x^{2}+y}}&=x+{\cfrac {y}{2x+{\cfrac {y}{2x+{\cfrac {y}{2x+\ddots }}}}}}\\&=x+{\cfrac {2x\cdot y}{2(2z-y)-y-{\cfrac {y^{2}}{2(2z-y)-{\cfrac {y^{2}}{2(2z-y)-\ddots }}}}}}\end{aligned}}$

и тот факт, что 114 - это 2/3 пути между 10 ² = 100 и 11 ² =121 приводит к

${\begin{aligned}{\sqrt {114}}={\cfrac {\sqrt {1026}}{3}}={\cfrac {\sqrt {32^{2}+2}}{3}}&={\cfrac {32}{3}}+{\cfrac {2/3}{64+{\cfrac {2}{64+{\cfrac {2}{64+{\cfrac {2}{64+\ddots }}}}}}}}\\&={\cfrac {32}{3}}+{\cfrac {2}{192+{\cfrac {18}{192+{\cfrac {18}{192+\ddots }}}}}},\end{aligned}}$

это просто вышеупомянутое [10;1,2, 10,2,1, 20,1,2], оцениваемое на каждом третьем семестре. Объединение пар дробей дает

${\begin{aligned}{\sqrt {114}}={\cfrac {\sqrt {32^{2}+2}}{3}}&={\cfrac {32}{3}}+{\cfrac {64/3}{2050-1-{\cfrac {1}{2050-{\cfrac {1}{2050-\ddots }}}}}}\\&={\cfrac {32}{3}}+{\cfrac {64}{6150-3-{\cfrac {9}{6150-{\cfrac {9}{6150-\ddots }}}}}},\end{aligned}}$

что сейчас $[10;1,2,{\overline {10,2,1,20,1,2}}]$ оценивается на третьем семестре и каждые шесть семестров после этого.

См. также

• Цепная дробь – число, представленное как a0+1/(a1+1/...).
• Обобщенная непрерывная дробь – обобщение непрерывных дробей, в котором частичные числители и частичные знаменатели могут принимать произвольные комплексные значения. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Проблема Эрмита
• Метод непрерывной дроби для вычисления квадратных корней - Алгоритмы вычисления квадратных корней
• Ограниченные частичные отношения
• Непрерывная факторизация дробей – алгоритм факторизации целых чисел. Страницы, отображающие описания викиданных в качестве запасного варианта.

Ссылки

• Бечану, Мариус (5 февраля 2003 г.). «Период непрерывной дроби sqrt(n)» (PDF) . Теорема 2.3. Архивировано из оригинала (PDF) 21 декабря 2015 года . Проверено 3 мая 2022 г.

• Кон, JHE (1977). «Длина периода разложения простой цепной дроби d ^1/2 « . Pacific J. Math . 71 : 21–32. doi : 10.2140/pjm.1977.71.21 .

• Давенпорт, Х. (декабрь 1982 г.). Высшая арифметика . Издательство Кембриджского университета . ISBN  0-521-28678-6 .

• Глига, Александра Иоана (17 марта 2006 г.). О непрерывных дробях квадратного корня из простых чисел (PDF) . Следствие 3.3 . Проверено 3 мая 2022 г.

• Хикерсон, Дин Р. (1973). «Длина периода разложения простой цепной дроби vd» . Пасифик Дж. Математика . 46 : 429–432. дои : 10.2140/pjm.1973.46.429 .

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

• Лонг, Кэлвин Т. (1972). Элементарное введение в теорию чисел (3 подред.). Waveland Pr Inc. LCCN   77-171950 .

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

• Подсыпанин Е.В. (1982). «Длина периода квадратичной иррациональной». Журнал советской математики . 18 (6): 919–923. дои : 10.1007/BF01763963 . S2CID   119567810 .

• Рокетт, Эндрю М.; Сюс, Питер (1992). НЕПРЕРЫВНЫЕ ДРОБИ . Мировое научное издательство. ISBN  9789810210526 .