Главная Промышленная автоматика.

Чтобы перейти к более общему случаю, начнём со следующего замечания. Из алгоритма вытягивания носов видно, что цепная дробь для коэффициента а наклона прямой I с уравнением у = ах на плоскости = {хе + yf) с коэффициентами х, i/ и с решёткой Г = целочисленных линейных комбинаций базисных векторов ей/ зависит не столько ОТ выбора базиса, сколько от расположения прямой I по отношению к решётке Г.

Чтобы описать эту зависимость, предположим для определённости, что а > 0. Рассмотрим два угла, на которые прямая I делит положительный квадрант

F+: у>ах, х>0; Г : у<ах, х>0.

Рассмотрим точки решётки в F+ (в Выпуклая оболочка этого множества ограничена снизу для Y+ (сверху для F ) бесконечной ломаной линией. Вершинами этой ломаной являются векторы алгоритма вытягивания носов: за вершиной = pje + qf на ломаной следует вершина (на одной из ломаных все номера k чётные, а на другой - нечётные). Элементы цепной дроби - это целочисленные длины отрезков ломаных (см. сноску *) на с. 22).

Согласно алгоритму вытягивания носов, и+з = kk+ik+i причём площадь параллелограмма, натянутого на и u+j, есть pqk+i --№+1=±1-


При переходе от базиса {e,f} к новому базису {e,f} и к новым коэффициентами х, у точки xe+yf = хе+yf мы заменим уравнение у = ах прямой I на новое уравнение у = ах той же прямой. Знаки и порядок базисных векторов можно выбрать так, что на луче х > > О прямой I выполнено условие х > О, а в угле Y, где х > О, у> ах выполняются неравенства х > О, у > ах, определяющие угол У => F (рис. 17, а).



Лемма. Границы выпуклых оболочек множеств точек решётки Г в углах F и У совпадают, начиная с некоторого места.

Доказательство. Прямая, соединяюш;ая лежаш;иев Yсоседние вершины и и+з границы выпуклой оболочки, пересекает ось у в точке с ординатой

Рк+1 Рк+1 Рк+1

(рис. 17, б). Поскольку Л < 1, все целые точки угла Y, не попавшие в угол Y, лежат выше соединяюш;ей с и+2 прямой. Поэтому они не влияют на вхождение этого соединяюш;его отрезка в границу выпуклой оболочки множества целых точек угла, которая и для угла Y будет содержать этот отрезок.

Разумеется, граница выпуклой оболочки множества целых точек угла Y содержит еш;ё и дополнительные отрезки, для которых X < min{pft} (например, х < 0). Только они и создают разницу границ выпуклых оболочек: при достаточно больших х разницы нет. Лемма доказана.

Следствие. Если цепная дробь для числа а периодична (хотя бы начиная с некоторого места), то это верно и для числа а.

Замечание. Число а легко явно выразить через а и через коэффициенты разложения векторов нового базиса {e,f} через векторы старого базиса. Получается дробно-линейное преобразование

, Аа + В " Ca + D

которое унимодулярно, т.е. для которого целые коэффициенты удовлетворяют условию сохранения основного параллелограмма при переходе от одного базиса к другому: AD - ВС = +1.

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

Покажем теперь, что от условия унимодулярности замены базиса здесь можно избавиться.

Теорема. Пусть прямая у = ах растягивается сохраняюш;им решётку Г = линейным преобразованием М плоскости. Тогда разложение в цепную дробь любого числа

, Аа + В " Ca + D



полученного из а целочисленным невырожденным (AD ВС) дробно-линейным преобразованием, периодично, начиная с некоторого места.

Доказательство. Число а является коэффициентом уравнения у = ах прямой у = ах, записанного в координатах, порождённых парой целочисленных векторов е = Се - Df, f = -Ае + Bf плоскости {xe + yf}. Если бы площадь порождённого этими новыми векторами параллелограмма равна +1, то векторы е, f составляли бы базис решётки Г и всё было бы уже доказано выше. В общем случае \AD-ВС\ =N> 1 векторы е и f порождают не Г, а лишь более разреженную (в N раз) решётку, и наше доказательство надо слегка усовершенствовать.

Обозначим через Гд решётку, порождённую векторами е и f. Решётка =МГд порождена векторами Me и Mf, образующими основной для неё параллелограмм такой же площади N, как и параллелограмм, порождённый векторами е и f, так как преобразование М сохраняет площади. Точно так же и каждая из решёток Tg = MTq порождена парой векторов, образующих параллелограмм площади N.

Лемма. Число подрешёток в Z, порождённых парами векторов, образующих параллелограммы площади N, конечно (ограничено зависящей лишь ОТ N постоянной).

Доказательство. Такая подрешётка содержит точку Р, удалённую ОТ О не дальше, чем на л/iV, иначе площадь параллелограмма (со сторонами и диагоналями длиннее лЩ) была бы больше, чем NlЗ>N.

Чтобы площадь параллелограмма, натянутого на векторы ОР и OQ, была бы равна N, прямая QQ, параллельная ОР, должна быть удалена от прямой ОР на расстояние N/\OP\ < N. Точки Q нашей подрешётки, лежащие на этой прямой, образуют прогрессию с шагом длины \ОР\ < лЩ. Поэтому число разных подрешёток, получающихся

при разных выборах точки Q, не превосходит л/iV. Умножая это число выборов на число целых точек на расстоянии не больше л/iV от О (это число не превосходит CN), мы получаем оценку сверху: искомое число подрешёток не превосходит CN (годится, например, значение С = 4).

Теперь заметим, что наша прямая у = ах растягивается не только преобразованием М, но и любой его степенью М*.

Преобразование М переставляет наши решётки Г,, с основным параллелограммом площади ЛГ. Поскольку их конечное число, найдутся





0 1 2 3 4 5 6 7 [8] 9 10 11 12

0.141