All issues

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

This work is dedicated to application of bicompact schemes to numerical solution of evolutionary hyperbolic equations. The main advantage of this class of schemes lies in combination of two beneficial properties: the first one is spatial approximation of high even order on a stencil that always occupies only one mesh cell; the second one is spectral resolution which is better in comparison to classic compact finite-difference schemes of the same order of spatial approximation. One feature of bicompact schemes is considered: their spatial approximation is rigidly tied to Cartesian meshes (with parallelepiped-shaped cells in three-dimensional case). This feature makes rather challenging any application of bicompact schemes to problems with complex computational domains as treated in the framework of unstructured meshes. This problem is proposed to be solved using well-known methods for treating complex-shaped boundaries and their corresponding boundary conditions on Cartesian meshes. The generalization of bicompact schemes on problems in geometrically complex domains is made in case of gas dynamics problems and Euler equations. The free boundary method is chosen as a particular tool to introduce the influence of arbitrary-shaped solid boundaries on gas flows on Cartesian meshes. A brief description of this method is given, its governing equations are written down. Bicompact schemes of fourth order of approximation in space with locally one-dimensional splitting are constructed for equations of the free boundary method. Its compensation flux is discretized with second order of accuracy. Time stepping in the obtained schemes is done with the implicit Euler method and the third order accurate $L$-stable stiffly accurate three-stage singly diagonally implicit Runge–Kutta method. The designed bicompact schemes are tested on three two-dimensional problems: stationary supersonic flows with Mach number three past one circular cylinder and past three circular cylinders; the non-stationary interaction of planar shock wave with a circular cylinder in a channel with planar parallel walls. The obtained results are in a good agreement with other works: influence of solid bodies on gas flows is physically correct, pressure in control points on solid surfaces is calculated with the accuracy appropriate to the chosen mesh resolution and level of numerical dissipation.

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

Recently, saddle point problems have received much attention due to their powerful modeling capability for a lot of problems from diverse domains. Applications of these problems occur in many applied areas, such as robust optimization, distributed optimization, game theory, and many applications in machine learning such as empirical risk minimization and generative adversarial networks training. Therefore, many researchers have actively worked on developing numerical methods for solving saddle point problems in many different settings. This paper is devoted to developing a numerical method for solving saddle point problems in the nonconvex uniformly-concave setting. We study a general class of saddle point problems with composite structure and H\"older-continuous higher-order derivatives. To solve the problem under consideration, we propose an approach in which we reduce the problem to a combination of two auxiliary optimization problems separately for each group of variables, the outer minimization problem w.r.t. primal variables, and the inner maximization problem w.r.t the dual variables. For solving the outer minimization problem, we use the Adaptive Gradient Method, which is applicable for nonconvex problems and also works with an inexact oracle that is generated by approximately solving the inner problem. For solving the inner maximization problem, we use the Restarted Unified Acceleration Framework, which is a framework that unifies the high-order acceleration methods for minimizing a convex function that has H\"older-continuous higher-order derivatives. Separate complexity bounds are provided for the number of calls to the first-order oracles for the outer minimization problem and higher-order oracles for the inner maximization problem. Moreover, the complexity of the whole proposed approach is then estimated.

Численное решение системы уравнений высокотемпературной радиационной газовой динамики (ВРГД) является вычислительно трудоемкой задачей, так как взаимодействие излучения с веществом нелинейно и нелокально. Коэффициенты поглощения излучения зависят от температуры, а поле температур определяется как газодинамическими процессами, так и переносом излучения. Обычно для решения системы ВРГД используется метод расщепления по физическим процессам, выделяется блок решения уравнения переноса совместно с уравнением баланса энергии вещества при известных давлениях и температурах. Построенные ранее разностные схемы, используемые для решения этого блока, обладают порядками сходимости не выше второго. Так как даже на современном уровне развития вычислительной техники имеются ограничения по памяти, то для решения сложных технических задач приходится применять не слишком подробные сетки. Это повышает требования к порядку аппроксимации разностных схем. В данной работе впервые реализованы бикомпактные схемы высокого порядка аппроксимации для алгоритма совместного решения уравнения переноса излучения и уравнения баланса энергии. Предложенный метод может быть применен для решения широкого круга практических задач, так как обладает высокой точностью и подходит для решения задач с разрывами коэффициентов. Нелинейность задачи и использование неявной схемы приводит к итерационному процессу, который может медленно сходиться. В данной работе используется мультипликативный HOLO-алгоритм — метод квазидиффузии В.Я. Гольдина. Ключевая идея HOLO-алгоритмов состоит в совместном решении уравнений высокого порядка (high order, HO) и низкого порядка (low order, LO). Уравнением высокого порядка (HO) является уравнение переноса излучения, которое решается в многогрупповом приближении, далее уравнение осредняется по угловой переменной и получается система уравнений квазидиффузии в многогрупповом приближении (LO₁). Следующим этапом является осреднение по энергии, при этом получается эффективная одногрупповая система уравнений квазидиффузии (LO₂), которая решается совместно с уравнением энергии. Решения, получаемые на каждом этапе HOLO-алгоритма, оказываются тесно связанными, что в итоге приводит к ускорению сходимости итерационного процесса. Для каждого из этапов HOLO-алгоритма предложены разностные схемы, построенные методом прямых в рамках одной ячейки и обладающие четвертым порядком аппроксимации по пространству и третьим порядком по времени. Схемы для уравнения переноса были разработаны Б.В. Роговым и его коллегами, схемы для уравнений LO₁ и LO₂ разработаны авторами. Предложен аналитический тест, на котором демонстрируются заявленные порядки сходимости. Рассматриваются различные варианты постановки граничных условий и исследовано их влияние на порядок сходимости по времени и пространству.

The numerical solving of the system of high-temperature radiative gas dynamics (HTRGD) equations is a computationally laborious task, since the interaction of radiation with matter is nonlinear and non-local. The radiation absorption coefficients depend on temperature, and the temperature field is determined by both gas-dynamic processes and radiation transport. The method of splitting into physical processes is usually used to solve the HTRGD system, one of the blocks consists of a joint solving of the radiative transport equation and the energy balance equation of matter under known pressure and temperature fields. Usually difference schemes with orders of convergence no higher than the second are used to solve this block. Due to computer memory limitations it is necessary to use not too detailed grids to solve complex technical problems. This increases the requirements for the order of approximation of difference schemes. In this work, bicompact schemes of a high order of approximation for the algorithm for the joint solution of the radiative transport equation and the energy balance equation are implemented for the first time. The proposed method can be applied to solve a wide range of practical problems, as it has high accuracy and it is suitable for solving problems with coefficient discontinuities. The non-linearity of the problem and the use of an implicit scheme lead to an iterative process that may slowly converge. In this paper, we use a multiplicative HOLO algorithm named the quasi-diffusion method by V.Ya.Goldin. The key idea of HOLO algorithms is the joint solving of high order (HO) and low order (LO) equations. The high-order equation (HO) is the radiative transport equation solved in the energy multigroup approximation, the system of quasi-diffusion equations in the multigroup approximation (LO₁) is obtained by averaging HO equations over the angular variable. The next step is averaging over energy, resulting in an effective one-group system of quasi-diffusion equations (LO₂), which is solved jointly with the energy equation. The solutions obtained at each stage of the HOLO algorithm are closely related that ultimately leads to an acceleration of the convergence of the iterative process. Difference schemes constructed by the method of lines within one cell are proposed for each of the stages of the HOLO algorithm. The schemes have the fourth order of approximation in space and the third order of approximation in time. Schemes for the transport equation were developed by B.V. Rogov and his colleagues, the schemes for the LO₁ and LO₂ equations were developed by the authors. An analytical test is constructed to demonstrate the declared orders of convergence. Various options for setting boundary conditions are considered and their influence on the order of convergence in time and space is studied.

Расчет переноса излучения в ударном слое космического аппарата вызывает значительные трудности из-за сложной многорезонансной зависимости макросечения поглощения излучения от энергий фотонов. В работе исследована сходимость двух приближенных методов осреднения спектров излучения к точному поточечному (line-by-line) расчету. Первым из приближенных методов является широко используемое многогрупповое приближение, вторым — метод лебеговского осреднения, относящийся к методам сокращения числа расчетных точек спектра за счет объединения точек с равновеликим поглощением. Показано, что с увеличением числа групп метод лебеговского осреднения сходится к точному решению значительно быстрее многогруппового приближения. Оказалось, что 100–150 лебеговых групп достаточно для достижения точности line-by-line-расчета даже в ударном слое в высоких слоях атмосферы, где линии поглощения узки. При этом объем вычислений сокращается более чем на четыре порядка. Выполнена серия расчетов функции распределения излучения в двумерном ударном слое, возникающем при обтекании сферы и затупленного конуса, с использованием приближения локально плоского слоя и метода лебеговского осреднения энергий фотонов. Показано, что излучение ударной волны становится все более сильным при увеличении размера космического аппарата, как в значениях падающего потока энергии на поверхности тела, так и в скорости обмена энергией с газодинамическим потоком, причем не только в точке торможения.

Calculations of radiation transport in the shockwave layer of a descent space vehicle cause essential difficulties due to complex multi-resonance dependence of the absorption macroscopic cross sections from the photon energy. The convergence of two approximate spectrum averaging methods to the results of exact pointwise spectrum calculations is investigated. The first one is the well known multigroup method, the second one is the Lebesgue averaging method belonging to methods of the reduction of calculation points by means of aggregation of spectral points which are characterized by equal absorption strength. It is shown that convergence of the Lebesgue averaging method is significantly faster than the multigroup approach as the number of groups is increased. The only 100–150 Lebesgue groups are required to achieve the accuracy of pointwise calculations even in the shock layer at upper atmosphere with sharp absorption lines. At the same time the number of calculations is reduced by more than four order. Series of calculations of the radiation distribution function in 2D shock layer around a sphere and a blunt cone were performed using the local flat layer approximation and the Lebesgue averaging method. It is shown that the shock wave radiation becomes more significant both in value of the energy flux incident on the body surface and in the rate of energy exchange with the gas-dynamic flow in the case of increasing of the vehicle’s size.

В данной работе приводятся нижние оценки скорости сходимости для класса численных методов выпуклой оптимизации первого порядка и выше, т. е. использующих градиент и старшие производные. Обсуждаются вопросы достижимости данных оценок. Приведенные в статье оценки замыкают известные на данный момент результаты в этой области. Отметим, что замыкание осуществляется без должного обоснования, поэтому в той общности, в которой данные оценки приведены в статье, их стоит понимать как гипотезу. Опишембо лее точно основной результат работы. Пожалуй, наиболее известнымм етодом второго порядка является метод Ньютона, использующий информацию о градиенте и матрице Гессе оптимизируемой функции. Однако даже для сильно выпуклых функций метод Ньютона сходится лишь локально. Глобальная сходимость метода Ньютона обеспечивается с помощью кубической регуляризации оптимизируемой на каждом шаге квадратичной модели функции [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.

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

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

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

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

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

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

Результаты численных экспериментов позволяют сделать следующие выводы.

1. Для разрывного начального профиля лучшие свойства показал ограничитель SuperBee.

2. Для непрерывного начального профиля при больших пространственных шагах лучше ограничитель SuperBee, а при малых шагах лучше ограничитель Koren.

3. Для гладкого начального профиля лучшие результаты показал ограничитель Koren.

4. Гладкий ограничитель F показал результаты, аналогичные Koren.

5. Ограничители разного типа оставляют дисперсионные ошибки, при этом зависимости дисперсионных ошибок от параметров схемы имеют большую вариабельность и сложным образом зависят от параметров этой схемы.

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

7. Построенная разностная схема при шагах по времени, не превышающих шаг Куранта, является монотонной и показывает хорошие характеристики точности для решений разных типов. При превышении шага Куранта схема остается устойчивой, но становится непригодной для задач неустойчивости, поскольку условия монотонности перестают в этом случае выполняться.

The purpose of the paper is a research of a 2nd order finite difference scheme based on the Z-scheme. This research is the numerical solution of several two-dimensional differential equations simulated the incompressible medium convection.

One of real tasks for similar equations solution is the numerical simulating of strongly non-stationary midscale processes in the Earth ionosphere. Because convection processes in ionospheric plasma are controlled by magnetic field, the plasma incompressibility condition is supposed across the magnetic field. For the same reason, there can be rather high velocities of heat and mass convection along the magnetic field.

Ionospheric simulation relevant task is the research of plasma instability of various scales which started in polar and equatorial regions first of all. At the same time the mid-scale irregularities having characteristic sizes 1–50 km create conditions for development of the small-scale instabilities. The last lead to the F-spread phenomenon which significantly influences the accuracy of positioning satellite systems work and also other space and ground-based radio-electronic systems.

The difference schemes used for simultaneous simulating of such multi-scale processes must to have high resolution. Besides, these difference schemes must to be high resolution on the one hand and monotonic on the other hand. The fact that instabilities strengthen errors of difference schemes, especially they strengthen errors of dispersion type is the reason of such contradictory requirements. The similar swing of errors usually results to nonphysical results at the numerical solution.

At the numerical solution of three-dimensional mathematical models of ionospheric plasma are used the following scheme of splitting on physical processes: the first step of splitting carries out convection along, the second step of splitting carries out convection across. The 2nd order finite difference scheme investigated in the paper solves approximately convection across equations. This scheme is constructed by a monotonized nonlinear procedure on base of the Z-scheme which is one of 2nd order schemes. At this monotonized procedure a nonlinear correction with so-called “oblique differences” is used. “Oblique differences” contain the grid nodes relating to different layers of time.

The researches were conducted for two cases. In the simulating field components of the convection vector had: 1) the constant sign; 2) the variable sign. Dissipative and dispersive characteristics of the scheme for different types of the limiting functions are in number received.

The results of the numerical experiments allow to draw the following conclusions.

1. For the discontinuous initial profile the best properties were shown by the SuperBee limiter.

2. For the continuous initial profile with the big spatial steps the SuperBee limiter is better, and at the small steps the Koren limiter is better.

3. For the smooth initial profile the best results were shown by the Koren limiter.

4. The smooth F limiter showed the results similar to Koren limiter.

5. Limiters of different type leave dispersive errors, at the same time dependences of dispersive errors on the scheme parameters have big variability and depend on the scheme parameters difficulty.

6. The monotony of the considered differential scheme is in number confirmed in all calculations. The property of variation non-increase for all specified functions limiters is in number confirmed for the onedimensional equation.

7. The constructed differential scheme at the steps on time which are not exceeding the Courant's step is monotonous and shows good exactness characteristics for different types solutions. At excess of the Courant's step the scheme remains steady, but becomes unsuitable for instability problems as monotony conditions not satisfied in this case.

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

In this paper, a gravitational system is understood as a set of point bodies that interact according to Newton's law of attraction and have a negative value of the total energy. The question of the stability (nonstability) of a gravitational system of general position is discussed by direct computational experiment. A gravitational system of general position is a system in which the masses, initial positions, and velocities of bodies are chosen randomly from given ranges. A new method for the numerical solution of ordinary differential equations at large time intervals has been developed for the computational experiment. The proposed method allowed, on the one hand, to ensure the fulfillment of all conservation laws by a suitable correction of solutions, on the other hand, to use standard methods for the numerical solution of systems of differential equations of low approximation order. Within the framework of this method, the trajectory of a gravitational system in phase space is assembled from parts, the duration of each of which can be macroscopic. The constructed trajectory, generally speaking, is discontinuous, and the points of joining of individual pieces of the trajectory act as branch points. In connection with the latter circumstance, the proposed method, in part, can be attributed to the class of Monte Carlo methods. The general conclusion of a series of computational experiments has shown that gravitational systems of general position with a number of bodies of 3 or more, generally speaking, are unstable. In the framework of the proposed method, special cases of zero-equal angular momentum of a gravitational system with a number of bodies of 3 or more, as well as the problem of motion of two bodies, are specially considered. The case of numerical modeling of the dynamics of the solar system in time is considered separately. From the standpoint of computational experiments based on analytical methods, as well as direct numerical methods of high-order approximation (10 and higher), the stability of the solar system was previously demonstrated at an interval of five billion years or more. Due to the limitations on the available computational resources, the stability of the dynamics of the planets of the solar system within the framework of the proposed method was confirmed for a period of ten million years. With the help of a computational experiment, one of the possible scenarios for the disintegration of the solar systems is also considered.

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

В первой части статьи мы рассматриваем два класса «хороших» невыпуклых функций, которые могут быть ограничены снизу и сверху параболической функцией. Такой класс задач не исследован широко в литературе, хотя является довольно интересным с прикладной точки зрения. Более того, для таких задач методы первого и более высоких порядков могут быть абсолютно неэффективны при поиске глобального минимума. Это связано с тем, что функция может сильно осциллировать или может быть сильно зашумлена. Поэтому наши новые методы используют информацию только нулевого порядка и основаны на поиске по сетке. Размер и мелкость этой сетки, а значит, и гарантии скорости сходимости и оракульной сложности зависят от «хорошести» задачи. В частности, мы показываем, если функция зажата довольно близкими параболическими функциями, то сложность не зависит от размерности задачи. Мы показываем, что наши новые методы сходятся с линейной скоростью сходимости $\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.

В работе рассмотрена краевая задача о движении тепловой волны для вырождающегося уравнения второго порядка параболического типа со степенной нелинейностью. Краевое условие задает уравнение движения на плоскости нулевого фронта тепловой волны, имеющего форму окружности. Предложен новый численно-аналитический алгоритм, в соответствии с которым решение строится по шагам по времени при разностной схеме дискретизации времени. На каждом шаге рассматривается краевая задача для уравнения Пуассона, к которому сводится исходное уравнение. Фактически она является обратной задачей Коши, в которой исходная граница области решения свободна от граничных условий, а на текущей границе (фронте волны) заданы два условия (Неймана и Дирихле). Решение этой задачи ищется в виде суммы частного решения уравнения Пуассона и решения соответствующего уравнения Лапласа, удовлетворяющего граничным условиям. Поскольку неоднородность зависит от искомой функции и ее производных, решение строится итерационно. Частное решение ищется методом коллокаций с помощью разложения неоднородности по радиальным базисным функциям. Обратная задача Коши для уравнения Лапласа решается методом нулевого поля применительно к круговым областям с круговыми отверстиями. Для таких задач этот метод применяется впервые. Вычислительный алгоритм оптимизирован за счет распараллеливания вычислений. Распараллеливание вычислений позволило эффективно реализовать алгоритм на высокопроизводительных вычислительных системах. На базе алгоритма была создана компьютерная программа. В качестве средства распараллеливания был выбран стандарт параллельного программирования 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.

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

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

Численные решения сопоставлены с результатами других авторов, полученных по схемам повышенного порядка аппроксимации: КАБАРЕ, HLLC (Harten Lax van Leer Contact), CFLFh (CFLF hybrid scheme), JT (centered scheme with limiter by Jiang and Tadmor), PPM (Piecewise Parabolic Method), WENO5 (weighted essentially non-oscillatory scheme), RKGD (Runge–Kutta Discontinuous Galerkin), с гибридной взвешенной нелинейной интерполяцией CCSSR-HW4 и CCSSR-HW6. К достоинствам гибридного метода крупных частиц относятся расширенные возможности решения задач гиперболического и смешанного типов, хорошее соотношение диссипативных и дисперсионных свойств, сочетание алгоритмической простоты и высокой разрешающей способности в задачах со сложной ударно-волновой структурой, развитием неустойчивости и вихреобразованием на контактных границах.

We study the computational properties of a parametric class of finite-volume schemes with customizable dissipative properties with splitting by physical processes into Lagrangian, Eulerian, and the final stages (the hybrid large-particle method). The method has a second-order approximation in space and time on smooth solutions. The regularization of a numerical solution at the Lagrangian stage is performed by nonlinear correction of artificial viscosity. Regardless of the grid resolution, the artificial viscosity value tends to zero outside the zone of discontinuities and extremes in the solution. At Eulerian and final stages, primitive variables (density, velocity, and total energy) are first reconstructed by an additive combination of upwind and central approximations weighted by a flux limiter. Then numerical divergent fluxes are formed from them. In this case, discrete analogs of conservation laws are performed.

The analysis of dissipative properties of the method using known viscosity and flow limiters, as well as their linear combination, is performed. The resolution of the scheme and the quality of numerical solutions are demonstrated by examples of two-dimensional benchmarks: a gas flow around the step with Mach numbers 3, 10 and 20, the double Mach reflection of a strong shock wave, and the implosion problem. The influence of the scheme viscosity of the method on the numerical reproduction of a gases interface instability is studied. It is found that a decrease of the dissipation level in the implosion problem leads to the symmetric solution destruction and formation of a chaotic instability on the contact surface.

Numerical solutions are compared with the results of other authors obtained using higher-order approximation schemes: CABARET, HLLC (Harten Lax van Leer Contact), CFLFh (CFLF hybrid scheme), JT (centered scheme with limiter by Jiang and Tadmor), PPM (Piecewise Parabolic Method), WENO5 (weighted essentially non-oscillatory scheme), RKGD (Runge –Kutta Discontinuous Galerkin), hybrid weighted nonlinear schemes CCSSR-HW4 and CCSSR-HW6. The advantages of the hybrid large-particle method include extended possibilities for solving hyperbolic and mixed types of problems, a good ratio of dissipative and dispersive properties, a combination of algorithmic simplicity and high resolution in problems with complex shock-wave structure, both instability and vortex formation at interfaces.