Русская Википедия:Непрерывная дробь
Непрерывная дробь (или цепная дробь) — это конечное или бесконечное математическое выражение вида
- <math>[a_0; a_1, a_2, a_3,\cdots] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \ldots}}},</math>
где <math>a_0</math> есть целое число, а все остальные <math>a_n</math> — натуральные числа (положительные целые)[1]. При этом числа <math>a_0, a_1, a_2, a_3, \dots</math> называются неполными частными или элементами цепной дробиШаблон:Sfn.
Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально.
Главное (но далеко не единственное) назначение непрерывных дробей состоит в том, что они позволяют находить хорошие приближения вещественных чисел в виде обычных дробей. Непрерывные дроби широко используются в теории чисел и вычислительной математике, а их обобщения оказались чрезвычайно полезны в математическом анализе и других разделах математики. Используются также в физике, небесной механике, технике и других прикладных сферах деятельности.
Разложение в цепную дробь
Любое вещественное число <math>x</math> может быть представлено (конечной или бесконечной, периодической или непериодической) цепной дробью <math>[a_0; a_1, a_2, a_3,\ldots]</math>, где
- <math>a_0 = \lfloor x \rfloor,\quad x_0 = x - a_0,</math>
- <math>a_1 = \left\lfloor \frac{1}{x_0} \right\rfloor,\quad x_1 = \frac{1}{x_0} - a_1,</math>
- <math>\dots</math>
- <math>a_n = \left\lfloor \frac{1}{x_{n-1}} \right\rfloor,\quad x_n = \frac{1}{x_{n-1}} - a_n,</math>
- <math>\dots</math>
где <math>\lfloor x \rfloor</math> обозначает целую часть числа <math>x</math>.
Для рационального числа <math>x</math> это разложение оборвётся по достижении нулевого <math>x_n</math> для некоторого <math>n</math>. В этом случае <math>x</math> представляется конечной цепной дробью <math>x = [a_0; a_1, \ldots, a_n]</math>. Эффективным алгоритмом для преобразования обычной дроби в цепную является алгоритм Евклида. Представление рационального числа в виде непрерывной дроби неоднозначно: если приведённый здесь алгоритм даёт непрерывную дробь <math>[\dots, a_n]</math>, то непрерывная дробь <math>[\dots, a_n-1, 1]</math> соответствует тому же самому числу.
Для иррационального <math>x</math> все величины <math>x_n</math> будут ненулевыми и процесс разложения можно продолжать бесконечно. В этом случае <math>x</math> представляется бесконечной цепной дробью <math>x = [a_0; a_1, a_2, a_3,\ldots]</math>. Если последовательность <math>[a_0; a_1, a_2, a_3,\ldots] </math> состоит из бесконечно повторяющегося набора одних и тех же чисел (периода), то цепная дробь называется периодической. Число представляется бесконечной периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью, то есть иррациональным корнем квадратного уравнения с целыми коэффициентами.
Подходящие дроби
n-й («энной») подходящей дробью для цепной дроби <math>x = [a_0; a_1, a_2, a_3, \ldots]</math> называется конечная цепная дробь <math>[a_0; a_1, \ldots, a_n]</math>, значение которой есть некоторое рациональное число <math>p_n/q_n</math>. Подходящие дроби с чётными номерами образуют возрастающую последовательность, предел которой равен <math>x</math>. Аналогично, подходящие дроби с нечётными номерами образуют убывающую последовательность, предел которой также равен <math>x</math>. Таким образом, значение цепной дроби всегда находится между значениями соседних подходящих дробей.
Эйлер вывел рекуррентные формулы для вычисления числителей и знаменателей подходящих дробей:
- <math>p_{-1} = 1,\quad p_0 = a_0,\quad p_n = a_n p_{n-1} + p_{n-2};</math>
- <math>q_{-1} = 0,\quad q_0 = 1,\quad q_n = a_n q_{n-1} + q_{n-2}.</math>
Таким образом, величины <math>p_n</math> и <math>q_n</math> являются полиномами от <math>a_0, a_1, \dots, a_n</math>, называемыми континуантами:
- <math>p_n = K_{n+1}(a_0, a_1, \dots, a_n),</math>
- <math>q_n = K_n(a_1, a_2, \dots, a_n).</math>
Последовательности как числителей <math>\{p_n\}</math>, так и знаменателей <math>\{q_n\}</math> подходящих дробей являются строго возрастающими.
Числители и знаменатели соседних подходящих дробей связаны соотношением Шаблон:EF Подходящие дроби, как видно из этого соотношения, всегда несократимы. Перепишем соотношение в виде
- <math>\frac{p_n}{q_n} - \frac{p_{n-1}}{q_{n-1}} = \frac{(-1)^{n-1}}{q_{n-1} q_n}.</math>
Отсюда следуетШаблон:Sfn, что
- <math>\left|x - \frac{p_{n-1}}{q_{n-1}}\right| < \frac{1}{q_{n-1}q_n} < \frac{1}{q_{n-1}^2}.</math>
Приближение вещественных чисел рациональными
Цепные дроби позволяют эффективно находить хорошие рациональные приближения вещественных чисел. А именно, если вещественное число <math>x</math> разложить в цепную дробь, то её подходящие дроби будут удовлетворять неравенству
- <math>\left|x - \frac{p_n}{q_n}\right| < \frac{1}{q_n^2}.</math>
СледствияШаблон:Sfn:
- Подходящая дробь <math>p_n/q_n</math> является наилучшим приближением исходного числа среди всех дробей, знаменатель которых не превосходит <math>q_n.</math>
- Мера иррациональности любого иррационального числа не меньше 2.
Примеры
Разложим число <math>\pi = 3{,}14159265\dots</math> в непрерывную дробь и подсчитаем его подходящие дроби:
- <math>3,\ \frac{22}{7},\ \frac{333}{106},\ \frac{355}{113},\ \frac{103993}{33102},\ \dots</math>
Вторая подходящая дробь <math>22/7</math> — это известное архимедово приближение. Четвёртая подходящая дробь <math>355/113</math> была впервые получена в Древнем Китае.
Свойства золотого сечения
Ниже приведено разложение золотого сечения:
- <math>\Phi = [1; 1, 1, 1, \dots].</math>
Интересный результат, который следует из того, что выражение непрерывной дроби для <math>\Phi</math> не использует чисел, больших 1, состоит в том, что <math>\Phi</math> является одним из самых «плохо» приближаемых чисел. Точнее, теорема Гурвица[2] утверждает, что любое действительное число <math>r</math> может быть приближено дробью <math>m/n</math> так, что
- <math>\left|r - \frac{m}{n}\right| < \frac{1}{n^2 \sqrt 5}.</math>
Хотя практически все действительные числа <math>r</math> имеют бесконечно много приближений <math>m/n</math>, которые находятся на значительно меньшем расстоянии от <math>r</math>, чем эта верхняя граница, приближения для <math>\Phi</math> (то есть чи́сла 5/3, 8/5, 13/8, 21/13 и т. д.) в пределе достигают этой границыШаблон:Sfn, удерживая расстояние на почти точно <math>1 / (n^2 \sqrt 5)</math> от <math>\Phi</math>, тем самым никогда не создавая столь хорошие приближения как, к примеру, 355/113 для π. Можно показать, что этим свойством обладает любое действительное число вида <math>(a + b\Phi)/(c + d\Phi)</math>, где <math>a, b, c</math> и <math>d</math> являются целыми числами, причём <math>ad - bc = \pm 1 </math>; а также, что все остальные действительные числа могут быть приближены намного лучше.
Свойства и примеры
- Любое рациональное число может быть представлено в виде конечной цепной дроби двумя способами, например:
- <math>9/4 = [2; 3, 1] = [2; 4].</math>
- Теорема Лагранжа: Число представляется в виде бесконечной периодической цепной дроби тогда и только тогда, когда оно является иррациональным решением квадратного уравнения с целыми коэффициентами.
- Например:
- <math>\sqrt{2} = [1; 2, 2, 2, 2, \dots],</math>
- <math>\sqrt{42} = [6; 2, 12, 2, 12, 2, 12 \dots],</math>
- золотое сечение <math>\Phi = [1; 1, 1, 1, \dots].</math>
- Теорема Гаусса — Кузьмина: почти для всех (кроме множества меры нуль) вещественных чисел распределение элементов соответствующих им цепных дробей подчиняется статистике Гаусса — Кузьмина; в частности, существует среднее геометрическое всех элементов, и оно равно постоянной Хинчина.
- Теорема Маршалла Холла. Если в разложении числа <math>x</math> в непрерывную дробь, начиная со второго элемента не встречаются числа большие <math>n</math>, то говорят, что число <math>x</math> относится к классу <math>F(n)</math>. Любое вещественное число может быть представлено в виде суммы двух чисел из класса <math>F(4)</math> и в виде произведения двух чисел из класса <math>F(4).</math>[3] В дальнейшем было показано, что любое вещественное число может быть представлено в виде суммы трёх чисел из класса <math>F(3)</math> и в виде суммы четырёх чисел из класса <math>F(2)</math>. Количество требуемых слагаемых в этой теореме не может быть уменьшено — для представления некоторых чисел указанным образом меньшего количества слагаемых недостаточно[4][5].
Открытые проблемы
Предпринимались попытки найти закономерности в разложениях в непрерывную дробь кубических иррациональностейШаблон:Sfn, а также других алгебраических чисел степени, большей 2, и трансцендентных чисел[6]. Для некоторых трансцендентных чисел можно найти простую закономерность. Например, основание натурального логарифма представимо в виде[7]
- <math>e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots, 1, 1, 2n - 2, 1, 1, 2n, \ldots],</math>
а тангенс угла в 1 радиан — в виде[8]
- <math>\operatorname{tg} 1 = [1; 1, 1, 3, 1, 5, 1, 7, \ldots, 1, 2n + 1, 1, 2n + 3, \ldots].</math>
У числа <math>\pi</math> простой закономерности не видно[9]:
- <math>\pi = [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, \dots]</math>
Однако для обобщённой непрерывной дроби (см. ниже раздел Вариации и обобщения) прослеживается ясная закономерность.
Неизвестно, ограничены ли сверху неполные частные разложения таких чисел, как <math>\sqrt[3]{2}</math> или <math>\pi</math>[6][10].
Приложения цепных дробей
Теория календаря
При разработке солнечного календаря необходимо найти рациональное приближение для числа дней в году, которое равно 365,2421988… Подсчитаем подходящие дроби для дробной части этого числа:
- <math>\frac{1}{4};\ \frac{7}{29};\ \frac{8}{33};\ \frac{31}{128};\ \frac{132}{545} \cdots</math>
Первая дробь означает, что раз в 4 года надо добавлять лишний день; этот принцип лёг в основу юлианского календаря. При этом ошибка в 1 день накапливается за 128 лет. Второе значение (7/29) никогда не использовалось, поскольку оно мало отличается от следующего, гораздо более точного. Третья дробь (8/33), то есть 8 високосных лет за период в 33 года, была предложена Омаром Хайямом в XI веке и положила начало персидскому календарю, в котором ошибка в день накапливается за 4500 лет (в григорианском — за 3280 лет). Очень точный вариант с четвёртой дробью (31/128, ошибка в сутки накапливается только за 100000 лет[11]) пропагандировал немецкий астроном Иоганн фон Медлер (1864 год), однако большого интереса он не вызвал.
Теория музыки
В теории музыки при построении равномерно темперированного строя требуют, чтобы интервал октавы <math>2:1</math> делился на <math>n</math> равных частей, и при этом интервал из <math>m</math> таких частей был по возможности близок к интервалу квинты <math>3:2</math>. Эти требования приводят к задаче отыскания рационального приближения для <math>\log_2 1{,}5 \approx 0{,}585</math>. Третья подходящая дробь <math>3/5</math> даёт равномерно темперированную пентатонику. Четвёртая подходящая дробь <math>7/12</math> приводит к классическому делению октавы на 12 равных полутонов[12].
Решение сравнений первой степени
Рассмотрим сравнение: <math>ax \equiv b \pmod m</math>, где <math>a,\ b</math> известны, причём можно считать, что <math>a</math> взаимно просто с <math>m</math>. Надо найти <math>x</math>.
Разложим <math>\frac{m}{a}</math> в непрерывную дробь. Она будет конечной, и последняя подходящая дробь <math>\frac{p_n}{q_n} = \frac{m}{a}</math>. Подставим в формулу (1):
- <math>m q_{n-1} - a p_{n-1} = (-1)^{n-1}.</math>
Отсюда вытекает:
- <math>a p_{n-1} \equiv (-1)^n \pmod m,</math>
или
- <math>\ a (-1)^n p_{n-1} \equiv 1 \pmod m.</math>
Вывод: класс вычетов <math>x \equiv (-1)^n p_{n-1} b \pmod m</math> является решением исходного сравнения.
Другие приложения
- Доказательство иррациональности чисел. Например, с помощью цепных дробей была доказана иррациональность значения дзета-функции Римана <math>\zeta(3)</math> (константа Апери)
- Решение в целых числах уравнения Пелля[13]: <math>\;x^2-n y^2=1\;</math> и других уравнений диофантова анализа
- Определение заведомо трансцендентного числа (см. теорема Лиувилля)
- Алгоритмы факторизации SQUFOF и CFRAC.
- Характеристика ортогональных многочленов
- Характеристика устойчивых многочленов
Вариации и обобщения
Ряд источников дают обобщённое определение непрерывной дроби, допуская для числителей в её звеньях не только 1, но и другие целые (в некоторых источниках допускаются даже комплексные) числа[1]:
- <math>[a_0; a_1, a_2, a_3, \dots] = a_0 + \cfrac{b_1}{a_1 + \cfrac{b_2}{a_2 + \cfrac{b_3}{a_3 + \ldots}}}.</math>
Это обобщение повышает гибкость теории, но имеет два недостатка: разложение вещественного числа в непрерывную дробь становится неоднозначным и, кроме того, существование предела подходящих дробей уже не гарантировано — предел может быть бесконечен или вообще отсутствовать.
Для обобщённых непрерывных дробей формулы Эйлера имеют видШаблон:Sfn:
- <math>p_{-1} = 1,\quad p_0 = a_0,\quad p_n = a_n p_{n-1} + b_n p_{n-2};</math>
- <math>q_{-1} = 0,\quad q_0 = 1,\quad q_n = a_n q_{n-1} + b_n q_{n-2}.</math>
При этом
- <math>p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}b_1 b_2\dots b_n.</math>
Частный случай, в котором все <math>b_n = -1</math>, называется непрерывной дробью Хирцебруха[14].
Выше было сказано, что разложение числа <math>\pi</math> в классическую непрерывную дробь не содержит видимой закономерности. Для обобщённой же непрерывной дроби имеет место формула Браункера[15]:
- <math>
\frac \pi 4 = \cfrac{1}{1 + \cfrac{1^2}{2 + \cfrac{3^2}{2 + \cfrac{5^2}{2 + \cfrac{7^2}{2 + \cfrac{9^2}{2 + \ddots}}}}}} </math>
Другое направление обобщения состоит в построении и применении аппарата непрерывных дробей не для чисел, а для многочленов — используется тот факт, что делимость многочленов по своим свойствам близка к делимости целых чисел[16]. Всякий многочлен или дробно-рациональная функция может быть разложена в непрерывную дробьШаблон:Sfn:
- <math>\cfrac{b_1}{a_1 + \cfrac{b_2 x}{a_2 + \cfrac{b_3 x}{a_3 + \ldots}}}.</math>
Пример: получим разложение для функции <math>f(x) = \frac{1 - x}{1 - 5x + 6x^2}</math>:
- <math>f(x) = \cfrac{1}{1 - \cfrac{4 x}{1 - \cfrac{2 x}{-4 + 6x}}}.</math>
Можно установить соответствие между непрерывными дробями и углами на решётках на плоскости. В связи с этим существуют различные варианты «многомерных непрерывных дробей»Шаблон:Sfn.
Историческая справка
Античные математики умели представлять отношения несоизмеримых величин в виде цепочки последовательных подходящих отношений, получая эту цепочку с помощью алгоритма Евклида. По-видимому, именно таким путём Архимед получил приближение <math>\sqrt{3} \approx \frac {1351}{780}</math> — это 12-я подходящая дробь для <math>\sqrt{3}</math> или одна треть от 4-й подходящей дроби для <math>\sqrt{27}</math>.
В V веке индийский математик Ариабхата применял аналогичный «метод измельчения» для решения неопределённых уравнений первой и второй степени. С помощью этой же техники было, вероятно, получено известное приближение для числа <math>\pi</math> (355/113). В XVI веке Рафаэль Бомбелли извлекал с помощью цепных дробей квадратные корни (см. его алгоритм).
Начало современной теории цепных дробей положил в 1613 году Пьетро Антонио Катальди. Он отметил основное их свойство (положение между подходящими дробями) и ввёл обозначение, напоминающее современное. Позднее его теорию расширил Джон Валлис, который и предложил термин «непрерывная дробь». Эквивалентный термин «цепная дробь» появился в конце XVIII века.
Применялись эти дроби в первую очередь для рационального приближения вещественных чисел; например, Христиан Гюйгенс использовал их для проектирования зубчатых колёс своего планетария. Гюйгенс уже знал, что подходящие дроби всегда несократимы и что они представляют наилучшее рациональное приближение для исходного числа.
В XVIII веке теорию цепных дробей в общих чертах завершили Леонард Эйлер и Жозеф Луи Лагранж.
См. также
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Хованский А. Н. Приложение цепных дробей и их обобщений к вопросам приближенного анализа. — М.: Гостехиздат, 1956. — 204 с.
- Brezinski C. History of continued fractions and Padé approximants. NY: Springer, 1980.
- Шаблон:Публикация
- Lorentzen, Lisa; Waadeland, Haakon (1992). Continued fractions with applications (engelsk). North-Holland Elsevier Science Publishers. ISBN 0444892656.
- ↑ 1,0 1,1 Шаблон:Книга
- ↑ Шаблон:Книга
- ↑ M. Hall, On the sum and product of continued fractions, Annals of Math. 48 (1947) 966—993.
- ↑ B. Diviš, On sums of continued fractions, Acta Arith. 22 (1973) 157—173.
- ↑ T. W. Cusick and R. A. Lee, Sums of sets of continued fractions, Proc. Amer. Math. Soc. 30 (1971) 241—246.
- ↑ 6,0 6,1 Шаблон:Статья
- ↑ Шаблон:OEIS: разложение Шаблон:Mvar в непрерывную дробь.
- ↑ Шаблон:OEIS: разложение <math>\operatorname{tg}\,1</math> в непрерывную дробь.
- ↑ Шаблон:OEIS: разложение <math>\pi</math> в непрерывную дробь.
- ↑ Шаблон:OEIS: разложение <math>\sqrt[3]{2}</math> в непрерывную дробь.
- ↑ На самом деле из-за постепенного замедления вращения Земли, и, соответственно, постепенного уменьшения числа суток в году, подобный календарь накопил бы фактическую ошибку в одни сутки уже через 4000 лет.
- ↑ Шаблон:Книга
- ↑ Бугаенко В. О. Уравнения Пелля Шаблон:Wayback, М.:МЦНМО, 2001. ISBN 5-900916-96-0.
- ↑ Шаблон:Cite web
- ↑ John Wallis, Arithmetica Infinitorum (Oxford, England: Leon Lichfield, 1656), page 182. Шаблон:Wayback. Brouncker expressed, as a continued fraction, the ratio of the area of a circle to the area of the circumscribed square (i.e., 4/π). The continued fraction appears at the top of page 182 (roughly) as: ☐ = 1 1/2 9/2 25/2 49/2 81/2 &c, where the square denotes the ratio that is sought. (Note: On the preceding page, Wallis names Brouncker as: "Dom. Guliel. Vicecon, & Barone Brouncher" (Lord William Viscount and Baron Brouncker).)
- ↑ Шаблон:Книга