Цепная дробь

Цепные дроби — Николай Мощевитин / ПостНаука

Цепная дробь (непрерывная дробь) — конечное или бесконечное выражение для действительного числа r вида

$r=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}+{\cfrac {1}{\ddots }}}}}}}}}},$

где $a_{0}$ — целое число, а $a_{i}$ — натуральные числа (при $i\geq 1$).

Сокращенная запись: $r=[a_{0};a_{1},a_{2},a_{3},\ldots ]$

Рациональным числам соответствуют конечные цепные дроби, а иррациональным — бесконечные.

Цепные дроби появились в работах Пьетро Антонио Катальди (1613 год), их теория развита Джоном Валлисом, Леонардом Эйлером и Жозефом Луи Лагранжем.

Примеры

• ${\frac {7}{5}}=1+{\frac {1}{2+{\frac {1}{2}}}}=[1;2,2]$ (конечная цепная дробь)
• ${\sqrt {2}}=1+{\frac {1}{{\sqrt {2}}+1}}=1+{\frac {1}{2+{\frac {1}{{\sqrt {2}}+1}}}}=[1;2,2,\ldots ]$ (бесконечная цепная дробь)

Цепные дроби и алгоритм Евклида

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

Если есть натуральные числа m и n и разложение по алгоритму Евклида:

$m=na_{0}+b_{0}$, $0<b_{0}<n$

$n=b_{0}a_{1}+b_{1}$, $0<b_{1}<b_{0}$

$b_{0}=b_{1}a_{2}+b_{2}$, $0<b_{2}<b_{1}$

…

$b_{k-3}=b_{k-2}a_{k-1}+b_{k-1}$, $0<b_{k-1}<b_{k-2}$

$b_{k-2}=b_{k-1}a_{k}$ (деление нацело),

то с помощью него получаются чи́сла, образующие (конечную) цепную дробь для рационального числа m/n:

${\frac {m}{n}}=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}$

Алгоритм получения цепной дроби для любого вещественного числа

Для любого вещественного числа $r$ может быть может быть получена конечная либо бесконечная цепная дробь $[a_{0};a_{1},a_{2},a_{3},\ldots ]$, его представляющая, по следующему алгоритму.

$a_{0}=\lfloor r\rfloor ,r_{0}=r-a_{0},$

$a_{1}=\left\lfloor {\frac {1}{r_{0}}}\right\rfloor ,r_{1}={\frac {1}{r_{0}}}-a_{1},$

$\ldots$

$a_{n}=\left\lfloor {\frac {1}{r_{n-1}}}\right\rfloor ,r_{n}={\frac {1}{r_{n-1}}}-a_{n},$

$\ldots$

где $\lfloor \alpha \rfloor$ обозначает целую часть числа $\alpha$ (округление $\alpha$ до ближайшего целого в меньшую сторону).

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

Свойства

Конечную дробь $[a_{0};a_{1},a_{2},a_{3},\ldots ,a_{n}]$, записанную в виде рациональной дроби ${\frac {P_{n}}{Q_{n}}}$, называют n-ой подходящей дробью.

Для числителей и знаменателей подходящих дробей выполнены рекуррентные формулы, выведенные Леонардом Эйлером:

$P_{n}=P_{n-1}a_{n}+P_{n-2}$

$Q_{n}=Q_{n-1}a_{n}+Q_{n-2}$

Также:

$P_{n}Q_{n-1}-P_{n-1}Q_{n}=(-1)^{n+1}$

Если дана бесконечная цепная дробь

$r=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}+{\cfrac {1}{\ddots }}}}}}}}}},$

то подходящие дроби ${\frac {P_{n}}{Q_{n}}}$ можно рассматривать как последовательные приближения к действительному числу r, и при любых натуральных $a_{i}$ из определения цепной дроби существует предел

$\lim _{n\to \infty }{\frac {P_{n}}{Q_{n}}}=r$

Скорость сходимости этой последовательности оценивается как $\left|r-{\frac {P_{k}}{Q_{k}}}\right|<{\frac {1}{Q_{k}^{2}}}$.

Отсюда следует, что подходящая дробь ${\frac {P_{k}}{Q_{k}}}$ является наилучшим приближением исходного числа r среди всех дробей (рациональных чисел), знаменатель которых не превосходит $Q_{n}$.

Цепная дробь является периодической тогда и только тогда, когда она представляет квадратическую иррациональность (то есть вещественное число вида ${\frac {a+{\sqrt {D}}}{c}};\ a,c,D\in \mathbb {Z}$, иными словами — корень квадратного уравнения с целыми коэффициентами). Это утверждение называется теоремой Лагранжа.

См. также

• Машина Рамануджана

Литература

• Хинчин А. Я. Цепные дроби. — М.: ГИФМЛ, 1960.