Цепная дробь

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

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

[math]r = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \ddots + \cfrac{1}{a_k + \cfrac{1}{\ddots}}}}},[/math]

где [math]a_0[/math] — целое число, а [math]a_i[/math] — натуральные числа (при [math]i \ge 1[/math]).

Сокращенная запись: [math]r = [a_0; a_1, a_2, a_3,\ldots][/math]

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

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

Содержание

[править] Примеры

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

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

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

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

[math]m = na_0 + b_0[/math], [math]0 \lt b_0 \lt n[/math]
[math]n = b_0a_1 + b_1[/math], [math]0 \lt b_1 \lt b_0[/math]
[math]b_0 = b_1a_2 + b_2[/math], [math]0 \lt b_2 \lt b_1[/math]
[math]b_{k-3} = b_{k-2}a_{k-1} + b_{k-1}[/math], [math]0 \lt b_{k-1} \lt b_{k-2}[/math]
[math]b_{k-2} = b_{k-1}a_k[/math] (деление нацело),

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

[math]\frac{m}{n} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \ddots + \cfrac{1}{a_k} }}}[/math]

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

Для любого вещественного числа [math]r[/math] может быть может быть получена конечная либо бесконечная цепная дробь [math][a_0; a_1, a_2, a_3,\ldots][/math], его представляющая, по следующему алгоритму.

[math]a_0 = \lfloor r \rfloor, r_0 = r - a_0,[/math]
[math]a_1 = \left\lfloor \frac{1}{r_0} \right\rfloor, r_1 = \frac{1}{r_0} - a_1,[/math]
[math]\ldots[/math]
[math]a_n = \left\lfloor \frac{1}{r_{n-1}} \right\rfloor, r_n = \frac{1}{r_{n-1}} - a_n,[/math]
[math]\ldots[/math]

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

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

[править] Свойства

Конечную дробь [math][a_0; a_1, a_2, a_3,\ldots, a_n][/math], записанную в виде рациональной дроби [math]\frac{P_n}{Q_n}[/math], называют n-ой подходящей дробью.

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

[math]P_n = P_{n-1}a_n + P_{n-2}[/math]
[math]Q_n = Q_{n-1}a_n + Q_{n-2}[/math]

Также:

[math]P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}[/math]

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

[math]r = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \ddots + \cfrac{1}{a_k + \cfrac{1}{\ddots}}}}},[/math]

то подходящие дроби [math]\frac{P_n}{Q_n}[/math] можно рассматривать как последовательные приближения к действительному числу r, и при любых натуральных [math]a_i[/math] из определения цепной дроби существует предел

[math]\lim_{n \to \infty} \frac{P_n}{Q_n} = r[/math]

Скорость сходимости этой последовательности оценивается как [math]\left|r-\frac{P_k}{Q_k}\right| \lt \frac{1}{Q_k^2}[/math].

Отсюда следует, что подходящая дробь [math]\frac{P_k}{Q_k}[/math] является наилучшим приближением исходного числа r среди всех дробей (рациональных чисел), знаменатель которых не превосходит [math]Q_n[/math].

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

[править] См. также

[править] Литература

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты