Цепная дробь

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

Цепная дробь (непрерывная дробь) — конечное или бесконечное выражение для действительного числа 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}}}}}}}}}$

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

Для любого вещественного числа Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle r} может быть может быть получена конечная либо бесконечная цепная дробь Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle [a_0; a_1, a_2, a_3,\ldots]} , его представляющая, по следующему алгоритму.

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle a_0 = \lfloor r \rfloor, r_0 = r - a_0,}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle a_1 = \left\lfloor \frac{1}{r_0} \right\rfloor, r_1 = \frac{1}{r_0} - a_1,}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \ldots}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle a_n = \left\lfloor \frac{1}{r_{n-1}} \right\rfloor, r_n = \frac{1}{r_{n-1}} - a_n,}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \ldots}

где Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lfloor \alpha \rfloor} обозначает целую часть числа Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \alpha} (округление Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \alpha} до ближайшего целого в меньшую сторону).

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

Свойства

Конечную дробь Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle [a_0; a_1, a_2, a_3,\ldots, a_n]} , записанную в виде рациональной дроби Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \frac{P_n}{Q_n}} , называют n-ой подходящей дробью.

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P_n = P_{n-1}a_n + P_{n-2}}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle Q_n = Q_{n-1}a_n + Q_{n-2}}

Также:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}}

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle r = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \ddots + \cfrac{1}{a_k + \cfrac{1}{\ddots}}}}},}

то подходящие дроби Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \frac{P_n}{Q_n}} можно рассматривать как последовательные приближения к действительному числу r, и при любых натуральных Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle a_i} из определения цепной дроби существует предел

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lim_{n \to \infty} \frac{P_n}{Q_n} = r}

Скорость сходимости этой последовательности оценивается как Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \left|r-\frac{P_k}{Q_k}\right| < \frac{1}{Q_k^2}} .

Отсюда следует, что подходящая дробь Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \frac{P_k}{Q_k}} является наилучшим приближением исходного числа r среди всех дробей (рациональных чисел), знаменатель которых не превосходит Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle Q_n} .

Цепная дробь является периодической тогда и только тогда, когда она представляет квадратическую иррациональность (то есть вещественное число вида Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \frac{a+\sqrt{D}}{c}; \ a,c,D \in \mathbb{Z}} , иными словами — корень квадратного уравнения с целыми коэффициентами). Это утверждение называется теоремой Лагранжа.

См. также

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

Литература

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