Цепная дробь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 14 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
== Определение ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 7: Строка 8:
 
}}
 
}}
  
−
Примеры:
+
== Цепные дроби для рациональных чисел ==
 +
{{Main|Связь цепных дробей и алгоритма Евклида}}
 +
Для рациональных чисел цепная дробь имеет конечный вид. Кроме того, последовательность <tex>a_i</tex> {{---}} это ровно та последовательность частных, которая получается при применении [[алгоритм Евклида|алгоритма Евклида]] к числителю и знаменателю дроби.
  
−
<tex> \frac{7}{5}=1+\frac{1}{2+\frac{1}{2}}=\langle 1, 2, 2 \rangle</tex>
+
== Цепные дроби как приближение к числу ==
 +
{{Main|Цепные дроби как приближение к числу|Сходимость цепных дробей}}
 +
Подходящие дроби можно рассматривать как последовательные приближения к некоторому вещественному числу. При любых значениях <tex>a_i</tex>, удовлетворяющих требованиям определения цепной дроби, последовательность подходящих дробей имеет предел. Кроме того, скорость сходимости можно оценить как <tex>|\alpha-\frac{P_i}{Q_i}| < \frac{1}{Q_i^2}</tex>.
  
−
<tex> \sqrt{2} = 1+\frac{1}{\sqrt{2}+1}=1+\frac{1}{2+\frac{1}{\sqrt{2}+1}}=\langle 1, 2, 2, \cdots \rangle</tex>
+
== Периодичность цепных дробей ==
 +
{{Main|Периодичность цепных дробей}}
 +
Цепная дробь [[квадратичная иррациональность|квадратичной иррациональности]] {{---}} периодична, а цепная дробь приведенной квадратичной иррациональности {{---}} чисто периодична.
  
−
Числитель и знаменатель цепной дроби можно записать в виде полиномов от переменных <tex>a_0, a_1, a_2,\cdots, a_n</tex>. При этом, поскольку числитель каждой дроби является знаменателем следующей, полиномы для числителей и знаменателей имеют одинаковый вид.
+
== Примеры разложения чисел в цепные дроби ==
−
Таким образом, цепная дробь <tex>\langle a_0, a_1, a_2,\cdots, a_n \rangle </tex> представима в виде <tex> \frac{[a_0, a_1, a_2,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]}</tex>, где <tex>[a_0, a_1, a_2,\cdots, a_n]</tex> {{---}} некоторый полином от
+
* <tex> \frac{7}{5}=1+\frac{1}{2+\frac{1}{2}}=\langle 1, 2, 2 \rangle</tex>
−
<tex>n+1</tex> переменной.
+
* <tex> \sqrt{2} = 1+\frac{1}{\sqrt{2}+1}=1+\frac{1}{2+\frac{1}{\sqrt{2}+1}}=\langle 1, 2, 2, \cdots \rangle</tex>
  
−
=== Свойства цепных дробей ===
+
== Свойства цепных дробей ==
 +
{{Main|Свойства цепных дробей}}
 +
Цепную дробь <tex>\langle a_0, a_1, a_2,\cdots, a_n \rangle</tex> можно записать в виде частного двух полиномов
 +
<tex> \frac{[a_0, a_1, a_2,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]}</tex>, где <tex>[a_0, a_1, a_2,\cdots, a_n]</tex> {{---}} некоторый полином от <tex>n+1</tex> переменной.
 +
 
 +
Эти полиномы удовлетворяют следующим свойствам:
 
* <tex>[a_0,\cdots, a_n]</tex> {{---}} полином от <tex>n+1</tex> переменной, состоящий из <tex>F_{n+1}</tex> мономов.
 
* <tex>[a_0,\cdots, a_n]</tex> {{---}} полином от <tex>n+1</tex> переменной, состоящий из <tex>F_{n+1}</tex> мономов.
 
* <tex>[a_0, a_1, a_2,\cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n]</tex>.
 
* <tex>[a_0, a_1, a_2,\cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n]</tex>.
 
* <tex>[a_0, a_1, a_2,\cdots, a_n] = [a_0, a_1,\cdots, a_{n - 1}]a_n + [a_0, a_1,\cdots, a_{n-2}]</tex>.
 
* <tex>[a_0, a_1, a_2,\cdots, a_n] = [a_0, a_1,\cdots, a_{n - 1}]a_n + [a_0, a_1,\cdots, a_{n-2}]</tex>.
−
* Для числителей и знаменателей <tex>n</tex>-ой подходящей дроби верны следующие формулы:
 
−
** <tex>P_n = P_{n-1}a_n + P_{n-2}</tex>
 
−
** <tex>Q_n = Q_{n-1}a_n + Q_{n-2}</tex>
 
 
* <tex>[a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] </tex>
 
* <tex>[a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] </tex>
−
 
+
Для числителей и знаменателей <tex>n</tex>-ой подходящей дроби верны следующие формулы:
−
=== Доказательства свойств ===
+
* <tex>P_n = P_{n-1}a_n + P_{n-2}</tex>
−
{{Лемма
+
* <tex>Q_n = Q_{n-1}a_n + Q_{n-2}</tex>
−
|id=lemma1
+
* <tex>P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}</tex>
−
|about=1
 
−
|statement=
 
−
<tex>[a_0, a_1, a_2,\cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n]</tex>.
 
−
|proof=
 
−
<tex> \frac{[a_0, a_1, a_2,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]} = a_0 + \frac{[a_2, a_3, a_4,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]} </tex>.
 
−
Следовательно <tex> [a_0, a_1, a_2,\cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n]</tex>.
 
−
}}
 
−
{{Лемма
 
−
|id=lemma2
 
−
|about=2
 
−
|statement=
 
−
<tex>[a_0,\cdots, a_n]</tex> {{---}} полином от <tex>n+1</tex> переменной, состоящий из <tex>F_{n+1}</tex> мономов.
 
−
|proof=
 
−
'''База'''. При <tex>n=0</tex>: <tex>[a_0] = a_0</tex> {{---}} полином от одной переменной с одним мономом. <tex>[a_0, a_1] = a_0 a_1 + 1</tex> {{---}} два монома.
 
−
'''Переход'''. Пусть верно, что в <tex>[a_0,\cdots, a_n]</tex> <tex>F_{n+1}</tex> монома. Докажем, что в <tex>[a_0,\cdots, a_{n+1}]</tex> <tex>F_{n+2}</tex> монома.
 
−
<tex>[a_0,\cdots, a_{n+1}] = a_0[a_1,\cdots, a_{n+1}] + [a_2,\cdots, a_{n+1}]</tex> В <tex>[a_2,\cdots, a_{n+1}]</tex> нет мономов, содержащих <tex> a_0 </tex>. Значит в <tex>[a_0,\cdots, a_{n+1}]</tex> <tex>F_{n+1}+F_n = F_{n+2}</tex> слагаемых.
 
−
}}
 
−
{{Теорема
 
−
|id=theorem1
 
−
|about=1
 
−
|statement=
 
−
<tex>[a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] </tex>
 
−
|proof=
 
−
База: <tex>[a_0] = a_0 = [a_0]</tex>
 
−
Пусть верно для всех <tex>m < n </tex>. Докажем для <tex>n</tex>.
 
−
 
 
−
<tex>[a_0, a_1, a_2, \cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n] = a_0(a_1[a_2, a_3, a_4,\cdots, a_n]+[a_3, a_4, a_5\cdots, a_n])+[a_2, a_3, a_4,\cdots, a_n]=(a_0a_1+1)[a_2, a_3, a_4,\cdots, a_n] + a_0[a_3, a_4, a_5\cdots, a_n] = [a_0, a_1][a_2, a_3, a_4,\cdots, a_n] + [a_0][a_3, a_4, a_5\cdots, a_n]</tex>
 
−
 
 
−
Обобщим последнюю формулу и докажем по индукции. Пусть верно :
 
−
<tex>[a_0, a_1, a_2, \cdots, a_n] = [a_0, \cdots, a_k][a_{k+1},\cdots, a_n]+[a_0,\cdots, a_{k-1}][a_{k+2}, \cdots, a_n]</tex>.
 
−
 
 
−
Докажем для больших <tex> k </tex> :
 
−
 
 
−
<tex> [a_0, \cdots, a_k][a_{k+1},\cdots, a_n]+[a_0,\cdots, a_{k-1}][a_{k+2}, \cdots, a_n] = [a_0, \cdots, a_k](a_{k+1}[a_{k+2}, \cdots, a_n]+[a_{k+3}, \cdots, a_n])+[a_0,\cdots, a_{k-1}][a_{k+2}, \cdots, a_n] = (a_{k+1}[a_0, \cdots, a_k] + [a_0,\cdots, a_{k-1}])[a_{k+2}, \cdots, a_n]+[a_0, \cdots, a_k][a_{k+3}, \cdots, a_n]</tex>.
 
−
 
 
−
Используя условие теоремы для <tex>k < n-1</tex> получаем :
 
−
 
 
−
<tex> a_{k+1}[a_0, \cdots, a_k] + [a_0,\cdots, a_{k-1}] = a_{k+1}[a_k, \cdots, a_0] + [a_{k-1}, \cdots, a_0] = [a_{k+1},\cdots, a_0] = [a_0, \cdots, a_{k+1}]</tex>
 
−
 
 
−
Следовательно получаем :
 
−
 
 
−
<tex>[a_0, a_1, a_2, \cdots, a_n] = [a_0, \cdots, a_{n-2}][a_{n-1}, a_n]+[a_0,\cdots, a_{n-3}][a_n] = [a_{n-2}, \cdots, a_0](a_{n-1}a_n + 1) + a_n[a_{n-3}, \cdots, a_0]=a_n[a_{n-1},\cdots, a_0] + [a_{n-2}, \cdots, a_0] = [a_n, \cdots, a_0]</tex>.
 
−
}}
 
−
{{Лемма
 
−
|id=lemma3
 
−
|about=3
 
−
|statement=
 
−
<tex>[a_0, a_1, a_2,\cdots, a_n] = [a_0, a_1,\cdots, a_{n - 1}]a_n + [a_0, a_1,\cdots, a_{n-2}, a_{n-1}]</tex>.
 
−
|proof=
 
−
Эта формула аналогична формуле из [[#lemma1|Леммы 1]], за исключением того, что <tex>a_n</tex> "отщепляются" с другого конца.
 
−
Для получения формулы достаточно скомбинировать результаты [[#lemma1|Леммы 1]] и [[#theorem1|Теоремы 1]].
 
−
}}
 
  
 
[[Категория: Теория чисел]]
 
[[Категория: Теория чисел]]

Текущая версия на 19:12, 4 сентября 2022

Определение

Определение:
Цепная дробь — это выражение вида

[math]\langle a_0, a_1, a_2, a_3,\cdots \rangle = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\ldots}}}\;[/math]
где [math]a_0[/math] есть целое число и все остальные [math]a_n[/math] натуральные числа.

Различают конечные и бесконечные цепные дроби. Любая конечная дробь [math]\langle a_0, a_1, a_2, a_3,\ldots, a_n \rangle[/math] представима в виде некоторой рациональной дроби [math]\frac{P_n}{Q_n}[/math], которую называют n-ой подходящей дробью.


Цепные дроби для рациональных чисел

Основная статья: Связь цепных дробей и алгоритма Евклида

Для рациональных чисел цепная дробь имеет конечный вид. Кроме того, последовательность [math]a_i[/math] — это ровно та последовательность частных, которая получается при применении алгоритма Евклида к числителю и знаменателю дроби.

Цепные дроби как приближение к числу

Основные статьи: Цепные дроби как приближение к числу, Сходимость цепных дробей

Подходящие дроби можно рассматривать как последовательные приближения к некоторому вещественному числу. При любых значениях [math]a_i[/math], удовлетворяющих требованиям определения цепной дроби, последовательность подходящих дробей имеет предел. Кроме того, скорость сходимости можно оценить как [math]|\alpha-\frac{P_i}{Q_i}| \lt \frac{1}{Q_i^2}[/math].

Периодичность цепных дробей

Основная статья: Периодичность цепных дробей

Цепная дробь квадратичной иррациональности — периодична, а цепная дробь приведенной квадратичной иррациональности — чисто периодична.

Примеры разложения чисел в цепные дроби

  • [math] \frac{7}{5}=1+\frac{1}{2+\frac{1}{2}}=\langle 1, 2, 2 \rangle[/math]
  • [math] \sqrt{2} = 1+\frac{1}{\sqrt{2}+1}=1+\frac{1}{2+\frac{1}{\sqrt{2}+1}}=\langle 1, 2, 2, \cdots \rangle[/math]

Свойства цепных дробей

Основная статья: Свойства цепных дробей

Цепную дробь [math]\langle a_0, a_1, a_2,\cdots, a_n \rangle[/math] можно записать в виде частного двух полиномов [math] \frac{[a_0, a_1, a_2,\cdots, a_n]}{[a_1, a_2, a_3,\cdots, a_n]}[/math], где [math][a_0, a_1, a_2,\cdots, a_n][/math] — некоторый полином от [math]n+1[/math] переменной.

Эти полиномы удовлетворяют следующим свойствам:

  • [math][a_0,\cdots, a_n][/math] — полином от [math]n+1[/math] переменной, состоящий из [math]F_{n+1}[/math] мономов.
  • [math][a_0, a_1, a_2,\cdots, a_n] = a_0[a_1, a_2, a_3,\cdots, a_n] + [a_2, a_3, a_4,\cdots, a_n][/math].
  • [math][a_0, a_1, a_2,\cdots, a_n] = [a_0, a_1,\cdots, a_{n - 1}]a_n + [a_0, a_1,\cdots, a_{n-2}][/math].
  • [math][a_0, a_1, \cdots, a_n] = [a_n, a_{n-1}, \cdots, a_0] [/math]

Для числителей и знаменателей [math]n[/math]-ой подходящей дроби верны следующие формулы:

  • [math]P_n = P_{n-1}a_n + P_{n-2}[/math]
  • [math]Q_n = Q_{n-1}a_n + Q_{n-2}[/math]
  • [math]P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n+1}[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Цепная_дробь&oldid=84589»