§ 2. Цепные дроби

Пункт 8. Вычисление подходящих дробей.

В этом пункте мы будем внимательно наблюдать за поведением подходящих дробей

цепной дроби

с целью научиться быстро их вычислять не связываясь с преобразованием многоэтажных выражений.

Мишке косолапому понятно, что подходящая дробь 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 ₀ = 1, Q ₀ = 0. (Это просто соглашение, не пугайтесь, на ноль делить никто не заставляет.) Имеем:

Видно, что получаются рекуррентные соотношения:

Просьба хорошенько запомнить эти соотношения вместе с начальными условиями P ₀ = 1, Q ₀ = 0, P ₁ = q ₁ , Q ₁ = 1, ибо их использование значительно ускоряет процесс вычисления подходящих дробей и доставляет много других радостей. Сами соотношения очень легко доказать, если воспользоваться принципом математической индукции и головным мозгом. Проделайте это, пожалуйста, самостоятельно.

Пример. Вспомним разложение в цепную дробь числа 105/38 из предыдущего пункта и вычислим подходящие дроби. Имеем:

Вычисления числителей и знаменателей подходящих дробей организуем в таблицу:

* Более того, вы зачем-то начали читать сноску к пустой клетке.

Посмотрите внимательно. Вторая строчка этой таблицы - неполные частные - заполняется сразу после работы алгоритма Евклида, числа P ₀ = 1, Q ₀ = 0, P ₁ = q ₁ , Q ₁ = 1 проставляются в таблицу автоматически. Две последние строки заполняются слева направо с использованием рекуррентных соотношений. Например, число 11 = P ₃ в третьей строке возникло так: тройка, стоящая над ним, умножилась на тройку, стоящую перед ним, и к результату прибавилась стоящая впереди двойка, ибо P ₃ = q ₃ P ₂ + P ₁ = 3 · 3 + 2. После того, как в таблице уже стоит число 11, следующая клетка в этой строке заполняется числом 4 · 11 + 3 = 47, и т.д. Согласитесь, этот процесс гораздо быстрее и приятнее раскручивания многоэтажных дробей. Ответ:

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

Я хотел было закончить здесь пункт 8, но человек - существо ужасно любопытное. Если он идет мимо забора за которым что-то попискивает, то он обязательно заглянет в щелочку, чтобы узнать, что это там пищит. Вот и сейчас любопытство взяло верх, и мне страшно хочется посчитать подходящие дроби разложения Ц 2 в цепную дробь из примера 1 предыдущего пункта. Не буду себя сдерживать и составлю таблицу:

Уже на шестом шаге я получил дробь 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).