Все выпуски

Любое бинарное отношение σ⊆X (где X - произвольное множество) порождает на множестве X² характеристическую функцию: если (x,y)∈σ, то σ(x,y)=1, а иначе σ(x,y)=0. В терминах характеристических функций на множестве всех бинарных отношений множества X вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар различных смежных бинарных отношений. Если X - конечное множество, то эта алгебраическая система - граф («граф графов»).

Показано, что если σ и τ - смежные отношения, то σ является частичным порядком тогда и только тогда, когда τ является частичным порядком. Исследованы некоторые особенности строения графа G(X) частичных порядков. В частности, если X состоит из n элементов, а T₀(n) - это число помеченных T₀-топологий, определенных на множестве X, то количество вершин в графе G(X) равно T₀(n), а количество компонент связности равно T₀(n-1).

Для всякого отношения частичного порядка σ определяется понятие его опорного множества S(σ), являющегося некоторым подмножеством множества X. Если X - конечное множество, а частичные порядки σ и τ принадлежат одной и той же компоненте связности графа G(X), то равенство S(σ)=S(τ) имеет место тогда и только тогда, когда σ=τ. Показано, что в каждой компоненте связности графа G(X) совокупность опорных множеств ее элементов является специфическим частично упорядоченным множеством относительно естественного отношения включения множеств.

Any binary relation σ⊆X (where X is an arbitrary set) generates a characteristic function on the set X²: if (x,y)∈σ, then σ(x,y)=1, otherwise σ(x,y)=0. In terms of characteristic functions on the set of all binary relations of the set X we introduced the concept of a binary reflexive relation of adjacency and determined the algebraic system consisting of all binary relations of a set and of all unordered pairs of various adjacent binary relations. If X is finite set then this algebraic system is a graph (“a graph of graphs”).

It is shown that if σ and τ are adjacent relations then σ is a partial order if and only if τ is a partial order. We investigated some features of the structure of the graph G(X) of partial orders. In particular, if X consists of n elements, and T₀(n) is the number of labeled T₀-topologies defined on the set X, then the number of vertices in a graph G(X) is T₀(n), and the number of connected components is T₀(n-1).

For any partial order σ there is defined the notion of its support set S(σ), which is some subset of X. If X is finite set, and partial orders σ and τ belong to the same connected component of the graph G(X), then the equality S(σ)=S(τ) holds if and only if σ=τ. It is shown that in each connected component of the graph G(X) the union of support sets of its elements is a specific partially ordered set with respect to natural inclusion relation of sets.

Любое бинарное отношение $\sigma\subseteq X^2$ (где $X$ - произвольное множество) порождает на множестве $X^2$ характеристическую функцию: если $(x,y)\in\sigma,$ то $\sigma(x,y)=1,$ а иначе $\sigma(x,y)=0.$ В терминах характеристических функций на множестве всех бинарных отношений множества $X$ вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар различных смежных бинарных отношений. Если $X$ - конечное множество, то эта алгебраическая система - граф («граф графов»).
Показано, что если $\sigma$ и $\tau$ - смежные отношения, то $\sigma$ является рефлексивно-транзитивным отношением тогда и только тогда, когда $\tau$ является рефлексивно-транзитивным отношением. Исследованы некоторые особенности строения графа $G(X)$ рефлексивно-транзитивных отношений. В частности, если $X$ состоит из $n$ элементов, а $T_0(n)$ - это число помеченных $T_0$-топологий, определенных на множестве $X,$ то количество компонент связности равно $\sum_{m=1}^n S(n,m) T_0(m-1),$ где $S(n,m)$ - числа Стирлинга 2-го рода. $($Хорошо известно, что количество вершин в графе $G(X)$ равно $\sum_{m=1}^nS(n,m) T_0(m).)$

Any binary relation $\sigma\subseteq X^2$ (where $X$ is an arbitrary set) generates on the set $X^2$ a characteristic function: if $(x,y)\in\sigma,$ then $\sigma(x,y)=1,$ otherwise $\sigma(x,y)=0.$ In terms of characteristic functions we introduce on the set of all binary relations of the set $X$ the concept of a binary reflexive relation of adjacency and determine an algebraic system consisting of all binary relations of the set and of all unordered pairs of various adjacent binary relations. If $X$ is a finite set then this algebraic system is a graph (“the graph of graphs’’).
It is shown that if $\sigma$ and $\tau$ are adjacent relations then $\sigma$ is a reflexive-transitive relation if and only if $\tau$ is a reflexive-transitive relation. Several structure features of the graph $G(X)$ of reflexive-transitive relations are investigated. In particular, if $X$ consists of $n$ elements, and $T_0(n)$ is the number of labeled $T_0$-topologies defined on the set $X,$ then the number of connected components is equal to $\sum_{m=1}^nS(n,m) T_0(m-1),$ where $S(n,m)$ are Stirling numbers of second kind. $($It is well known that the number of vertices in a graph $G(X)$ is equal to $\sum_{m=1}^nS(n,m) T_0(m).)$

В терминах характеристических функций на множестве всех бинарных отношений множества $X$ вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар смежных бинарных отношений. Если $X$ — конечное множество, то эта алгебраическая система — граф («граф графов»). Доказано, что диаметр графа бинарных отношений равен 2. Показано, что если $\sigma$ и $\tau$ — смежные отношения, то $\sigma$ — ациклическое отношение (конечный ациклический орграф) тогда и только тогда, когда $\tau$ — ациклическое отношение. Получена явная формула для числа компонент связности графа ациклических отношений.

The paper introduces the concept of a binary reflexive relation of adjacency on the set of all binary relations of a set $X$ (in terms of characteristic functions) and determines an algebraic system consisting of all binary relations of the set and of all unordered pairs of adjacent binary relations. If $X$ is a finite set then this algebraic system is a graph (“the graph of graphs”). It is proved that the diameter of a graph of binary relations is 2. It is shown that if $\sigma$ and $\tau$ are adjacent relations, then $\sigma$ is an acyclic relation (finite acyclic digraph) if and only if $\tau$ is an acyclic relation. An explicit formula for the number of connected components of a graph of acyclic relations is received

В предыдущих работах авторов на множестве всех бинарных отношений множества $X$ введено понятие бинарного рефлексивного отношения смежности и определена алгебраическая система, состоящая из всех бинарных отношений множества $X$ и из всех неупорядоченных пар смежных бинарных отношений. Если $X$ - конечное множество, то эта алгебраическая система - граф (граф бинарных отношений $G$). В настоящей работе для ациклических и транзитивных орграфов вводится понятие опорного множества: это совокупности $S(\sigma)$ и $S'(\sigma)$, состоящие из вершин орграфа $\sigma\in G$, имеющих нулевую полустепень захода и исхода соответственно. Доказано, что если $G_\sigma$ - связная компонента графа $G$, содержащая ациклический или транзитивный орграф $\sigma\in G$, то $\{S(\tau): \tau\in G_\sigma\}=\{S'(\tau): \tau\in G_\sigma\}$. Получена формула для числа транзитивных орграфов, имеющих фиксированное опорное множество. Аналогичная формула для числа ациклических орграфов, имеющих фиксированное опорное множество, получена авторами ранее.

In previous works of the authors, the concept of a binary reflexive adjacency relation was introduced on the set of all binary relations of the set $X$, and an algebraic system consisting of all binary relations of the set $X$ and of all unordered pairs of adjacent binary relations was defined. If $X$ is a finite set, then this algebraic system is a graph (graph of binary relations $G$). The current paper introduces the notion of a support set for acyclic and transitive digraphs. This is the collections $S(\sigma)$ and $S'(\sigma)$ consisting of the vertices of the digraph $\sigma\in G$ that have zero indegree and zero outdegree, respectively. It is proved that if $G_\sigma $ is a connected component of the graph $G$ containing the acyclic or transitive digraph $\sigma\in G$, then $\{S(\tau): \tau\in G_\sigma\}=\{S'(\tau): \tau\in G_\sigma\}$. A formula for the number of transitive digraphs having a fixed support set is obtained. An analogous formula for the number of acyclic digraphs having a fixed support set was obtained by the authors earlier.

Рассматривается биркгофова интерполяция функции двух переменных многочленами степени $2k+1$ по совокупности двух переменных на треугольнике. Подобные оценки автоматически переносятся на оценки погрешности метода конечных элементов, с которым тесно связаны. Оценки погрешности аппроксимации для производных функции в предложенных конечных элементах зависят только от диаметра разбиения и не зависят от углов триангуляции. Показана неулучшаемость полученных оценок погрешности аппроксимации функции и ее частных производных. Неулучшаемость понимается в том смысле, что существует функция из заданного класса и существуют абсолютные положительные константы, не зависящие от триангуляции, такие, что для любого невырожденного треугольника справедливы оценки снизу. В данной работе для рассматриваемых интерполяционных условий предлагается набор конкретных функций, позволяющих получить соответствующие оценки погрешности для определенных частных производных.

The paper considers Birkhoff-type triangle-based interpolation of two-variable function by polynomials of $2k+1$ degree by set of two variables. Similar estimates are automatically transferred to error estimates of related finite element method. The approximation error estimates of derivatives for the given finite elements depend only on the decomposition diameter, and do not depend on triangulation angles. We show that obtained approximation error estimates for a function and its partial derivatives are unimprovable. Unimprovability is understood in a following sense: there exists a function from the given class and there exist absolute positive constants independent of triangulation such that for any nondegenerate triangle estimates from below are valid. In this work, a system of specific functions is offered for interpolation conditions. These functions allow to obtain corresponding error estimates for definite partial derivatives.

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

The abstract problem of control and its relaxations connected with a weakening of constraints on the choice of programmed strategies are considered. Relations connecting the sets of admissible elements of the initial problem and its extension are investigated. Conditions sufficient for the stability of the initial attainable set (with the exactness until a closure) are obtained.

Изучаются свойства дискретной вариационной задачи динамической аппроксимации в комплексном евклидовом (L + 1)-мерном пространстве E. Она обобщает известные задачи среднеквадратической полиномиальной аппроксимации функций, заданных своими отсчетами в конечном интервале. В рассматриваемой задаче аппроксимация последовательности y = {y_i}_L⁰ отсчетов функции y(t) ∈ L²[0, T], T = Lh на сетке I_h осуществляется решениями однородных линейных дифференциальных или разностных уравнений заданного порядка n с постоянными, но, возможно, неизвестными коэффициентами. Тем самым показано, что в последнем случае задача аппроксимации включает в себя и задачу идентификации. Анализ ее особенностей - основная тема статьи. Ставится задача нахождения вектора коэффициентов  разностного уравнения Σ_n⁰ ŷ_i+k α_i = 0, где k = 0,L − n. Оптимизируются коэффициенты  и начальные условия переходного процесса y этого уравнения. Цель оптимизации - наилучшая аппроксимация исследуемого динамического процесса y ∈ E. Критерий аппроксимации  минимум величины ||y − ŷ||²_E. Показано, что изучаемая вариационная задача сводится к задачам проектирования в E вектора y на ядра разностных операторов с неизвестными коэффициентами α ∈ ω ⊂ S ⊂ Eⁿ⁺¹. Здесь α - направление, S - сфера или гиперплоскость. Показана связь изучаемой задачи с задачами дискретизации и идентифицируемости. Тогда координаты вектора y ∈ E есть точное решение дифференциального уравнения на сетке I_h и y = ŷ. Дано сравнение изучаемой задачи вариационной идентификации с алгебраическими методами идентификации. Показано, что ортогональные дополнения к ядрам разностных операторов всегда имеют теплицев базис. Это приводит к быстрым проекционным алгоритмам вычислений. Показано, что задача нахождения оптимального вектора α сводится к задаче безусловной минимизации функционала идентификации, зависящего от направления  в Eⁿ⁺¹. Предложена итерационная процедура его минимизации на сфере с широкой областью и высокой скоростью сходимости. Изучаемую вариационную задачу можно применять при математическом моделировании в управлении и научных исследованиях. При этом на конечных интервалах может использоваться, в частности, возможность кусочно-линейной динамической аппроксимации сложных динамических процессов разностными и дифференциальными уравнениями указанного типа.

Some properties of the discrete variational problem of the dynamic approximation in the complex Euclidean (L + 1)-dimensional space are studied here. It generalizes familiar problems of the mean square polynomial approximation of the functions given on the finite interval in accordance with their references. In the problem under consideration sequence approximation y = {y_i}_L⁰ of the references of the function y(t) ∈ L²[0, T], T = Lh on the lattice I_h is achieved by solving homogeneous linear differential equations or difference equations of the given order n with constant but possibly unknown coefficients. Thus, it is shown that in the latter case the approximation problem also includes the identification problem. The analysis of its properties is the main subject of the article. The problem is set to find vector of coefficients  of difference equation Σ_n⁰ ŷ_i+k α_i = 0, where k = 0,L − n. Coefficients  and initial conditions of the transient process by of this equation are optimized. The optimization purpose is to achieve the best approximation of the dynamic process y ∈ E being considered here. The approximation criterion is a minimum of the quantity ||y − ŷ||²_E. The variational problem under study is shown to be reduced to the problem of projecting vector y in E on the kernels of the difference operators with unknown coefficients  α ∈ ω ⊂ S ⊂ Eⁿ⁺¹, where  is a direction, S is a sphere or a hyperplane. The problem under study is shown to be related to the problems of the discretization and identifiability. In this case vector coordinates y ∈ E is an exact solution of differential equation on the lattice I_h and y = ŷ. The problem of the variational identification is compared with algebraic methods of identification. The orthogonal complement to the kernels of the difference operators are shown to always have Toeplitz basis. This results in fast projecting algorithms of computation. The problem of finding optimal vector α is shown to be reduced to the problem of the absolute minimization of the identification functional depending on the direction  in Eⁿ⁺¹. The iterative procedure of its minimization on a sphere with wide domain and high speed of convergence is presented here. The variational problem considered here can be applied in mathematical modeling for control problem and research purposes. On the finite intervals, for example, it is possible to use piecewise-linear dynamic approximations of the complex dynamic processes with difference and differential equations of the specified type.

На основе известных свойств функции вероятности протекания простой кубической решётки размера L=2 в приближении линейной связи порога протекания бесконечной решётки x_c и среднего значения x_cL конечной решётки введена нескейлинговая функция вероятности протекания для решётки размера L>2. Показано, что на пороге протекания нескейлинговые вероятности для всех ПК решёток одинаковы.
Компьютерные эксперименты на основе метода Монте-Карло согласуются с предлагаемой в работе теорией.

Using known properties of the probability function for passing in a simple cubic lattice with L=2 in approximation of a linear relation between a passing threshold of an infinite lattice x_c and average value x_cL of a finite lattice, we introduce a nonscaling probability function of passing of a lattice with L>2. We show that on the passing threshold nonscaling probabilities for all simple cubic lattices are the same.
Computer experiments based on the Monte-Carlo method are in agreement with the theory proposed.

Рассматриваются конструкции, связанные с представлением свободных $\sigma$-мультипликативных ультрафильтров широко понимаемых измеримых пространств. В основе построений находятся представления, связанные с применением открытых ультрафильтров в случаях кофинитной и косчетной топологий. Такие ультрафильтры сохраняются (как максимальные фильтры) при замене топологий соответственно алгеброй и $\sigma$-алгеброй, порожденных упомянутыми топологиями. В (основном) случае косчетной топологии устанавливается единственность $\sigma$-мультипликативного свободного ультрафильтра, составленного из непустых открытых множеств. Показано, что данное свойство сохраняется для $\sigma$-алгебр, содержащих косчетную топологию. Указаны две топологии пространства ограниченных конечно-аддитивных борелевских мер, для которых ультрафильтр непустых открытых множеств определяет одноэлементный нарост секвенциально замкнутого множества мер Дирака, возникающий при построении замыкания.

Constructions related to the representation of free $\sigma$-multiplicative ultrafilters of widely interpreted measurable spaces are considered. These constructions are based on the representations connected with the application of open ultrafilters for co-finite and co-countable topologies. Such ultrafilters are preserved (as maximal filters) under the replacement of topologies by algebra and $\sigma$-algebra generated by above-mentioned topologies, respectively. In (general) case of co-countable topology, uniqueness of $\sigma$-multiplicative free ultrafilter composed of nonempty open sets is established. It is demonstrated that the given property is preserved for $\sigma$-algebras containing co-countable topology. Two topologies of the space of bounded finitely additive Borel measures with the property of uniqueness of remainder for sequentially closed set of Dirac measures under the closure construction are stated.

Рассматривается нелинейная управляемая система в конечномерном евклидовом пространстве, заданная на конечном промежутке времени. Изучается одна из основных задач математической теории управления - задача о сближении фазового вектора управляемой системы с компактным целевым множеством в фазовом пространстве в фиксированный момент времени. В этой работе в качестве целевого множества выбрано множество Лебега скалярной липшицевой функции, определенной на фазовом пространстве. Упомянутая задача о сближении тесно связана с многими важными и ключевыми задачами теории управления, в частности с задачей об оптимальном по быстродействию приведении управляемой системы на целевое множество. Из-за сложности задачи о сближении для нетривиальных управляемых систем аналитическое представление решений невозможно даже для относительно простых управляемых систем. Поэтому в настоящей работе мы изучаем прежде всего вопросы, связанные с конструированием приближенного решения задачи о сближении. Конструирование приближенного решения тем методом, который изложен в работе, связано прежде всего с конструированием интегральной воронки управляемой системы, представленной в так называемом «обратном» времени. К настоящему времени известно несколько алгоритмов конструирования разрешающего программного управления в задаче о сближении. Здесь представлен алгоритм построения управления, основанный на максимальном притяжении движения системы к множеству разрешимости задачи о сближении. В работе приведены примеры.

We consider a nonlinear controlled system in a finite-dimensional Euclidean space defined on a finite time interval. One of the main problems of mathematical control theory is studied: the problem of approaching a phase vector of a controlled system with a compact target set in the phase space at a fixed time instant. In this paper, a Lebesgue set of a scalar Lipschitz function defined on the phase space is a target set. The mentioned approach problem is closely connected with many important and key problems of control theory and, in particular, with the problem of optimally reducing a controlled system to a target set. Due to the complexity of the approach problem for nontrivial controlled systems, an analytical representation of solutions is impossible even for relatively simple controlled systems. Therefore, in the present work, we study first of all the issues related to the construction of an approximate solution of the approach problem. The construction of an approximate solution by the method described in the paper is primarily concerned with the design of the integral funnel of the controlled system, presented in the so-called “reverse” time. To date, there are several algorithms for constructing a resolving program control in the approach problem. This paper presents an algorithm for constructing a control based on the maximum attraction of the system's motion to the solvability set of the approach problem. Examples are provided.