Все выпуски

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

A new statement of Integral Geometry problem where the image of function in each point is taken as an integral with respect to measure which depends on the point is suggested. Such Measure System is named Measure Induction. It is shown that an inversion formula exists for class of measures having a unit atom in corresponding
point and limited on whole space. Previously obtained results for average on systems of measurement dissections and for weight average on graphs are generalized.

Мультипликативные методы для разреженных матриц являются наиболее приспособленными для снижения трудоемкости операций решения систем линейных уравнений, выполняемых на каждой итерации симплекс-метода. Матрицы ограничений в этих задачах слабо заполнены ненулевыми элементами, что позволяет получать мультипликаторы, главные столбцы которых также разрежены, а операция умножения вектора на мультипликатор по трудоемкости пропорциональна числу ненулевых элементов этого мультипликатора. Кроме того, при переходе к смежному базису мультипликативное представление достаточно легко корректируется. Для повышения эффективности таких методов требуется уменьшение заполненности мультипликативного представления ненулевыми элементами. Однако на каждой итерации алгоритма к последовательности мультипликаторов добавляется еще один. А трудоемкость умножения, которая линейно зависит от длины последовательности, растет. Поэтому требуется выполнять время от времени перевычисление обратной матрицы, получая ее из единичной. Однако в целом проблема не решается. Кроме того, набор мультипликаторов представляет собой последовательность структур, причем размер этой последовательности неудобно велик и точно неизвестен. Мультипликативные методы не учитывают фактора высокой степени разреженности исходных матриц и ограничения-равенства, требуют определения первоначального базисного допустимого решения задачи и, как следствие, не допускают сокращения размерности задачи линейного программирования и регулярной процедуры сжатия — уменьшения размерности мультипликаторов и исключения ненулевых элементов из всех главных столбцов мультипликаторов, полученных на предыдущих итерациях. Таким образом, разработка численных методов решения задач линейного программирования, позволяющих преодолеть или существенно ослабить недостатки схем реализации симплекс-метода, относится к актуальным проблемам вычислительной математики.

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

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

Multiplicative methods for sparse matrices are best suited to reduce the complexity of operations solving systems of linear equations performed on each iteration of the simplex method. The matrix of constraints in these problems of sparsely populated nonzero elements, which allows to obtain the multipliers, the main columns which are also sparse, and the operation of multiplication of a vector by a multiplier according to the complexity proportional to the number of nonzero elements of this multiplier. In addition, the transition to the adjacent basis multiplier representation quite easily corrected. To improve the efficiency of such methods requires a decrease in occupancy multiplicative representation of the nonzero elements. However, at each iteration of the algorithm to the sequence of multipliers added another. As the complexity of multiplication grows and linearly depends on the length of the sequence. So you want to run from time to time the recalculation of inverse matrix, getting it from the unit. Overall, however, the problem is not solved. In addition, the set of multipliers is a sequence of structures, and the size of this sequence is inconvenient is large and not precisely known. Multiplicative methods do not take into account the factors of the high degree of sparseness of the original matrices and constraints of equality, require the determination of initial basic feasible solution of the problem and, consequently, do not allow to reduce the dimensionality of a linear programming problem and the regular procedure of compression — dimensionality reduction of multipliers and exceptions of the nonzero elements from all the main columns of multipliers obtained in previous iterations. Thus, the development of numerical methods for the solution of linear programming problems, which allows to overcome or substantially reduce the shortcomings of the schemes implementation of the simplex method, refers to the current problems of computational mathematics.

In this paper, the approach to the construction of numerically stable direct multiplier methods for solving problems in linear programming, taking into account sparseness of matrices, presented in packaged form. The advantage of the approach is to reduce dimensionality and minimize filling of the main rows of multipliers without compromising accuracy of the results and changes in the position of the next processed row of the matrix are made that allows you to use static data storage formats.

As a direct continuation of this work is the basis for constructing a direct multiplicative algorithm set the direction of descent in the Newton methods for unconstrained optimization is proposed to put a modification of the direct multiplier method, linear programming by integrating one of the existing design techniques significantly positive definite matrix of the second derivatives.

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

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

Третье решение построено для уравнений движения гиростата в магнитном поле с учетом эффекта Барнетта–Лондона. Для него структура такова: первая и вторая компоненты вектора угловой скорости—многочлены второй степени, квадрат третьей компоненты—многочлен четвертой степени по вспомогательной переменной, которая находится обращением эллиптического интеграла Лежандра.

Все построенные решения не имеют аналогов в динамике твердого тела с неподвижной точкой.

We study polynomial solutions of gyrostat motion equations under potential and gyroscopic forces applied and of gyrostat motion equations in magnetic field taking into account Barnett–London effect. Mathematically, either of the above mentioned problems is described by a system of non-linear ordinary differential equations whose right hand sides contain fifteen constant parameters. These parameters characterize the gyrostat mass distribution, as well as potential and non-potential forces acting on gyrostat. We consider polynomial solutions of Steklov–Kovalevski–Gorjachev and Doshkevich classes. The structure of invariant relations for polynomial solutions shows that, as a rule, on top of the fifteen parameters mentioned one should add no less than twenty five problem parameters. In the process of solving such a multi-parametric problem in this paper we (in addition to analytic approach) apply numeric methods based on CAS. We break our studies of polynomial solutions existence into two steps. During the first step, we estimate maximal degrees of polynomials considered and obtain a non-linear algebraic system for parameters of differential equations and polynomial solutions. In the second step (using the above CAS software) we study the solvability conditions of the system obtained and investigate the conditions of the constructed solutions to be real.

We construct two new polynomial solutions for Kirchhoff–Poisson. The first one is described by the following property: the projection squares of angular velocity on the non-baracentric axes are the fifth degree polynomials of the angular velocity vector component of the baracentric axis that is represented via hypereliptic function of time. The second solution is characterized by the following: the first component of velocity conditions is a second degree polynomial, the second component is a polynomial of the third degree, and the square of the third component is the sixth degree polynomial of the auxiliary variable that is an inversion of the elliptic Legendre integral.

The third new partial solution we construct for gyrostat motion equations in the magnetic field with Barnett–London effect. Its structure is the following: the first and the second components of the angular velocity vector are the second degree polynomials, and the square of the third component is a fourth degree polynomial of the auxiliary variable which is found via inversion of the elliptic Legendre integral of the third kind.

All the solutions constructed in this paper are new and do not have analogues in the fixed point dynamics of a rigid body.

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

In this paper we describe an algorithm of numerical solving of an inverse problem on a hyperbolic heat equation with additional second time derivative with a small parameter. The problem in this case is finding an initial distribution with given final distribution. This algorithm allows finding a solution to the problem for any admissible given precision. Algorithm allows evading difficulties analogous to the case of heat equation with inverted time. Furthermore, it allows finding an optimal grid size by learning on a relatively big grid size and small amount of iterations of a gradient method and later extrapolates to the required grid size using Richardson’s method. This algorithm allows finding an adequate estimate of Lipschitz constant for the gradient of the target functional. Finally, this algorithm may easily be applied to the problems with similar structure, for example in solving equations for plasma, social processes and various biological problems. The theoretical novelty of the paper consists in the developing of an optimal procedure of finding of the required grid size using Richardson extrapolations for optimization problems with inexact gradient in ill-posed problems.

В работе рассматривается обратная задача определения по экспериментальным данным параметров модели выделения водорода из порошка гидрида металла. Методом слепого поиска в пространстве параметров установлено, что задача имеет многочисленные физически разумные решения. Решения задачи получены с помощью высокопроизводительного численного моделирования в грид–системе на базе платформы BOINC.

In the paper we consider the inverse problem of evaluating kinetic parameters of the model of dehydriding of metal powder using experimental data. The «blind search» in the space of parameters revealed multiple physically reasonable solutions. The solutions were obtained using high–performance computational modeling based on BOINC–grid.

В данной работе приводятся нижние оценки скорости сходимости для класса численных методов выпуклой оптимизации первого порядка и выше, т. е. использующих градиент и старшие производные. Обсуждаются вопросы достижимости данных оценок. Приведенные в статье оценки замыкают известные на данный момент результаты в этой области. Отметим, что замыкание осуществляется без должного обоснования, поэтому в той общности, в которой данные оценки приведены в статье, их стоит понимать как гипотезу. Опишембо лее точно основной результат работы. Пожалуй, наиболее известнымм етодом второго порядка является метод Ньютона, использующий информацию о градиенте и матрице Гессе оптимизируемой функции. Однако даже для сильно выпуклых функций метод Ньютона сходится лишь локально. Глобальная сходимость метода Ньютона обеспечивается с помощью кубической регуляризации оптимизируемой на каждом шаге квадратичной модели функции [Nesterov, Polyak, 2006]. Сложность решения такой вспомогательной задачи сопоставима со сложностью итерации обычного метода Ньютона, т. е. эквивалентна по порядку сложности обращения матрицы Гессе оптимизируемой функции. В 2008 году Ю. Е. Нестеровымбыл предложен ускоренный вариант метода Ньютона с кубической регуляризацией [Nesterov, 2008]. В 2013 г. Monteiro – Svaiter сумели улучшить оценку глобальной сходимости ускоренного метода с кубической регуляризацией [Monteiro, Svaiter, 2013]. В 2017 году Arjevani – Shamir – Shiff показали, что оценка Monteiro – Svaiter оптимальна (не может быть улучшена более чем на логарифми- ческий множитель на классе методов 2-го порядка) [Arjevani et al., 2017]. Также удалось получить вид нижних оценок для методов порядка $p ≥ 2$ для задач выпуклой оптимизации. Отметим, что при этом для сильно выпуклых функций нижние оценки были получены только для методов первого и второго порядка. В 2018 году Ю. Е. Нестеров для выпуклых задач оптимизации предложил методы 3-го порядка, которые имеют сложность итерации сопоставимую со сложностью итерации метода Ньютона и сходятся почти по установленным нижним оценкам [Nesterov, 2018]. Таким образом, было показано, что методы высокого порядка вполне могут быть практичными. В данной работе приводятся нижние оценки для методов высокого порядка $p ≥ 3$ для сильно выпуклых задач безусловной оптимизации. Работа также может рассматриваться как небольшой обзор современного состояния развития численных методов выпуклой оптимизации высокого порядка.

In this paper we discuss lower bounds for convergence of convex optimization methods of high order and attainability of this bounds. We formulate a hypothesis that covers all the cases. It is noticeable that we provide this statement without a proof. Newton method is the most famous method that uses gradient and Hessian of optimized function. However, it converges locally even for strongly convex functions. Global convergence can be achieved with cubic regularization of Newton method [Nesterov, Polyak, 2006], whose iteration cost is comparable with iteration cost of Newton method and is equivalent to inversion of Hessian of optimized function. Yu.Nesterov proposed accelerated variant of Newton method with cubic regularization in 2008 [Nesterov, 2008]. R.Monteiro and B. Svaiter managed to improve global convergence of cubic regularized method in 2013 [Monteiro, Svaiter, 2013]. Y.Arjevani, O. Shamir and R. Shiff showed that convergence bound of Monteiro and Svaiter is optimal (cannot be improved by more than logarithmic factor with any second order method) in 2017 [Arjevani et al., 2017]. They also managed to find bounds for convex optimization methods of p-th order for $p ≥ 2$. However, they got bounds only for first and second order methods for strongly convex functions. In 2018 Yu.Nesterov proposed third order convex optimization methods with rate of convergence that is close to this lower bounds and with similar to Newton method cost of iteration [Nesterov, 2018]. Consequently, it was showed that high order methods can be practical. In this paper we formulate lower bounds for p-th order methods for $p ≥ 3$ for strongly convex unconstrained optimization problems. This paper can be viewed as a little survey of state of the art of high order optimization methods.

Представлен вариант обратного метода характеристик (МОМХ), в алгоритм которого введен дополнительный дробный временной шаг, что позволяет повысить точность вычислений за счет более точной аппроксимации характеристик. Приведены расчетные формулы модифицированного метода для уравнений односкоростной модели газожидкостной смеси, с помощью которого рассчитаны одномерные, а также плоские тестовые задачи, имеющие автомодельные решения. При решении многомерных задач исходная система уравнений расщепляется на ряд одномерных подсистем, для расчета которых применяется обратный метод характеристик с дробным временным шагом. С использованием предложенного метода рассчитаны: одномерная задача распада произвольного разрыва в дисперсной среде; двумерная задача взаимодействия однородного газожидкостного потока с препятствием с присоединенным ударным скачком, а также течение с центрированной волной разрежения. Результаты численных расчетов этих задач сопоставлены с автомодельными решениями и отмечено их удовлетворительное совпадение. На примере задачи Римана с ударным скачком приведено сравнение с рядом консервативных, неконсервативных первого и повышенного порядков точности схем, из которого, в частности, следует, что представленный метод расчета вполне конкурентоспособен. Несмотря на то что применение МОМХ требует в разы больших временных затрат по сравнению с оригинальным обратным методом характеристик (ОМХ), вычисления можно проводить с увеличенным временным шагом и в ряде случаев получать более точные результаты. Отмечено, что метод с дробным временным шагом имеет преимущества в случаях, когда характеристики системы криволинейные. По этой причине для уравнений Эйлера целесообразно использовать ОМХ вместо МОМХ, поскольку в этом случае характеристики в пределах временного шага мало отличаются от прямых линий.

A variant of the inverse method of characteristics (IMH) is presented, in whose algorithm an additional fractional time step is introduced, which makes it possible to increase the accuracy of calculations due to a more accurate approximation of the characteristics. The calculation formulas of the modified method for the equations of the one-velocity model of a gas-liquid mixture are given, with the help of which one-dimensional and also flat test problems with self-similar solutions are calculated. When solving multidimensional problems, the original system of equations is split into a number of one-dimensional subsystems, for the calculation of which the inverse method of characteristics with a fractional time step is used. Using the proposed method, the following were calculated: the one-dimensional problem of the decay of an arbitrary discontinuity in a dispersed medium; a twodimensional problem of the interaction of a homogeneous gas-liquid flow with an obstacle with an attached shock wave, as well as a flow with a centered rarefaction wave. The results of numerical calculations of these problems are compared with self-similar solutions and their satisfactory agreement is noted. On the example of the Riemann problem with a shock wave, a comparison is made with a number of conservative, non-conservative, first and higher orders of accuracy schemes, from which, in particular, it follows that the presented calculation method, i. e. MIMC, quite competitive. Despite the fact that the application of MIMC requires many times more time than the original inverse method of characteristics (IMC), calculations can be carried out with an increased time step and, in some cases, more accurate results can be obtained. It is noted that the method with a fractional time step has advantages over the IMC in cases where the characteristics of the system are significantly curvilinear. For this reason, the use of MIMC, for example, for the Euler equations is inappropriate, since for the latter the characteristics within the time step differ little from straight lines.

В работе рассмотрена краевая задача о движении тепловой волны для вырождающегося уравнения второго порядка параболического типа со степенной нелинейностью. Краевое условие задает уравнение движения на плоскости нулевого фронта тепловой волны, имеющего форму окружности. Предложен новый численно-аналитический алгоритм, в соответствии с которым решение строится по шагам по времени при разностной схеме дискретизации времени. На каждом шаге рассматривается краевая задача для уравнения Пуассона, к которому сводится исходное уравнение. Фактически она является обратной задачей Коши, в которой исходная граница области решения свободна от граничных условий, а на текущей границе (фронте волны) заданы два условия (Неймана и Дирихле). Решение этой задачи ищется в виде суммы частного решения уравнения Пуассона и решения соответствующего уравнения Лапласа, удовлетворяющего граничным условиям. Поскольку неоднородность зависит от искомой функции и ее производных, решение строится итерационно. Частное решение ищется методом коллокаций с помощью разложения неоднородности по радиальным базисным функциям. Обратная задача Коши для уравнения Лапласа решается методом нулевого поля применительно к круговым областям с круговыми отверстиями. Для таких задач этот метод применяется впервые. Вычислительный алгоритм оптимизирован за счет распараллеливания вычислений. Распараллеливание вычислений позволило эффективно реализовать алгоритм на высокопроизводительных вычислительных системах. На базе алгоритма была создана компьютерная программа. В качестве средства распараллеливания был выбран стандарт параллельного программирования OpenMP для языка программирования C++ как наиболее подходящий для вычислительных программ с параллельными циклами. Эффективность алгоритма и работоспособность программы были проверены сравнением результатов расчетов с известным точным решением, а также с численным решением, полученным авторами ранее с помощью метода граничных элементов. Проведенный вычислительный эксперимент показал хорошую сходимость итерационных процессов и более высокую точность нового алгоритма по сравнению с разработанным ранее. Анализ решений позволил определить наиболее подходящую систему радиальных базисных функций.

The paper deals with a heat wave motion problem for a degenerate second-order nonlinear parabolic equation with power nonlinearity. The considered boundary condition specifies in a plane the motion equation of the circular zero front of the heat wave. A new numerical-analytical algorithm for solving the problem is proposed. A solution is constructed stepby- step in time using difference time discretization. At each time step, a boundary value problem for the Poisson equation corresponding to the original equation at a fixed time is considered. This problem is, in fact, an inverse Cauchy problem in the domain whose initial boundary is free of boundary conditions and two boundary conditions (Neumann and Dirichlet) are specified on a current boundary (heat wave). A solution of this problem is constructed as the sum of a particular solution to the nonhomogeneous Poisson equation and a solution to the corresponding Laplace equation satisfying the boundary conditions. Since the inhomogeneity depends on the desired function and its derivatives, an iterative solution procedure is used. The particular solution is sought by the collocation method using inhomogeneity expansion in radial basis functions. The inverse Cauchy problem for the Laplace equation is solved by the null field method as applied to a circular domain with a circular hole. This method is used for the first time to solve such problem. The calculation algorithm is optimized by parallelizing the computations. The parallelization of the computations allows us to realize effectively the algorithm on high performance computing servers. The algorithm is implemented as a program, which is parallelized by using the OpenMP standard for the C++ language, suitable for calculations with parallel cycles. The effectiveness of the algorithm and the robustness of the program are tested by the comparison of the calculation results with the known exact solution as well as with the numerical solution obtained earlier by the authors with the use of the boundary element method. The implemented computational experiment shows good convergence of the iteration processes and higher calculation accuracy of the proposed new algorithm than of the previously developed one. The solution analysis allows us to select the radial basis functions which are most suitable for the proposed algorithm.

В работе предлагается подход, позволяющий организовать оперативный контроль за интенсивностью действия источника выбросов в атмосферу. Восстановление неизвестной интенсивности источника загрязнения атмосферы производится по измерениям концентрации примеси в отдельных стационарных точках. Для решения обратной задачи использовались методы шаговой регуляризации и последовательной функциональной аппроксимации. Решение представлено в форме цифрового фильтра в смысле Хэмминга. Описан алгоритм выбора регуляризирующего параметра r для метода функциональной аппроксимации. Работа продолжает исследования, представленные в [1,2].

The approach given in this work helps to organize the operative control over action intensity of pollution emissions in atmosphere. The approach allows to sequential estimate of unknown intensity of atmospheric pollution source on the base of concentration measurements of impurity in several stationary control points is offered in the work. The inverse problem was solved by means of the step-by-step regularization and the sequential function specification method. The solution is presented in the form of the digital filter in terms of Hamming. The fitting algorithm of regularization parameter r for function specification method is described.

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

The question on improvement of quality of images obtained in a tomography problem is considered. The problem consists in finding of boundaries of inhomogeneities (inclusions) in a continuous medium by results of X-ray radiography of this medium. A nonlinear integral transformation of a special kind is proposed which allows to improve quality of images obtained earlier at a set of papers. The method is realized numerically by the use of computer modelling. Some calculations are carried out with use of data for concrete materials. The results obtained are presented by drawings and graphic images.