Алгоритм обобщенной цепной дроби
( Algorithm of the generalizationued continued fraction
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Введение

Пусть a₀ и a₁ - натуральные числа. Для нахождения их наибольшего общего делителя используется алгоритм Евклида [1] последовательного деления с остатком:

где натуральные числа a₀,a₁,a₂, … суть неполные частные. Это алгоритм разложения числа a =a₀/a₁ в правильную цепную дробь, и он применим к любым вещественным числам a. При этом a₀=[a], где [a] - целая часть числа a, a₁=[1/(a-a₀)], … , т.е.

и

Если разложение (1) оборвать на a_k и свернуть эту оборванную цепную дробь в рациональное число p_k/q_k, то получается подходящая дробь, которая дает наилучшее рациональное приближение к числу a. При этом

и

т.е векторы (a_k,a_k+1) и (p_k,q_k) принадлежат сопряженным плоскостям, и пара векторов (p_k,q_k), (p_k-1,q_k-1) может служить базисом в одной из них.

Цепные дроби (1) и соотношения (2), (3) рассматривал Валлис [3] в 1655 г. В 1737 г. Эйлер [4] дал название "непрерывная дробь" (fractio continua). Лагранж [5] доказал, что для квадратичных иррациональностей a разложение в цепную дробь периодично (и обратно).

Итак, алгоритм разложения числа в цепную дробь:

1) прост;

2) дает наилучшие рациональные приближения к числу;

3) периодичен для квадратичных иррациональностей.

Кроме того, он обладает еще рядом замечательных свойств.

В 1775 г. Эйлер [6] сделал первую попытку обобщить алгоритм цепной дроби на векторы. Впоследствии его подход развивали Якоби [7,8], Пуанкаре [9], Брун [10], Перрон [11], Бернштейн [12], Пустыльников [13] и др. (см. [14]). Они по аналогии с (2) строили матричные алгоритмы вида

где A_k - n-мерный вектор и C_k - квадратная n-матрица с целыми элементами, которая образована по вектору A_k, и det C_k= ± 1. Эти алгоритмы просты, но, вообще говоря, не дают наилучших рациональных приближений к вектору и не всегда при n=3 обладают аналогом свойства 3):

3 ′ ) периодичность для кубических иррациональностей.

Еще Эрмит [15] критиковал алгоритм Якоби. В работах [16-23] было проведено сравнение качества матричных алгоритмов и было установлено, что ни один их них не обладает свойствами 2) и 3 ′ ) для всех векторов A₀. При этом оказалось, что наихудшим является алгоритм Пуанкаре [9].

В 1842 г. Дирихле [24] при n=3 предложил рассматривать не трехмерный вектор A=A₀, а две линейные однородные формы l₁(X) и l₂(X) такие, что l₁(A)=l₂(A)=0. В 1850 г. Эрмит [25], развивая этот подход, предложил свое обобщение цепной дроби. Наконец, в 1895-96 гг. Клейн [26], Минковский [27] и Вороной [28] независимо пришли к тому, что надо в R³ рассматривать тройку однородных линейных форм l₁(X), l₂(X), l₃(X) и предложили свои концепции обобщения цепной дроби. При этои Клейн ограничился общими геометрическими соображениями, а Минковский и Вороной предложили конкретные алгоритмы. Впоследствии подход Клейна переоткрывали Скубенко [29] и Арнольд [30] и называли многогранники Клейна парусами и многогранниками Арнольда [43,44]. И хотя в [16] был предложен алгоритм вычисления многогранников Клейна, в [17-23] было выяснено, что многогранники Клейна-Скубенко-Арнольда не дают основы для хорошего алгоритма, обобщающего цепную дробь. Только алгоритмы Минковского и Вороного обладают свойствами 2 и 3 ′ , но они весьма громоздки. Их применению и развитию было посвящено много работ (см. [31-33]).

Свой подход к обобщению цепной дроби предложил Гурвиц [34] в 1894 г., но без алгоритма.

Интерес автора к обобщению цепной дроби возник в связи с его работой [35] 1964 г., которая была повторена Ленгом [36] в 1972 г. (см. также Старк [37]). Ниже в § 1 для правильной цепной дроби излагаются конструкции Клейна и Вороного, а также предложенная автором в [41] "выпуклая цепная дробь". В § 2 показано, как вычисляется выпуклая цепная дробь. В § 3 излагаются конструкции Клейна, Вороного и автора для n=3. В § 4 для n=3 уточняется новый алгоритм, обобщающий выпуклую цепную дробь и предложенный в [54]. В § 5 уточняется алгоритм упорядочивания трех точек на плоскости.

§ 1. Цепные дроби

Клейн [26,38,39] предложил следующую геометрическую интерпретацию цепной дроби числа a (см. также [40]). Пусть на плоскости с координатами X=(x₁,x₂) заданы две независимые однородные линейные формы

Прямые линии L_i={X: l_i(X)=0}, i=1,2 делят плоскость R² на четыре квадранта или угла. Рассмотрим два смежных угла O₁={X: l₁(X) ≥ 0, l₂(X) ≥ 0}, O₂={X: l₁(X) ≤ 0, l₂(X) ≥ 0}. Через K_i обозначим выпуклую оболочку целочисленных точек (x₁,x₂), кроме x₁=x₂=0, попавших в угол O_i  (i=1,2). Границы ∂ K_i этих множеств K_i суть выпуклые ломаные линии, состоящие из вершин B_j и ребер R_j. Если

то вершинам B_j=(x₁,x₂) этих линий соответствуют подходящие дроби x₁/x₂=p_j/q_j цепной дроби числа a. При этом четности чисел j и i совпадают, т.е. вершина B_j лежит на ломаной ∂ K_i с i=1, если j нечетное, и с i=2, если j - четное. Целочисленным точкам (x₁,x₂), лежащим на ребрах R_j ломаных ∂ K_i, соответствуют промежуточные дроби цепной дроби числа a (см. [2, с. 21]). Число целочисленных точек на ребре, минус один равно неполному частному цепной дроби и т.д. (см. рис. 1).

Вороной [28, отдел I] предложил такую интерпретацию цепной дроби. Пусть на плоскости R² заданы две линейные формы (1.1). Значения пары форм l₁(X) и l₂(X) в целочисленной точке X ≠ 0 называются относительным минимумом, если нет другой целочисленной точки Y ≠ 0, для которой

Вороной показал, что все целочисленные точки X, в которых пара форм (1.1) имеет относительные минимумы, полностью упорядочены и переход от одной пары соседних точек B_k-2=(p_k-2,q_k-2) и B_k-1=(p_k-1,q_k-1) к следующей паре B_k-1=(p_k-1,q_k-1) и B_k=(p_k,q_k) дается формулами вида (2) и (3), т.е. алгоритмом цепной дроби. В частоности, для форм (1.2) они соответствуют всем подходящим дробям цепной дроби числа a, и их последовательность по убыванию |l₁(X)| и возрастанию |l₂(X)| соответствует последовательности подходящих дробей. На рис. 2 в I-м квадранте плоскости |l₁|, |l₂| для каждого относительного минимума (|l₁^(k)|, |l₂^(k)|)=V_k заштрихован прямоугольник |l₁| ≤ |l₁^(k)|, |l₂| ≤ |l₂^(k)|, в котором нет точек (|l₁(X)|, |l₂(X)|) для целочисленных X ≠ 0.

В [41] автор предложил такую конструкцию. Пусть в R² заданы две однородные линейные формы (1.1), причем l₁₁a+l₁₂=0. Рассматриваются только точки полуплоскости l₂(X) ≥ 0. На плоскости с координатами m₁(X)=|l₁(X)|, m₂(X)=|l₂(X)|, M(X)=(m₁(X),m₂(X)) рассмотрим множество Z² точек M(X) для всех целочисленных точек X ∈ Z² кроме нуля. Пусть M - выпуклая оболочка множества Z². Граница ∂ M множества M является ломаной линией, состоящей из вершин W_k и ребер U_k. На рис. 3 заштриховано множество M и его граница ∂ M изображена жирными отрезками и точками.

Пусть Z_k=(z_1k,z_2k)=M(C_k) - точки множества Z², расположенные на ломаной ∂ M и занумерованные в порядке убывания первой координаты z_1k, C_k ∈ Z². Ломаная ∂ M и точки Z_k на ней обладают следующими свойствами.

1. Всякая точка Z_k является точкой относительного минимума пары форм (1.1), т.е. C_k=B_j; но обратное, вообще говоря, не верно.

2. Пусть Z_k=M(C_k) и Z_k+1=M(C_k+1) - две соседние точки, тогда det(C_kC_k+1)= ± 1.

3. На одном ребре U_s ломаной ∂ M не может быть трех точек Z_k, соответствующих трем вершинам B_j одной ломаной Клейна ∂ K_i. Действительно, никакие три вершины одной ломаной Клейна ∂ K_i не лежат на одной прямой, а отображение M(X) для них линейно.

4. Если число a является квадратичной иррациональностью, то последовательности Z_k и C_k периодичны, начиная с некоторого номера, т.е. существуют такие унимодулярная матрица D и натуральное число t, что DB_l=mB_l+t для l > l₀.

Последовательность точек Z_k ломаной ∂ M, занумерованных в порядке убывания |l₁| и возрастания |l₂|, назовем выпуклой цепной дробью. Ее можно получить как подходящие дроби цепной дроби вида

где b_i - натуральные числа.

Пример 1.1. Пусть a =(3+ √ {21})/6=1.2637626 … , l₁(X)=x₁-
-ax₂, l₂(X)=x₂. Для a правильная цепная дробь периодична:

Последовательные подходящие дроби суть

Вершинам ломаной ∂ M соответствуют только подходящие дроби с нечетными номерами. Они являются также подходящими дробями цепной дроби

На рис. 4 на плоскости (m₁,m₂) показаны относительные минимумы, соответствующие цепной дроби (1.3), и множества M, ∂ M, соответствующие выпуклой цепной дроби (1.4). При этом ребра и вершины ломаной ∂ M показаны на рис. 4 жирными отрезками и жирными точками. Выпуклая цепная дробь (1.4) также является диагональной цепной дробью [50;51;40, с. 39; 55, § 41] и цепной дробью до ближайшего целого [52;40, с. 39; 55, § 39]. Но они не всегда совпадают, как показывает следующий пример.

Пример 1.2. Пусть a =(1+ √ 3)/2=1.3660254 … , l₁(X)=x₁-ax₂, l₂(X)=x₂. Для a правильная цепная дробь периодична:

и выпуклая цепная дробь совпадает с правильной. Но диагональная цепная дробь такова

Она же является цепной дробью до ближайшего целого.

§ 2. Вычисление выпуклой цепной дроби

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

где b < 1, на агрегат a+1-1/(b+1+b), как это сделано в примере 1.1 (к этим местам относятся все случаи с b ≥ 3 и некоторые случаи с b=2). Однако можно вычислять ее последовательно шаг за шагом.

Опишем один шаг такого вычисления. Пусть согласно свойству 2 § 1 в качестве базиса взяты точки C_k и C_k+1, соответствующие соседним точкам Z_k=M(C_k) и Z_k+1=M(C_k+1) ломаной ∂ M. Найдем точку C_k+2. Положим E₁=C_k+1, E₂=C_k - единичные векторы. Пусть в этом базисе вектор A имеет вид A=(a₁,a₂), где a₁ > |a₂| > 0. Для простоты будем считать, что |a₂|=1. Пусть линейные формы l₁(X) и l₂(X) в этом базисе имеют вид

Точку C_k+2 ищем на прямой

Пусть a=[a₁/|a₂|], тогда ближайшими к точке персечения прямой (2.1) с лучом lA, l > 0 являются две целочисленные точки, лежащие на прямой (2.1): с x₁=a и с x₁=a+1 (см. рис. 5). Только в этих точках X значения |l₁(X)| < |l₁(B_k+1)|. Следовательно, из двух точек B ′ =(a,a₂) и B"=(a+1,a₂) надо выбрать такую, которой соответствует точка Z_k+2 на ломаной ∂ M. Предшествующие две точки этой ломаной суть

Далее

Пусть C=(c₁,c₂) и D=(d₁,d₂) две точки плоскости Y=(y₁,y₂). Проведенная через них прямая пересекает ось y₂ в точке

Вычислим значения (2.3) для двух пар точек

и в качестве точки C_k+2 возьмем ту из точек B ′ и B", для которой значения y₂ в (2.4) меньше (см. рис. 6). Если для обеих точек B ′ и B" значения y₂ в (2.4) равны, то в качестве C_k+2 берем ту из этих точек, у которой m₁ меньше.

Выбрав точку C_k+2, переходим к базису C_k+1, C_k+2 и т.д.

§ 3. Трехмерные обобщения геометрических конструкций

Клейн [26,38] предложил трехмерный аналог своей двумерной интерпретации цепной дроби. Пусть в R³ заданы три независимые однородные линейные формы

где X ∈ R³, L_i=(l_i1,l_i2,l_i3) ∈ R³_*, б  · , ·  с означает скалярное произведение, и пространство R³_* двойственно пространству R³. Каждому набору S = (s₁,s₂,s₃), где s_i= ± 1, соответствует свой октант

ограниченный плоскостями L_i={X: l_i(X)=0}, i=1,2,3. В каждом октанте O_S рассматривается выпуклая оболочка K_S всех целочисленных точек X ∈ O_S, X ≠ 0. Ее граница ∂ K_S является выпуклой двумерной многогранной поверхностью, состоящей из вершин, ребер и граней. Ее вершины должны давать наилучшие целочисленные приближения в октанте O_S к плоскостям L_i и к прямым, являющимся их пересечением.

В работах [16-23,42-46] многогранники Клейна были вычислены для ряда однородных кубических форм с целыми коэффициентами вида

каждая из которых соответствует корням свего кубического уравнения. Оказалось, что они устроены довольно сложно и разнообразно. На сайте [46] приведено много примеров плоских логарифмических проекций многогранников Клейна. На рис. 7 и 8 показаны ортогонализованные логарифмические проекции поверхностей многогранников Клейна ∂ K₊₊₊ для двух кубических форм

и

вида (3.2), взятых из [23] и соответствующих уравнению l³-2l²-l+1=0, в координатах

где m_i(X)= | б L_i,X с | , i=1,2,3. Показаны проекции вершин, ребер и целочисленных точек, лежащих на ребрах и гранях поверхности ∂ K₊₊₊, а также - целочисленных точек X=B ′ , являющихся относительными минимумами для одного октанта O₊₊₊. Точка B ′ ∈ O_S, B ′ ≠ 0 называется точкой относительного минимума октанта O_S, если нет другой целочисленной точки B" ∈ O_S, B" ≠ 0, и такой, что

На рис. 7 и 8 рядом с каждой точкой указано значение модуля формы (3.1) в ней. Видна двупериодичность рис. 7 и 8. На них жирными линиями выделены границы фундаментальных областей.

На рис. 7 фундаментальная область состоит из одного шестиугольника и двух треугольников. У многогранника ∂ K₊₊₊ грани, соответствующие шестиугольнику и малому треугольнику, удалены от начала координат на расстояние 1, а большие треугольные грани - на расстояние 3. На малых треугольных гранях нет внутренних целочисленных точек, на больших треугольных гранях имеется по одной целочисленной точке с |h|=|h₇|=8 и за гранью имеются шесть точек относительных минимумов с |h|=13 и 29. На шестиугольных гранях имеются по 9 целочисленных точек с |h|=7,8,13.

На рис. 8 фундаментальная область состоит из граней трех типов: (I) один равносторонний треугольник, (II) три скошенных треугольника и (III) три четырехугольника. Грань типа I отстоит от начала координат на расстояние 2, не содержит внутренних целочисленных точек и за ней имеется одна точка относительного минимума с |h|=|[(h)\tilde]₇|=49. Грань второго типа отстоит на расстояние 3, не содержит внутренних целочисленных точек и за ней имеются две точки относительного минимума с |h|=29 и 56. Грань типа III отстоит на расстояние 1 и имеет одну внутреннюю целочисленную точку с |h|=13. Кроме того, на некоторых ребрах имеются целочисленные точки с |h|=8.

В [16] предложен алгоритм вычисления многогранника Клейна одновременно с его сопряженным многогранником, но этот алгоритм нельзя рассматривать как обобщение алгоритма цепной дроби.

Пусть в R³ заданы три линейные однородные формы (3.1) и отображение M(X)=(m₁(X),m₂(X),m₃(X)), где m_i(X)=|l_i(X)|, i=1,2,3. Значение M(X) в целочисленной точке X ∈ Z³ называется относительным минимумом, если нет такой целочисленной точки Y ∈ Z³, что

где ||M||=m₁+m₂+m₃. Вороной [28, отдел III] рассматривал в R³ точки X ∈ Z³, соответствующие относительным минимумам форм (3.1). Он предложил способ их частичного упорядочивания и построил алгоритм движения по этим упорядоченным точкам. Этот алгоритм он назвал обобщением алгоритма цепной дроби (см. также [47, гл. IV; 48]). По одному примеру вычислений алгоритмом Вороного имеется в работах [28, § 53; 47, § 59].

В [41] предложена следующая конструкция. Вектор-функция M(X) отображает пространство R³ с координатами X в пространство R³ с координатами M=(m₁,m₂,m₃), точнее - в его неотрицательный октант. При этом множество Z³\0 всех целочисленных точек X кроме X=0 отображается в некоторое множество Z³ в R³. Пусть M - выпуклая оболочка точек множества Z³ и ∂ M - ее граница. Очевидно, что M - это выпуклый многогранник и ∂ M - это выпуклая многогранная поверхность, состоящая из вершин V_i, ребер R_i и граней G_i.

Грань G_i поверхности ∂ M назовем простой, если она является треугольником с вершинами

и не содержит других точек из множества Z³. Для простой грани G_i с вершинами (3.3) положим

Очевидно, w(G_i) принимает целые неотрицательные значения.

Теорема 3.1. Если у простой грани G_i с вершинами (3.3) w(G_i)=0, то один из векторов B₁,B₂,B₃ является суммой двух остальных.

Будем говорить, что тройка форм (3.1) находится в общем положении, если у их произведения (3.2), деленного на произведение l₁₁l₂₁l₃₁, любой из коэффициентов может быть рациональным числом, но между коэффициентами l_ij нет других независимых от этих алгебраических соотношений с рациональными коэффициентами.

Теорема 3.2. В случае общего положения все грани G_i поверхности ∂ M являются простыми и w(G_i) ≤ 2.

Множество точек из Z³, лежащих на поверхности ∂ M обозначим M, т.е.

Следствие 3.1. В случае общего положения все точки множества M являются вершинами поверхности ∂ M.

На рис. 9 и 10, взятых из [49], в координатах n₁=lnm₁,    n₂=lnm₂ показаны логарифмические проекции поверхности ∂ M для форм h₇ и [(h)\tilde]₇, многогранники Клейна для которых показаны на рис. 7 и 8 соответственно. На рис. 7 и 8 показаны вершины и ребра, а также точки относительных минимумов. Для каждой точки Y=M(X) указаны значение модуля формы h(X) и значение вектора X. Жирными линиями показаны границы фундаментальных областей. В них для каждой грани G_i указано значение w(G_i). Для обеих форм в вершинах многогранника ∂ M имеем |h|=1.

На рис. 9 фундаментальная область состоит из 6 треугольников, два имеют w =1 и четыре - w =0. В ней есть одна точка относительного минимума, соответствующая точке, лежащей в центре большой треугольной грани рис. 7. Следовательно, не все относительные минимумы соответствуют вершинам многогранников Клейна, как это было в двумерном случае. Очевидно, что всем вершинам многогранника ∂ M соответствуют вершины многогранников Клейна, но обратное не верно.

На рис. 10 фундаментальная область состоит из двух треугольников (для обоих w =1) и содержит четыре точки относительных минимумов, в одной |h|=|[(h)\tilde]₇|=7 и в трех |h|=8 (точка с |h|=8 у левой границы фундаментальной области лежит в ней, а точка с |h|=7 лежит в правом треугольнике). Все эти точки с |h|=7 и 8 соответствуют вершинам многогранников Клейна. Здесь все вершины многогранников Клейна являются относительными минимумами.

Предлагаемое ниже обобщение выпуклой цепной дроби является направленным движением по поверхности ∂ M, один шаг которого дает переход от грани с w =1 к ближайшей грани с этим же свойством.

§ 4. Алгоритм движения по поверхности ∂ M

Лемма 4.1. Пусть в R³ заданы три точки U=(u₁,u₂,u₃), V=(v₁,v₂,v₃) и W=(w₁,w₂,w₃). Проходящая через них плоскость пересекает третью координатную ось в точке

Пусть в R³ заданы три линейные формы (3.1) и такой вектор A=(a₁,a₂,a₃), что l₁(A)=l₂(A)=0. Обозначим через pR³ полупространство l₃(X) ≥ 0. Пусть A ∈ pR³ (этого всегда можно достичь изменением знака вектора A). Наша цель - построить целочисленные приближения к лучу mA, m > 0.

Предположим сначала, что на поверхности ∂ M

и у них

Согласно теореме 3.2 свойство (4.1 ′ ) выполнено в случае общего положения.

Пусть целочисленные векторы B₁,B₂,B₃ ∈ pZ³ образут базис, т.е det(B₁B₂B₃)= ± 1. Тогда мы имеем l_ij[(   def) || ( = )]  l_i(B_j), i,j=1,2,3 и такой вектор L = (l₁,l₂,l₃), что l₁B₁+l₂B₂+l₃B₃=mA, m ≠ 0. При этом ∑ _j=1³l_ijl_j=0, i=1,2. Эти начальные данные удобно записать в виде таблицы

При этом M_i=M(B_i), т.е. m_ij=|l_ij|, i,j=1,2,3. Для точки M или множества точек, например G_i, в пространстве R³ чертой сверху [`(M)] или [`(G)]_i будем обозначать их ортогональные проекции на плоскость (m₁,m₂). Пусть точки M_i являются вершинами треугольника G.

Переход к другому базису B₁ ^′ ,B₂ ^′ ,B₃ ^′ состоит из последовательного выполнения следующих 5 шагов.

Шаг 1. Первым делом на плоскости (m₁,m₂) надо выяснить взаимное расположение трех точек [`(M)]<sub>j</sub>=(|l<sub>1j</sub>|,|l<sub>2j</sub>|)[(   def) || ( = )]  (m<sub>1j</sub>,m<sub>2j</sub>), j=1,2,3, которые являются вершинами треугольника [`(G)]. Ребро треугольника [`(G)], противоположное вершине [`(M)]_j, обозначим [`(R)]<sub>j</sub>. Ребро [`(R)]_j назовем отделяющим, если точка [`(M)]<sub>j</sub> и начало координат [`(M)] =0 расположены по разные стороны от прямой L_j, проведенной через ребро [`(R)]<sub>j</sub>. Очевидно, что у каждого треугольника [`(G)], целиком расположенного в первом квадранте, есть хотя бы одно отделяющее ребро. Пара точек из [`(M)]<sub>1</sub>, [`(M)]₂, [`(M)]<sub>3</sub>, лежащих на этом ребре, является выделенной. Технически выделение такой пары точек можно сделать либо на рисунке, либо вычислениями, которые описаны ниже в § 5. Если таких ребер два, т.е. имеется две пары выделенных точек, то алгоритм разветвляется, и надо его продолжить для каждой из этих пар отдельно. Пусть для определенности выделенными являются точки [`(M)]₁ и [`(M)]₂. Прямую, проходящую через них, обозначим L.

Шаг 2. Вычисляем a_i=[l_i/|l₃|], i=1,2,3. Здесь a₃= ± 1.

Шаг 3. Для каждой из шести точек

выясняем расположение ее проекции [`(U)]<sub>i</sub>, [`(V)]_j относительно прямой L. Точки U_i, V_j, у которых проекции [`(U)]<sub>i</sub>, [`(V)]_j отделены от начала координат прямой L, отбрасываем. Оставляем только точки, проекции которых лежат от прямой L по ту же сторону, что и начало координат.

Лемма 4.2. Из двух точек [`(U)]<sub>1</sub>, [`(U)]₂ не более одной точки лежит по ту же сторону прямой L, что и начало координат.

Лемма 4.3. Из четырех точек [`(V)]<sub>1</sub>-[`(V)]₄ хотя бы одна лежит по ту же сторону прямой L, что и начало координат.

Шаг 4. Для каждой из оставшихся точек (4.4) по лемме 4.1 вычисляем точку пересечения плоскости, проведенной через точки M₁,M₂ и эту точку, с третьей координатной осью. Из этих значений выбираем наименьшее и соответствующую ему точку U_i или V_j. Если таких точек несколько, то процедура ветвится, ибо далее рассматриваем каждую из них.

Шаг 5. Если выбранная на шаге 4 точка соответствует одной из точек U_i, то делаем шаг 5а). Если она соответствует одной из точек V_i, то делаем шаг 5б).

Шаг 5а. Пусть выбрана точка U₁. Рассматриваем треугольник с вершинами [`(M)]<sub>1</sub>, [`(M)]₂, [`(U)]<sub>1</sub>. Из двух его ребер, инцидентных с вершиной [`(U)]₁, выбираем то ребро, которое отделяет точку [`(M)]<sub>3</sub> от начала координат [`(M)] =0. Если такого ребра нет, то берем ту точку V_j из оставленных на шаге 3, у которой значение y₃, вычисленное на шаге 4, наименьшее. Если их два, то алгоритм разветвляется. Пусть точка [`(M)]₂ принадлежит выбранному ребру. Тогда из двух векторов B₁ и B₂ оставляем B₂. От базиса B₁,B₂,B₃ переходим к базису B₄=B₁+B₂, B₂,B₃. Выписываем матрицу N, для которой

Матрица N^*-1 дает преобразование

где звездочка означает транспонирование. Если была выбрана точка U₂, то B₄=B₁-B₂ или B₂-B₁, чтобы B₄ ∈ pR³, и соответственно меняются матрицы N и N^*-1.

Шаг 5б. Пусть выбрана точка V_j=M(B₃ ^′ ), где B₃ ^′ =[(a)\tilde]₁B₁+[(a)\tilde]₂B₂+a₃B₃ согласно (4.4). Тогда от базиса B₁,B₂,B₃ переходим к базису B₁ ^′ =B₁, B₂ ^′ =B₂ ^′ , B₃ ^′ =B₃ ^′ =[(a)\tilde]₁B₁+[(a)\tilde]₂B₂+a₃B₃ по формулам

При этом

Векторы B₁ ^′ ,B₂ ^′ ,B₃ ^′ дают новый базис; вектор ′ - значение вектора A в этом базисе. Таким образом, переход от старого базиса B₁,B₂,B₃ к новому базису B₁ ^′ ,B₂ ^′ ,B₃ ^′ окончен.

Теорема 4.1. В предположениях (4.1 ′ ) и (4.2) если базису B₁,B₂,B₃ соответствовала грань поверхности ∂ M, то указанный переход к другому базису дает другую грань поверхности ∂ M с вершинами M₁,M₂ и U_i или V_j.

Теорема 4.2. В предположениях (4.1 ′ ) и (4.2) если базису B₁,B₂,B₃ соответствовала грань поверхности ∂ M, после нескольких указанных переходов к новому базису получен базис [(B)\tilde]₁,[(B)\tilde]₂,[(B)\tilde]₃ и в последнем переходе была выбрана точка типа V_j вида (4.4), то новому базису [(B)\tilde]₁,[(B)\tilde]₂,[(B)\tilde]₃ также соответствует грань поверхности ∂ M с вершинами M([(B)\tilde]_i),i=1,2,3.

Замечание 4.1. Выше дана самая простая и общая формулировка перехода к другому базису. Можно выделить различные случаи и подслучаи, когда этот переход упрощается. Например, если l₁₁l₁₂ и l₂₁l₂₂ < 0, то можно не рассматривать точку U₂; если l₁₁l₁₂ и l₂₁l₂₂ > 0, то - точку U₁. Однако, эта общая форма перехода наиболее удобна для программирования.

Замечание 4.2. Если исходному базису не соответствует грань поверхности ∂ M, то предложенный алгоритм после нескольких переходов к другому базису выводит на грань поверхности ∂ M.

Если предположение (4.2) не выполнено, то для треугольника G_i поверхности ∂ M с w(G_i) > 1 алгоритм дает последовательность таких треугольников D_ik с w(D_ik)=0 или 1, которые расположены за треугольником G_i и проекции которых [`(D)]<sub>ik</sub> расположены внутри проекции [`(G)]_i. Причем первый из этих треугольников D_ik имеет с треугольником G_i общее ребро. Через несколько шагов алгоритм выходит на другое ребро треугольника G_i и продолжает двигаться по треугольникам поверхности ∂ M. Получается выпукло-вогнутая поверхность, которую обозначим ∂ N₃.

Например, если w(G_i)=2, то имеется точка относительного минимума W_i, проекция которой [`(W)]<sub>i</sub> лежит внутри проекции [`(G)]_i треугольника G_i. Эта точка получается при применении алгоритма к тому ребру R₁ треугольника G_i, проекция которого [`(R)]<sub>1</sub> не является отделяющей по отношению к треугольнику [`(G)]_i. На точку W_i и ребра R_k треугольника G_i натянуты три треугольные грани D_ik с w(D_ik)=1, k=1,2,3. Алгоритм сначала выходит на грань D_i1, затем на одну из граней D_i2 или D_i3, а потом - на грань поверхности ∂ M с w =1, примыкающую к грани G_i по соответствующему ребру R₂ или R₃. У поверхности ∂ M каждую грань G_i с w(G_i)=2 заменяем тройкой граней D_ik, а грани G_i с w(G_i) ≤ 1 оставляем неизменными. В результате получаем многогранную поверхности ∂ N₃, если для поверхности ∂ M все грани G_i имеют w(G_i) ≤ 2.

Если предположение (4.1 ′ ) не выполнено, т.е. имеется непростая грань, то описанный алгоритм позволяет выходить на такую грань, двигаться по ней и сходить с нее на другую грань.

§ 5. Упорядочивание трех точек

Лемма 5.1. Пусть на плоскости R² с координатами X=(x₁,x₂) заданы три точки A=(a₁,a₂), B=(b₁,b₂) и C=(c₁,c₂). Положим

где

Если æ = 0, то точки A,B,C лежат на одной прямой.

Если æ ≠ 0, то точки A,B,C являются вершинами треугольника. При обходе этого треугольника в положительном направлении, т.е. против часовой стрелки, эти вершины расположены в прямой последовательности A,B,C, если æ < 0, и в обратной последовательности A,C,B, если æ > 0.

Следствие 5.1. У треугольника с вершинами A,B,C ребро AB является отделяющим, если величины |AB| и æ из (5.1) имеют разные знаки.

Поэтому для нахождения отделяющего ребра надо вычислить определители |AB|, |BC|, |CA| и их сумму æ. Если знак определителя отличен от знака æ, то соответствующее этому определителю ребро является отделяющим.

Если отделяющим является ребро AB, то точка D=(d₁,d₂) лежит по ту же сторону от прямой L, проведенной через точки A и B, что и начало координат, если величины |AB| и |AB|+|BD|+|DA| имеют одинаковые знаки. При этом |BD|+|DA|=|B-A,D|.

§ 6. Вычисления для формы h₇

Первый этап вычислений для формы h₇ представлен в табл. 1 и 2. Табл. 1 устроена так. В первом столбце указан номер k векторов басиса B_k. Во втором столбце указан вектор B_k. В третьем, четвертом и пятом столбце даны значения форм l₁(B_k), l₂(B_k), l₃(B_k). В шестом столбце дан нормированный вектор-столбец L =(l₁,l₂,l₃) такой, что mA=l₁ B₁+l₂ B₂+l₃ B₃ и min |l_i|=1. В седьмом столбце даны значения определителей |[`(M)]<sub>i+1</sub>[`(M)]_i+2|. В восьмом столбце ставятся звездочки (и кружочки), отмечающие выделенные пары точек. В девятом столбце даны значения a_i, вычисленные на втором шаге. В десятом столбце приведена матрица N, полученная на пятом шаге. В одиннадцатом столбце дана матрица N^*-1. В двенадцатом столбце - вектор L ′ =N^*-1L.

Заметим, что в табл. 1 столбцы 1-6 соответствуют таблице начальных данных (4.3). Напомним, что m_i(B_k)=|l_i(B_k)|. Поэтому специально таблица значений m_i(B_k) не выписывается, но при вычислении определителей в столбце 7 используются модули значений, стоящих в столбцах 3-5. Сумма значений в столбце 7 есть æ = 1.2864 > 0. Поскольку в столбце 7 имеются два отрицательных значения, то получаем две выделенные пары точек: [`(M)]<sub>1</sub>,[`(M)]₂ (отмеченные звездочками в столбце 8) и [`(M)]<sub>2</sub>,[`(M)]₃ (отмеченные в столбце 8 кружочками). Следовательно, здесь алгоритм разветвляется на два варианта. Сначала рассмотрим

Вариант 1 (выделенные векторы B₁ и B₂). Для них результат шага 2 показан в столбце 9 табл. 1. Вычисления шагов 3 и 4 по этому варианту показаны в табл. 2, которая организована так. В первом столбце указываются векторы U_i и V_j из (4.4). В столбце 2 даны значения таких векторов B_k, что U_i=M(B_k) и V_j=M(B_k). В столбцах 3-5 даны значения форм l₁(B_k), l₂(B_k), l₃(B_k). В столбцах 6 и7 даны значения определителей |[`(M)]<sub>2</sub>[`(M)]_k| и |[`(M)]<sub>k</sub>[`(M)]₁|, где M_k=M(B_k). В столбце 8 даны значения æ_k=|[`(M)]<sub>1</sub>[`(M)]₂|+|[`(M)]<sub>2</sub>[`(M)]_k|+|[`(M)]<sub>k</sub>[`(M)]₁|. В столбце 9 даны значения det(M₁M₂M_k) и в столбце 10 - отношения (4.1). При этом шагу 3 соответствуют столбцы 1-8. Согласно последней строчке столбца 7 табл. 1 имеем |[`(M)]<sub>1</sub>[`(M)]₂|=-.3351 < 0. Согласно столбцу 8 табл. 2 число æ_k для V₄ положительно, а остальные æ_k отрицательны. Следовательно, на шаге 3 отбрасываем точку V₄ (и точку U₁), но оставляем точки U₂, V₁-V₃. Согласно столбцу 10 табл. 2 наименьшее значение y₃ имеется для точки U₂. Поэтому далее делаем шаг 5а. По табл. 1 и 2 вычисляем |[`(M)]<sub>3</sub>[`(U)]₂|=1.2687. Если вектор B₁-B₂ взять вместо B₁, то æ = |[`(U)]<sub>2</sub>[`(M)]₂|+|[`(M)]<sub>2</sub>[`(M)]₃|+|[`(M)]<sub>3</sub>[`(U)]₂|=-.3351-.1764+1.1687=.7572 имеет знак противоположный к |[`(U)]<sub>2</sub>[`(M)]₂|=-.3351. Поэтому этот вариант не годится. Однако в качестве вектора B₄ берем разность B₂-B₁=(-1,1,0), чтобы иметь l₃(B₄) > 0. Получаемые матрицы N и N^*-1 приведены в столбцах 10 и 11 табл. 1. Наконец в столбце 12 табл. 1 дан вектор L ′ =N^*-1L.

В табл. 3, аналогичной табл. 1, приведены результаты вычислений шагов 1, 2 и 5 для второго этапа варианта 1. Здесь сумма значений в столбце 7 есть æ = .7572 > 0. В этом столбце имеются два отрицательных значения, т.е. процедура ветвится. Но вариант с выделенными точками M₂ и M₃ это вариант 2 этапа 1. Поэтому здесь остается единственный вариант - выделенные точки M₄ и M₂. На самом деле, результаты, приведенные в стобце 7, были получены на шаге 5а этапа 1. Значения a_i для этого варианта приведены в столбце 9 табл. 3. Вычисления шагов 3 и 4, которые здесь не приводим, дают вектор B₅=B₄+B₂=(-1,2,0). На шаге 5а получаем 2 варианта: вариант 1.1, где B₅ берется вместо B₄, и вариант 1.2, где B₅ берется вместо B₂. Соответствующие варианту 1.1 матрицы N, N^*-1 и вектор N указаны в столбцах 10, 11, 12 табл. 3. Далее будем кратко описываь результаты этапов вычислений, не приводя подробные значения промежуточных величин. За этими результатами удобно следить по рис. 7.

В варианте 1.1 на четвертом этапе получаем B₆=B₅+B₂=(-1,3,0) вместо B₂. Поэтому

Здесь и далее A=(a₁,a₂,a₃) - вектор, полученный на шаге 2. На пятом этапе получаем B₇=2B₅+2B₆-B₃=(-4,10,-1) вместо B₃, т.е.

Здесь и далее L" - это нормированный вектор N.

Итак, пришли к тройке векторов B₅, B₆, B₇, образующих новый базис. Но продолжим вычисления. На шестом этапе получаем B₈=B₇-B₆=(-3,7,-1) вместо B₆, т.е.

На седьмом этапе получаем B₉=B. Выделены B₈ и B₇, следовательно, A=(-1,0,3), и получаем B₉=-B₅+3B₇=(-11,28,-3) вместо B₅, т.е.

Итак, получили три вектора B₉, B₈, B₇, образующих новый базис. Здесь остановимся.

Теперь рассмотрим вариант 1.2. В нем B₅=B₄+B₂=(-1,2,0) вместо B₂, т.е.

На третьем этапе получаем B₁₀=B₄+B₅=(-2,3,0) вместо B₄, т.е.

На четвертом этапе получаем B₁₁=-2B₁₀+7B₅-B₃=(-3,8,-1) вместо B₃, т.е.