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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(не показано 6 промежуточных версий 2 участников)
Строка 1: Строка 1:
{{Требует доработки
+
[[Цепная дробь|Цепные дроби]] позволяют находить рациональные приближения вещественных чисел. Если действительное иррациональное число <tex>\alpha</tex> разложить в цепную дробь, то точность <tex>n</tex>-ой подходящей дроби будет соответствовать следующему неравенству:
|item1=(Исправлено. Создана отдельная статья)Необходимо добавить теоремы о том, что для любого вещественного числа можно построить цепную дробь, подходящие дроби которой стремятся к этому числу и теорему о том, что для любых <tex>a_i</tex> (нулевое целое, остальные натуральные) подходящие дроби имеют предел.
+
:<tex>|\alpha-\frac{P_i}{Q_i}| < \frac{1}{Q_i \cdot Q_{i+1}} < \frac{1}{Q_i^2}</tex>.
 +
{{Лемма
 +
|id=lm0
 +
|about=0
 +
|statement=
 +
<tex>|\alpha-\frac{P_i}{Q_i}| < \frac{1}{Q_i \cdot Q_{i+1}} < \frac{1}{Q_i^2}</tex>, где <tex>\frac{P_i}{Q_i}</tex> подходящие дроби к <tex>\alpha</tex>.
 +
|proof=
 +
Две последующие подходящие дроби будут лежать по разные стороны от <tex>\alpha</tex>. Значит <tex>~|\alpha-\frac{P_i}{Q_i}|<~|\frac{P_{i+1}}{Q_{i+1}}-\frac{P_i}{Q_i}|</tex>. По [[Свойства_цепных_дробей|свойствам цепных]] дробей <tex>~|\frac{P_{i+1}}{Q_{i+1}}-\frac{P_i}{Q_i}|=\frac{~|(-1)^n|}{Q_iQ_{i+1}}</tex>. Откуда и следует условие теоремы.
 
}}
 
}}
 
[[Цепная дробь|Цепные дроби]] позволяют находить рациональные приближения вещественных чисел. Если действительное иррациональное число <tex>\alpha</tex> разложить в цепную дробь, то точность n-ой подходящей дроби будет соответствовать следующему неравенству:
 
<tex>|\alpha-\frac{P_i}{Q_i}| < \frac{1}{Q_i \cdot Q_{i+1}} < \frac{1}{Q_i^2}</tex>.
 
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
Строка 18: Строка 22:
 
|about=2
 
|about=2
 
|statement=
 
|statement=
Для любого иррационального числа <tex>\alpha</tex> существует бесконечное число дробей <tex>\frac{P}{Q}</tex> таких, что <tex>~|\alpha-\frac{P}{Q}|<\frac{1}{\sqrt{5}Q^2}</tex>
+
Для любого иррационального числа <tex>\alpha</tex> существует бесконечное число дробей <tex>\frac{P}{Q}</tex> таких, что <tex>~|\alpha-\frac{P}{Q}|<\frac{1}{\sqrt{5}Q^2}</tex>.
 
|proof=
 
|proof=
 
Рассмотрим три последующие подходящие дроби к <tex>\alpha : \frac{P_k}{Q_k}, \frac{P_{k+1}}{Q_{k+1}} </tex> и <tex> \frac{P_{k+2}}{Q_{k+2}}</tex>. Пусть ни одна из них не удовлетворяет условию теоремы. Тогда имеем: <tex>~|\alpha-\frac{P_k}{Q_k}|\geqslant\frac{1}{\sqrt{5}Q_k^2}, ~|\alpha-\frac{P_{k+1}}{Q_{k+1}}|\geqslant\frac{1}{\sqrt{5}Q_{k+1}^2}, ~|\alpha-\frac{P_{k+2}}{Q_{k+2}}|\geqslant\frac{1}{\sqrt{5}Q_{k+2}^2}</tex>.
 
Рассмотрим три последующие подходящие дроби к <tex>\alpha : \frac{P_k}{Q_k}, \frac{P_{k+1}}{Q_{k+1}} </tex> и <tex> \frac{P_{k+2}}{Q_{k+2}}</tex>. Пусть ни одна из них не удовлетворяет условию теоремы. Тогда имеем: <tex>~|\alpha-\frac{P_k}{Q_k}|\geqslant\frac{1}{\sqrt{5}Q_k^2}, ~|\alpha-\frac{P_{k+1}}{Q_{k+1}}|\geqslant\frac{1}{\sqrt{5}Q_{k+1}^2}, ~|\alpha-\frac{P_{k+2}}{Q_{k+2}}|\geqslant\frac{1}{\sqrt{5}Q_{k+2}^2}</tex>.
Строка 34: Строка 38:
 
|about=1
 
|about=1
 
|statement=
 
|statement=
Любую конечную цепную дробь <tex><a_0, a_1, a_2,\cdots, a_n></tex> с чётным(нечётным) числом подходящих дробей можно представить в виде эквивалентной конечной цепной дроби с нечётным(чётным) числом подходящих дробей.
+
Любую конечную цепную дробь <tex>\langle a_0, a_1, a_2,\cdots, a_n \rangle</tex> с чётным(нечётным) числом подходящих дробей можно представить в виде эквивалентной конечной цепной дроби с нечётным(чётным) числом подходящих дробей.
 
|proof=
 
|proof=
Если <tex>a_n \geqslant 2</tex> : <tex><a_0, a_1, a_2,\cdots,a_n> = <a_0, a_1, a_2,\cdots,a_n-1,1></tex>. Если <tex>a_n = 1</tex> : <tex><a_0, a_1, a_2,\cdots,a_{n-1}, 1> = <a_0, a_1, a_2,\cdots,a_{n-1} + 1></tex>.
+
Если <tex>a_n \geqslant 2</tex> : <tex>\langle a_0, a_1, a_2,\cdots,a_n \rangle = \langle a_0, a_1, a_2,\cdots,a_n-1,1 \rangle</tex>. Если <tex>a_n = 1</tex> : <tex>\langle a_0, a_1, a_2,\cdots,a_{n-1}, 1\rangle = \langle a_0, a_1, a_2,\cdots,a_{n-1} + 1 \rangle</tex>.
 
}}
 
}}
 
{{Лемма
 
{{Лемма
Строка 42: Строка 46:
 
|about=2
 
|about=2
 
|statement=
 
|statement=
Если <tex>x = \frac{P\zeta+R}{Q\zeta+S}</tex>, где <tex>\zeta > 1, P, Q, R, S</tex> удовлетворяют <tex>Q>S>0</tex> и <tex>PS-QR= +- 1</tex>, то <tex>\frac{R}{S}, \frac{P}{Q} </tex> - n-1-ая и n-ая подходящие дроби для <tex>x</tex>.
+
Если <tex>x = \frac{P\zeta+R}{Q\zeta+S}</tex>, где <tex>\zeta > 1, P, Q, R, S</tex> удовлетворяют <tex>Q>S>0</tex> и <tex>PS-QR= \pm 1</tex>, то <tex>\frac{R}{S}, \frac{P}{Q} </tex> - n-1-ая и n-ая подходящие дроби для <tex>x</tex>.
 
|proof=
 
|proof=
Разложим <tex>\frac{P}{Q}</tex> в цепную дробь<tex><a_0, a_1, a_2, \dots, a_n> = \frac{P_n}{Q_n}</tex>.
+
Разложим <tex>\frac{P}{Q}</tex> в цепную дробь<tex>\langle a_0, a_1, a_2, \dots, a_n \rangle = \frac{P_n}{Q_n}</tex>.
 
По [[#lm1|лемме 1]] мы можем задать чётное либо нечётное <tex>n : PS-QR=(-1)^{n-1}</tex>
 
По [[#lm1|лемме 1]] мы можем задать чётное либо нечётное <tex>n : PS-QR=(-1)^{n-1}</tex>
 
<tex>P_nS-Q_nR=(-1)^{n-1}=P_nQ_{n-1}-P_{n-1}Q_n</tex> следовательно <tex>P_n(S-Q_{n-1})=Q_n(R-P_{n-1})</tex>. Так как <tex>P_n</tex> и <tex> Q_n</tex> взаимно просты, то <tex>(S-Q_{n-1})\vdots Q_n </tex>. Но <tex>Q_n = Q > S</tex> следовательно <tex> Q_n > S-Q_{n-1}</tex>, что возможно только если <tex>S=Q_{n-1}</tex> аналогично <tex>R=P_{n-1}</tex>. Что и требовалось доказать.
 
<tex>P_nS-Q_nR=(-1)^{n-1}=P_nQ_{n-1}-P_{n-1}Q_n</tex> следовательно <tex>P_n(S-Q_{n-1})=Q_n(R-P_{n-1})</tex>. Так как <tex>P_n</tex> и <tex> Q_n</tex> взаимно просты, то <tex>(S-Q_{n-1})\vdots Q_n </tex>. Но <tex>Q_n = Q > S</tex> следовательно <tex> Q_n > S-Q_{n-1}</tex>, что возможно только если <tex>S=Q_{n-1}</tex> аналогично <tex>R=P_{n-1}</tex>. Что и требовалось доказать.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
 +
|id=contFracCrit
 
|about=3
 
|about=3
 
|statement=
 
|statement=
Если некоторая дробь <tex>\frac{P}{Q}</tex> удовлетворяет условию <tex>~|\alpha - \frac{P}{Q}|<\frac{1}{2Q^2}</tex>, то она - подходящая дробь для <tex> \alpha </tex>.
+
Если некоторая дробь <tex>\frac{P}{Q}</tex> удовлетворяет условию <tex>~|\alpha - \frac{P}{Q}|<\frac{1}{2Q^2}</tex>, то она {{---}} подходящая дробь для <tex> \alpha </tex>.
 
|proof=
 
|proof=
 
Пусть для дроби <tex>\frac{P}{Q}</tex> выполняется условие теоремы, тогда <tex>\frac{P}{Q}-\alpha=\frac{\epsilon\theta}{Q^2}</tex>, где <tex>~|\epsilon| = 1</tex>, <tex>0<\theta<\frac{1}{2}</tex>. Дробь <tex>\frac{P}{Q}</tex> можно представить в виде конечной цепной дроби <tex>\langle a_0, \cdots, a_n \rangle </tex>. В силу [[#lm1|леммы 1]] мы можем сделать <tex> n</tex> чётным или нечётным. Пусть <tex> n </tex> такое, что <tex>\epsilon = (-1)^{n-1}</tex>.
 
Пусть для дроби <tex>\frac{P}{Q}</tex> выполняется условие теоремы, тогда <tex>\frac{P}{Q}-\alpha=\frac{\epsilon\theta}{Q^2}</tex>, где <tex>~|\epsilon| = 1</tex>, <tex>0<\theta<\frac{1}{2}</tex>. Дробь <tex>\frac{P}{Q}</tex> можно представить в виде конечной цепной дроби <tex>\langle a_0, \cdots, a_n \rangle </tex>. В силу [[#lm1|леммы 1]] мы можем сделать <tex> n</tex> чётным или нечётным. Пусть <tex> n </tex> такое, что <tex>\epsilon = (-1)^{n-1}</tex>.

Версия 23:54, 13 сентября 2010

Цепные дроби позволяют находить рациональные приближения вещественных чисел. Если действительное иррациональное число [math]\alpha[/math] разложить в цепную дробь, то точность [math]n[/math]-ой подходящей дроби будет соответствовать следующему неравенству:

[math]|\alpha-\frac{P_i}{Q_i}| \lt \frac{1}{Q_i \cdot Q_{i+1}} \lt \frac{1}{Q_i^2}[/math].
Лемма (0):
[math]|\alpha-\frac{P_i}{Q_i}| \lt \frac{1}{Q_i \cdot Q_{i+1}} \lt \frac{1}{Q_i^2}[/math], где [math]\frac{P_i}{Q_i}[/math] подходящие дроби к [math]\alpha[/math].
Доказательство:
[math]\triangleright[/math]
Две последующие подходящие дроби будут лежать по разные стороны от [math]\alpha[/math]. Значит [math]~|\alpha-\frac{P_i}{Q_i}|\lt ~|\frac{P_{i+1}}{Q_{i+1}}-\frac{P_i}{Q_i}|[/math]. По свойствам цепных дробей [math]~|\frac{P_{i+1}}{Q_{i+1}}-\frac{P_i}{Q_i}|=\frac{~|(-1)^n|}{Q_iQ_{i+1}}[/math]. Откуда и следует условие теоремы.
[math]\triangleleft[/math]
Теорема (1):
Для любого иррационального числа [math]\alpha[/math] существует бесконечное число дробей [math]\frac{P}{Q}[/math] таких, что [math]~|\alpha-\frac{P}{Q}|\lt \frac{1}{2Q^2}[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим две последующие подходящие дроби к [math]\alpha : \frac{P_k}{Q_k}[/math] и [math] \frac{P_{k+1}}{Q_{k+1}}[/math]. Пусть ни одна из них не удовлетворяет условию теоремы. Тогда имеем: [math]|\alpha-\frac{P_k}{Q_k}|\geqslant\frac{1}{2Q_k^2}, |\alpha-\frac{P_{k+1}}{Q_{k+1}}|\geqslant\frac{1}{2Q_{k+1}^2}[/math]. Отсюда [math]|\alpha-\frac{P_k}{Q_k}|+|\alpha-\frac{P_{k+1}}{Q_{k+1}}|\geqslant\frac{1}{2Q_k^2}+\frac{1}{2Q_{k+1}^2}[/math].

Но поскольку [math]\alpha[/math] лежит между [math]\frac{P_k}{Q_k}[/math] и [math]\frac{P_{k+1}}{Q_{k+1}}[/math], то [math]|\alpha-\frac{P_k}{Q_k}|+|\alpha-\frac{P_{k+1}}{Q_{k+1}}| = |\frac{P_k}{Q_k}-\frac{P_{k+1}}{Q_{k+1}}| = \frac{1}{Q_k Q_{k+1}}[/math], вследствие чего [math]\frac{1}{2Q_k^2}+\frac{1}{2Q_{k+1}^2}\leqslant\frac{1}{Q_k Q_{k+1}}[/math]. Следовательно [math](\frac{1}{Q_k}-\frac{1}{Q_{k+1}})^2 \leqslant 0[/math], что невозможно. Мы пришли к противоречию. Поэтому, по крайней мере для одной из двух подходящих дробей выполнено условие теоремы. Придавая различные значения [math]k[/math], получим бесконечное множество дробей, удовлетворяющих условию теоремы.
[math]\triangleleft[/math]
Теорема (2):
Для любого иррационального числа [math]\alpha[/math] существует бесконечное число дробей [math]\frac{P}{Q}[/math] таких, что [math]~|\alpha-\frac{P}{Q}|\lt \frac{1}{\sqrt{5}Q^2}[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим три последующие подходящие дроби к [math]\alpha : \frac{P_k}{Q_k}, \frac{P_{k+1}}{Q_{k+1}} [/math] и [math] \frac{P_{k+2}}{Q_{k+2}}[/math]. Пусть ни одна из них не удовлетворяет условию теоремы. Тогда имеем: [math]~|\alpha-\frac{P_k}{Q_k}|\geqslant\frac{1}{\sqrt{5}Q_k^2}, ~|\alpha-\frac{P_{k+1}}{Q_{k+1}}|\geqslant\frac{1}{\sqrt{5}Q_{k+1}^2}, ~|\alpha-\frac{P_{k+2}}{Q_{k+2}}|\geqslant\frac{1}{\sqrt{5}Q_{k+2}^2}[/math].

Так как [math]\frac{P_k}{Q_k}[/math] и [math]\frac{P_{k+1}}{Q_{k+1}}[/math] расположены по разные стороны от [math]\alpha[/math], то при нечётном [math]k[/math] имеем [math]\frac{P_k}{Q_k}+\frac{1}{\sqrt{5}Q_k^2}\leqslant\alpha\leqslant\frac{P_{k+1}}{Q_{k+1}}-\frac{1}{\sqrt{5}Q_{k+1}^2} [/math], а при чётном [math] k [/math] - [math]\frac{P_{k+1}}{Q_{k+1}}+\frac{1}{\sqrt{5}Q_{k+1}^2}\leqslant\alpha\leqslant\frac{P_k}{Q_k}-\frac{1}{\sqrt{5}Q_k^2}[/math].

Из последних двух неравенств следует, что [math]\frac{1}{\sqrt{5}}(\frac{1}{Q_k^2}+\frac{1}{Q_{k+1}^2})\leqslant~|\frac{P_k}{Q_k}-\frac{P_{k+1}}{Q_{k+1}}| = \frac{1}{Q_k Q_{k+1}}[/math]. Умножив обе части на [math]Q_{k+1}^2[/math] и перенеся все члены в левую часть получим: [math](\frac{Q_{k+1}}{Q_k})^2 - \sqrt{5}(\frac{Q_{k+1}}{Q_k}) + 1 \leqslant 0[/math]. То есть [math](\frac{Q_{k+1}}{Q_k}-\frac{\sqrt{5}}{2})^2 \leqslant \frac{1}{4}[/math], следовательно для целых [math]Q_k[/math] и [math]Q_{k+1}[/math] имеем [math]\frac{Q_{k+1}}{Q_k} \lt \frac{1+\sqrt{5}}{2}[/math].

Так как [math]\frac{P_{k+1}}{Q_{k+1}}[/math] и [math]\frac{P_{k+2}}{Q_{k+2}}[/math] расположены по разные стороны от [math]\alpha[/math], то аналогично получаем [math]\frac{Q_{k+2}}{Q_{k+1}} \lt \frac{1+\sqrt{5}}{2}[/math].

Пользуясь рекуррентным соотношением получаем [math]\frac{1+\sqrt{5}}{2} \gt \frac{Q_{k+2}}{Q_{k+1}} = \frac{Q_{k+1}a_{k+1}+Q_k}{Q_{k+1}} = a_{k+1} + \frac{Q_k}{Q_{k+1}} \gt 1 + \frac{2}{1+\sqrt{5}} = \frac{1+\sqrt{5}}{2}[/math]. Пришли к противоречию. Значит для одной из трёх последовательных подходящих дробей будет выполняться условие теоремы. Тогда придавая различные значения [math]k[/math] получим бесконечно много дробей, для которых выполняется условие теоремы.
[math]\triangleleft[/math]
Лемма (1):
Любую конечную цепную дробь [math]\langle a_0, a_1, a_2,\cdots, a_n \rangle[/math] с чётным(нечётным) числом подходящих дробей можно представить в виде эквивалентной конечной цепной дроби с нечётным(чётным) числом подходящих дробей.
Доказательство:
[math]\triangleright[/math]
Если [math]a_n \geqslant 2[/math] : [math]\langle a_0, a_1, a_2,\cdots,a_n \rangle = \langle a_0, a_1, a_2,\cdots,a_n-1,1 \rangle[/math]. Если [math]a_n = 1[/math] : [math]\langle a_0, a_1, a_2,\cdots,a_{n-1}, 1\rangle = \langle a_0, a_1, a_2,\cdots,a_{n-1} + 1 \rangle[/math].
[math]\triangleleft[/math]
Лемма (2):
Если [math]x = \frac{P\zeta+R}{Q\zeta+S}[/math], где [math]\zeta \gt 1, P, Q, R, S[/math] удовлетворяют [math]Q\gt S\gt 0[/math] и [math]PS-QR= \pm 1[/math], то [math]\frac{R}{S}, \frac{P}{Q} [/math] - n-1-ая и n-ая подходящие дроби для [math]x[/math].
Доказательство:
[math]\triangleright[/math]

Разложим [math]\frac{P}{Q}[/math] в цепную дробь[math]\langle a_0, a_1, a_2, \dots, a_n \rangle = \frac{P_n}{Q_n}[/math]. По лемме 1 мы можем задать чётное либо нечётное [math]n : PS-QR=(-1)^{n-1}[/math]

[math]P_nS-Q_nR=(-1)^{n-1}=P_nQ_{n-1}-P_{n-1}Q_n[/math] следовательно [math]P_n(S-Q_{n-1})=Q_n(R-P_{n-1})[/math]. Так как [math]P_n[/math] и [math] Q_n[/math] взаимно просты, то [math](S-Q_{n-1})\vdots Q_n [/math]. Но [math]Q_n = Q \gt S[/math] следовательно [math] Q_n \gt S-Q_{n-1}[/math], что возможно только если [math]S=Q_{n-1}[/math] аналогично [math]R=P_{n-1}[/math]. Что и требовалось доказать.
[math]\triangleleft[/math]
Теорема (3):
Если некоторая дробь [math]\frac{P}{Q}[/math] удовлетворяет условию [math]~|\alpha - \frac{P}{Q}|\lt \frac{1}{2Q^2}[/math], то она — подходящая дробь для [math] \alpha [/math].
Доказательство:
[math]\triangleright[/math]

Пусть для дроби [math]\frac{P}{Q}[/math] выполняется условие теоремы, тогда [math]\frac{P}{Q}-\alpha=\frac{\epsilon\theta}{Q^2}[/math], где [math]~|\epsilon| = 1[/math], [math]0\lt \theta\lt \frac{1}{2}[/math]. Дробь [math]\frac{P}{Q}[/math] можно представить в виде конечной цепной дроби [math]\langle a_0, \cdots, a_n \rangle [/math]. В силу леммы 1 мы можем сделать [math] n[/math] чётным или нечётным. Пусть [math] n [/math] такое, что [math]\epsilon = (-1)^{n-1}[/math].

Возьмём [math]\omega = \frac{1}{\theta} - \frac{Q_{n-1}}{Q_n} \gt 1[/math]. Получим [math] \theta = \frac{Q_n}{\omega Q_n + Q_{n-1}} [/math]. Тогда [math] \alpha = \frac{P}{Q}-\frac{\epsilon\theta}{Q^2}[/math]. Заметим, что [math]\epsilon = P_nQ_{n-1}-P_{n-1}Q_n[/math], тогда [math]\alpha = \frac{P_n}{Q_n}-\frac{P_nQ_{n-1}-P_{n-1}Q_n}{Q_n(\omega Q_n+Q_{n-1})}[/math]. Получаем в итоге [math]\alpha = \frac{\omega P_n + Q_{n-1}}{\omega Q_n + Q_{n-1}}[/math]. Следовательно, по лемме 2 теорема доказана.
[math]\triangleleft[/math]