КИНЕМАТИЧЕСКОЕ ПРОСТРАНСТВО И ДОКАЗАТЕЛЬНОЕ РЕШЕНИЕ СИСТЕМЫ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

KINEMATICAL SPACE AND VALIDATING SOLVING OF SYSTEM OF ALGEBRAIC EQUATIONS

Adahаmjan Joraev

Candidate of Science, assistant professor  Kyrgyz-Uzbek University,

Republic of Kyrgyzstan, Osh

АННОТАЦИЯ

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

ABSTRACT

There is constructed an interactive algorithm of virtual motion in a plane to provide opportunity for the user to construct domains surely containing solutions of a system of two algebraic equations. Data are validating presentations of functions in left hand parts of these equations. Тhe principle of non-zero rotation of a vector is applied.

Ключевые слова: кинематическое пространство; алгебраическое уравнение; система уравнений; алгоритм; движение; принцип ненулевого вращения

Keywords: kinematical space; algebraic equation; system of equations; algorithm; motion; principle of non-zero rotation

Введение

Для целей интерактивного компьютерного представления топологических пространств в книге [1] было введено определение кинематического пространства и осуществлена реализация некоторых известных пространств. Эта концепция дала возможность построения алгоритмов виртуального движения [6] для решения различных задач в разделах математики, связанных с непрерывностью.

Для обеспечения доказательности вычислений [3] возможно применение интервального анализа. Обзор первых результатов для дифференциальных уравнений, полученных с его помощью, имеется в [5].

Ранее нами были построены алгоритмы для исследования римановых поверхностей, представленных заданным дифференциальным уравнением [2] или алгебраическим уравнением [4].

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

1. Постановка задачи

Рассматривается система уравнений

f(x,y)=0,

g(x,y)=0,(1)

где f(x,y), g(x,y) - непрерывные функции. Эти функции задают векторное поле {f(x,y), g(x,y)}.

Предполагается, что заданы алгоритмы для интервальных расширений F(X,Y) и G(X,Y), где X,Y - машинные интервалы, такие, что из x∈X,y∈Y следует f(x,y)∈F(X,Y), g(x,y)∈G(X,Y). При этом интервалы F(X,Y) и G(X,Y) «достаточно узкие» для «узких» интервалов X,Y. Требуется построить такие прямоугольные области на плоскости, чтобы они гарантированно содержали решения системы [1].

Используется следующая известная

ТЕОРЕМА. Если векторное поле {f(x,y), g(x,y)} на границе области не обращается в нуль и вращение векторного поля по границе области отлично от нуля, то система (1) имеет хотя бы одно решение внутри области.

2. Неформальное описание интерактивного алгоритма и целей пользователя

Выбирается некоторое (машинное) число h>0. Начиная с некоторой (машиной) точки, в которой вектор не равен нулю, пользователь двигается шагами длины h параллельно одной из осей координат, при этом алгоритм

- вычисляет интервальный вектор {F(X,Y), G(X,Y)} на каждом получающемся звене;

- в тех случаях, когда этот интервальныйвектор содержит нулевой вектор, предупреждает о некорректности данного шага (*) и не переходит в следующую точку;

- иначе, переходит в следующую точку и запоминает ее; вычисляет изменение вращения;

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

В последнем случае пользователь принимает решение о продолжении поиска или начале нового поиска.

Сначала пользователю рекомендуется обойти более широкую область. Далее, пользователь, с учетом сообщений (*) и (**), либо проверяет более широкую область, либо сужает область поиска. При нахождении достаточно узкой области, содержащей решение, можно уменьшить шаг и попытаться еще сузить область.

3. Формальное описание интерактивного алгоритма

Предлагается следующая индексация I направлений векторного поля:

(F>0, 0∈G)→ 0; (F>0, G>0)→ 45; (0∈F, G>0)→ 90; (F<0, G>0)→ 135;

(F<0, 0∈G)→ 180; (F<0, G<0)→ 225; (0∈F, G<0)→ 270; (F>0, G<0)→ 315.

Случай(0∈F, 0∈G)не допускается (*).

При каждом переходе вращение изменяется на разность нового и преж-него индексов (она может принимать значения-90;-45; 0; 45; 90). При переходе от 315 к 0 прибавляется 360 (0-315+360=45), при обратном переходе вычитается 360. Таким образом, при возврате в уже пройденную точку вращение получается кратным 360.

ПРИМЕЧАНИЕ. Такое свойство дискретной величины (в данном случае - в цикле из восьми элементов, в более общем случае - в вершинах связного графа) - переходить только к некоторым соседним значениям - можно назвать «обобщенной непрерывностью».

(Для интервалов запись [a,b] при a>b преобразуется в запись [b,a]).

Алгоритм. Пользователь вводит координаты {x₀, y₀} начальной точки и значение шага h. Не должно быть (0 ∈ F([x₀, x₀], [y₀, y₀]), 0 ∈ G([x₀, x₀], [y₀, y₀])).

Вычисляем индекс интервального вектора {F([x₀, x₀], [y₀, y₀]), G([x₀, x₀], [y₀, y₀])}. Полагаем вращение S:=0; номер точки n:=0.

Основной шаг алгоритма.

А) От текущей точки {x_n,y_n} пользователь выбирает одно из четырех направлений движения v:v[1] = {1,0},  v [2]={0,1}, v[3] ={ –1,0}, v[4] = {0, –1}.

Б) Вычисляем координаты следующей точки {x_n+1,y_n+1}:={x_n,y_n}+hv; интервальный вектор {F([x_n, x_n+1], [y_n, y_n+1]), G([x_n, x_n+1], [y_n, y_n+1])}.

В) Если этот вектор содержит нулевой вектор, то выводим соответствующее сообщение «ДАННОЕ ДВИЖЕНИЕ НЕВОЗМОЖНО» и переходим к п. А), иначе

Г) Вычисляем индекс интервального вектора {F([x_n, x_n+1], [y_n, y_n+1]), G([x_n, x_n+1], [y_n, y_n+1])}, изменение индекса и новое значение S. Полагаем n:=n+1.

Д) Если для хотя бы одного k=0..n-1 будет {x_n,y_n}={x_k,y_k}, то выводим соответствующее сообщение «ГРАНИЦА ОБЛАСТИ ЗАМКНУЛАСЬ», список точек и значение S, запрашиваем: «ПРОДОЛЖАТЬ ИЛИ НАЧАТЬ СНАЧАЛА?».

ИЛЛЮСТРАТИВНЫЙ ПРИМЕР. Система

x- 3=0,

√y- 0.1x-1.7=0

в полуплоскости y³0 (для применения формулы квадратного корня интервала).

Имеем: F([x_-,x₊],[y_-,y₊])=[ x_--3,x₊-3];

G([x_-,x₊],[y_-,y₊])=[ √y_--x₊-1.7,√y₊-x_{_}-1.7].

Направленное округление будем производить до 0.1.

Шаг h=2, начальная точка x₀=2, y₀= 3. S=0.

{F([2,2],[3,3]), G([2,2],[3,3])}= {[-1, -1],[-0.2,-0.1]}, I=225.

1) Пользователь выбирает v= {1,0}, x₁=4,y₁ = 3.

{F([2,4],[3,3]), G([2,4],[3,3])}= {[-1, 1],[-0.4,-0.1]}, I=270. S=45.

2) Пользователь выбирает v= {0,1}, x₂=4,y₂ = 5.

{F([4,4],[3,5]), G([4,4],[3,5])}= {[1, 1],[-0.4,0.2]}, I=0. S=135.

3) Пользователь выбирает v= {-1,0}, x₃=2,y₃ = 5.

{F([2,4],[5,5]), G([2,4],[5,5])}= {[-1, 1],[0.1, 0.4]}, I=90. S=225.

4) Пользователь выбирает v= {0,-1}, x₄=2, y₄ = 3.

{F([2,2],[3,5]), G([2,2],[3,5])}= {[-1, -1],[-0.2,0.4]}, I=180. S=315.

Граница замкнулась. В начальной-конечной точке I=225, S=360 - решение существует.

Заключение

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

Список литературы:

1. Борубаев А.А., Панков П.С. Компьютерное представление кинематических топологических пространств. - Бишкек: Кыргызский государственный национальный университет, 1999. – 131 с.
2. Жораев А.Х. Доказательное кинематическое представление римановой поверхности, определяемой дифференциальным уравнением // Математический журнал, 2008, том 8, № 4. – Алматы: Институт математики Министерства образования и науки РК. – С. 52-58.
3. Панков П.С. Доказательные вычисления на электронных вычислительных машинах. - Фрунзе: Илим, 1978. - 179 с.
4. Панков П.С., Жораев А.Х. Автоматизация метода определения рода римановой поверхности, заданной алгебраическим уравнением // Актуальные проблемы теории управления, топологии и операторных уравнений: Тезисы докладов II международной научной конференции, посвященной 20-летию образования Кыргызско-Российского Славянского университета и 100-летию Я.В.Быкова. – Бишкек, 2013. – С. 155-156.
5. Шокин Ю.И. Интервальный анализ. – Новосибирск: Наука, 1981. – 112 с.
6. Pankov P.S., Joraev A.H. Manned search in kinematical topological spaces  // Reports of the Third Congress of the World Mathematical Society of Turkic countries, Vol. 1. Almaty, June 30 – July 4, 2009. – Almaty: Al-Farabi Kazakh National University, 2009. – Pp. 102-105.