Правильное обобщение цепной дроби

The correct generalization of the continued fraction
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Брюно А.Д.
(A.D.Bruno)

ИПМ им. М.В.Келдыша РАН

Москва, 2003
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты №№ 02-01-01067 и 03-01-00027)

Аннотация

В трехмерном пространстве рассматриваются три однородные линейные формы. В другом трехмерном пространстве, координаты в котором суть модули значений этих форм, рассматривается выпуклая оболочка точек, соответствующих всем целочисленным точкам первого пространства, кроме начала координат. Обобщение цепной дроби заключается в движении по граням этой выпуклой оболочки, для чего предлагается алгоритм. Приведены примеры. Этим дано решение проблемы, которую безуспешно пытались решить многие математики (Эйлер, Эрмит, Якоби, Пуанкаре, Минковский, Клейн, Арнольд и др.).

Abstract

In a three-dimensional space we consider three gomogeneous linear forms. In another three-dimensional space, where coordinates are modulus of values of these forms, we consider the convex hull of points corresponding to all integers of the first space, exept the origin. The proposed generalization of the continued fraction is a motion along faces of the convex hull. Two examples are given. Thus that gives a solution of an old problem, which was attacted without a success by a lot of mathematicians (Euler, Hermit, Jacobi, Poincare, Minkowski, Klein, Arnold etc.).



E-mail: bruno@spp.keldysh.ru
Введение
Алгоритм разложения числа в обычную цепную дробь [1] обладает многими замечательными свойствами. В том числе:
1. Он прост.
2. Он дает наилучшие рациональные приближения к числу.
3. Он периодичен для квадратичных иррациональностей.
В XVIII, XIX и XX веках были сделаны многочисленные попытки обобщить этот алгоритм на векторы (Эйлер [2], Эрмит [3], Якоби [4], Пуанкаре [5], Брун [6], Минковский [7], Клейн [8], Вороной [9], Перрон [10], Скубенко [11], Арнольд [12] и др.). Но пока так и не найден алгоритм, обладающий свойствами 1 и 2 и свойством
3в. Периодичность для кубических иррациональностей.
Только алгоритм Вороного [9] обладает свойствами 2 и 3в, но он довольно громоздок. Многогранники Клейна [8]-Скубенко [11]-Арнольда [12] хотя и дают геометрическую интерпретацию наилучших приближений, но не дают основы для хорошего алгоритма, что было выяснено в работах [13-20]. Алгоритмические и геометрические концепции, заложенные в указанные обобщения, видимо, не достаточно отражали фундаментальные свойства цепной дроби. Интерес автора к обобщению цепной дроби возник в связи с работой [21].
Здесь предлагается новая двумерная концепция цепной дроби (§ 1), которая затем обобщается на трехмерную ситуацию (§ 2) и позволяет построить алгоритм (§§ 3,4), обладающий свойствами 1, 2 и 3в. В §§ 5, 6 рассмотрены два примера с подробными вычислениями по новому алгоритму.
§ 1. Новая интерпретация цепной дроби
Пусть на плоскости R2 с координатами (x1,x2)[(   def) || ( = )]  X задан вектор A[(   def) || ( = )]  (a1,a2) > 0 и две вещественные линейные формы
l1(X)    def
=
 
   l11x1+l12x2,    l2(X)    def
=
 
   l21x1+l22x2.
Причем det(lij) ╣ 0 и l1(A)=0. Положим mi(X)=|li(X)|, i=1,2 и в квадранте m1,m2 │ 0 рассмотрим множество Z2 точек M(X)[(   def) || ( = )]  (m1(X),m2(X)), соответствующих всем целочисленным точкам X ╬ Z2, кроме X=0. Пусть многоугольник M является выпуклой оболочкой множества Z2. Граница ╢M многоугольника M является ломаной линией, состоящей из ребер и вершин. Занумеруем вершины Vi=(mi1,mi2) последовательно согласно убыванию координаты m1 и возрастанию координаты m2 с ростом индекса i. Каждой вершине Vi соответствуют две такие точки Bi и -Bi ╬ Z2, что Vi=M(Bi). Через Bi=(b1i,b2i) обозначим ту из них, для которой l2(Bi) > 0. Ломаная ╢M обладает следующими свойствами.
1. Каждой ее вершине Vi соответствует подходящая дробь b2i/b1i числа a2/a1.
2. Для соседних вершин Vi,Vi+1 определитель
ъ
ъ
ъ
ъ
b1i
b1,i+1
b2i
b2,i+1
 ъ
ъ
ъ
ъ 		=▒1.
Поэтому соответствующие вершинам точки Bi, Bi+1 могут служить базисом.
Пусть A=l1Bi+l2Bi+1. Если l1 и l2 > 0, то числа b2i/b1i и b2,i+1/b1,i+1 являются последовательными подходящими дробями к числу a2/a1. Если l1l2 < 0, то между подходящими дробями b2i/b1i и b2,i+1/b1,i+1 имеется еще одна подходящая дробь b2iв/b1iв. При этом точке X=(b1iв,b2iв)[(   def) || ( = )]  Biв соответствует точка W=M(Biв), являющаяся относительным минимумом точек M(X) для X ╬ Z2\0. Если ребро {Vi,Vi+1} ломаной ╢M заменить двумя ребрами {Vi,Wi} и {Wi,Vi+1}, то вместо ломаной ╢M получим новую ломаную, которую обозначим ╢N.
3. Разложению числа a2/a1 в цепную дробь соответствует шагание по вершинам Vi и Wi ломаной ╢N в порядке возрастания индекса i, т.е. переход от пары соседних вершин к следующей паре и т.д. При этом соседние точки Bi и Biв являются базисом на плоскости R2 и переходу к соседней паре вершин соответствует переход к новому базису и т.д.
Пример 1.1. Рассмотрим более подробно шаги движения по ломаным ╢M и ╢N. Пусть
A=(a,1),    a > 1,    l1(X)=x1-ax2,    l2=x1+ax2.
Пусть B1=(0,1), B2=(1,0). В них M1=M(B1)=(a,a), M2=M(B2)=(1,1). Луч mA, m > 0 пересекает прямую x2=1 в точке x1=a. Пусть a=[a]. Тогда точки Xв=(a,1) и X"=(a+1,1) являются ближайшими целочисленными к точке (a,1). Для этих точек Mв=M(Xв)=(a-a,a+a) и M"=M(X")=(a+1-a,a+1+a). Прямая, проходящая через точки M2 и M", дается уравнением
(a+a)m1+(a-a)m2=2a.
В точке Mв=(m1в,m2в) имеем
(a+a)m1в+(a-a)m2в=2(a+a)(a-a)=2(a2-a2).
Она не является вершиной ломаной ╢M, если
a2-a2 > a.
(1.1)
Положим a = a+e, e ╬ (0,1). Тогда при e │ 1/2+1/(8a) неравенство (1.1) выполнено и точка Mв не является вершиной ломаной ╢M, а точка M" является, хотя точке Xв соответствует подходящая дробь. В базисе B2,X" имеем A=l1 B2+l2 X", т.е. a = l1+l2(a+1), 1=l2. Следовательно, l2=1, l1=a-(a+1) < 0. Ребро {B2,X"} можно заменить двумя отрезками {B2,Xв}, {Xв,X"}, соответствующими обычной цепной дроби.
§ 2. Многогранные поверхности
Пусть в R3 в базисе E1,E2,E3 заданы три линейные формы
l1(X)=сL1,Xё,    l2(X)=сL2,Xё,    l3(X)=сL3,Xё
и такой вектор A, что l1(A)=l2(A)=0. При этом Li=(li1,li2,li3) i=1,2,3.
Обозначим через pR3 полупространство l3(X) > 0. Пусть A ╬ pR3 (этого всегда можно достичь изменением знака вектора A). Линейные формы li(X) определяют отображение пространства R3 в пространство R3 с координатами mi(X)=|li(X)|, i=1,2,3, M(X)=(m1(X),m2(X),m3(X)), точнее - в его неотрицательный октант. При этом множество Z3\0 всех целочисленных точек X кроме X=0 отображается в некоторое множество Z3 в R3. Пусть M - выпуклая оболочка точек множества Z3 и ╢M - ее граница. Очевидно, что M - это выпуклый многогранник и ╢M - это выпуклая многогранная поверхность, состоящая из вершин Vi, ребер Ri и граней Gi.
Теорема 2.1. Каждая грань Gi поверхности ╢M является треугольником, который:
а) содержит только те точки из множества Z3, которые являются вершинами V1,V2,V3 этого треугольника;
б) det(B1B2B3) равен 0 или ▒1, где Vj=M(Bj), Bj ╬ Z3, j=1,2,3.
Теорема 2.2. Если грань Gi поверхности ╢M имеет вершины M(B1),M(B2),M(B3) и det(B1B2B3)=0, то один из векторов B1,B2,B3 является суммой двух остальных.
Рассмотрим случай, когда det(B1B2B3)=▒1. Если векторы B1,B2,B3 ╬ pR3 использовать как локальный базис и в нем разложить вектор A=l1B1+l2B2+l3B3, то при l1,l2,l3 │ 0 вектор A лежит внутри конуса, натянутого на векторы B1,B2,B3, а при хотя бы одном отрицательном li вектор A лежит вне этого конуса.
В первом подслучае предпишем грани Gi число dGi=1, во втором - число dGi=-1. Если же det(B1B2B3)=0, то положим dGi=0.
Точка W ╬ Z3 называется точкой относительного минимума, если нет другой точки U ╬ Z3 с U г W.
Будем говорить, что точка относительного минимума W лежит внутри трех точек V1,V2,V3, если ортогональная проекция точки W на плоскость m1,m2 лежит в треугольнике, натянутом на такие же проекции точек V1,V2,V3.
Теорема 2.3. Пусть грань Gi поверхности ╢M с вершинами V1,V2,V3 имеет dGi=▒1, причем Vj=M(Bj), Bj ╬ Z3, i=1,2,3. Если для одного из векторов C=▒Bj▒Bk, j,k=1,2,3 точка W=M(C) является точкой относительного минимума и лежит внутри трех точек V1,V2,V3, то она единственная с этими свойствами.
В ситуации теоремы 2.3 на точку W и ребра треугольника Gi натянуты треугольные грани Di1,Di2,Di3. У поверхности ╢M каждую грань Gi, удовлетворяющую условию теоремы 2.3, заменим тройкой граней Di1,Di2,Di3, а остальные грани Gj оставим неизменными. В результате получим многогранную поверхность ╢N. Предлагаемый ниже в § 3 алгоритм позволяет вычислять поверхность ╢N, начиная с любой ее грани Gi или Dij, имеющей dGi ╣ 0 или dDij ╣ 0 соответственно, передвигаясь к ближайшей аналогичной грани, расположенной ближе к оси m1=m2=0. Роль подходящих дробей здесь играют векторы Bi, соответствующие вершинам Vi и Wj поверхности ╢N. Они дают наилучшие преближения к лучу mA, m > 0.
Замечание 2.1. Несложно дать алгоритм, позволяющий двигаться по граням поверхности ╢M, но он требует более громоздких вычислений, которым нет аналога в алгоритме обычной цепной дроби.
§ 3. Алгоритм движения по поверхности ╢N
Пусть точки V1,V2,V3 - вершины треугольника поверхности ╢N и им соответствуют векторы B1,B2,B3 ╬ Z3, образующие базис. Тогда мы имеем lij[(   def) || ( = )]  li(Bj), i,j=1,2,3 и такой вектор L = (l1,l2,l3), что l1B1+l2B2+l3B3=A. При этом хj=13lijlj=0, i=1,2. Эти начальные данные удобно записать в виде таблицы
B1
l11
l21
l31
l1
B2
l12
l22
l32
l2
B3
l13
l23
l33
l1.
(3.1)
Переход к ближайшему треугольнику на ╢N с d ╣ 0 состоит из последовательного выполнения следующих шагов.
Шаг 1. Первым делом надо выяснить взаимное расположение трех точек Mjв=(|l1j|,|l2j|)[(   def) || ( = )]  (m1j,m2j), j=1,2,3. А именно, надо выделить из них две такие точки, что проведенная через них прямая отделяет начало координат от третьей точки. Технически это можно сделать либо на рисунке, либо вычислениями, которые будут описаны позже в § 4.
Предположим, что такая пара точек единственна. Пусть для определенности это точки M1в и M2в. Прямую, проходящую через них, обозначим L. Для простоты предположим, что ее нормальный вектор D=(d1,d2) положителен.
Шаг 2. Берем вектор B4=B1+B2 и для него вычисляем значения l4j=l1j+l2j, j=1,2,3. Затем смотрим, куда попала точка M4в=(|l14|,|l24|). Если она лежит левее прямой L, то переходим к шагу 4. Если она лежит правее прямой L, то делаем следующий шаг.
Шаг 3. Берем вектор B5=▒(B1-B2) такой, у которого третья компонента положительна. Если точка M5в лежит левее прямой L, то переходим к шагу 4. Если правее, то полагаем Biв=Bi, i=1,2,3, Lв=L и переходим к шагу 5.
Шаг 4. Из двух векторов Bi, i=1,2 оставляем тот, для которого li больше. Пусть это B2. Тогда от базиса B1,B2,B3 переходим к базису B4 (или B5), B2,B3. Выписывам матрицу N, для которой
ц
ч
ч
ч
ш
B1в
B2в
B3в
 Ў
ў
ў
ў
° 		   def
=
 
    ц
ч
ч
ч
ш
B4
B2
B3
 Ў
ў
ў
ў
° 		= N ц
ч
ч
ч
ш
B1
B2
B3
 Ў
ў
ў
ў
° 		,    N= ц
ч
ч
ч
ш
1
1
0
0
1
0
0
0
1
 Ў
ў
ў
ў
° 		.
В случае шага 3 вместо B4 должен быть вектор B5. Матрица N*-1 дает преобразование
Lв=N*-1L,    N*-1= ц
ч
ч
ч
ш
1
0
0
-1
1
0
0
0
1
 Ў
ў
ў
ў
° 		,
где звездочка означает транспонирование. Переходим к следующему шагу.
Шаг 5. Для базиса B1в,B2в,B3в делаем такое же упорядочивание, как в шаге 1. Пусть точка Mв(B3в), соответствующая вектору B3в, лежит правее прямой Lв, проходящей через точки Mв(B1в) и Mв(B2в). Тогда полагаем [(L)\tilde]=Lв/|l3в| и вычисляем целые части ai=[[(l)\tilde]i], i=1,2,3, где a3=▒1. Берем вектор B4в=a1B1в+a2B2в+a3B3в. Если точка Mв(B4в) лежит левее прямой Lв, то от базиса B1в,B2в,B3в переходим к базису
ц
ч
ч
ч
ш
B1вв
B2вв
B3вв
 Ў
ў
ў
ў
° 		   def
=
 
    ц
ч
ч
ч
ш
B1в
B2в
B4в
 Ў
ў
ў
ў
° 		=
~
N
 
 ц
ч
ч
ч
ш
B1в
B2в
B3в
 Ў
ў
ў
ў
° 		,    
~
N
 
 = ц
ч
ч
ч
ш
1
0
0
0
1
0
a1
a2
a3
 Ў
ў
ў
ў
° 		.
(3.2)
При этом
L"=N*-1Lв=|l3в|N*-1
~
L
 
 > 0,    N*-1= ц
ч
ч
ч
ш
1
0
-a3a1
0
1
-a3a2
0
0
a3
 Ў
ў
ў
ў
° 		.
(3.3)
Векторы B1вв,B2вв,B3вв дают новый базис, для которого соответствующие точки V1вв,V2вв,V3вв являются вершинами некоторого треугольника поверхности ╢N, т.е. переход окончен.
Если точка Mв(B4в) лежит правее прямой Lв, то надо взять вектор
B5в= ь
я
э
я
ю
(a1+1)B1в+a2B2в+a3B3в,
если
l1* > l2*,
a1B1в+(a2+1)B2в+a3B3в,
если
l1* < l2*,
(3.4)
где
l1*=l1в-(a+1)a3l3в,    l2*=l2в-(a+1)a3l3в.
Если точка Mв(B5в) лежит левее прямой Lв, то делаем замену базиса и вектора Lв по формулам (3.2) и (3.3), где соответствующее ai заменено на ai+1, i г 2. Если точка Mв(B5в) лежит праее прямой Lв, то в качестве B6в берем оставшийся из векторов (3.4). Если точка Mв(B6в) подходит, то делаем замены вида (3.2) и (3.3). Если точка Mв(B6в) не подходит, то берем
B7в=(a1+1)B1в+(a2+1)B2в+a3B3в.
Если точка Mв(B7в) не подходит, то идем по последовательности векторов
Bm+nв=(a1+m)B1в+(a2+n)B2в+a3B3в,    m,n │ 0,
и находим подходящую с наименьшим значением (m+n)l3в. Выполнив соответствующие преобразования вида (3.2) и (3.3), получаем новые начальные данные B1вв,B2вв,B3вв,L", отвечающие треугольнику поверхности ╢N с d ╣ 0.
§ 4. Упорядочивание трех точек
Упорядочивать три точки Mjв=(|l1j|,|l2j|), i=1,2,3 можно следующим образом. Сначала среди чисел |l1j| выберем наименьшее, и аналогично среди чисел |l2j|, i=1,2,3. В соответствующих строках таблицы (3.1) поставим звездочки. Будем предполагать, что это разные строки. Пусть для определенности это первые две строки и в них
mi*= min
{|li1|,|li2|},    mi**= max
{|li1|,|li2|},     i=1,2.
Если в третьей строке таблицы (3.1) хотя бы для одного i=1,2 число |li3| > mi**, то точка (|l13|,|l23|) лежит правее прямой, проходящей через точки M1в и M2в. Эту прямую обозначим через L. Нормальный вектор к прямой L есть
D=(||l12|-|l22||,||l21|-|l11||).
Положение точки M3в относительно прямой L определяется знаком разности
сD,M1вё-сD,M3вё.
 (4.1)
Если она положительна, то точка M3в лежит левее прямой L. В этом случае обе прямые, проведенные через пары точек M1в,M3в и M2в,M3в являются левыми, т.е. возникают два подслучая, и оба надо рассмотреть в шаге 2. Если разность (4.1) отрицательна, то прямая L является левой и можно переходить к шагу 2.
§ 5. Первый пример
В работах [13-20] были рассмотрены 10 однородных кубических тернарных форм с целыми коэффициентами, которые являются произведением трех линейных форм, и искались разложения по разным алгоритмам [2-10] кратных корневых векторов этих форм. Ниже для двух из этих форм демонстрируются вычисления разложений указанных векторов по предлагаемому алгоритму.
В этом параграфе согласно [13,14] рассматривается форма
h2(X)=сL1,XёсL2,XёсL3,Xё,
где
L1=(1,-l3,-1-l2),    L2=(1,-l1,-1-l3),    L3=(1,-l2,-1-l1),
li суть корни уравнения l3-3l-1=0:
l1=2cos (7p/9)=-1.5320,
l2=2cos (5p/9)=-0.3473,
l3=2cos (p/9)=1.8793.
Здесь li(X)=сLi,Xё,    i=1,2,3 и A=L3. Начальные данные вида (3.1) и вычисления по алгоритму §§ 3,4 представлены в табл. 1, которая организована следующим образом.
В левой колонке указывается номер j операции, приводящей к замене базиса. Во второй колонке указан номер k векторов базиса Bk. В третьей колонке приведены векторы Bk. В четвертой, пятой и шестой колонках даны значения форм l1(Bk), l2(Bk) и l3(Bk). В седьмой колонке дан вектор-столбец L = (l1,l2,l3) такой, что mA=l1B1+l2B2+l3B3. В восьмой колонке ставятся звездочки, указывающие ближайшие к нулю Mв=0 точки Mkв. В девятом столбце в строках со звездочками даны значения нормали D=(d1,d2) к прямой L, причем в верхней строке d1 , а в нижней d2; в строках без звездочки даны скалярные произведения сD,Mkвё. В десятом столбце при выделенном значении li даны нормированные значения вектор-столбца [(L)\tilde]=L/|li|. В одиннадцатом столбце даны целые части [[(L)\tilde]]. В двенадцатом и тринадцатом столбцах приведены матрицы N и N*-1. В четырнадцатом стобце даны вектор-стобцы Lв=N*-1L. При этом столбцы 10-14 выделены в нижнюю часть таблицы.
Сами вычисления происходят так. Сначала для j=1 и k=1,2,3 заполняется таблица начальных данных вида (3.1), т.е. первые 7 столбцов табл. 1 в строках 1-3. Теперь по алгоритму § 4 находим строки с наименьшим значением |l1| - это строка k=3 - и с наименьшим значением |l2| - это строка k=1. В колонке 8 ставим в этих строках звездочки. Поскольку в строке k=2 значения |l1| и |l2| больше таких же значений в строке k=1, то прямая L проходит через точки M1в и M3в. Компоненты нормали D=(1.879,.347) к прямой L даны в столбце 9: d1 в строке k=1 и d2 в строке k=3. В строке k=2 дано значение скалярного произведения сD,M1вё = d1+d2 на прямой L.
Теперь делаем шаг 2 из § 3, т.е. полагаем B4=B1+B3 и заполняем строку k=4 в столбцах 2-6. В столбце 7 отмечаем, что складываются векторы Bk с индексами k=1 и 3. В столбце 9 ставим значение сD,M4вё. Поскольу это значение меньше, чем сD,M1вё, стоящее в строке k=2, то точка M4в лежит левее прямой L и вектор B4 годится в качестве нового базисного вектора.
Поскольку l1 > l3, то согласно шагу 4 § 3 из двух векторов B1 и B3 оставляем вектор B1, а вектор B3 заменяем вектором B4. В стобцах 12 и 13 даны значения соответствующей матрицы N и матрицы N*-1. В стобце 14 дан новый преобразованный вектор-столбец Lв=N*-1L.
Теперь переходим к шагу 5 § 3. Сначала для j=2 заполняем в строках с k=1,2,4 первые 7 столбцов табл. 1, переписывая их из соответствующих мест строк k=1,2,3,4 с j=1 этой же таблицы. Теперь по алгоритму § 4 в столбце 8 выделяем звездочками строки с k=1 и k=4, находим нормальный вектор D=(d1,d2) к прямой L, проходящей через точки M1в и M4в, и значение сD,M1вё. Поскольку точка M2в лежит правее прямой L, то нормируем вектор L так: [(L)\tilde]=L/|l2| и результат записываем в столбец 10. В столбце 11 помещаем значения [[(L)\tilde]]. Согласно этим значениям образуем новый вектор B5=B1+B2+B4 и для него заполняем строку k=5 в столбцах 2-7. В столбце 9 записываем значение сD,M5вё. Поскольку оно меньше, чем это значение в строке k=2, то точка M5в лежит левее прямой L и вктор B5 нам подходит как новый базисный вектор вместо вектора B2. Соответствующие матрицы N и N*-1 приведены в столбцах 12 и 13. В столбце 14 дано новое значение вектора Lв=N*-1L. Оно отличается от исходных значений L, приведенных в столбце 7 для j=1, только порядком компонент и переходит в него при подстановке с матрицей
N*-13= ц
ч
ч
ч
ш
0
1
0
1
0
0
0
0
1
 Ў
ў
ў
ў
° 		.
Для нее N3=N3*-1. Следовательно, при линейном преобразовании Y=CX, где
C=N*-13N*-12N*-11 = ц
ч
ч
ч
ш
0
1
0
1
0
0
0
0
1
 Ў
ў
ў
ў
° 		ц
ч
ч
ч
ш
1
-1
0
0
1
0
0
-1
1
 Ў
ў
ў
ў
° 		ц
ч
ч
ч
ш
1
0
-1
0
1
0
0
0
1
 Ў
ў
ў
ў
° 		=

= ц
ч
ч
ч
ш
0
1
0
1
-1
-1
0
-1
1
 Ў
ў
ў
ў
° 		,
луч mA переходит в себя. Аналогично для матрицы
T=C-1=N*1N*2N*3 = ц
ч
ч
ч
ш
1
0
1
0
1
0
0
0
1
 Ў
ў
ў
ў
° 		ц
ч
ч
ч
ш
1
1
0
0
1
0
0
1
1
 Ў
ў
ў
ў
° 		ц
ч
ч
ч
ш
0
1
0
1
0
0
0
0
1
 Ў
ў
ў
ў
° 		= ц
ч
ч
ч
ш
2
1
1
1
0
0
1
0
1
 Ў
ў
ў
ў
° 		.
Эта матрица дает элементарный период T для алгоритма, и векторы L1,L2,L3 являются ее собственными векторами.
§ 6. Вычисление разложения для формы h3
Здесь согласно [15] рассмотрим форму
h3(X)=сL1,XёсL2,XёсL3,Xё,
где
Li=(1,-li,1-li2),    i=1,2,3,
li суть корни уравнения l3-3l2-l+1=0:
l1=-2.4812,    l2=1.17,    l3=-0.68889.
Здесь li(X)=сLi,Xё,    i=1,2,3 и A=L3. Начальные данные вида (3.1) и вычисления по алгоритму §§ 3, 4 представлены в табл. 2, которая организована также, как табл. 1 (см. § 5).
Вычисления проходят так. Сначала для j=1 и k=1,2,3 заполняется таблица начальных данных вида (3.1), т.е. первые 7 столбцов табл. 2 в строках k=1-3. Теперь делаем шаг 1 § 3, используя § 4. Наименьшее значение |l1| находится в первой строке, а |l2| - в третьей. Поэтому в 8 колонке ставим звездочки в этих строках. Вычисляем нормальный вектор D=(d1,d2) прямой L, проходящей через точки M1в и M3в. Его компоненты вписываем в девятый столбец: d1 - в первую и d2 - в третью строки. Во вторую строку этого же столбца вписываем значение сD,M1вё = d1+d2. Делаем второй шаг § 3. Берем вектор B4=B1+B3 и заполняем четвертую строку в колонках 2-6. В колонку 9 вписываем значение сD,M4вё. Поскольку оно больше, чем значение сD,M1вё, записанное во второй строке, то вектор B4 не подходит.
Делаем шаг 3. Берем B5=B1-B3 и заполняем столбцы 2-9 строки 5. Здесь |l1| и |l2| в пятой строке больше, чем |l1|=1 и |l2|=1 в первой строке. Поэтому точка M5в лежит правее прямой L, и вектор B5 нам не подходит.
Переходим к шагу 5. Здесь выделенное значение есть l2. Делаем нормировку [(L)\tilde]=L/|l2| и результат записываем в столбец 10. В столбец 11 записываем целые части [[(l)\tilde]j]. Согласно им образуем вектор B6=B1+B2 и заполняем начало шестой строки. Поскольку сD,M6вё < сD,M1вё, то точка M6в лежит левее прямой L и вектор B6 можно взять в качестве нового базисного вектора вместо B2. Соответствующие матрицы N и N*-1 приведены в 12 и 13 столбцах. В столбце 14 дано новое значение вектора-столбца Lв=N*-1L.
Теперь начинаем второй этап вычислений с j=2, заполняя начальные данные, полученные при j=1. Действуем согласно шагу 1 и § 4, заполняя столбцы 8 и 9. Согласно шагу 2 образуем вектор B7=B1+B6 и заполняем для него строку с k=7. Для M7в имеем сD,M7вё = 5.7 > сD,M1вё = 3.3. Поэтому точка M7в лежит правее прямой L, и вектор B7 не подходит. Согласно шагу 3 образуем вектор B6-B1, но это вектор B2, который уже был использован, поэтому теперь он не подходит.
Итак, переходим к шагу 5. Здесь отмеченным является значение l3. По нему нормируем [(L)\tilde]=L/|l3|, и записываем результат в столбец 10. В столбец 11 записываем [[(l)\tilde]j]. Согласно этим значениям образуем вектор B8=B6+B3 и заполняем строку с k=8. Поскольку сD,M8вё < сD,M1вё, то точка M8в лежит левее прямой L и вектор B8 нам подходит в качестве басисного вместо B3. Соответствующие матрицы N, N*-1 и вектор Lв=N*-1[(L)\tilde] приведены в 12,13 и 14 столбцах.
Переходим к третьему этапу, т.е. j=3, и заполняем начальные части трех новых строк табл. 2, используя данные, полученные на этапе 2. Упорядочивание трех точек дает сначала те же точки M1в, M6в и значения D, сD,M1вё, сD,M8вё, которые были получены на этапе j=2 и записаны в строках j=2, k=1,6,3,8 столбца 9. Следовательно, точка M8в лежит левее прямой L, но прямая Lв, проведенная через точки M6в и M8в, лежит левее точки M1в. Итак, получаем два варианта.
Начнем с первого варианта (прямая Lв с нормальным вектором Dв). Этот вариант указан в столбцах 8 и 9 при j=3. Образуем вектор B9=B1+B8 и заполняем строку k=9. Поскольку сDв,M1вё > сDв,M9вё, то вектор B9 подходит в качестве нового базисного. Здесь l3 > l1, поэтому оставляем вектор B8, а вектор B1 заменяем вектором B9. Соответствующие матрицы N и N*-1 и вектор Lв=N*-1L приведены в колонках 12-14. Если вектор Lв нормировать L"=Lв/l1в, то получаем вектор L"=(1,.526,.689), который отличается от начального вектора L при j=1 только порядком компонент и переходит в него при преобразовании N4*-1L", где
N*-14= ц
ч
ч
ч
ш
1
0
0
0
0
1
0
1
0
 Ў
ў
ў
ў
° 		.
Следовательно, преобразование Y=TX, где
T=N*1N*2N*3N*4 = ц
ч
ч
ч
ш
1
1
0
0
1
0
0
0
1
 Ў
ў
ў
ў
° 		ц
ч
ч
ч
ш
1
0
0
0
1
1
0
0
1
 Ў
ў
ў
ў
° 		ц
ч
ч
ч
ш
1
0
0
0
1
0
1
0
1
 Ў
ў
ў
ў
° 		ц
ч
ч
ч
ш
1
0
0
0
0
1
0
1
0
 Ў
ў
ў
ў
° 		=

= ц
ч
ч
ч
ш
2
1
1
1
1
1
1
1
0
 Ў
ў
ў
ў
° 		,
это период алгоритма, и луч mA инвариантен относительно этого преобразования. Более того, векторы L1, L2, L3 являются собственными для матрицы T [15].
Теперь рассмотрим второй вариант: прямая L" проходит через точки M6в, M8в и имеет нормальный вектор D"=(.369,1.806). При этом сD",M6вё = 1.59. Согласно шагу 2 берем вектор B10=B6+B8 и заполняем строку k=10, j=3 табл. 2. Для точки M10в имеем сD",M10вё = 1.92 > сD",M6вё = 1.59. Поэтому вектор B10 нам не подходит. Согласно шагу 3 берем B8-B6, но это вектор B3, рассмотренный ранее и теперь не нужный. Согласно шагу 5 здесь выделенное значение есть l1=.592. Делаем нормировку [(L)\tilde]=L/|l1| и результат записываем в столбец 10. В столбце 11 стоят [[(l)\tilde]i]. Согласно им образуем вектор B1+B8. Но это как раз вектор B9, рассмотренный в первом варианте. Поскольку точка M1в лежит вне прямой L", то оставляем вектор B8, а вектор B1 заменяем вектором B9. Получаем такое же преобразование, как в первом варианте.
Заметим, что все преобразования этого параграфа соответствуют алгоритму Бруна [6].


Список литературы
  1. Хинчин А.Я. Цепные дроби. 3-е изд. М.: Физматгиз, 1961.

  2. Euler L. De relatione inter ternas pluresve quantitates instituenda // Petersburger Akademie Notiz. Exhib. August 14, 1775 // Commentationes arithmeticae collectae. V. II. St. Petersburg, 1849. P. 99-104.

  3. Hermite Ch. Correspondance dвHermite et de Stieltjes II, lettres 232, 238, 408. Gauthier-Villars, Paris, 1905.

  4. Jacobi K.G.J. Allgemeine Theorie der Kettenbruchänlichen Algorithmen, in welchen jede Zahl aus drei vorhergehenden gebildet wird // J. Reine Angew. Math. 1868. V. 69. P. 29-64.

  5. Poincare H. Sur une generalization des fractionés continues // C.R. Acad. Sci. Paris. Ser. 1. 1884. V. 99. P. 1014-1016.

  6. Brun V. En generalisation av Kjedebroken // Skrifter utgit av Videnskapsselskapeti Kristiania. I. Matematisk-Naturvidenskabelig Klasse 1919. N 6; 1920. N 6.

  7. Klein F. Über eine geometrische Auffassung der gewöhnlichen Kettenbruchentwicklung // Nachr. Ges. Wiss. Göttingen Math.-Phys. Kl. 1895. N 3. P. 357-359.

  8. Minkowski H. Generalisation de le theorie des fractions continues // Ann. Sci. Ec. Norm. Super. ser III, 1896, t. 13, p. 41-60. Also in: Gesamm. Abh. I, p. 278-292.

  9. Вороной Г.Ф. Об одном обобщении алгорифма непрерывных дробей. Варшава: Из-во Варш. Ун-та, 1896. Также: Собр. соч. в 3-х томах. Киев: Из-во АН УССР, 1952. Т. 1. С. 197-391.

  10. Perron O. Grundlagen für eine Theorie des Jacobischen Ketten-bruchalgorithmus // Math. Ann. 1907. V. 64. P. 1-76.

  11. Скубенко Б.Ф. Минимумы разложимых кубических форм от трех переменных // Записки научных семинаров Ленинградского отделения математич. ин-та им. Стеклова (ЛОМИ). 1988, т. 168, с. 125-139.

  12. Арнольд В.И. Цепные дроби. М.: МЦНМО, 2001.

  13. Брюно А.Д., Парусников В.И. Многогранники Клейна для двух кубических форм Давенпорта // Матем. заметки. 1994. Т. 56. N 4. С. 9-27.

  14. Брюно А.Д., Парусников В.И. Сравнение разных обобщений цепных дробей // Матем. заметки, 1997, т. 61, N 3, с. 339-348.

  15. Parusnikov V.I. Klein polyhedra for complete decomposable forms // Number theory. Dyophantine, Computational and Algebraic Aspects. Editors: K. Györy, A. Pethö and V.T. Sós. De Gruyter. Berlin, New York. 1998, p. 453-463.

  16. Парусников В.И. Многогранники Клейна для четвертой экстремальной кубической формы // Матем. заметки, 2000, т. 67, N 1, с. 110-128.

  17. Парусников В.И. Многогранники Клейна с большими гранями // Препринт N 93. М.: ИПМ им. М.В.Келдыша, 1997.

  18. Парусников В.И. Многогранники Клейна для пятой экстремальной кубической формы // Препринт N 69. М.: ИПМ им. М.В.Келдыша, 1998.

  19. Парусников В.И. Многогранники Клейна для шестой экстремальной кубической формы // Препринт N 69. М.: ИПМ им. М.В.Келдыша, 1999. 31 с.

  20. Парусников В.И. Многогранники Клейна для седьмой экстремальной кубической формы // Препринт N 79. М.: ИПМ им. М.В.Келдыша, 1999. 32 с.

  21. Брюно А.Д. Разложения алгебраических чисел в цепные дроби // Журнал вычислительной матем. и матем. физики, 1964, т. 4, N 2, с. 211-221.



Таблица 1. Вычисления для формы h2.
123456789
jkBkl1l2l3L* D, сD,Mвё
111,0,01.1.1.1.*1.879
20,1,0-1.8791.534.347.3472.226
30,0,1-.653-2.879.532.532*.347
41,0,1.347-1.8791.532(1)+(3)1.304
211,0,01.1.1..468*.879
20,1,0-1.8791.534.347.3471.532
41,0,1.347-.8791.532.532*.653
52,1,1-.532.6552.879(1)+(2)+(4).895
121011121314
jk[(L)\tilde][[(L)\tilde]]Nj Nj*-1Lв
111      0      01    0-1.468
20      1      00      1      0.347
31      0      10      0      1.532
4
211.34711      0      01-1    0.347
2111      1      10      1      01
41.53210      0      10-1    1.532
5
Таблица 2. Вычисления для формы h3.
123456789
jkBkl1l2l3L* D, сD,Miвё
111,0,01.1.1.1.*.631
20,1,02.481-1.17.689.6894.787
30,0,1-5.156-.369.525.525*4.156
41,0,1-4.156.6311.525(1)+(3)5.244
51,0,-16.1561.369.475(1)-(3)
61,1,03.481-.171.689(1)+(2)2.903
211,0,01.1.1..451*.83
61,1,03.481-.171.6891*2.481
30,0,1-5.156-.369.525.7623.311
72,1,04.481.832.689(1)+(6)5.778
81,1,1-1.675-.5392.214(6)+(3)2.727
311,0,01.1.1..592*.461
61,1,03.481-.171.689.3121.136
81,1,1-1.675-.5392.2141*.675
92,1,1-.675.4613.214(1)+(8).622
102,2,11.806-.7093.903(6)+(8)
121011121314
jk[(L)\tilde][[(L)\tilde]]NjN*-1jLв
111.45111      0      01-1    0.451
2111      1      00      1      01.
3.76200      0      10      0      1.762
4
5
6
21.59201      0      01      0      0.592
61.31210      1      00    1-1.312
3110      1      10      0      11
7
8
31111      0      11      0      0.592
6.52700      1      00      1      0.526
81.68910      0      1-1  0      1.689
9
10


File translated from TEX by TTH, version 3.40.
On 14 May 2004, 16:07.