Основное свойство А-полиномов состоит в том, что

Xi,X2,..-,Xn = Kn-l{X2,.--,Xn)/KniXi,X2,...,Xn), П > 1. (5)

Это можно доказать по индукции: поскольку из (5) следует, что

Хо + Xi,..., Хп = Kn+l{xo, Xl,..., Xn)/Kn{xi ,...,Хп),

xo,xi,... ,Хп есть величина, обратная правой части последнего равенства. /С-полиномы симметричны в том смысле, что

Kn{Xi,X2,...,Xn) = Kn{Xn,...,X2,Xi). (6)

Это вытекает из указанного выше свойства, подмеченного Эйлером, и как следствие имеем

Кп{Х1,...,Хп) =XnK„-i{Xi,...,Xn-l) +K„-2{xi,...,Xn-2) (7)

для п > 1. /С-полиномы удовлетворяют также важному тождеству

Kn{Xi,. . .,Хп)К„{Х2,. . .,Xn+l) - Kn+liXl,. . ,Xn+l)Kn-l{X2, . . jn)

= (-!)", п>1. (8) (См. упр. 4.) Из этого тождества и равенства (5) следует, что

xi,...,Xn =---+-----4----,

9o9i 9i92 Ч2Чз Яп-1Яп

гдеяк = Kk{xi,...,Xk). (9)

Итак, А-полиномы тесно связаны с цепными дробями.

Всякое вещественное число А в интервале О < X <1 представляется в виде правильной цепной дроби, определяемой следующим образом. Положим, что Xq = А. Для всех п > О, таких, что Хп ф О, положим

Л„+1 = \\/Хп\, Хп+1 = \/Хп - Ап+1. (10)

Если Хп = О, то величины An+i и Xn+i не определены и правильной цепной дробью для X будет Al,.. .,Ап . Если Хп ф О, данное определение гарантирует, что О < Хп+1 < 1, так что любое А будет положительным целым числом. Из определений (10) следует также, что

Ai-i-Xi Л1 + 1/(Л2 + А2) поэтому

Х = Л1,...,Л„ ьЛ„ + Х„ (11)

для всех п > 1, для которых определено Хп- В частности, если АГ„ = О, то А" = Ai,...,An . Если Хп ф О, то число А всегда лежит между Ai,... ,Ап и Al, ..., An + I , так как согласно (7) величина д„ = Kn{Ai, Л„ -I- Хп) монотонно возрастает от Kn{AiА„) до /<Г„( Ai,..., Л„ + 1) при возрастании Хп от О до 1. Согласно равенству (9) при возрастании д„ цепная дробь будет возрастать или убывать в зависимости от того, будет ли число п четным или нечетным.

Действительно, в силу (5), (7), (8) и (10)

\Х - II Аи..., Л„ = l/Mi,..., Л„ + ХпЦ - II Al,.. .,Ап11\ = \IIAi,. ..,А„, llXnII -llAi,..., AJI\

К„{А2, ...,Ап, II Хп) Kn-i{A2,..., An) Kn+i {Al,..., An, II Хп) Kn{Ai,...,An)

= ll{Kn{AiAn)Kn+i {Al,..., An, II Xn))

< ll{Kn{Ai,...,An)Kn+i{Ai,...,An,An+i)). (12)

Поэтому IIAl,...,Anil - экстремально близкое приближение к X, если п не мало. Если Хп не равно нулю для всех п, получаем бесконечную цепную дробь II Al, А2, A3,... II, значение которой определяется как

lim IIAi,A2,...,Anll; П-+00

и из неравенства (12) ясно, что этот предел равен X.

Разложение вещественных чисел в правильную цепную дробь обладает рядом свойств, аналогичных свойствам чисел, представленных в десятичной системе счисления. Если при помощи приведенных выше формул разложить в правильные цепные дроби некоторые известные вещественные числа, получим, например,

= 3,1,1,1,2 ;

VI" = 1,1,9,2,2,3,2,2,9,1,2,1,9,2,2,3,2,2,9,1,2,1,9,2,2,3,2,2,9,1,... ; = 1 + 3,1,5,1,1,4,1,1,8,1,14,1,10,2,1,4,12,2,3,2,1,3,4,1,1,2,14,3,... ; гг = 3 -I-117,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,... ; (13) е = 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,1,18,1,... ; 7 = III, 1,2,1,2,1,4,3,13,5,1,1,8,1,2,4,1,1,40,1,11,3,7,1,7,1,1,5,1,49,... ; 0 = 1+ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,... .

Числа Ль-Лг, ••• называются настичньши отношениями числа X Обратите внимание на закономерность поведения частичных отношений для чисел у/ЩТд, ф ие; причины этой закономерности рассматриваются в упр. 12 и 16. Для чисел же \/2, 7Г и 7 никакой видимой закономерности в поведении частичных отношений не наблюдается.

Интересно отметить, что когда древние греки обнаружили существование иррациональных чисел, то, по существу, первое определение вещественных чисел они дали в терминах бесконечных цепных дробей. (Позже они приняли предложение Евдокса вместо этого определить х = у следующим образом: "ж < г для тех же рациональных чисел г, таких, что у < г".) (См. О. Becker, Quellen und Studien zur Geschichte Math., Astron., Physik B2 (1933), 311-333.)

Если A - рациональное число, то его разложение в правильную цепную дробь естественным образом соотносится с алгоритмом Евклида. Предположим, что X = vlu для U > i; > 0. Процесс разложения в правильную цепную дробь начинается с Xq = X; обозначим Щ = и, Vq = v. В предположении, что Хп = VnlUn ф О,

уравнение (10) принимает вид

Л„+1 = \UnlVn\, Хп+1 = Un/Vn - Ап+г = {Un mod Vn)/Vn. (14)

Поэтому, если принять

U„+i=Vn, V;+i =[/„modV;, (15)

то условие Хп = Vn/Un будет выполняться в течение всего процесса разложения дроби. Далее, соотношение (15)-это в точности преобразование, выполняемое в алгоритме Евклида над переменными и и v (см. алгоритм 4.5.2А, шаг А2). Например, поскольку ~ = ЦЪ,1,1,1,211, известно, что применение алгоритма Евклида к числам U = 29 и t; = 8 потребует выполнения ровно пяти шагов деления и на шаге А2 частными [w/wj будут последовательно 3, 1, 1, 1 и 2. Если Х„ = О и п > 1, то частичное отношение Л„ всегда должно равняться 2 или более, поскольку X„ i меньше единицы.

Такое соответствие с алгоритмом Евклида означает, что правильная цепная дробь для числа X заканчивается на некотором шаге со значением А„ = О тогда и только тогда, когда X - рациональное число, ибо очевидно, что А„ не может равняться нулю, если число X иррационально, и, наоборот, известно, что алгоритм Евклида всегда заканчивается. Если частичные отношения, получаемые в ходе выполнения алгоритма Евклида, равны Ai, Лг, ..., Л„, то согласно (5)

V Кп-\{А2,...,Ап)

и Kn{Ai,A2,...,An)

Эта формула справедлива также в случае и < v, когда А\ = 0. Более того, согласно (8) Kn-i{A2,..., Л„) и Kn{Ai, Лг,..., Л„) бздут взаимно просты и дробь в правой части выражения (16) является несократимой. Поэтому

u = Kn{AuA2,...,An)d, v = Kn-i{A2,...,An)d, (17)

где d= gcd(u,w).

Наихудший случай. Теперь можно использовать сформулированные выше свойства для того, чтобы выяснить, как себя ведет алгоритм Евклида в наихудшем случае, или, другими словами, чтобы найти верхнюю границу числа шагов деления. Наихудший случай имеет место, когда на входе задаются последовательные числа Фибоначчи.

Теорема F. Пусть для п > \ и и v - целые числа (и > v > Q), такие, что при применении кипу алгоритма Евклида необходимо выполнить ровно п шагов деления, причем число и-наименьшее возможное число, удовлетворяющее этим

условиям. Тогда и = Fn+2 HV = Fn+l.

Доказательство. Согласно (17) должнобыть и = /<Г„(Л1, Лг,..., Л„)</, где Л Лг,... ...,Ап и d-положительные целые числа, а Л„ > 2. Поскольку АГ„ - полином с неотрицательными коэффициентами, включающий все переменные, минимальное значение достигается только тогда, когда Ai = 1, Л„ 1 = 1, Л„ = 2, d = 1. Подставляя эти значения в (17), получаем искомый результат.