Цепная дробь

Материал из Википедии — свободной энциклопедии

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

$[a_0; a_1, a_2, a_3,\cdots] = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\ldots}}}\;$

где a₀ есть целое число и все остальные a_n натуральные числа (т.е. положительные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.

Содержание

1 Разложение в цепную дробь
2 Подходящие дроби
3 Приближение вещественных чисел рациональными
4 Свойства и примеры
5 Приложения цепных дробей
6 Ссылки

[править] Разложение в цепную дробь

Любое ненулевое вещественное число $x$ может быть представлено цепной дробью $[a_0; a_1, a_2, a_3,\cdots]$ , где

$a_0 = \lfloor x \rfloor, x_0 = x - a_0,$

$a_1 = \left\lfloor \frac{1}{x_0} \right\rfloor, x_1 = \frac{1}{x_0} - a_1,$

$\dots$

$a_n = \left\lfloor \frac{1}{x_{n-1}} \right\rfloor, x_n = \frac{1}{x_{n-1}} - a_n,$

$\dots$

где $\lfloor x \rfloor$ обозначает целую часть числа $x$ .

Для рационального числа $x$ это разложение оборвётся по достижению нулевого $x n$ для некоторого n. В этом случае $x$ представляется конечной цепной дробью $x = [a_0; a_1, \cdots, a_n]$ .

Для иррационального $x$ все величины $x n$ будут ненулевыми и процесс разложения можно продолжать бесконечно. В этом случае $x$ представляется бесконечной цепной дробью $x = [a_0; a_1, a_2, a_3,\cdots]$ .

[править] Подходящие дроби

n-ой подходящей дробью для цепной дроби $x=[a_0; a_1, a_2, a_3,\cdots]$ , называется конечная цепная дробь $[a_0; a_1, \cdots, a_n]$ , значение которой равно некоторому рациональному числу $\frac{p_n}{q_n}$ . Подходящие дроби с чётными номерами образуют возрастающую последовательность, предел которой равен $x$ . Аналогично, подходящие дроби с нечётными номерами образуют убывающую последовательность, предел которой также равен $x$ .

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

$p_{-1} = 1,\quad p_0 = a_0,\quad p_n = a_n p_{n-1} + p_{n-2};$

$q_{-1} = 0,\quad q_0 = 1,\quad q_n = a_n q_{n-1} + q_{n-2}.$

Таким образом, величины $p n$ и $q n$ представляются значениями континуант:

$p_n = K_{n+1}(a_0, a_1, \cdots, a_n)$

$q_n = K_n(a_1, a_2, \cdots, a_n)$

Последовательности $\left\{p_n\right\}$ и $\left\{q_n\right\}$ являются возрастающими.

Числители и знаменатели соседних подходящих дробей связаны соотношением

p n q n - 1 - q n p n - 1 = ( - 1) n - 1,

которое можно переписать в виде

$\frac{p_n}{q_n} - \frac{p_{n-1}}{q_{n-1}} = \frac{(-1)^{n-1}}{q_{n-1} q_n}.$

Откуда следует, что

$\left|x - \frac{p_{n-1}}{q_{n-1}}\right| < \frac{1}{q_{n-1}q_n} < \frac{1}{q_{n-1}^2}.$

[править] Приближение вещественных чисел рациональными

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

$\left|x - \frac{p_n}{q_n}\right| < \frac{1}{q_n^2}.$

Отсюда, в частности, следует, что мера иррациональности любого иррационального числа не меньше 2.

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

Любое рациональное число может быть представлено в виде конечной цепной дроби двумя способами, например:

$9/4=[2; 3, 1] = [2; 4]\;$

Теорема Лагранжа: Число представляется в виде бесконечной периодической цепной дроби тогда и только тогда когда оно является иррациональным решением квадратного уравнения с целыми коэффициентами.

Например:

$\sqrt{2} = [1; 2, 2, 2, 2, \dots]$

золотое сечение $\phi = [1;1,1,1,\dots]$

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

e = [2;1,2,1,1,4,1,1,6,1,1,8,...,1,1,2(n - 1),1,1,2 n,...]

Для числа пи подобной закономерности не выявлено:

π =

[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15,...]

[править] Приложения цепных дробей

Приближение вещественных чисел рациональными
Доказательство иррациональности чисел. Например, с помощью цепных дробей была доказана иррациональность значения дзета-функции Римана $ζ(3)$
Алгоритмы факторизации SQUFOF и CFRAC.