Непрерывная дробь

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

[ a 0 ; a 1 , a 2 , a 3 , ⋯ ] = a 0 + 1 a 1 + 1 a 2 + 1 a 3 + … {displaystyle [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 0 {displaystyle a_{0}} есть целое число, а все остальные a n {displaystyle a_{n}} — натуральные числа (положительные целые). При этом числа a 0 , a 1 , a 2 , a 3 , ⋯ {displaystyle a_{0},a_{1},a_{2},a_{3},cdots } называются неполными частными или элементами цепной дроби.

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

Главное (но далеко не единственное) назначение непрерывных дробей состоит в том, что они позволяют находить хорошие приближения вещественных чисел в виде обычных дробей. Непрерывные дроби широко используются в теории чисел и вычислительной математике, а их обобщения оказались чрезвычайно полезны в математическом анализе и других разделах математики. Используются также в физике, небесной механике, технике и других прикладных сферах деятельности.

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

Любое вещественное число x {displaystyle x} может быть представлено (конечной или бесконечной, периодической или непериодической) цепной дробью [ a 0 ; a 1 , a 2 , a 3 , ⋯ ] {displaystyle [a_{0};a_{1},a_{2},a_{3},cdots ]} , где

a 0 = ⌊ x ⌋ , x 0 = x − a 0 , {displaystyle a_{0}=lfloor x floor ,x_{0}=x-a_{0},} a 1 = ⌊ 1 x 0 ⌋ , x 1 = 1 x 0 − a 1 , {displaystyle a_{1}=leftlfloor {frac {1}{x_{0}}} ight floor ,x_{1}={frac {1}{x_{0}}}-a_{1},} … {displaystyle dots } a n = ⌊ 1 x n − 1 ⌋ , x n = 1 x n − 1 − a n , {displaystyle a_{n}=leftlfloor {frac {1}{x_{n-1}}} ight floor ,x_{n}={frac {1}{x_{n-1}}}-a_{n},} … {displaystyle dots }

где ⌊ x ⌋ {displaystyle lfloor x floor } обозначает целую часть числа x {displaystyle x} .

Для рационального числа x {displaystyle x} это разложение оборвётся по достижении нулевого x n {displaystyle x_{n}} для некоторого n {displaystyle n} . В этом случае x {displaystyle x} представляется конечной цепной дробью x = [ a 0 ; a 1 , ⋯ , a n ] {displaystyle x=[a_{0};a_{1},cdots ,a_{n}]} . Эффективным алгоритмом для преобразования обычной дроби в цепную является алгоритм Евклида. Представление рационального числа в виде непрерывной дроби неоднозначно: если приведённый здесь алгоритм даёт непрерывную дробь [ … , a n ] {displaystyle [dots ,a_{n}]} , то непрерывная дробь [ … , a n − 1 , 1 ] {displaystyle [dots ,a_{n}-1,1]} соответствует тому же самому числу.

Для иррационального x {displaystyle x} все величины x n {displaystyle x_{n}} будут ненулевыми и процесс разложения можно продолжать бесконечно. В этом случае x {displaystyle x} представляется бесконечной цепной дробью x = [ a 0 ; a 1 , a 2 , a 3 , ⋯ ] {displaystyle x=[a_{0};a_{1},a_{2},a_{3},cdots ]} . Если последовательность [ a 0 ; a 1 , a 2 , a 3 , ⋯ ] {displaystyle [a_{0};a_{1},a_{2},a_{3},cdots ]} состоит из бесконечно повторяющегося набора одних и тех же чисел (периода), то цепная дробь называется периодической. Число представляется бесконечной периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью, то есть иррациональным корнем квадратного уравнения с целыми коэффициентами.

Подходящие дроби

n-й подходящей дробью для цепной дроби x = [ a 0 ; a 1 , a 2 , a 3 , ⋯ ] {displaystyle x=[a_{0};a_{1},a_{2},a_{3},cdots ]} , называется конечная цепная дробь [ a 0 ; a 1 , ⋯ , a n ] {displaystyle [a_{0};a_{1},cdots ,a_{n}]} , значение которой есть некоторое рациональное число p n q n {displaystyle {frac {p_{n}}{q_{n}}}} . Подходящие дроби с чётными номерами образуют возрастающую последовательность, предел которой равен x {displaystyle x} . Аналогично, подходящие дроби с нечётными номерами образуют убывающую последовательность, предел которой также равен x {displaystyle x} . Таким образом, значение цепной дроби всегда находится между значениями соседних подходящих дробей.

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

p − 1 = 1 , p 0 = a 0 , p n = a n p n − 1 + p n − 2 ; {displaystyle p_{-1}=1,quad p_{0}=a_{0},quad p_{n}=a_{n}p_{n-1}+p_{n-2};} q − 1 = 0 , q 0 = 1 , q n = a n q n − 1 + q n − 2 . {displaystyle q_{-1}=0,quad q_{0}=1,quad q_{n}=a_{n}q_{n-1}+q_{n-2}.}

Последовательности как числителей { p n } {displaystyle left{p_{n} ight}} , так и знаменателей { q n } {displaystyle left{q_{n} ight}} подходящих дробей являются строго возрастающими.

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

Подходящие дроби, как видно из этого соотношения, всегда несократимы. Перепишем соотношение в виде

p n q n − p n − 1 q n − 1 = ( − 1 ) n − 1 q n − 1 q n . {displaystyle {frac {p_{n}}{q_{n}}}-{frac {p_{n-1}}{q_{n-1}}}={frac {(-1)^{n-1}}{q_{n-1}q_{n}}}.}

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

| x − p n − 1 q n − 1 | < 1 q n − 1 q n < 1 q n − 1 2 . {displaystyle left|x-{frac {p_{n-1}}{q_{n-1}}} ight|<{frac {1}{q_{n-1}q_{n}}}<{frac {1}{q_{n-1}^{2}}}.}

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

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

| x − p n q n | < 1 q n 2 . {displaystyle left|x-{frac {p_{n}}{q_{n}}} ight|<{frac {1}{q_{n}^{2}}}.}

Следствия.

Подходящая дробь p n q n {displaystyle {frac {p_{n}}{q_{n}}}} является наилучшим приближением исходного числа среди всех дробей, знаменатель которых не превосходит q n . {displaystyle q_{n}.}

Мера иррациональности любого иррационального числа не меньше 2.

Примеры

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

3 , 22 7 , 333 106 , 355 113 , 103993 33102 ,   . . . {displaystyle 3,{frac {22}{7}},{frac {333}{106}},{frac {355}{113}},{frac {103993}{33102}},~...}

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

Свойства золотого сечения

Ниже приведено разложение золотого сечения:

Φ = [ 1 ; 1 , 1 , 1 , … ] {displaystyle Phi =[1;1,1,1,dots ]}

Интересный результат, который следует из того, что выражение непрерывной дроби для Φ {displaystyle Phi } не использует чисел, больших 1, состоит в том, что Φ {displaystyle Phi } является одним из самых «плохо» приближаемых чисел. Точнее, теорема Гурвица утверждает, что любое действительное число r {displaystyle r} может быть приближено дробью m / n {displaystyle m/n} так, что

| r − m n | < 1 n 2 5 . {displaystyle left|r-{m over n} ight|<{1 over n^{2}{sqrt {5}}}.}

Хотя практически все действительные числа r {displaystyle r} имеют бесконечно много приближений m / n {displaystyle m/n} , которые находятся на значительно меньшем расстоянии от r {displaystyle r} , чем эта верхняя граница, приближения для Φ {displaystyle Phi } (то есть числа 5/3, 8/5, 13/8, 21/13 и т. д.) в пределе достигают этой границы, удерживая расстояние на почти точно 1 / ( n 2 5 ) {displaystyle 1/(n^{2}{sqrt {5}})} от Φ {displaystyle Phi } , тем самым никогда не создавая столь хорошие приближения как, к примеру, 355/113 для π. Можно показать, что этим свойством обладает любое действительное число вида ( a + b Φ ) / ( c + d Φ ) {displaystyle (a+bPhi )/(c+dPhi )} , где a , b , c {displaystyle a,b,c} и d {displaystyle d} являются целыми числами, причём a d − b c = ± 1 {displaystyle ad-bc=pm 1} ; а также, что все остальные действительные числа могут быть приближены намного лучше.

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

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

9 / 4 = [ 2 ; 3 , 1 ] = [ 2 ; 4 ] {displaystyle 9/4=[2;3,1]=[2;4];}

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

Например: 2 = [ 1 ; 2 , 2 , 2 , 2 , … ] {displaystyle {sqrt {2}}=[1;2,2,2,2,dots ]} золотое сечение Φ = [ 1 ; 1 , 1 , 1 , … ] {displaystyle Phi =[1;1,1,1,dots ]}

• Теорема Гаусса — Кузьмина: почти для всех (кроме множества меры нуль) вещественных чисел распределение элементов соответствующих им цепных дробей подчиняется статистике Гаусса — Кузьмина; в частности, существует среднее геометрическое всех элементов, и оно равно постоянной Хинчина.
• Теорема Маршалла Холла. Если в разложении числа x {displaystyle x} в непрерывную дробь, начиная со второго элемента не встречаются числа большие n {displaystyle n} , то говорят, что число x {displaystyle x} относится к классу F ( n ) {displaystyle F(n)} . Любое вещественное число может быть представлено в виде суммы двух чисел из класса F ( 4 ) {displaystyle F(4)} и в виде произведения двух чисел из класса F ( 4 ) . {displaystyle F(4).} В дальнейшем было показано, что любое вещественное число может быть представлено в виде суммы трёх чисел из класса F ( 3 ) {displaystyle F(3)} и в виде суммы четырёх чисел из класса F ( 2 ) {displaystyle F(2)} . Количество требуемых слагаемых в этой теореме не может быть уменьшено — для представления некоторых чисел указанным образом меньшего количества слагаемых недостаточно.

Открытые проблемы

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

e = [ 2 ; 1 , 2 , 1 , 1 , 4 , 1 , 1 , 6 , 1 , 1 , 8 , … , 1 , 1 , 2 n − 2 , 1 , 1 , 2 n , … ] , {displaystyle e=[2;1,2,1,1,4,1,1,6,1,1,8,ldots ,1,1,2n-2,1,1,2n,ldots ],}

а тангенс угла в 1 радиан — в виде

tg 1 = [ 1 ; 1 , 1 , 3 , 1 , 5 , 1 , 7 , … , 1 , 2 n + 1 , 1 , 2 n + 3 , … ] {displaystyle operatorname {tg} ,1=[1;1,1,3,1,5,1,7,ldots ,1,2n+1,1,2n+3,ldots ]}

У числа π {displaystyle 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 , … ] {displaystyle 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 ]}

Однако для обобщённой непрерывной дроби (см. ниже раздел Вариации и обобщения) прослеживается ясная закономерность.

Неизвестно, ограничены ли сверху неполные частные разложения таких чисел, как 2 3 {displaystyle {sqrt[{3}]{2}}} или π {displaystyle pi } .

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

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

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

1 4 ;   7 29 ;   8 33 ;   31 128 ;   132 545 ⋯ {displaystyle {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 лет (в григорианском — за 3280 лет). Очень точный вариант с четвёртой дробью (31/128, ошибка в сутки накапливается только за 100000 лет) пропагандировал немецкий астроном Иоганн фон Медлер (1864 год), однако большого интереса он не вызвал.

Теория музыки

В теории музыки при построении равномерно темперированного строя требуют, чтобы интервал октавы 2 : 1 {displaystyle 2:1} делился на n {displaystyle n} равных частей, и при этом интервал из m {displaystyle m} таких частей был по возможности близок к интервалу квинты 3 : 2 {displaystyle 3:2} . Эти требования приводят к задаче отыскания рационального приближения для log 2 ⁡ 3 ≈ 1 , 585 {displaystyle extstyle log _{2}3approx 1,585} . Третья подходящая дробь 5 / 3 {displaystyle 5/3} даёт равномерно темперированную пентатонику. Четвёртая подходящая дробь 12 / 7 {displaystyle 12/7} приводит к классическому делению октавы на 12 равных полутонов.

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

Рассмотрим сравнение: a x ≡ b ( mod m ) {displaystyle axequiv b{pmod {m}}} , где a ,   b {displaystyle a, b} известны, причём можно считать, что a {displaystyle a} взаимно просто с m {displaystyle m} . Надо найти x {displaystyle x} .

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

m q n − 1 − a p n − 1 = ( − 1 ) n − 1 {displaystyle mq_{n-1}-ap_{n-1}=(-1)^{n-1}}

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

a p n − 1 ≡ ( − 1 ) n ( mod m ) {displaystyle ap_{n-1}equiv (-1)^{n}{pmod {m}}} , или:   a ( − 1 ) n p n − 1 ≡ 1 ( mod m ) {displaystyle a(-1)^{n}p_{n-1}equiv 1{pmod {m}}}

Вывод: класс вычетов x ≡ ( − 1 ) n p n − 1 b ( mod m ) {displaystyle xequiv (-1)^{n}p_{n-1}b{pmod {m}}} является решением исходного сравнения.

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

• Доказательство иррациональности чисел. Например, с помощью цепных дробей была доказана иррациональность значения дзета-функции Римана ζ ( 3 ) {displaystyle zeta (3)} (константа Апери)
• Решение в целых числах уравнения Пелля: x 2 − n y 2 = 1 {displaystyle ;x^{2}-ny^{2}=1;} и других уравнений диофантова анализа
• Определение заведомо трансцендентного числа (см. теорема Лиувилля)
• Алгоритмы факторизации SQUFOF и CFRAC.
• Характеристика ортогональных многочленов
• Характеристика устойчивых многочленов

Вариации и обобщения

Ряд источников дают обобщённое определение непрерывной дроби, допуская для числителей в её звеньях не только 1, но и другие целые (в некоторых источниках допускаются даже комплексные) числа:

[ a 0 ; a 1 , a 2 , a 3 , ⋯ ] = a 0 + b 1 a 1 + b 2 a 2 + b 3 a 3 + … {displaystyle [a_{0};a_{1},a_{2},a_{3},cdots ]=a_{0}+{cfrac {b_{1}}{a_{1}+{cfrac {b_{2}}{a_{2}+{cfrac {b_{3}}{a_{3}+ldots }}}}}};}

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

Для обобщённых непрерывных дробей формулы Эйлера имеют вид:

p − 1 = 1 , p 0 = a 0 , p n = a n p n − 1 + b n p n − 2 ; {displaystyle p_{-1}=1,quad p_{0}=a_{0},quad p_{n}=a_{n}p_{n-1}+b_{n}p_{n-2};} q − 1 = 0 , q 0 = 1 , q n = a n q n − 1 + b n q n − 2 . {displaystyle q_{-1}=0,quad q_{0}=1,quad q_{n}=a_{n}q_{n-1}+b_{n}q_{n-2}.}

При этом:

p n q n − 1 − q n p n − 1 = ( − 1 ) n − 1 b 1 b 2 … b n {displaystyle p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}b_{1}b_{2}dots b_{n}}

Частный случай, в котором все b n = − 1 {displaystyle b_{n}=-1} , называется непрерывной дробью Хирцебруха. В отличие от обыкновенных непрерывных дробей, разложения рациональных чисел в непрерывную дробь Хирцебруха однозначны, однако не всякая конечная последовательность натуральных чисел может служить элементами непрерывной дроби Хирцебруха.

Выше было сказано, что разложение числа π {displaystyle pi } в классическую непрерывную дробь не содержит видимой закономерности. Для обобщённой же непрерывной дроби имеет место формула Браункера:

π 4 = 1 1 + 1 2 2 + 3 2 2 + 5 2 2 + 7 2 2 + 9 2 2 + ⋱ {displaystyle {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 }}}}}}}}}}}}}

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

b 1 a 1 + b 2 x a 2 + b 3 x a 3 + … {displaystyle {cfrac {b_{1}}{a_{1}+{cfrac {b_{2}x}{a_{2}+{cfrac {b_{3}x}{a_{3}+ldots }}}}}};}

Пример: получим разложение для функции f ( x ) = 1 − x 1 − 5 x + 6 x 2 . {displaystyle f(x)={frac {1-x}{1-5x+6x^{2}}}.}

f ( x ) = 1 1 − 4 x 1 − 2 x − 4 + 6 x {displaystyle f(x)={cfrac {1}{1-{cfrac {4x}{1-{cfrac {2x}{-4+6x}}}}}};}

Можно установить соответствие между непрерывными дробями и углами на решётках на плоскости. В связи с этим существуют различные варианты «многомерных непрерывных дробей».

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

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

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

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

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

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