Все выпуски

The grid-characteristic method is a promising numerical method for solving hyperbolic systems of equations, e.g., equations describing elastic and acoustic waves. This method has high precision and allows physically correct simulations of wave processes in heterogeneous media. The grid-characteristic method makes it possible to correctly take into account boundary conditions and conditions on surfaces with different physical characteristics. The method offers the greatest advantages for one-dimensional equations, especially in combination with a fixed difference grid, as in conventional grid-based methods. However, in the multidimensional case using the algorithms of splitting with respect to spatial variables, the author has managed to preserve its positive qualities. The use of the method of Runge–Kutta type, or the integro-interpolation method for hyperbolic equations makes it possible to effectively carry out a generalization of methods developed for linear equations, in the nonlinear case, in particular, to enforce the difference analogs of the conservation laws, which is important for shock-capturing, for example, discontinuous solutions. Based on the author’s variant of the grid-characteristic method, several important problems of seismic prospecting, seismic resistance, global seismic studies on Earth and Mars, medical applications, nondestructive testing of railway lines, the simulation of the creation and characteristics of composite materials for the aerospace industry and other areas of practical application were numerically solved. A significant advantage of the constructed method is the preservation of its stability and precision at the strains of the environment. This article presents the results of a numerical solution based on the grid-characteristic method to the problem of modeling elastic-plastic deformation in traumatic brain injury.

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

В квадратичном случае формальное решение демонстрирует контринтуитивное поведение. Оно заключается в том, что решение однозначно определено лишь на части бесконечной полуплоскости, обращается в нуль вместе со всеми производными на границе и неоднозначно при переходе за границу. Если продолжить его на другую область в соответствии с аналитическим решением, то оно имеет двухгорбый вид, сохраняет количество вещества и, что лишено физического смысла, периодично во времени. Если продолжить его нулем, то нарушается свойство консервативности. Аномальности квадратичного случая дается объяснение, хотя и нестрогое, через аналогию движения материальной точки с ускорением, пропорциональным квадрату скорости. Здесь мы имеем дело с математическим курьезом. Для всех случаев приведены численные расчеты. Дополнительно рассчитываются энтропия вероятностного распределения и функция надежности, а также прослеживается их корреляционная связь.

Verification of the physical-statistical approach within reliability theory for the simplest cases was carried out, which showed its validity. An analytical solution of the one-dimensional basic equation of the physicalstatistical approach is presented under the assumption of a stationary degradation rate. From a mathematical point of view this equation is the well-known continuity equation, where the role of density is played by the density distribution function of goods in its characteristics phase space, and the role of fluid velocity is played by intensity (rate) degradation processes. The latter connects the general formalism with the specifics of degradation mechanisms. The cases of coordinate constant, linear and quadratic degradation rates are analyzed using the characteristics method. In the first two cases, the results correspond to physical intuition. At a constant rate of degradation, the shape of the initial distribution is preserved, and the distribution itself moves equably from the zero. At a linear rate of degradation, the distribution either narrows down to a narrow peak (in the singular limit), or expands, with the maximum shifting to the periphery at an exponentially increasing rate. The distribution form is also saved up to the parameters. For the initial normal distribution, the coordinates of the largest value of the distribution maximum for its return motion are obtained analytically.

In the quadratic case, the formal solution demonstrates counterintuitive behavior. It consists in the fact that the solution is uniquely defined only on a part of an infinite half-plane, vanishes along with all derivatives on the boundary, and is ambiguous when crossing the boundary. If you continue it to another area in accordance with the analytical solution, it has a two-humped appearance, retains the amount of substance and, which is devoid of physical meaning, periodically over time. If you continue it with zero, then the conservativeness property is violated. The anomaly of the quadratic case is explained, though not strictly, by the analogy of the motion of a material point with an acceleration proportional to the square of velocity. Here we are dealing with a mathematical curiosity. Numerical calculations are given for all cases. Additionally, the entropy of the probability distribution and the reliability function are calculated, and their correlation is traced.

В данной работе рассматривается задача восстановления матрицы корреспонденций для наблюдений реальных корреспонденций в г. Москве. Следуя общепринятому подходу [Гасников и др., 2013], транспортная сеть рассматривается как ориентированный граф, дуги которого соответствуют участкам дороги, а вершины графа — районы, из которых выезжают / в которые въезжают участники движения. Число жителей города считается постоянным. Задача восстановления матрицы корреспонденций состоит в расчете всех корреспонденций израйона $i$ в район $j$.

Для восстановления матрицы предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийная модель. В работе, в соответствии с работой [Вильсон, 1978], приводится описание эволюционного обоснования энтропийной модели, описывается основная идея перехода к решению задачи энтропийно-линейного программирования (ЭЛП) при расчете матрицы корреспонденций. Для решения полученной задачи ЭЛП предлагается перейти к двойственной задаче и решать задачу относительно двойственных переменных. В работе описывается несколько численных методов оптимизации для решения данной задачи: алгоритм Синхорна и ускоренный алгоритм Синхорна. Далее приводятся численные эксперименты для следующих вариантов функций затрат: линейная функция затрат и сумма степенной и логарифмической функции затрат. В данных функциях затраты представляют из себя некоторую комбинацию среднего времени в пути и расстояния между районами, которая зависит от параметров. Для каждого набора параметров функции затрат рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Мы предполагаем, что шум в восстановленной матрице корреспонденций является гауссовским, в результате в качестве метрики качества выступает среднеквадратичное отклонение. Данная задача представляет из себя задачу невыпуклой оптимизации. В статье приводится обзор безградиенных методов оптимизации для решения невыпуклых задач. Так как число параметров функции затрат небольшое, для определения оптимальных параметров функции затрат было выбрано использовать метод перебора по сетке значений. Таким образом, для каждого набора параметров рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Далее по минимальному значению невязки для каждой функции затрат определяется, для какой функции затрат и при каких значениях параметров восстановленная матрица наилучшим образом описывает реальные корреспонденции.

In this paper, we consider the problem of restoring the correspondence matrix based on the observations of real correspondences in Moscow. Following the conventional approach [Gasnikov et al., 2013], the transport network is considered as a directed graph whose edges correspond to road sections and the graph vertices correspond to areas that the traffic participants leave or enter. The number of city residents is considered constant. The problem of restoring the correspondence matrix is to calculate all the correspondence from the $i$ area to the $j$ area.

To restore the matrix, we propose to use one of the most popular methods of calculating the correspondence matrix in urban studies — the entropy model. In our work, which is based on the work [Wilson, 1978], we describe the evolutionary justification of the entropy model and the main idea of the transition to solving the problem of entropy-linear programming (ELP) in calculating the correspondence matrix. To solve the ELP problem, it is proposed to pass to the dual problem. In this paper, we describe several numerical optimization methods for solving this problem: the Sinkhorn method and the Accelerated Sinkhorn method. We provide numerical experiments for the following variants of cost functions: a linear cost function and a superposition of the power and logarithmic cost functions. In these functions, the cost is a combination of average time and distance between areas, which depends on the parameters. The correspondence matrix is calculated for multiple sets of parameters and then we calculate the quality of the restored matrix relative to the known correspondence matrix.

We assume that the noise in the restored correspondence matrix is Gaussian, as a result, we use the standard deviation as a quality metric. The article provides an overview of gradient-free optimization methods for solving non-convex problems. Since the number of parameters of the cost function is small, we use the grid search method to find the optimal parameters of the cost function. Thus, the correspondence matrix calculated for each set of parameters and then the quality of the restored matrix is evaluated relative to the known correspondence matrix. Further, according to the minimum residual value for each cost function, we determine for which cost function and at what parameter values the restored matrix best describes real correspondence.

Большой класс задач описывает физические процессы, протекающие в невыпуклых областях, содержащих угол больший 180 градусов на границе. Решение в окрестности такого угла сингулярно, а его отыскание, при использовании классических подходов, влечет за собой потерю точности. В представленной работе рассмотрены стационарные, линеаризованные с помощью итераций Пикара несжимаемые уравнения Навье – Стокса течения вязкой жидкости в конвективной форме в $L$-образной области. Определено $R_\nu$-обобщенное решение задачи в специальных множествах весовых пространств. Для нахождения приближенного $R_\nu$-обобщенного решения построен специальный метод конечных элементов. Во-первых, пространства конечно-элементных функций удовлетворяют закону сохранения массы в сильном смысле, то есть в узлах сетки. Для этой цели используется Скотт – Вогелиус конечно-элементная пара. Выполнение закона сохранения массы ведет к отысканию более точного с физической точки зрения решения. Во-вторых, базисные функции конечномерных пространств дополнены весовыми функциями как множителями, которые совпадают с расстоянием от точки до вершины тупого угла в $\delta$-окрестности точки сингулярности и радиусом $\delta$ вне ее. Степень весовой функции, как и параметр $\nu$ в определении $R_\nu$-обобщенного решения, так и радиус $\delta$-окрестности точки сингулярности являются свободными параметрами метода. Специально подобранная их комбинация приводит к увеличению порядка сходимости приближенного решения к точному решению задачи почти в два раза по сравнению с классическими подходами и достигает единицы по шагу сетки в нормах весовых пространств Соболева. Таким образом, установлено, что скорость сходимости не зависит от величины угла.

An essential class of problems describes physical processes occurring in non-convex domains containing a corner greater than 180 degrees on the boundary. The solution in a neighborhood of a corner is singular and its finding using classical approaches entails a loss of accuracy. In the paper, we consider stationary, linearized by Picard’s iterations, Navier – Stokes equations governing the flow of a incompressible viscous fluid in the convection form in $L$-shaped domain. An $R_\nu$-generalized solution of the problem in special sets of weighted spaces is defined. A special finite element method to find an approximate $R_\nu$-generalized solution is constructed. Firstly, functions of the finite element spaces satisfy the law of conservation of mass in the strong sense, i.e. at the grid nodes. For this purpose, Scott – Vogelius element pair is used. The fulfillment of the condition of mass conservation leads to the finding more accurate, from a physical point of view, solution. Secondly, basis functions of the finite element spaces are supplemented by weight functions. The degree of the weight function, as well as the parameter $\nu$ in the definition of an $R_\nu$-generalized solution, and a radius of a neighborhood of the singularity point are free parameters of the method. A specially selected combination of them leads to an increase almost twice in the order of convergence rate of an approximate solution to the exact one in relation to the classical approaches. The convergence rate reaches the first order by the grid step in the norms of Sobolev weight spaces. Thus, numerically shown that the convergence rate does not depend on the corner value.

В статье рассматривается задача минимизации математического ожидания выпуклой функции. Задачи такого вида повсеместны в машинном обучении, а также часто возникают в ряде других приложений. На практике для их решения обычно используются процедуры типа стохастического градиентного спуска (SGD). В нашей работе предлагается решать такие задачи с использованием метода эллипсоидов с мини-батчингом. Алгоритм имеет линейную скорость сходимости и может оказаться эффективнее SGD в ряде задач. Это подтверждается в наших экспериментах, исходный код которых находится в открытом доступе. Для получения линейной скорости сходимости метода не требуется ни гладкость, ни сильная выпуклость целевой функции. Таким образом, сложность алгоритма не зависит от обусловленности задачи. В работе доказывается, что метод эллипсоидов с наперед заданной вероятностью находит решение с желаемой точностью при использовании мини-батчей, размер которых пропорционален точности в степени -2. Это позволяет выполнять алгоритм параллельно на большом числе процессоров, тогда как возможности для батчараллелизации процедур типа стохастического градиентного спуска весьма ограничены. Несмотря на быструю сходимость, общее количество вычислений градиента для метода эллипсоидов может получиться больше, чем для SGD, который неплохо сходится и при маленьком размере батча. Количество итераций метода эллипсоидов квадратично зависит от размерности задачи, поэтому метод подойдет для относительно небольших размерностей.

The article considers minimization of the expectation of convex function. Problems of this type often arise in machine learning and a variety of other applications. In practice, stochastic gradient descent (SGD) and similar procedures are usually used to solve such problems. We propose to use the ellipsoid method with mini-batching, which converges linearly and can be more efficient than SGD for a class of problems. This is verified by our experiments, which are publicly available. The algorithm does not require neither smoothness nor strong convexity of the objective to achieve linear convergence. Thus, its complexity does not depend on the conditional number of the problem. We prove that the method arrives at an approximate solution with given probability when using mini-batches of size proportional to the desired accuracy to the power −2. This enables efficient parallel execution of the algorithm, whereas possibilities for batch parallelization of SGD are rather limited. Despite fast convergence, ellipsoid method can result in a greater total number of calls to oracle than SGD, which works decently with small batches. Complexity is quadratic in dimension of the problem, hence the method is suitable for relatively small dimensionalities.

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

В первой части статьи мы рассматриваем два класса «хороших» невыпуклых функций, которые могут быть ограничены снизу и сверху параболической функцией. Такой класс задач не исследован широко в литературе, хотя является довольно интересным с прикладной точки зрения. Более того, для таких задач методы первого и более высоких порядков могут быть абсолютно неэффективны при поиске глобального минимума. Это связано с тем, что функция может сильно осциллировать или может быть сильно зашумлена. Поэтому наши новые методы используют информацию только нулевого порядка и основаны на поиске по сетке. Размер и мелкость этой сетки, а значит, и гарантии скорости сходимости и оракульной сложности зависят от «хорошести» задачи. В частности, мы показываем, если функция зажата довольно близкими параболическими функциями, то сложность не зависит от размерности задачи. Мы показываем, что наши новые методы сходятся с линейной скоростью сходимости $\log(1/\varepsilon)$ к глобальному минимуму на кубе.

Во второй части статьи мы рассматриваем задачу невыпуклой оптимизации с другого ракурса. Мы предполагаем, что целевая минимизируемая функция есть сумма выпуклой квадратичной задачи и невыпуклой «шумовой» функции, пропорциональной по модулю расстоянию до глобального решения. Рассмотрение функций с такими предположениями о шуме для методов нулевого порядка является новым в литературе. Для такой задачи мы используем классический безградиентный подход с аппроксимацией градиента через конечную разность. Мы показываем, как можно свести анализ сходимости для нашей задачи к стандартному анализу для задач выпуклой оптимизации. В частности, и для таких задач мы добиваемся линейной скорости сходимости.

Экспериментальные результаты подтверждают работоспособность и практическую применимость всех полученных методов.

Finding the global minimum of a nonconvex function is one of the key and most difficult problems of the modern optimization. In this paper we consider special classes of nonconvex problems which have a clear and distinct global minimum.

In the first part of the paper we consider two classes of «good» nonconvex functions, which can be bounded below and above by a parabolic function. This class of problems has not been widely studied in the literature, although it is rather interesting from an applied point of view. Moreover, for such problems first-order and higher-order methods may be completely ineffective in finding a global minimum. This is due to the fact that the function may oscillate heavily or may be very noisy. Therefore, our new methods use only zero-order information and are based on grid search. The size and fineness of this grid, and hence the guarantee of convergence speed and oracle complexity, depend on the «goodness» of the problem. In particular, we show that if the function is bounded by fairly close parabolic functions, then the complexity is independent of the dimension of the problem. We show that our new methods converge with a linear convergence rate $\log(1/\varepsilon)$ to a global minimum on the cube.

In the second part of the paper, we consider the nonconvex optimization problem from a different angle. We assume that the target minimizing function is the sum of the convex quadratic problem and a nonconvex «noise» function proportional to the distance to the global solution. Considering functions with such noise assumptions for zero-order methods is new in the literature. For such a problem, we use the classical gradient-free approach with gradient approximation through finite differences. We show how the convergence analysis for our problems can be reduced to the standard analysis for convex optimization problems. In particular, we achieve a linear convergence rate for such problems as well.

Experimental results confirm the efficiency and practical applicability of all the obtained methods.

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

Корректирующие функции берутся одинаковыми для всех шагов. В общем случае для расчетов на больших интервалах времени используются 4 или 5 корректирующих функций: в первом наборе — базовые степенные функции от 2-й до 4-й или 5-й степеней; во втором наборе — образованные из базовых функций ортогональные степенные полиномы; в третьем наборе — образованные из базовых функций специальные линейно независимые многочлены с конечными условиями, упрощающими «стыковку» решений на следующих шагах.

На двух примерах расчета нелинейных колебаний систем с одной и с двумя степенями свободы выполнены численные исследования точности численного решения начальных задач на различных интервалах времени по методу Галёркина с использованием указанных наборов степенных корректирующих функций. Выполнены сравнения результатов, полученных по методу Галёркина и по методам Адамса и Рунге – Кутты четвертого порядка. Показано, что методом Галёркина можно получить достоверные результатына значительно больших интервалах времени, чем по методам Адамса и Рунге – Кутты.

A nonlinear oscillatory system described by ordinary differential equations with variable coefficients is considered, in which terms that are linearly dependent on coordinates, velocities and accelerations are explicitly distinguished; nonlinear terms are written as implicit functions of these variables. For the numerical solution of the initial problem described by such a system of differential equations, the one-step Galerkin method is used. At the integration step, unknown functions are represented as a sum of linear functions satisfying the initial conditions and several given correction functions in the form of polynomials of the second and higher degrees with unknown coefficients. The differential equations at the step are satisfied approximately by the Galerkin method on a system of corrective functions. Algebraic equations with nonlinear terms are obtained, which are solved by iteration at each step. From the solution at the end of each step, the initial conditions for the next step are determined.

The corrective functions are taken the same for all steps. In general, 4 or 5 correction functions are used for calculations over long time intervals: in the first set — basic power functions from the 2nd to the 4th or 5th degrees; in the second set — orthogonal power polynomials formed from basic functions; in the third set — special linear-independent polynomials with finite conditions that simplify the “docking” of solutions in the following steps.

Using two examples of calculating nonlinear oscillations of systems with one and two degrees of freedom, numerical studies of the accuracy of the numerical solution of initial problems at various time intervals using the Galerkin method using the specified sets of power-law correction functions are performed. The results obtained by the Galerkin method and the Adams and Runge –Kutta methods of the fourth order are compared. It is shown that the Galerkin method can obtain reliable results at significantly longer time intervals than the Adams and Runge – Kutta methods.

Предложен численный метод, аппроксимирующий уравнения динамики слабосжимаемого вязкого течения при наличии полимерной составляющей потока. Исследуется поведение течения под воздействием статической внешней периодической силы в периодической квадратной ячейке. Методика основывается на гибридном подходе. Гидродинамика течения описывается системой уравнений Навье – Стокса и численно аппроксимируется линеаризованным методом Годунова. Полимерное поле описывается системой уравнений для вектора растяжений полимерных молекул $\bf R$, которая численно аппроксимируются методом Курганова – Тедмора. Выбор модельных соотношений при разработке численной методики и подбор параметров моделирования позволили на качественном уровне смоделировать и исследовать режим эластической турбулентности при низких числах Рейнольдса $Re \sim 10^{-1}$. Уравнения динамики течения полимерного раствора отличаются от уравнений динамики ньютоновской жидкости наличием в правой части членов, описывающих силы, действующие со стороны полимерной компоненты. Коэффициент пропорциональности $A$ при данных членах характеризует степень обратного влияния количества полимеров на поток. В статье подробно исследуется влияние этого коэффициента на структуру и характеристики потока. Показано, что с его ростом течение становится более хаотическим. Построены энергетические спектры полученных течений и спектры полей растяжения полимеров для различных величин коэффициента $A$. В спектрах прослеживается инерциальный поддиапа- зон энергетического каскада для скорости течения с показателем $k \sim −4$, для каскада растяжений полимерных молекул с показателем $−1,6$.

A numerical method is proposed that approximates the equations of the dynamics of a weakly compressible viscous flow in the presence of a polymer component of the flow. The behavior of the flow under the influence of a static external periodic force in a periodic square cell is investigated. The methodology is based on a hybrid approach. The hydrodynamics of the flow is described by a system of Navier – Stokes equations and is numerically approximated by the linearized Godunov method. The polymer field is described by a system of equations for the vector of stretching of polymer molecules $\bf R$, which is numerically approximated by the Kurganov – Tedmor method. The choice of model relationships in the development of a numerical methodology and the selection of modeling parameters made it possible to qualitatively model and study the regime of elastic turbulence at low Reynolds $Re \sim 10^{-1}$. The polymer solution flow dynamics equations differ from the Newtonian fluid dynamics equations by the presence on the right side of the terms describing the forces acting on the polymer component part. The proportionality coefficient $A$ for these terms characterizes the backward influence degree of the polymers number on the flow. The article examines in detail how the flow and its characteristics change depending on the given coefficient. It is shown that with its growth, the flow becomes more chaotic. The flow energy spectra and the spectra of the polymers stretching field are constructed for different values of $A$. In the spectra, an inertial sub-range of the energy cascade is traced for the flow velocity with an indicator $k \sim −4$, for the cascade of polymer molecules stretches with an indicator $−1.6$.

Традиционные методы решения задачи коммивояжера не являются эффективными для задач высокой размерности из-за их высокой вычислительной сложности. Одним из эффективных способов решения этой проблемы является декомпозиционный подход, который включает в себя три основных этапа: кластеризацию вершин, решение подзадач внутри каждого кластера и последующее объединение полученных решений в итоговое. В данной статье основное внимание уделяется третьему этапу — объединению циклов решений подзадач, поскольку этому этапу не всегда уделяется должное внимание, что приводит к менее точному итоговому решению. В статье предлагается новый модифицированный алгоритм Сигала для объединения циклов. Для оценки его эффективности проводится сравнение с двумя алгоритмами объединения циклов: метод соединения средних точек ребер и алгоритм на основе близости центроидов кластеров. Исследуется зависимость качества решения подзадач на алгоритмы объединения циклов. Модифицированный алгоритм Сигала выполняет попарное объединение кластеров, минимизируя количество пересечений и общее расстояние. Метод центроидов ориентирован на соединение кластеров на основе близости центроидов, а алгоритм с использованием средних точек оценивает расстояние между средними точками ребер. Также были рассмотрены два типа кластеризации: алгоритмы k-means и affinity propagation. Для проверки эффективности предложенного алгоритма были проведены численные эксперименты на наборе данных TSPLIB с различным количеством городов. В исследовании анализируются ошибки, вызванные порядком объединения кластеров, качеством решения подзадач и количеством кластеров. Эксперименты показали, что модифицированный алгоритм Сигала демонстрирует наименьшую медиану итогового расстояния и наиболее устойчивые результаты по сравнению с другими методами. Результаты указывают на большую устойчивость качества конечного решения, полученным модифицированным алгоритмом Сигала, от последовательности объединения кластеров. Повышение качества решения подзадачи обычно приводит к линейному улучшению конечного решения, но используемый алгоритм объединения редко влияет на степень этого улучшения.

Traditional methods for solving the traveling salesman problem are not effective for high-dimensional problems due to their high computational complexity. One of the most effective ways to solve this problem is the decomposition approach, which includes three main stages: clustering vertices, solving subproblems within each cluster and then merging the obtained solutions into a final solution. This article focuses on the third stage — merging cycles of solving subproblems — since this stage is not always given sufficient attention, which leads to less accurate final solutions of the problem. The paper proposes a new modified Sigal algorithm for merging cycles. To evaluate its effectiveness, it is compared with two algorithms for merging cycles — the method of connecting midpoints of edges and an algorithm based on closeness of cluster centroids. The dependence of quality of solving subproblems on algorithms used for merging cycles is investigated. Sigal’s modified algorithm performs pairwise clustering and minimizes total distance. The centroid method focuses on connecting clusters based on closeness of centroids, and an algorithm using mid-points estimates the distance between mid-points of edges. Two types of clustering — k-means and affinity propagation — were also considered. Numerical experiments were performed using the TSPLIB dataset with different numbers of cities and topologies to test effectiveness of proposed algorithm. The study analyzes errors caused by the order in which clusters were merged, the quality of solving subtasks and number of clusters. Experiments show that the modified Sigal algorithm has the smallest median final distance and the most stable results compared to other methods. Results indicate that the quality of the final solution obtained using the modified Sigal algorithm is more stable depending on the sequence of merging clusters. Improving the quality of solving subproblems usually results in linear improvement of the final solution, but the pooling algorithm rarely affects the degree of this improvement.

Получены асимптотические формулы для верхних граней уклонений прямоугольных сумм Валле Пуссена на классах периодических функций двух переменных высокой гладкости. Эти соотношения в некоторых важных случаях обеспечивают решение известной задачи Колмогорова–Никольского для прямоугольных сумм Валле Пуссена и указанных классов функций.

We obtain asymptotic equalities for upper bounds of the deviations of the right-angled de la Vallee Poussin sums taken over classes of periodical functions of two variables of high smoothness. These equalities guarantee the solvability of the Kolmogorov–Nikol’skii problem for the right-angled de la Vallee Poussin sums on the specified classes of functions.