В этом пункте мы будем внимательно наблюдать за поведением подходящих дробей
d
1
=
q
1
,
d
2
, =
q
1
+
|
1
q 2 |
,
d
3
=
q
1
+
|
1
|
, ... |
цепной дроби
с целью научиться быстро их вычислять не связываясь с преобразованием многоэтажных выражений.
Мишке косолапому понятно, что подходящая дробь d s , s > 1, получается из дроби d s -1 заменой в записи выражения d s -1 буквы q s -1 выражением q s -1 + 1/ q s . (Признаюсь честно, что это я погорячился, написав "мишке косолапому понятно". Лично мне, в свое время, для понимания этого потребовалось сделать над собой изрядное усилие. Ну, да я и не мишка косолапый.) Мы уже знаем из пункта 7, что если "многоэтажную" подходящую дробь упростить (посчитать), то получится некоторое рациональное число P / Q - "одноэтажная" дробь. Договоримся всегда буквой P s обозначать числитель подходящей дроби d s (числитель именно ее рационального значения, т.е. "одноэтажной" дроби), а буквой Q s - знаменатель. Давайте научимся быстро считать эти числители и знаменатели.
Положим для удобства P 0 = 1, Q 0 = 0. (Это просто соглашение, не пугайтесь, на ноль делить никто не заставляет.) Имеем:
d 0 = |
P
0
Q 0 |
= Ґ |
d 1 = |
q
1
1 |
= |
P
1
Q 1 |
, т.е. P 1 = q 1 , Q 1 = 1, |
d 2 = |
q
1
+1/
q
2
1 |
= |
q
1
q
2
+1
1· q 2 + 0 |
= |
q
2
P
1
+
P
0
q 2 Q 1 + Q 0 |
= |
P
2
Q 2 |
, |
d 3 = |
(
q
2
+ 1/
q
3
)
P
1
+
P
0
( q 2 + 1/ q 3 ) Q 1 + Q 0 |
= |
q
3
P
2
+
P
1
q 3 Q 2 + Q 1 |
= |
P
3
Q 3 |
и т.д. |
Видно, что получаются рекуррентные соотношения:
P
s
= q
s
P
s
-1
+
P
s
-2
- числители
Q s = q s Q s -1 + Q s -2 - знаменатели |
Просьба хорошенько запомнить эти соотношения вместе с начальными условиями P 0 = 1, Q 0 = 0, P 1 = q 1 , Q 1 = 1, ибо их использование значительно ускоряет процесс вычисления подходящих дробей и доставляет много других радостей. Сами соотношения очень легко доказать, если воспользоваться принципом математической индукции и головным мозгом. Проделайте это, пожалуйста, самостоятельно.
Пример. Вспомним разложение в цепную дробь числа 105/38 из предыдущего пункта и вычислим подходящие дроби. Имеем:
Вычисления числителей и знаменателей подходящих дробей организуем в таблицу:
s | 0 | 1 | 2 | 3 | 4 | 5 |
Q s |
Это пустая клетка,
зачем вы в нее смотрите? * |
2 | 1 | 3 | 4 | 2 |
P s | 1 | 2 | 3 | 11 | 47 | 105 |
Q s | 0 | 1 | 1 | 4 | 17 | 38 |
* Более того, вы зачем-то начали читать сноску к пустой клетке.
Посмотрите внимательно. Вторая строчка этой таблицы - неполные частные - заполняется сразу после работы алгоритма Евклида, числа P 0 = 1, Q 0 = 0, P 1 = q 1 , Q 1 = 1 проставляются в таблицу автоматически. Две последние строки заполняются слева направо с использованием рекуррентных соотношений. Например, число 11 = P 3 в третьей строке возникло так: тройка, стоящая над ним, умножилась на тройку, стоящую перед ним, и к результату прибавилась стоящая впереди двойка, ибо P 3 = q 3 P 2 + P 1 = 3 · 3 + 2. После того, как в таблице уже стоит число 11, следующая клетка в этой строке заполняется числом 4 · 11 + 3 = 47, и т.д. Согласитесь, этот процесс гораздо быстрее и приятнее раскручивания многоэтажных дробей. Ответ:
d 0 = Ґ ; d 1 = 2; d 2 = 3; d 3 = |
11
4 |
= 2,75; |
d 4 = |
47
17 |
» 2,764...; d 5 = |
105
38 |
» 2,76315... |
- на пятом шаге (считая с нуля) подходящие дроби подошли к самому числу, прыгая вокруг него. Я имею ввиду то, что дроби с четными номерами больше исходного числа, а дроби с нечетными номерами - меньше, и последовательность подходящих дробей очень быстро сходится к самому числу. Это, конечно, не случайно, но об этих свойствах как раз чуть ниже и в следующем пункте.
Я хотел было закончить здесь пункт 8, но человек - существо ужасно любопытное. Если он идет мимо забора за которым что-то попискивает, то он обязательно заглянет в щелочку, чтобы узнать, что это там пищит. Вот и сейчас любопытство взяло верх, и мне страшно хочется посчитать подходящие дроби разложения Ц 2 в цепную дробь из примера 1 предыдущего пункта. Не буду себя сдерживать и составлю таблицу:
s | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Q s | 1 | 2 | 2 | 2 | 2 | 2 | 2 | |
P s | 1 | 1 | 3 | 7 | 17 | 41 | 99 | 239 |
Q s | 0 | 1 | 2 | 5 | 12 | 29 | 70 | 169 |
Уже на шестом шаге я получил дробь 99/70 = 1,41428..., т.е. достиг точности, которую помнят только влюбленные в математику человеки - Ц 2 » 1,4142; понадобилось же мне для этого две минуты и шесть секунд устных вычислений. Вот какой мощный аппарат - цепные дроби!
Задачки |
1 . Составляя таблицу, вычислите десяток подходящих дробей следующих цепных дробей и запишите их значения в виде десятичной дроби: а)
(все неполные частные равны единице); б)
(последовательность неполных частных такова: 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1,...); * в)
(последовательность неполных частных такова: 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, 3, 13,...); ** 2 . Решите уравнение: , где справа в цепной дроби стоит n дробных черточек. |
* Разложение в цепную дробь основания натуральных логарифмов впервые получил Эйлер, подметивший и доказавший закономерность в последовательности неполных частных.
** Для последовательности неполных частных разложения в цепную дробь числа p в настоящее время неизвестно никакой закономерности и никаких ее свойств, кроме того, что эта последовательность заве-домо не периодическая (см. пункт 11).
NS | СООБЩЕНИЯ |
Знаете ли вы, что сpеди английских джентльменов окончательно вышли из моды цилиндpы? Тепеpь они носят на головах исключительно конусы. Marlboro предупреждает: Минздрав опасен для вашего здоровья. |