All issues

Работа посвящена вопросам приближения периодических функций высокой гладкости средними арифметическими суммами Фурье. Наиболее естественным и простым примером линейного процесса аппроксимации непрерывных периодических функций действительной переменной является приближение элементами последовательностей частичных сумм ряда Фурье. Известно, что последовательности частичных сумм ряда Фурье не являются равномерно сходящимися на всем пространстве C 2$\pi$-периодических непрерывных функций. Значительное число работ данного направления посвящено изучению аппроксимативных свойств методов приближения, которые для заданной функции $f$ образуются с помощью преобразований частичных сумм ее ряда Фурье и позволяют построить последовательности тригонометрических полиномов, которые равномерно сходятся для каждой функции $f \in C$. На протяжении последних десятилетий широко изучаются суммы Валле Пуссена и их частные случаи суммы Фейера. Одним из наиболее важных направлений в этой области является изучение асимптотического поведения верхних граней уклонений средних арифметических сумм Фурье по различным классам периодических функций. Методы исследования интегральных представлений уклонений тригонометрических полиномов, которые порождаются линейными методами суммирования рядов Фурье, возникли и получили свое развитие в работах С.М. Никольского, С.Б. Стечкина, Н.П. Корнейчука, В.К. Дзядыка и их учеников.

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

The paper deals with the problems of approximation of periodic functions of high smoothness by arithmetic means of Fourier sums. The simplest and natural example of a linear process of approximation of continuous periodic functions of a real variable is the approximation of these functions by partial sums of the Fourier series. However, the sequences of partial Fourier sums are not uniformly convergent over the entire class of continuous $2\pi$-periodic functions. In connection with this, a significant number of papers is devoted to the study of the approximative properties of other approximation methods, which are generated by certain transformations of the partial sums of Fourier series and allow us to construct sequences of trigonometrical polynomials that would be uniformly convergent for each function $f \in C$. In particular, over the past decades, de la Vallee Poussin sums and Fejer sums have been widely studied. One of the most important directions in this field is the study of the asymptotic behavior of upper bounds of deviations of arithmetic means of Fourier sums on different classes of periodic functions. Methods of investigation of integral representations of deviations of polynomials on the classes of periodic differentiable functions of real variable originated and received its development through the works of S.M. Nikol’sky, S.B. Stechkin, N.P. Korneichuk, V.K. Dzadyk, etc.

The aim of the work systematizes known results related to the approximation of classes of periodic functions of high smoothness by arithmetic means of Fourier sums, and presents new facts obtained for particular cases. In the paper is studied the approximative properties of $r$-repeated de la Vallee Poussin sums on the classes of periodic functions that can be regularly extended into the fixed strip of the complex plane. We obtain asymptotic formulas for upper bounds of the deviations of repeated de la Vallee Poussin sums taken over classes of periodic analytic functions. In certain cases, these formulas give a solution of the corresponding Kolmogorov–Nikolsky problem. We indicate conditions under which the repeated de la Vallee Poussin sums guarantee a better order of approximation than ordinary de la Vallee Poussin sums.

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

In various applications arise problems modeled by nonlinear partial differential equations on graphs (networks, trees). In order to study such problems and various extreme situations arose in the problems of designing and optimizing networks developed the computational model based on solving the corresponding boundary problems for partial differential equations of hyperbolic type on graphs (networks, trees). As applications, three different problems were chosen solved in the framework of the general approach of network computational models. The first was modeling of traffic flow. In solving this problem, a macroscopic approach was used in which the transport flow is described by a nonlinear system of second-order hyperbolic equations. The results of numerical simulations showed that the model developed as part of the proposed approach well reproduces the real situation various sections of the Moscow transport network on significant time intervals and can also be used to select the most optimal traffic management strategy in the city. The second was modeling of data flows in computer networks. In this problem data flows of various connections in packet data network were simulated as some continuous medium flows. Conceptual and mathematical network models are proposed. The numerical simulation was carried out in comparison with the NS-2 network simulation system. The results showed that in comparison with the NS-2 packet model the developed streaming model demonstrates significant savings in computing resources while ensuring a good level of similarity and allows us to simulate the behavior of complex globally distributed IP networks. The third was simulation of the distribution of gas impurities in ventilation networks. It was developed the computational mathematical model for the propagation of finely dispersed or gas impurities in ventilation networks using the gas dynamics equations by numerical linking of regions of different sizes. The calculations shown that the model with good accuracy allows to determine the distribution of gas-dynamic parameters in the pipeline network and solve the problems of dynamic ventilation management.

Универсальные сценарии перехода к хаосу в динамических системах к настоящему моменту хорошо изучены. К типичным сценариям относятся каскад бифуркаций удвоения периода (сценарий Фейген-баума), разрушение тора малой размерности (сценарий Рюэля–Такенса) и переход через перемежаемость (сценарий Помо–Манневилля). В более сложных пространственно-распределенных динамических системах нарастающая с изменением параметра сложность поведения по времени тесно переплетается с формированием пространственных структур. Однако вопрос о том, могут ли в каком-то сценарии пространственная и временная оси полностью поменяться ролями, до сих пор остается открытым. В данной работе впервые предлагается математическая модель конвекции–реакции–диффузии, в рамках которой реализуется пространственный аналог перехода к хаосу через разрушение квазипериодического режима в рамках сценария Рюэля–Такенса. Исследуемая физическая система представляет собой два водных раствора кислоты (A) и основания (B), в начальный момент времени разделенных по пространству и помещенных в вертикальную ячейку Хеле–Шоу, находящуюся в статическом поле тяжести. При приведении растворов в контакт начинается фронтальная реакция нейтрализации второго порядка: A + B $\to$ C, которая сопровождается выделением соли (С). Процесс характеризуется сильной зависимостью коэффициентов диффузии реагентов от их концентрации, что приводит к возникновению двух локальных зон пониженной плотности, в которых независимо друг от друга возникают хемоконвективные движения жидкости. Слои, в которых развивается конвекция, все время остаются разделенными прослойкой неподвижной жидкости, но они могут влиять друг на друга посредством диффузии реагентов через прослойку. Формирующаяся хемо-конвективная структура представляет собой модулированную стоячую волну, постепенно разрушающуюся со временем, повторяя последовательность бифуркаций сценария разрушения двумерного тора. Показано, что в ходе эволюции системы пространственная ось, направленная вдоль фронта реакции, выполняет роль времени, а само время играет роль управляющего параметра.

In the last decades, universal scenarios of the transition to chaos in dynamic systems have been well studied. The scenario of the transition to chaos is defined as a sequence of bifurcations that occur in the system under the variation one of the governing parameters and lead to a qualitative change in dynamics, starting from the regular mode and ending with chaotic behavior. Typical scenarios include a cascade of period doubling bifurcations (Feigenbaum scenario), the breakup of a low-dimensional torus (Ruelle–Takens scenario), and the transition to chaos through the intermittency (Pomeau–Manneville scenario). In more complicated spatially distributed dynamic systems, the complexity of dynamic behavior growing with a parameter change is closely intertwined with the formation of spatial structures. However, the question of whether the spatial and temporal axes could completely exchange roles in some scenario still remains open. In this paper, for the first time, we propose a mathematical model of convection–diffusion–reaction, in which a spatial transition to chaos through the breakup of the quasi–periodic regime is realized in the framework of the Ruelle–Takens scenario. The physical system under consideration consists of two aqueous solutions of acid (A) and base (B), initially separated in space and placed in a vertically oriented Hele–Shaw cell subject to the gravity field. When the solutions are brought into contact, the frontal neutralization reaction of the second order A + B $\to$ C begins, which is accompanied by the production of salt (C). The process is characterized by a strong dependence of the diffusion coefficients of the reagents on their concentration, which leads to the appearance of two local zones of reduced density, in which chemoconvective fluid motions develop independently. Although the layers, in which convection develops, all the time remain separated by the interlayer of motionless fluid, they can influence each other via a diffusion of reagents through this interlayer. The emerging chemoconvective structure is the modulated standing wave that gradually breaks down over time, repeating the sequence of the bifurcation chain of the Ruelle–Takens scenario. We show that during the evolution of the system one of the spatial axes, directed along the reaction front, plays the role of time, and time itself starts to play the role of a control parameter.

В данной работе рассматривается возможность применения концепции $(\delta, L)$-модели функции для оптимизационных задач, в которых посредством решения прямой задачи имеется необходимость восстанавливать решение двойственной задачи. Концепция $(\delta, L)$-модели основана на концепции $(\delta, L)$-оракула, предложенной Деволдером–Глинером–Нестеровым, при этом данные авторы предложили фукнционалы в оптимизационных задачах аппроксимировать сверху выпуклой параболой с некоторым аддитивным шумом $\delta$; таким образом, им удалось получить квадратичные верхние оценки с шумом даже для негладких функционалов. Концепция $(\delta, L)$-модели продолжает эту идею за счет того, что аппроксимация сверху делается не выпуклой параболой, а некоторым более сложным выпуклым функционалом. Возможность восстанавливать решение двойственной задачи хорошо зарекомендовала себя, так как во многих случаях в прямой задаче можно значительно быстрее находить решение, чем в двойственной. Отметим, что прямо-двойственные методы хорошо изучены, но при этом, как правило, каждый метод предлагается под конкретный класс задач. Наша же цель — предложить метод, который бы включал в себя сразу различные методы. Это реализуется за счет использования концепции $(\delta, L)$-модели и адаптивной структуры наших методов. Таким образом, нам удалось получить прямо-двойственный адаптивный градиентный метод и быстрый градиентный метод с $(\delta, L)$-моделью и доказать оценки сходимости для них, причем для некоторых классов задач данные оценки являются оптимальными. Основная идея заключается в том, что нахождение двойственных решений происходит относительно оптимизационной задачи, которая аппроксимируют прямую с помощью концепции $(\delta, L)$-модели и имеет более простую структуру, поэтому находить двойственное решение у нее проще. Стоит отметить, что это происходит на каждом шаге работы оптимизационного метода; таким образом, реализуется принцип «разделяй и властвуй».

In this work we consider a possibility to use the conception of $(\delta, L)$-model of a function for optimization tasks, whereby solving a primal problem there is a necessity to recover a solution of a dual problem. The conception of $(\delta, L)$-model is based on the conception of $(\delta, L)$-oracle which was proposed by Devolder–Glineur–Nesterov, herewith the authors proposed approximate a function with an upper bound using a convex quadratic function with some additive noise $\delta$. They managed to get convex quadratic upper bounds with noise even for nonsmooth functions. The conception of $(\delta, L)$-model continues this idea by using instead of a convex quadratic function a more complex convex function in an upper bound. Possibility to recover the solution of a dual problem gives great benefits in different problems, for instance, in some cases, it is faster to find a solution in a primal problem than in a dual problem. Note that primal-dual methods are well studied, but usually each class of optimization problems has its own primal-dual method. Our goal is to develop a method which can find solutions in different classes of optimization problems. This is realized through the use of the conception of $(\delta, L)$-model and adaptive structure of our methods. Thereby, we developed primal-dual adaptive gradient method and fast gradient method with $(\delta, L)$-model and proved convergence rates of the methods, moreover, for some classes of optimization problems the rates are optimal. The main idea is the following: we find a dual solution to an approximation of a primal problem using the conception of $(\delta, L)$-model. It is much easier to find a solution to an approximated problem, however, we have to do it in each step of our method, thereby the principle of “divide and conquer” is realized.

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

The paper concerns the study of the Rice statistical distribution’s peculiarities which cause the possibility of its efficient application in solving the tasks of high precision phase measuring in optics. The strict mathematical proof of the Rician distribution’s stable character is provided in the example of the differential signal consideration, namely: it has been proved that the sum or the difference of two Rician signals also obey the Rice distribution. Besides, the formulas have been obtained for the parameters of the resulting summand or differential signal’s Rice distribution. Based upon the proved stable character of the Rice distribution a new original technique of the high precision measuring of the two quasi-harmonic signals’ phase shift has been elaborated in the paper. This technique is grounded in the statistical analysis of the measured sampled data for the amplitudes of the both signals and for the amplitude of the third signal which is equal to the difference of the two signals to be compared in phase. The sought-for phase shift of two quasi-harmonic signals is being calculated from the geometrical considerations as an angle of a triangle which sides are equal to the three indicated signals’ amplitude values having been reconstructed against the noise background. Thereby, the proposed technique of measuring the phase shift using the differential signal analysis, is based upon the amplitude measurements only, what significantly decreases the demands to the equipment and simplifies the technique implementation in practice. The paper provides both the strict mathematical substantiation of a new phase shift measuring technique and the results of its numerical testing. The elaborated method of high precision phase measurements may be efficiently applied for solving a wide circle of tasks in various areas of science and technology, in particular — at distance measuring, in communication systems, in navigation, etc.

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

In this paper, using our bifurcation-geometric approach, we study global dynamics and solve the problem of the maximum number and distribution of limit cycles (self-oscillating regimes corresponding to states of dynamical equilibrium) in a planar polynomial mechanical system of the Euler–Lagrange–Liйnard type. Such systems are also used to model electrical, ecological, biomedical and other systems, which greatly facilitates the study of the corresponding real processes and systems with complex internal dynamics. They are used, in particular, in mechanical systems with damping and stiffness. There are a number of examples of technical systems that are described using quadratic damping in second-order dynamical models. In robotics, for example, quadratic damping appears in direct-coupled control and in nonlinear devices, such as variable impedance (resistance) actuators. Variable impedance actuators are of particular interest to collaborative robotics. To study the character and location of singular points in the phase plane of the Euler–Lagrange–Liйnard polynomial system, we use our method the meaning of which is to obtain the simplest (well-known) system by vanishing some parameters (usually, field rotation parameters) of the original system and then to enter sequentially these parameters studying the dynamics of singular points in the phase plane. To study the singular points of the system, we use the classical Poincarй index theorems, as well as our original geometric approach based on the application of the Erugin twoisocline method which is especially effective in the study of infinite singularities. Using the obtained information on the singular points and applying canonical systems with field rotation parameters, as well as using the geometric properties of the spirals filling the internal and external regions of the limit cycles and applying our geometric approach to qualitative analysis, we study limit cycle bifurcations of the system under consideration.

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

Roads are a shared resource which can be used either by drivers and autonomous vehicles. Since the total number of vehicles increases annually, each considered vehicle spends more time in traffic jams, and thus the total travel time prolongs. The main purpose while planning the road system is to reduce the time spent on traveling. The optimization of transportation networks is a current goal, thus the formation of traffic flows by creating certain ligaments of the roads is of high importance. The Braess paradox states the existence of a network where the construction of a new edge leads to the increase of traveling time. The objective of this paper is to propose various solutions to the Braess paradox in the presence of autonomous vehicles. One of the methods of solving transportation topology problems is to introduce artificial restrictions on traffic. As an example of such restrictions, this article considers designated lanes which are available only for a certain type of vehicles. Designated lanes have their own location in the network and operating conditions. This article observes the most common two-roads traffic situations, analyzes them using analytical and numerical methods and presents the model of optimal traffic flow distribution, which considers different ways of lanes designation on isolated transportation networks. It was found that the modeling of designated lanes eliminates Braess’ paradox and optimizes the total traveling time. The solutions were shown on artificial networks and on the real-life example. A modeling algorithm for Braess network was proposed and its correctness was verified using the real-life example.

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

In this paper, we consider the conjugate gradient method for solving the problem of minimizing a quadratic function with additive noise in the gradient. Three concepts of noise were considered: antagonistic noise in the linear term, stochastic noise in the linear term and noise in the quadratic term, as well as combinations of the first and second with the last. It was experimentally obtained that error accumulation is absent for any of the considered concepts, which differs from the folklore opinion that, as in accelerated methods, error accumulation must take place. The paper gives motivation for why the error may not accumulate. The dependence of the solution error both on the magnitude (scale) of the noise and on the size of the solution using the conjugate gradient method was also experimentally investigated. Hypotheses about the dependence of the error in the solution on the noise scale and the size (2-norm) of the solution are proposed and tested for all the concepts considered. It turned out that the error in the solution (by function) linearly depends on the noise scale. The work contains graphs illustrating each individual study, as well as a detailed description of numerical experiments, which includes an account of the methods of noise of both the vector and the matrix.

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

The paper presents a numerical solution to the heat wave motion problem for a degenerate second-order nonlinear parabolic equation with a source term. The nonlinearity is conditioned by the power dependence of the heat conduction coefficient on temperature. The problem for the case of two spatial variables is considered with the boundary condition specifying the heat wave motion law. A new solution algorithm based on an expansion in radial basis functions and the boundary element method is proposed. The solution is constructed stepwise in time with finite difference time approximation. At each time step, a boundary value problem for the Poisson equation corresponding to the original equation at a fixed time is solved. The solution to this problem is constructed iteratively as the sum of a particular solution to the nonhomogeneous equation and a solution to the corresponding homogeneous equation satisfying the boundary conditions. The homogeneous equation is solved by the boundary element method. The particular solution is sought by the collocation method using inhomogeneity expansion in radial basis functions. The calculation algorithm is optimized by parallelizing the computations. The algorithm is implemented as a program written in the C++ language. The parallel computations are organized by using the OpenCL standard, and this allows one to run the same parallel code either on multi-core CPUs or on graphic CPUs. Test cases are solved to evaluate the effectiveness of the proposed solution method and the correctness of the developed computational technique. The calculation results are compared with known exact solutions, as well as with the results we obtained earlier. The accuracy of the solutions and the calculation time are estimated. The effectiveness of using various systems of radial basis functions to solve the problems under study is analyzed. The most suitable system of functions is selected. The implemented complex computational experiment shows higher calculation accuracy of the proposed new algorithm than that of the previously developed one.

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

$$ \text{Argmin}_{x\in X}{\langle p,\,x \rangle} $$

для заданного вектора $p \in \mathbb{R}^n$. Существует целый ряд методов условного градиента, имеющих линейную скорость сходимости в сильно выпуклом случае. Однако во всех этих методах в оценку скорости сходимости входит размерность задачи, которая в современных приложениях может быть очень большой. В данной работе доказывается, что в сильно выпуклом случае скорость сходимости методов условного градиента в лучшем случае зависит от размерности задачи $n$ как $\widetilde{\Omega}\left(\!\sqrt{n}\right)$. Таким образом, методы условного градиента могут оказаться неэффективными для решения сильно выпуклых оптимизационных задач больших размерностей.

Отдельно рассматривается приложение методов условного градиента к задачам минимизации квадратичной формы. Уже была доказана эффективность метода Франк – Вульфа для решения задачи квадратичной оптимизации в выпуклом случае на симплексе (PageRank). Данная работа показывает, что использование методов условного градиента для минимизации квадратичной формы в сильно выпуклом случае малоэффективно из-за наличия размерности в оценке скорости сходимости этих методов. Поэтому рассматривается метод рестартов условного градиента (Shrinking Conditional Gradient). Его отличие от методов условного градиента заключается в том, что в нем используется модифицированный линейный минимизационный оракул, который для заданного вектора $p \in \mathbb{R}^n$ вычисляет решение задачи $$ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. $$ В оценку скорости сходимости такого алгоритма размерность уже не входит. С помощью рестартов метода условного градиента получена сложность (число арифметических операций) минимизации квадратичной формы на $\infty$-шаре. Полученная оценка работы метода сравнима со сложностью градиентного метода.

In this paper, we consider conditional gradient methods for optimizing strongly convex functions. These are methods that use a linear minimization oracle, which, for a given vector $p \in \mathbb{R}^n$, computes the solution of the subproblem

\[ \text{Argmin}_{x\in X}{\langle p,\,x \rangle}. \]There are a variety of conditional gradient methods that have a linear convergence rate in a strongly convex case. However, in all these methods, the dimension of the problem is included in the rate of convergence, which in modern applications can be very large. In this paper, we prove that in the strongly convex case, the convergence rate of the conditional gradient methods in the best case depends on the dimension of the problem $ n $ as $ \widetilde {\Omega} \left(\!\sqrt {n}\right) $. Thus, the conditional gradient methods may turn out to be ineffective for solving strongly convex optimization problems of large dimensions.

Also, the application of conditional gradient methods to minimization problems of a quadratic form is considered. The effectiveness of the Frank – Wolfe method for solving the quadratic optimization problem in the convex case on a simplex (PageRank) has already been proved. This work shows that the use of conditional gradient methods to solve the minimization problem of a quadratic form in a strongly convex case is ineffective due to the presence of dimension in the convergence rate of these methods. Therefore, the Shrinking Conditional Gradient method is considered. Its difference from the conditional gradient methods is that it uses a modified linear minimization oracle. It's an oracle, which, for a given vector $p \in \mathbb{R}^n$, computes the solution of the subproblem \[ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. \] The convergence rate of such an algorithm does not depend on dimension. Using the Shrinking Conditional Gradient method the complexity (the total number of arithmetic operations) of solving the minimization problem of quadratic form on a $ \infty $-ball is obtained. The resulting evaluation of the method is comparable to the complexity of the gradient method.