Рассмотрим бесконечную последовательность функций Эти функции и есть наша главная хитрость. Заметим, что
Пусть имеются две функции и . Новую функцию можно представлять себе как результат некоторой операции над функциями и — операции композиции. Операцию принято обозначать кружком: Операция композиции является ассоциативной, то есть для неё выполняется сочетательный закон: равенство выполняется для любых трёх функций , , . Этот факт вытекает прямо из определения композиции.
Так что наша задача состоит в последовательном нахождении композиций . Подстановка ноля вместо в полученные функции даёт подходящие дроби для заданной непрерывной дроби.
Пора обратить внимание на то, что все функции принадлежат замечательному семейству дробно-линейных функций, то есть является отношением двух линейных функций. Общий вид дробно-линейной функции таков: (числа и не должны обращаться в ноль одновременно). Дробно-линейная функция полностью задаётся четырьмя числами — своими коэффициентами.
Семейство замечательно, помимо прочего, ещё и тем, что композиция дробно-линейных функций снова является дробно-линейной. Математики говорят, что множество дробно-линейных функций замкнуто относительно операции композиции. В справедливости этого утверждения легко убедиться прямым вычислением:
Это наблюдение позволяет, зная наборы коэффициентов двух функций, легко найти коэффициенты их композиции.
Удобно (а главное полезно) поставить в соответствие дробно-линейной функции квадратную матрицу с четырьмя коэффициентами: (о матрицах мы уже кое-что писали в разделе «Матричная версия» главы 9. «Числа Фибоначчи»). Это соответствие не является взаимно-однозначным. В то время как матрица вполне задаёт дробно-линейную функцию (кроме матриц с нулевой нижней строкой), каждая такая функция может быть задана многими разными матрицами, отличающимся друг от друга умножением всех коэффициентов на одно и то же ненулевое число.
Особенно нас должно порадовать то, что композиции двух дробно-линейных функций соответствует произведение их матриц:
В нашем случае следовательно, Вычислив элементы , , , , найдём -ю подходящую дробь. Для этого в функцию нужно подставить , тогда получим число .
Таким образом, задача вычисления -й подходящей дроби свелась к вычислению произведения матриц Это произведение можно вычислять индуктивно, точно так же, как вычислялось произведение элементов числовой последовательности. Рассмотрим функцию на пространстве последовательностей числовых пар (она принимает матричные значения). При удлинении последовательности функция перевычисляется по формуле В качестве значения функции для пустой последовательности следует взять единичную матрицу: . Для элементов матрицы получаются такие формулы перевычисления: Итак, четыре функции , , , осуществляют индуктивное расширение функции , причём .
Приведём программу, вычисляющую последовательные приближения к числу по формуле Броункера. Её алгоритм в точности следует общей схеме вычисления индуктивной функции, но с одним добавлением.
Дело в том, что элементы матрицы , а значит, числители и знаменатели подходящих дробей, имеют обыкновение очень быстро расти при удлинении последовательности. Сами же дроби при этом могут оставаться ограниченными (именно так и будет, если непрерывная дробь сходится). Очень скоро числители и знаменатели превысят допустимые пределы для числовых значений языка программирования, и произойдёт арифметическое переполнение. К счастью, с этим явлением можно бороться.
Вспомним, что матрицу дробно-линейной функции можно поэлементно умножить на любое ненулевое число, и получившаяся матрица будет по-прежнему изображать ту же самую функцию. Можно, вычислив , тут же разделить все её элементы, скажем, на , тем самым превратив в единицу, и заметно уменьшив все остальные элементы. Этому делению посвящена вторая строка в теле цикла:
#!/usr/bin/perl use warnings; my ($a, $b, $c, $d)=(1, 0, 0, 1); my $n=1; while() { ($a, $b, $c, $d)=($b, $a*$n**2+$b*2, $d, $c*$n**2+$d*2); ($a, $b, $c, $d)=map { $_/$c } ($a, $b, $c, $d); $n+=2; print 4/($b/$d+1), "\n"; }
Попробуйте убрать эту строчку, и вы увидите, что получится:
%
./pi-brouncker.pl
2.66666666666667 3.46666666666667 2.8952380952381 3.33968253968254 2.97604617604618 3.28373848373848 3.01707181707182 (пропущено чуть меньше сотни строк вывода) 3.14830398741449 3.13492606099309 -nan -nan -nan -nan -nan -nan …
Программа, не добравшись даже до сотого приближения, начинает выводить странные
значения -nan
. Аббревиатура NaN
означает Not a Number — «не
число». Почему это «не число» ещё и с минусом, мы уже не в состоянии
объяснить.