Непрерывные дроби

Исторически непрерывные, или цепные дроби появились в связи с необходимости найти наилучшее приближение вещественного числа с помощью числа рационального. Так, при конструировании зубчатых передач для передачи вращения с одного колеса на другое требуется нарезать на одном из них q зубцов, а на другом — p, так чтобы отношение \frac{p}{q} как можно лучше приближало заранее заданное отношение угловых скоростей \omega. При этом ясно, что чем меньше зубцов нужно будет нарезать, тем это будет выгоднее. Интересно, что к такой же задаче сводится и установление длины года — ведь Земля совершает оборот вокруг Солнца за 365.24219878\ldots суток, а это число иррациональное. Давайте же посмотрим, что такое цепные дроби и как они связаны с алгоритмом Евклида нахождения наибольшего общего делителя двух чисел.

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

\displaystyle q_1+\frac{1}{q_2+\frac{1}{q_3+}}

\ddots

+\frac{1}{q_n+}

\ddots

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

Числа q_1,q_2,\ldots, участвующие в разложении числа \alpha в непрерывную дробь, называются неполными частными.

Иногда непрерывную дробь обозначают следующим образом (с помощью неполных частных): [q_1,q_2,q_3,\ldots,q_s,\ldots].

Возьмем произвольное вещественное число \alpha. Пусть q_1 — целая часть числа \alpha (q_1=[\alpha] — наибольшее целое число, не превосходящее \alpha). Если число \alpha не целое, то получим \displaystyle \alpha=q_1+\frac{1}{\alpha_2},\ \alpha_2>1. Если \alpha_2 не является целым числом, то для него также можно найти целую часть и найти число \alpha_3 и т.д.:

    \[\begin{array}{ll} \displaystyle \alpha_2=q_2+\frac{1}{\alpha_3};&\alpha_3>1,\\[2mm] \ldots&\\ \displaystyle \alpha_{s-1}=q_{s-1}+\frac{1}{\alpha_{s}};&\alpha_{s}>1, \end{array}\]

откуда и получаем разложение \alpha в непрерывную дробь:

\displaystyle q_1+\frac{1}{q_2+\frac{1}{q_3+}}

\ddots

\displaystyle+\frac{1}{q_{s-1}+\frac{1}{\alpha_s}}.

Ясно, что если число \alpha иррационально, то непрерывная дробь будет бесконечной. Действительно, любая конечная цепная дробь является рациональным числом.

Пример 1. Разложим в непрерывную дробь число \sqrt{3}.

\left[\sqrt{3}\right]=1, поэтому

    \[\sqrt{3}=1+\frac{1}{q_2};\ q_2=\frac{1}{\sqrt{3}-1}=\frac{\sqrt{3}+1}{2} .\]

\displaystyle\left[\frac{\sqrt{3}+1}{2}\right]=1, следовательно,

    \[\frac{\sqrt{3}+1}{2}=1+\frac{1}{\sqrt{3}-1}=\sqrt{3}+1 ;\]

\left[\sqrt{3}+1\right]=2, поэтому

    \[\sqrt{3}+1=2+\frac{1}{q_4};\ q_4=\frac{1}{\sqrt{3}-1}=\frac{\sqrt{3}+1}{2} ,\]

т.е. q_2=q_4. Следовательно, неполные частные также будут повторяться. И разложение \sqrt{3} в непрерывную дробь имеет вид

    \[\sqrt{3}=[1;1,2,1,2,1,2,\ldots]\]

Если же число \alpha рационально, то оно представимо конечной непрерывной дробью. Разложить \alpha в непрерывную дробь в этом случае можно с помощью алгоритма Евклида.

    \[\begin{array}{ll} a=bq_1+r_1;&\displaystyle \frac{a}{b}=q_1+\frac{r_1}{b}=q_1+\frac{1}{\frac{b}{r_1}},\\[3mm] b=r_1q_2+r_2;&\displaystyle \frac{b}{r_1}=q_2+\frac{r_2}{r_1}=q_2+\frac{1}{\frac{r_1}{r_2}},\\[3mm] r_1=r_2q_3+r_3;&\displaystyle \frac{r_1}{r_2}=q_3+\frac{r_3}{r_2}=q_3+\frac{1}{\frac{r_2}{r_3}},\\[3mm] \ldots&\\ r_{n-2}=r_{n-1}q_n+r_n;&\displaystyle \frac{r_{n-2}}{r_{n-1}}=q_n+\frac{r_n}{r_{n-1}}=q_n+\frac{1}{\frac{r_{n-1}}{r_n}},\\[3mm] r_{n-1}=r_nq_{n+1};&\displaystyle \frac{r_{n-1}}{r_n}=q_{n+1}. \end{array}\]

Отсюда последовательной заменой каждой дроби

    \[\frac{b}{r_1},\frac{r_1}{r_2},\ldots,\frac{r_{n-2}}{r_{n-1}},\frac{r_{n-1}}{r_n}\]

на ее соответствующее выражение, получается представление

\displaystyle \frac{a}{b}=q_1+\frac{1}{q_2+\frac{1}{q_3+}}

\displaystyle \ddots +\frac{1}{q_n} .

Определение. Дроби

    \[\delta_1=\frac{P_1}{Q_1}=q_1,\delta_2=\frac{P_2}{Q_2}=q_1+\frac{1}{q_2},\delta_3=\frac{P_3}{Q_3}=q_1+\frac{1}{q_2+\frac{1}{q_3}},\ldots\]

называются подходящими дробями.

Теорема. Для подходящих дробей при s>1 справедливо соотношение

    \[\delta_s=\frac{P_s}{Q_s}=\frac{q_sP_{s-1}+P_{s-2}}{q_sQ_{s-1}+Q_{s-2}} .\]

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

    \[P_s= q_sP_{s-1}+P_{s-2},\ Q_s= q_sQ_{s-1}+Q_{s-2} .\]

Доказательство. Доказывать будем по индукции. Проверим базу индукции. Положим P_0=1, Q_0=0. Тогда поскольку \delta_s получается из \delta_{s-1} заменой в выражении для \delta_{s-1} числа q_{s-1} на \displaystyle q_{s-1}+\frac{1}{q_s}, имеем

    \[\frac{P_1}{Q_1}=\frac{q_1}{1},\]

    \[\frac{P_2}{Q_2}=q_1+\frac{1}{q_2}=\frac{q_1+\frac{1}{q_2}}{1}=\frac{q_1q_2+1}{q_2\cdot1+0}=\frac{q_2P_1+P_0}{q_2Q_1+Q_0} .\]

Предположим теперь, что справедливо равенство

    \[\frac{P_k}{Q_k}=\frac{q_kP_{k-1}+P_{k-2}}{q_kQ_{k-1}+Q_{k-2}} .\]

Тогда

    \[\frac{P_{k+1}}{Q_{k+1}}=\frac{\left( q_k+\frac{1}{q_{k+1}}\right) P_{k-1}+P_{k-2}}{\left( q_k+\frac{1}{q_{k+1}}\right) Q_{k-1}+Q_{k-2}}=\]

    \[=\frac{q_{k+1}(q_kP_{k-1}+P_{k-2})+P_{k-1}}{ q_{k+1}(q_kQ_{k-1}+Q_{k-2})+Q_{k-1}}=\frac{q_{k+1}P_k+P_{k-1}}{ q_{k+1}Q_k+Q_{k-1}} .\]

Тем самым, для \delta_{k+1} справедливо равенство того же вида. Теорема доказана.

Вычисления P_k и Q_k удобно производить с помощью следующей таблицы:

    \[\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline $q$&-&$q_1$&$q_2$&$\ldots$&$q_{k-2}$&$q_{k-1}$&$q_k$&$\ldots$&$q_n$&$q_{n+1}$\\ \hline $P$&$1$&$q_1$&$P_2$&$\ldots$&$P_{k-2}$&$P_{k-1}$&$P_k$&$\ldots$&$P_n$&$a$\\ \hline $Q$&$0$&$1$&$Q_2$&$\ldots$&$Q_{k-2}$&$Q_{k-1}$&$Q_k$&$\ldots$&$Q_n$&$b$\\ \hline \end{tabular}\]

Замечание. Последний столбец пишем только в том случае, когда \alpha — несократимая дробь с положительным знаменателем: \alpha=\displaystyle \frac{a}{b}.

Пример 2. Разложим в непрерывную дробь несократимую дробь \displaystyle \frac{125}{92}:

\begin{tabular}{c@{}r@{}|l} &125&92\\ \cline{1--1}\cline{3--3} &92&1\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &92&33\\ \cline{1--1}\cline{3--3} &66&2\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &33&26\\ \cline{1--1}\cline{3--3} &26&1\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &26&7\\ \cline{1--1}\cline{3--3} &21&3\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &7&5\\ \cline{1--1}\cline{3--3} &5&1\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &5&2\\ \cline{1--1}\cline{3--3} &4&2\\ \cline{1--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &2&1\\ \cline{1--1}\cline{3--3} &2&2\\ \cline{1--2} &0& \end{tabular}

Получаем непрерывную дробь:

    \[\frac{125}{92}=1+\frac{1}{2+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{2+\frac{1}{2}}}}}} .\]

Таблица выглядит следующим образом:

    \[\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline $q$&$-$&$1$&$2$&$1$&$3$&$1$&$2$&$2$\\ \hline $P$&$1$&$1$&$3$&$4$&$15$&$19$&$53$&$125$\\ \hline $Q$&$-$&$1$&$2$&$3$&$11$&$14$&$39$&$92$\\ \hline \end{tabular}\]

Таким образом, подходящие дроби будут следующие:

    \[\delta_1=1,\delta_2=\frac{3}{2},\delta_3=\frac{4}{3},\delta_4=\frac{15}{11},\delta_5=\frac{19}{14},\delta_5=\frac{53}{39} .\]

В случае же, когда числитель и знаменатель дроби не взаимно простые (НОД(a,b)=d\ne1) в последнем столбце таблицы будут стоять числитель и знаменатель несократимой дроби, равной данной дроби \displaystyle \frac{a}{b}.

Пример 3. Разложим в непрерывную дробь \displaystyle \frac{525}{231}:

Rendered by QuickLaTeX.com

    \[\frac{525}{231}=\frac{25\cdot21}{11\cdot21}=\frac{25}{11} .\]

Утверждение 1. 1) При s>0 имеем

    \[P_sQ_{s-1}-Q_sP_{s-1}=(-1)^s .\]

2) При s>0 имеем

    \[\delta_s-\delta_{s-1}=\frac{(-1)^s}{Q_sQ_{s-1}} .\]

Доказательство. Действительно, при s=1 получаем

    \[P_1Q_0-P_0Q_1=q_1\cdot0-1\cdot1=-1 .\]

Далее из равенств

    \[P_s= q_sP_{s-1}+P_{s-2},\ Q_s= q_sQ_{s-1}+Q_{s-2}\]

    \[P_sQ_{s-1}-Q_sP_{s-1}=P_{s-1}Q_{s-2}-Q_{s-1}P_{s-2} ,\]

откуда сразу же следует требуемое.

Вторая часть утверждения получается следующим образом:

    \[\delta_s-\delta_{s-1}=\frac{P_s}{Q_s}-\frac{P_{s-1}}{Q_{s-1}}=\frac{(-1)^s}{Q_sQ_{s-1}} .\]

Следствие. Линейное представление наибольшего общего делителя чисел a и b получается из равенства

    \[P_{n+1}Q_{n}-Q_{n+1}P_{n}=(-1)^{n+1}\]

домножением на НОД(a,b)=d, поскольку a=d\cdot P_{n+1},\ b=d\cdot Q_{n+1}.

Пример 4. Приведем линейное представление наибольшего общего делителя чисел 525 и 231 (см. пример 3):

    \[25\cdot4\cdot21-11\cdot9\cdot21=(-1)^4\cdot21\]

или

    \[4\cdot525-9\cdot231=21 .\]

Утверждение 2. Пусть s>1, а если \alpha — рациональная несократимая дробь \displaystyle \alpha=\frac{a}{b} с положительным знаменателем, то пусть также s<n+1. Тогда \alpha лежит между \delta_{s-1} и \delta_s, причем ближе к \delta_s, чем к \delta_{s-1}.

Доказательство. Заменим в равенстве

    \[\delta_s=\frac{P_s}{Q_s}=\frac{q_sP_{s-1}+P_{s-2}}{q_sQ_{s-1}+Q_{s-2}}\]

q_s на \displaystyle q_s+\frac{1}{\alpha_{s+1}}, получим

    \[\alpha=\frac{\alpha_{s+1}P_s+P_{s-1}}{\alpha_{s+1}Q_s+Q_{s-1}} ,\]

    \[\alpha\alpha_{s+1}Q_s+\alpha Q_{s-1}-\alpha_{s+1}P_s-P_{s-1}=0 ,\]

    \[\displaystyle \alpha_{s+1}Q_s\left(\alpha-\frac{P_s}{Q_s}\right)+Q_{s-1}\left(\alpha-\frac{P_{s-1}}{Q_{s-1}}\right)=0,\]

откуда ясно, что первая из разностей, стоящих в скобках, по знаку противоположна второй и численно меньше (так как Q_s>Q_{s-1}), что и доказывает наше утверждение.

Литература

1. Баврин И.И., Фрибус Е.А. Занимательные задачи по математике.
2. Виноградов И.М. Основы теории чисел
3. Нестеренко Ю.В., Никишин Е.М. Очерк о цепных дробях, Квант, 1983. – N5. – C- 16—20; N6. – С. 26-30

Комментариев: 3

  1. 1 гость:

    Одна третья больше чем одна вторая. Сравнение идет в десятичном исчислении значит десять разделить на одну треть и десять разделить на одну вторую значит 30 больше чем 20. Умножаем десятичное 10 на перевернутую дробь. Сколько раз одна третья встречается в десятке десятичного исчисления. А сколько раз встречается 3 в единице? Ни одного раза. А есть шестнадцатиричная система исчисления 0123456789ABCDEF. Буквы это некие предпосылки к образованияю компьютерной программы которая наиболее быстро производит вычисления при меньшем объеме памяти. Все упущено. Промах!
    Пили линейку. Люди говорят пили линейку. Ведь сравнение ведется в статистическом десятке в общем поле с десятичными числами а не в общем основании которое есть частное основание. Выборка из десятка. Сравнение это статистика а статистика требует учесть выборку из наибольшего количества исследуемого числового массива.
    Пили же скорее линейки.
    Сэмь раз отмэръ одын раз отреш. А что если сравниваить общее и частное частота возникновения частного в общем?

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Одна третья меньше одной второй :-) Или я чего-то не понимаю?

    [Ответить]

  2. 2 Дмитрий:

    Надеюсь пригодится ресурс в тему
    Калькулятор элементов непрерывной, цепной дроби
    http://abak.pozitiv-r.ru/online-16/111-nepreryvnaya-tsepnaya-drob

    [Ответить]

Оставьте свой отзыв

Добавить изображение