All issues

Предложено обобщение блочного клеточного автомата Марголуса на гексагональную сетку. Проведена статистическая обработка результатов вероятностных клеточно-автоматных вычислений для ряда модификаций схемы, решающей тестовую задачу диффузии вещества. Показано, что выбор блоков в виде гексагонов на 25% эффективнее, чем в виде Y-блоков. Показано, что алгоритмы имеют полиномиальную сложность, причем степень полинома для параллельных вычислителей лежит в пределах 0.6÷0.8, а для последовательных — в пределах 1.5÷1.7. Исследовалось влияние внедренных в поле клеточного автомата дефектных ячеек на скорость сходимости.

The generalization of Margolus’s block cellular automaton on a hexagonal grid is formulated. Statistical analysis of the results of probabilistic cellular automation for vast variety of this scheme solving the test task of diffusion is done. It is shown that the choice of the hexagon blocks is 25% more efficient than Y-blocks. It is shown that the algorithms have polynomial complexity, and the polynom degree lies within 0.6÷0.8 for parallel computer, and in the range 1.5÷1.7 for serial computer. The effects of embedded into automaton’s field defective cells on the rate of convergence are studied also.

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

При решении задачи Неймана для колебаний круглой мембраны показана критичность требований к дискретизации условий для граничных КА-ячеек. Для квазиодномерной задачи «диффузия в полупространство» сравниваются КА-расчеты, проводимые по простой схеме и с использованием обобщенного блочно-поворотного механизма Марголуса. При решении смешанной задачи для классического случая колебания круглой мембраны с закрепленными концами показано, что одновременное применение метода Кранка–Николсон и учет членов второго порядка позволяет избежать ИГС-эффекта, наблюдаемого нами для более простой схемы. С точки зрения КА центральное место занимает уравнение диффузии, на пути решения которого на бесконечных временах находится решение краевой задачи для уравнения Лапласа, а путем введения вектор-переменной становится разрешимо волновое уравнение (по крайней мере скалярное).

На примере центрально-симметричной задачи Неймана продемонстрирован новый способ введения пространственных производных в postfix-процедуру КА, отражающую временные производные (основанием является уравнение непрерывности). Для случая центральной симметрии эмпирически найдено значение константы, связывающее эти производные. Показано, что препятствием к применению КА-методов для таких задач являются низкая скорость сходимости и точность, лимитируемая точностью дискретизации границ, а не формальной точностью метода (4-й порядок); наша рекомендация состоит в использовании техники multigrid. При решении квазиодномерного уравнения диффузии (двумерным КА) показано, что блочно-поворотный КА (по механизму Марголуса) более эффективен, чем простой КА.

The second part of paper is devoted to final study of three classic partial differential equations (Laplace, Diffusion and Wave) solution using simple numerical methods in terms of Cellular Automata. Specificity of this solution has been shown by different examples, which are related to the hexagonal grid. Also the next statements that are mentioned in the first part have been proved: the matter conservation law and the offensive effect of excessive hexagonal symmetry.

From the point of CA view diffusion equation is the most important. While solving of diffusion equation at the infinite time interval we can find solution of boundary value problem of Laplace equation and if we introduce vector-variable we will solve wave equation (at least, for scalar). The critical requirement for the sampling of the boundary conditions for CA-cells has been shown during the solving of problem of circular membrane vibrations with Neumann boundary conditions. CA-calculations using the simple scheme and Margolus rotary-block mechanism were compared for the quasione-dimensional problem “diffusion in the half-space”. During the solving of mixed task of circular membrane vibration with the fixed ends in a classical case it has been shown that the simultaneous application of the Crank–Nicholson method and taking into account of the second-order terms is allowed to avoid the effect of excessive hexagonal symmetry that was studied for a simple scheme.

By the example of the centrally symmetric Neumann problem a new method of spatial derivatives introducing into the postfix CA procedure, which is reflecting the time derivatives (on the base of the continuity equation) was demonstrated. The value of the constant that is related to these derivatives has been empirically found in the case of central symmetry. The low rate of convergence and accuracy that limited within the boundaries of the sample, in contrary to the formal precision of the method (4-th order), prevents the using of the CAmethods for such problems. We recommend using multigrid method. During the solving of the quasi-diffusion equations (two-dimensional CA) it was showing that the rotary-block mechanism of CA (Margolus mechanism) is more effective than simple CA.

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

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

In the article a theory of the implicit iterative line-by-line recurrence method for solving the systems of finite-difference equations which arise as a result of approximation of the two-dimensional elliptic differential equations on a regular grid is stated. On the one hand, the high effectiveness of the method has confirmed in practice. Some complex test problems, as well as several problems of fluid flow and heat transfer of a viscous incompressible liquid, have solved with its use. On the other hand, the theoretical provisions that explain the high convergence rate of the method and its stability are not yet presented in the literature. This fact is the reason for the present investigation. In the paper, the procedure of equivalent and approximate transformations of the initial system of linear algebraic equations (SLAE) is described in detail. The transformations are presented in a matrix-vector form, as well as in the form of the computational formulas of the method. The key points of the transformations are illustrated by schemes of changing of the difference stencils that correspond to the transformed equations. The canonical form of the method is the goal of the transformation procedure. The correctness of the method follows from the canonical form in the case of the solution convergence. The estimation of norms of the matrix operators is carried out on the basis of analysis of structures and element sets of the corresponding matrices. As a result, the convergence of the method is proved for arbitrary initial vectors of the solution of the problem.

The norm of the transition matrix operator is estimated in the special case of weak restrictions on a desired solution. It is shown, that the value of this norm decreases proportionally to the second power (or third degree, it depends on the version of the method) of the grid step of the problem solution area in the case of transition matrix order increases. The necessary condition of the method stability is obtained by means of simple estimates of the vector of an approximate solution. Also, the estimate in order of magnitude of the optimum iterative compensation parameter is given. Theoretical conclusions are illustrated by using the solutions of the test problems. It is shown, that the number of the iterations required to achieve a given accuracy of the solution decreases if a grid size of the solution area increases. It is also demonstrated that if the weak restrictions on solution are violated in the choice of the initial approximation of the solution, then the rate of convergence of the method decreases essentially in full accordance with the deduced theoretical results.

Работа принадлежит направлению экспериментальной математики, исследующей свойства математических объектов вычислительными средствами компьютера. Базовым отображением служит экспоненциальное, топологические свойства (букеты Кантора) которого отличаются от свойств полиномиальных и рациональных функций на комплексной плоскости. Предметом исследования являются характер и особенности множеств Фату и Жюлиа, а также точек равновесия и орбит нуля трех итерированных комплекснозначных отображений: $f:z \to (1+ \mu) \exp (iz)$, $g : z \to \big(1+ \mu |z - z^*|\big) \exp (iz)$, $h : z \to \big(1+ \mu (z - z^* )\big) \exp (iz)$, где $z,\mu \in \mathbb{C}$, $z^* : \exp (iz^*) = z^*$. Для квазилинейного отображения g, не обладающего свойством аналитичности, было обнаружено два бифуркационных перехода: рождение новой точки равновесия (для него было найдено критическое значение параметра, а сама бифуркация представляет собой смешанный случай «вилки» и седлоузельного перехода) и переход к радикальной трансформации множества Фату. Выявлен нетривиальный характер сходимости к фиксированной точке, связанный с появлением «долин» на графике скоростей сходимости. Для двух других отображений существенна монопериодичность режимов, отмечен феномен «удвоения периода» (в одном случае по пути $39\to 3$, в другом — по пути $17\to 2$), причем обнаружено совпадение кратности периода и числа рукавов спирали множества Жюлиа в окрестности фиксированной точки. Приведен богатый иллюстративный материал, численные результаты экспериментов и сводные таблицы, отражающие параметрическую зависимость отображений. Сформулированы вопросы для дальнейшего исследования средствами традиционной математики.

The work belongs to the direction of experimental mathematics, which investigates the properties of mathematical objects by the computing facilities of a computer. The base is an exponential map, its topological properties (Cantor's bouquets) differ from properties of polynomial and rational complex-valued functions. The subject of the study are the character and features of the Fatou and Julia sets, as well as the equilibrium points and orbits of the zero of three iterated complex-valued mappings: $f:z \to (1+ \mu) \exp (iz)$, $g : z \to \big(1+ \mu |z - z^*|\big) \exp (iz)$, $h : z \to \big(1+ \mu (z - z^* )\big) \exp (iz)$, with $z,\mu \in \mathbb{C}$, $z^* : \exp (iz^*) = z^*$. For a quasilinear map g having no analyticity characteristic, two bifurcation transitions were discovered: the creation of a new equilibrium point (for which the critical value of the linear parameter was found and the bifurcation consists of “fork” type and “saddle”-node transition) and the transition to the radical transformation of the Fatou set. A nontrivial character of convergence to a fixed point is revealed, which is associated with the appearance of “valleys” on the graph of convergence rates. For two other maps, the monoperiodicity of regimes is significant, the phenomenon of “period doubling” is noted (in one case along the path $39\to 3$, in the other along the path $17\to 2$), and the coincidence of the period multiplicity and the number of sleeves of the Julia spiral in a neighborhood of a fixed point is found. A rich illustrative material, numerical results of experiments and summary tables reflecting the parametric dependence of maps are given. Some questions are formulated in the paper for further research using traditional mathematics methods.

В данной работе рассматривается проксимальный быстрый градиентный метод Монтейро – Свайтера (2013 г.), в котором используется один шаг метода Ньютона для приближенного решения вспомогательной задачи на каждой итерации проксимального метода. Метод Монтейро – Свайтера является оптимальным (по числу вычислений градиента и гессиана оптимизируемой функции) для достаточно гладких задач выпуклой оптимизации в классе методов, использующих только градиент и гессиан оптимизируемой функции. За счет замены шага метода Ньютона на шаг недавно предложенного тензорного метода Ю. Е. Нестерова (2018 г.), а также за счет специального обобщения условия подбора шага в проксимальном внешнем быстром градиентном методе удалось предложить оптимальный тензорный метод, использующий старшие производные. В частности, такой тензорный метод, использующий производные до третьего порядка включительно, оказался достаточно практичным ввиду сложности итерации, сопоставимой со сложностью итерации метода Ньютона. Таким образом, получено конструктивное решение задачи, поставленной Ю. Е. Нестеровым в 2018 г., об устранении зазора в точных нижних и завышенных верхних оценках скорости сходимости для имеющихся на данный момент тензорных методов порядка $p \geqslant 3$.

In this work we consider Monteiro – Svaiter accelerated hybrid proximal extragradient (A-HPE) framework and accelerated Newton proximal extragradient (A-NPE) framework. The last framework contains an optimal method for rather smooth convex optimization problems with second-order oracle. We generalize A-NPE framework for higher order derivative oracle (schemes). We replace Newton’s type step in A-NPE that was used for auxiliary problem by Newton’s regularized (tensor) type step (Yu. Nesterov, 2018). Moreover we generalize large step A-HPE/A-NPE framework by replacing Monteiro – Svaiter’s large step condition so that this framework could work for high-order schemes. The main contribution of the paper is as follows: we propose optimal highorder methods for convex optimization problems. As far as we know for that moment there exist only zero, first and second order optimal methods that work according to the lower bounds. For higher order schemes there exists a gap between the lower bounds (Arjevani, Shamir, Shiff, 2017) and existing high-order (tensor) methods (Nesterov – Polyak, 2006; Yu.Nesterov, 2008; M. Baes, 2009; Yu.Nesterov, 2018). Asymptotically the ratio of the rates of convergences for the best existing methods and lower bounds is about 1.5. In this work we eliminate this gap and show that lower bounds are tight. We also consider rather smooth strongly convex optimization problems and show how to generalize the proposed methods to this case. The basic idea is to use restart technique until iteration sequence reach the region of quadratic convergence of Newton method and then use Newton method. One can show that the considered method converges with optimal rates up to a logarithmic factor. Note, that proposed in this work technique can be generalized in the case when we can’t solve auxiliary problem exactly, moreover we can’t even calculate the derivatives of the functional exactly. Moreover, the proposed technique can be generalized to the composite optimization problems and in particular to the constraint convex optimization problems. We also formulate a list of open questions that arise around the main result of this paper (optimal universal method of high order e.t.c.).