Ланцюговий дріб

Ланцюговий дріб (або неперервний дріб) — це математичний вираз виду

$[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 є натуральними числами. Узагальненими ланцюговими дробами називають вирази виду:

$a_0+\cfrac{b_1}{a_1+\cfrac{b_2}{a_2+\frac{b_3}{a_3+\dots}}}$

Будь-яке дійсне число може бути представлене ланцюговим дробом. Число представляється скінченним ланцюговим дробом тоді й лише тоді , коли воно раціональне.

Розклад в ланцюговий дріб

Будь-яке дійсне число $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$ будуть ненульовими и процес розкладу можна продовжувати нескінченно.

Приклад обчислення ланцюгового дробу для числа 3,245 подано в таблиці.

Обчислення ланцюгового дробу для числа 3,245
$3\,$	$3.245\ \left(3 \tfrac{49}{200}\right) - 3\,$	$= 0.245\ \left(\tfrac{49}{200}\right)\,$	$1 / 0.245\ \left(\tfrac{200}{49}\right)\,$	$= 4.082\ \left(4 \tfrac{4}{49}\right)\,$
$4\,$	$4.082\ \left(4 \tfrac{4}{49}\right)- 4\,$	$= 0.082\ \left(\tfrac{4}{49}\right)\,$	$1 / 0.082\ \left(\tfrac{49}{4}\right)\,$	$= 12.250\ \left(12 \tfrac{1}{4}\right)\,$
$12\,$	$12.250\ \left(12 \tfrac{1}{4}\right)- 12\,$	$= 0.250\ \left(\tfrac{1}{4}\right)\,$	$1 / 0.250\ \left(\tfrac{4}{1}\right)\,$	$= 4.000\,$
$4\,$	$4.000 - 4\,$	$= 0.000\,$	STOP
ланцюговий дріб для числа 3,245 рівний [3; 4, 12, 4]
$3.245 = 3 + \cfrac{1}{4 + \cfrac{1}{12 + \cfrac{1}{4}}}$

Приклади розкладу

• $\pi=[3;7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,\cdots]$

якщо проте використовувати узагальнені ланцюгові дроби то отримаємо певні закономірності: $\pi=3+\cfrac{1^2}{6+\cfrac{3^2}{6+\cfrac{5^2}{6+\cfrac{7^2}{6+\cfrac{9^2}{6+\cfrac{11^2}{6+\cfrac{13^2}{6+\cfrac{15^2}{6+\ddots}}}}}}}} \ =\cfrac{4}{1+\cfrac{1^2}{3+\cfrac{2^2}{5+\cfrac{3^2}{7+\cfrac{4^2}{9+\cfrac{5^2}{11+\cfrac{6^2}{13+\cfrac{7^2}{15+\ddots}}}}}}}}$

• $e = \exp(1) = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, \dots] \,\!.$

Якщоn ціле число більше одиниці,

• $\exp(1/n) = [1; n-1, 1, 1, 3n-1, 1, 1, 5n-1, 1, 1, 7n-1, 1, 1, \dots] \,\!.$

Якщо також n парне:

• $\exp(2/n) = [1; (n-1)/2, 6n, (5n-1)/2, 1, 1, \dots, 3nk+(n-1)/2, 6n(2k+1), 3nk+(5n-1)/2, 1, 1, \dots ] \,\!$

при n = 1:

• $e^2 = \exp(2) = [7; 2, 1, 1, 3, 18, 5, 1, 1, 6, 30, 8, 1, 1, 9, 42, 11, 1, 1, \dots, 3k, 12k+6, 3k+2, 1, 1, \dots] \,\!.$

• $\tanh(1/n) = [0; n, 3n, 5n, 7n, 9n, 11n, 13n, 15n, 17n, 19n, \dots] \,\!$

якщо n додатнє число; також

• $\tan(1) = [1; 1, 1, 3, 1, 5, 1, 7, 1, 9, 1, 11, 1, 13, 1, 15, 1, \dots]\,\!$

якщо n > 1,

• $\tan(1/n) = [0; n-1, 1, 3n-2, 1, 5n-2, 1, 7n-2, 1, \dots]\,\!.$

Властивості

• Будь-яке раціональне число може бути представлене в виді скінченного ланцюгового дробу двома способами, більш довгий з яких завжди закінчується одиницею, а коротший відрізняється від нього тим, що останньої одиниці немає, а елемент перед одиницею на 1 більший. Наприклад:

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

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

Наприклад:

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

золотий поділ $\phi = [1;1,1,1,\dots]$

• Для інших — не квадратичних — алгебраїчних чисел характер розкладу не відомий.
• Для майже всіх дійсних чисел x середнє геометричне коефіцієнтів розкладу числа в ланцюговий дріб рівний константі Хітчіна (K ≈ 2.6854520010...)

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

• Парні наближені дроби утворюють зростаючу послідовність, а непарні  - спадну. Обидві послідовності збігаються до 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-1} - q_n p_{n-1} = (-1)^{n-1},$

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

Звідси випливає наступне твердження:

• наближений дріб $\frac{p_n}{q_n}$ є найкращим наближенням для $x$ серед всіх дробів, знаменник яких не перевищує $q_n$;

Застосування

• при розробці сонячного календаря необхідно знайти раціональне наближення для числа 365,2421988… За допомогою ланцюгових дробів одержується послідовність:

$\frac{1}{4}; \frac{7}{29}; \frac{8}{33}; \frac{31}{128}; \frac{132}{545} \cdots$

Перший з цих дробів є основою юліанського календаря.

• Доведення ірраціональності чисел. Наприклад, за допомогою ланцюгових дробів доведена ірраціональність дзета-функції Рімана $\zeta(3)$ числа пі.
• Алгоритми факторизації SQUFOF и CFRAC.
• Характеристика ортогональних многочленів
• Характеристика стабільних многочленів
• Алгоритм Ланцоша використовує ланцюгові дроби для обчислення власних значень великих розріджених матриць.

Література

• В. И. Арнольд Цепные дроби. — М.: МЦНМО, 2000. — Т. 14. — 40 с. — (Библиотека «Математическое просвещение»).
• А. А. Бухштаб Теория чисел. — Просвещение, 1966. — 384 с.
• И. М. Виноградов Основы теории чисел. — Гос. изд. технико-теоретической литературы, 1952. — 180 с.
• С. Н. Гладковский Анализ условно-периодических цепных дробей, ч. 1. — 2009. — 138 с.
• И. Я. Депман История арифметики. Пособие для учителей. — Просвещение, 1965. — С. 253—254.
• Г. Дэвенпорт Высшая Арифметика. — М.: Наука, 1965.
• С. В. Сизый Лекции по теории чисел. — Екатеринбург: Уральский государственный университет им. А. М. Горького, 1999.
• А. Я. Хинчин Цепные дроби. — М.: ГИФМЛ, 1960.