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

22 Июнь 2011, 0:05

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

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

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

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

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

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

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

$\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} &525&231\\ \cline{1–1}\cline{3–3} &462&2\\ \cline{1–2} \end{tabular}$

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

$\begin{tabular}{c@{}r@{}|l} &63&42\\ \cline{1–1}\cline{3–3} &42&1\\ \cline{1–2} \end{tabular}$

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

$\begin{tabular}{|c|c|c|c|c|c|} \hline $q$&$-$&$2$&$3$&$1$&$2$\\ \hline $P$&$1$&$2$&$7$&$9$&$25$\\ \hline $Q$&$-$&$1$&$3$&$4$&$11$\\ \hline \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}} .$

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

$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

Теги: алгебра, математика
Рубрика: Статьи по математике | Отзывы (RSS) | Трекбек

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

1 гость:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Май 22nd, 2015 at 23:50
Одна третья меньше одной второй Или я чего-то не понимаю?

[Ответить]
22 Май 2015, 12:56
2 Дмитрий:

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

[Ответить]
28 Июль 2015, 16:15

Математика, которая мне нравится

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

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

1 гость:

2 Дмитрий:

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

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер