Распечатать запись Распечатать запись

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

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

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

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}<br />
\displaystyle<br />
\alpha_2=q_2+\frac{1}{\alpha_3};&\alpha_3>1,\\[2mm]<br />
\ldots&\\<br />
\displaystyle<br />
\alpha_{s-1}=q_{s-1}+\frac{1}{\alpha_{s}};&\alpha_{s}>1,<br />
\end{array}

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

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

\ddots

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

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

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

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

\displaystyle \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, следовательно,

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

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

\displaystyle \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}<br />
a=bq_1+r_1;&\displaystyle \frac{a}{b}=q_1+\frac{r_1}{b}=q_1+\frac{1}{\frac{b}{r_1}},\\[3mm]<br />
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]<br />
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]<br />
\ldots&\\<br />
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]<br />
r_{n-1}=r_nq_{n+1};&\displaystyle \frac{r_{n-1}}{r_n}=q_{n+1}.<br />
\end{array}

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

\displaystyle \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} .

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

\displaystyle\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 справедливо соотношение

\displaystyle \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}, имеем

\displaystyle\frac{P_1}{Q_1}=\frac{q_1}{1},

\displaystyle \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} .

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

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

Тогда

\displaystyle \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}}=

\displaystyle =\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|}<br />
\hline<br />
$q$&-&$q_1$&$q_2$&$\ldots$&$q_{k-2}$&$q_{k-1}$&$q_k$&$\ldots$&$q_n$&$q_{n+1}$\\<br />
\hline<br />
$P$&$1$&$q_1$&$P_2$&$\ldots$&$P_{k-2}$&$P_{k-1}$&$P_k$&$\ldots$&$P_n$&$a$\\<br />
\hline<br />
$Q$&$0$&$1$&$Q_2$&$\ldots$&$Q_{k-2}$&$Q_{k-1}$&$Q_k$&$\ldots$&$Q_n$&$b$\\<br />
\hline<br />
\end{tabular}

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

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

\begin{tabular}{c@{}r@{}|l}<br />
&125&92\\<br />
\cline{1–1}\cline{3–3}<br />
&92&1\\<br />
\cline{2–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&92&33\\<br />
\cline{1–1}\cline{3–3}<br />
&66&2\\<br />
\cline{2–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&33&26\\<br />
\cline{1–1}\cline{3–3}<br />
&26&1\\<br />
\cline{2–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&26&7\\<br />
\cline{1–1}\cline{3–3}<br />
&21&3\\<br />
\cline{2–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&7&5\\<br />
\cline{1–1}\cline{3–3}<br />
&5&1\\<br />
\cline{2–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&5&2\\<br />
\cline{1–1}\cline{3–3}<br />
&4&2\\<br />
\cline{1–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&2&1\\<br />
\cline{1–1}\cline{3–3}<br />
&2&2\\<br />
\cline{1–2}<br />
&0&<br />
\end{tabular}

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

\displaystyle \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|}<br />
\hline<br />
$q$&$-$&$1$&$2$&$1$&$3$&$1$&$2$&$2$\\<br />
\hline<br />
$P$&$1$&$1$&$3$&$4$&$15$&$19$&$53$&$125$\\<br />
\hline<br />
$Q$&$-$&$1$&$2$&$3$&$11$&$14$&$39$&$92$\\<br />
\hline<br />
\end{tabular}

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

\displaystyle \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}:

\begin{tabular}{c@{}r@{}|l}<br />
&525&231\\<br />
\cline{1–1}\cline{3–3}<br />
&462&2\\<br />
\cline{1–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&231&63\\<br />
\cline{1–1}\cline{3–3}<br />
&189&3\\<br />
\cline{1–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&63&42\\<br />
\cline{1–1}\cline{3–3}<br />
&42&1\\<br />
\cline{1–2}<br />
\end{tabular}

\begin{tabular}{c@{}r@{}|l}<br />
&42&21\\<br />
\cline{1–1}\cline{3–3}<br />
&42&2\\<br />
\cline{1–2}<br />
&$0$&<br />
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|}<br />
\hline<br />
$q$&$-$&$2$&$3$&$1$&$2$\\<br />
\hline<br />
$P$&$1$&$2$&$7$&$9$&$25$\\<br />
\hline<br />
$Q$&$-$&$1$&$3$&$4$&$11$\\<br />
\hline<br />
\end{tabular}

\displaystyle \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 имеем

\displaystyle \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} ,

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

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

\displaystyle \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}.

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

\displaystyle \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}}, получим

\displaystyle \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

    [Ответить]

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

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