Пункт 8. Обчислення прямуючих дробів.
Проспостерігаємо за поведінкою прямуючих дробів
d 1 = q 1 , d 2 = q 1
+ 
, d 3 = q 1 + 
, ...
ланцюгового дробу
з метою навчитися швидко їх обчислювати без перетворення багатоповерхових виразів.
Прямуючий дріб d s , s > 1, одержуємо із дробу d s -1 заміною в записі виразу d s -1 букви q s -1 виразом q s -1 + 1/ q s . Ми вже знаємо з пункту 7, що якщо "багатоповерховий" прямуючий дріб спростити (порахувати), то вийде деяке раціональне число P/Q - "одноповерховий" дріб. Домовимося завжди буквою Ps позначати чисельник придатної дробу d s (чисельник його раціонального значення, тобто "одноповерхового" дробу), а буквою Q s - знаменник.
Приймемо для зручності P 0 = 1, Q 0 = 0. (Це просто угода, на нуль ділити не потрібно.) Маємо:
,
тобто P 1 = q 1 , Q 1 = 1,
,
і т.д.
Видно, що виходять рекурентні співвідношення:
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 |
Другий рядок цієї таблиці - неповні частки - заповнюється відразу після роботи алгоритму Евкліда, числа P0 = 1, Q0 = 0, P1 = q1 , Q1 = 1 проставляються в таблицю автоматично. Два останні рядки заповнюються зліва направо з використанням рекурентних співвідношень. Наприклад, число 11 = P3 у третьому рядку виникло так: трійка, що стоїть над ним, помножилася на трійку, що стоїть перед ним, і до результату додалася двійка спереду, отже P3=q3P2+P1=3×3+2. Після того, як у таблиці вже є число 11, наступна клітинка в цьому рядку заповнюється числом 4 · 11 + 3 = 47, і т.д. Погодьтеся, що цей процес набагато швидший за розкручування багатоповерхових дробів. Відповідь:
d 0 = ¥ ; d 1 = 2; d
2 = 3; d 3
= 
=2,75,
- на п'ятому кроці (починаючи з нуля) прямуючі дроби підійшли до самого числа, стрибаючи довкола нього, причому дроби з парними номерами більші за початкове число, а з непарними - менші, і послідовність прямуючих дробів дуже швидко сходиться до самого числа. Це, звичайно, не випадково, але про ці властивості трохи нижче.
Порахуємо прямуючі дроби розкладу Ö 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..., тобто досягнена дуже висока точність. Знадобилося для цього лише кілька хвилин, що показує ефективність ланцюгових дробів.
