Восстановление рационального числа

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

Лемма

Пусть - строго выпуклая функция и , где при и , тогда .

Доказательство проведем индукцией по n. При n=2, по определению строго выпуклой функции выполняется неравенство , что и требовалось. Пусть утверждение леммы справедливо при n-1. Докажем его справедливость для n. Положим . По предположению индукции, выполняется неравенство . Поскольку , то выполняется неравенство .

Для симметричной строго выпуклой функции точка 0 всегда является точкой минимума. Действительно, для произвольной точки x имеем , , откуда выводим . Для выпуклых и симметричных функций справедлива

Теорема

Пусть , две точки с целочисленными компонентами удовлетворяющие условиям:

Треугольник с вершинами в точках 0, , не содержит точек с целочисленными координатами, отличных от его вершин

Выполняются неравенства , .

Тогда, для любой точки с целочисленными компонентами выполняется неравенство , если не лежит на прямой , или , если лежит на прямой , и .

Доказательство. Пусть произвольная точка с целочисленными координатами. Для определённости, пусть точка лежит в той же стороне по отношению к прямой , что и точка , или лежит на этой прямой (иначе вместо возьмем точку ). Тогда найдутся числа и , что . Величины и , суть целые числа. Действительно, в противном случае одна из точек , или , где - дробная часть , имеет целочисленные компоненты и принадлежит треугольнику с вершинами в точках 0, , , что противоречит условию 1. Если , то при из представления , согласно утверждению леммы выводим . Аналогично, при , выводим . Таким образом, в случае когда точка лежит на прямой , утверждение теоремы выполнено (если , то ).

Рассмотрим теперь случай .

Если , то . Согласно лемме выполняется неравенство . Отсюда и условий теоремы вытекает .

Если , то , и по лемме выполняется неравенство . Отсюда и условий теоремы выводим .

Если , то , и по лемме . Отсюда и условий теоремы вытекает . Теорема доказана.

Опишем алгоритм построения точек и , удовлетворяющих условиям теоремы.

Алгоритм A1.

1. Положим , .

2. Найдем целое t, при котором значение функции наименьшее. Положим .

3. Если , то поменяем точки и местами и вернемся на шаг 2. Иначе, конец, искомые точки построены.

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

Оценим трудоемкость алгоритма A1, в предположении, что искомые точки лежат в круге радиуса r с центром в начале координат. Обозначим через и точки и , получаемые на i-ой итерации после второго шага, через - значение параметра t на (i+1)-ой итерации. По определению выполняются неравенства (см. шаг 2). Если i-ая итерация алгоритма не является последней итерацией, то и (см. шаг 3). На втором шаге (i+1) итерации будет построена точка , причем если эта итерация не последняя, то значение функции в точке будет меньше чем значение в точке , а значит меньше чем значения функции в точках , и . Тем самым установлено неравенство , в предположении, что (i+1) итерация не последняя. Матрицу коэффициентов разложения векторов и по системам векторов , и , . обозначим через и , соответственно. Легко проверить равенства и . Поскольку , то все элементы матрицы имеют одинаковый знак, а значит, элементы матрицы так же имеют одинаковый знак. Обозначим через сумму элементов j-го столбца матрицы A. Если элементы матриц A и B имеют одинаковый знак (у каждой матрицы знак свой), то из правила умножения матриц вытекает неравенство . В частности справедливо неравенство , из которого, для вытекает . Рассмотрим случай . Во первых заметим что не возможны ситуации, когда , ( т.к. ), или , . Во вторых, если , , или , , то . Таким образом, в любом случае выполняется неравенство . Пусть k – номер последней итерации алгоритма. Элементы матрицы по абсолютной величине не превосходят 2r, так как искомые точки лежат в круге радиуса r с центром в начале координат. Но тогда справедливо неравенство , откуда .

Вернемся к задаче восстановления рационального числа , которая формулируется как задача минимизации , при ограничениях , , и - целые числа. Запишем сравнение в виде уравнения . Исключим a из поставленной задачи, и перейдем к задаче , при ограничениях, , и - целые числа. Для функции алгоритмом A1 найдем две точки и удовлетворяющие условиям теоремы. Если , то искомое рациональное число равно , иначе оно равно .

Поскольку искомые решения находятся в круге радиуса , то число итераций алгоритма . Самый трудоемкий шаг в итерации алгоритма – второй. Он заключается в нахождения минимума функции на точках прямой. Для рассматриваемых критериев, задача построения минимума на точках прямой сводится к делению чисел длины .