Цепная дробь

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

$[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 натуральные числа (то есть положительные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.

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

Любое вещественное число 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\}$ являются возрастающими.

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

pnqn - 1 - qnpn - 1 = ( - 1)n - 1,

(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}.$

Отсюда, в частности, следует:

• подходящая дробь $\frac{p_n}{q_n}$ является наилучшим приближением для x среди всех дробей, знаменатель которых не превосходит q_n;
• мера иррациональности любого иррационального числа не меньше 2.

Примеры

• Разложим число π=3,14159265… в непрерывную дробь и подсчитаем его подходящие дроби:

  3, 22/7, 333/106, 355/113, 103993/33102, …

Вторая дробь (22/7) — это известное архимедово приближение. Четвёртая (355/113) была впервые получена в Древнем Китае.

• В теории музыки требуется отыскать рациональное приближение для $\log_2 \frac {3}{2} \approx 0{,}585$. Третья подходящая дробь: 7/12 соответствует классической октаве из 12 полутонов.^[1]

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

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

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

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

Например:

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

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

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

e − 1 = [1;1;2;1;1;4;1;1;6;1;1;8;...;1;1;2n − 2;1;1;2n;...]

для числа

tg1 = [1;1;1;3;1;5;1;7;...;1;2n + 1;1;2n + 3;...]

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

π = [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,…]

• Теорема Гаусса — Кузмина: Почти для всех (кроме множества меры нуль) действительных чисел существует среднее геометрическое коэффициентов соответствующих им цепных дробей, и оно равно одному и тому же числу.

Приложения цепных дробей

Теория календаря

При разработке солнечного календаря необходимо найти приближение для числа дней в году, которое равно 365,2421988… Подсчитаем подходящие дроби для этого числа:

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

Первая дробь означает, что раз в 4 года надо добавлять лишний день; этот принцип лёг в основу юлианского календаря. При этом ошибка в 1 день накапливается за 128 лет. Второе значение (7/29) никогда не использовалось. Третья дробь (8/33), то есть 8 високосных лет за период в 33 года, была предложена Омаром Хайямом в XI веке и положила начало персидскому календарю, в котором ошибка в день накапливается за 4500 лет. Вариант 31/128 пропагандировал немецкий астроном Медлер (1864), однако большого интереса он не вызвал, так как существенных преимуществ перед григорианским не имел.

Решение сравнений первой степени

Рассмотрим сравнение: $ax \equiv b \pmod m$, где $a,\ b$ известны, причём можно считать, что a взаимно просто с m. Надо найти x.

Разложим $\frac{m}{a}$ в непрерывную дробь. Она будет конечной, и последняя подходящая дробь $\frac{p_n}{q_n}=\frac{m}{a}$. Подставим в формулу (1):

mq_{n − 1} − ap_{n − 1} = ( − 1)^{n − 1}

Отсюда вытекает:

$a p_{n-1} \equiv (-1)^n \pmod m$,  или:  $\ a (-1)^n p_{n-1} \equiv 1 \pmod m$

Вывод: класс вычетов $x \equiv (-1)^n p_{n-1} b \pmod m$  является решением исходного сравнения.

Другие приложения

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

Историческая справка

Античные математики умели представлять отношения несоизмеримых величин в виде цепочки последовательных подходящих отношений, получая эту цепочку с помощью алгоритма Евклида. По-видимому, именно таким путём Архимед получил приближение $\sqrt{3} \approx \frac {1351}{780}$ — это 12-я подходящая дробь для $\sqrt{3}$ или $\frac {1}{3}$ от 4-й подходящей дроби для $\sqrt{27}$.

В V веке индийский математик Ариабхата применял аналогичный «метод измельчения» для решения неопределённых уравнений первой и второй степени. С помощью этой же техники было, вероятно, получено известное приближение для числа π (355/113). В XVI веке Рафаэль Бомбелли извлекал с помощью цепных дробей квадратные корни (см. его алгоритм).

Начало современной теории цепных дробей положил в 1613 году Пьетро Антонио Катальди. Он отметил основное их свойство (положение между подходящими дробями) и ввёл обозначение, напоминающее современное. Позднее его теорию расширил Джон Валлис, который и предложил термин «непрерывная дробь». Эквивалентный термин «цепная дробь» появился в конце XVIII века.

Применялись эти дроби в первую очередь для рационального приближения вещественных чисел; например, Христиан Гюйгенс использовал их для проектирования зубчатых колёс своего планетария. Гюйгенс уже знал, что подходящие дроби всегда несократимы и что они представляют наилучшее рациональное приближение.

В XVIII веке теорию цепных дробей в общих чертах завершили Леонард Эйлер и Жозеф Луи Лагранж.

См. также

• Алгоритм Евклида
• Числа Фибоначчи

Ссылки

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

Примечания

1. ↑ См. Шилов Г. Е. Простая гамма. Устройство музыкальной шкалы. М.: Физматгиз, 1963. 20 с. Серия «Популярные лекции по математике», выпуск 37.