All issues

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

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

На примере центрально-симметричной задачи Неймана продемонстрирован новый способ введения пространственных производных в 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.

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

This article solves the problem of vehicles drivers intoxication functional statedetermining. Its solution is relevant in the transport security field during pre-trip medical examination. The problem solution is based on the papillomometry method application, which allows to evaluate the driver state by his pupillary reaction to illumination change. The problem is to determine the state of driver inebriation by the analysis of the papillogram parameters values — a time series characterizing the change in pupil dimensions upon exposure to a short-time light pulse. For the papillograms analysis it is proposed to use a neural network. A neural network model for determining the drivers intoxication functional state is developed. For its training, specially prepared data samples are used which are the values of the following parameters of pupillary reactions grouped into two classes of functional states of drivers: initial diameter, minimum diameter, half-constriction diameter, final diameter, narrowing amplitude, rate of constriction, expansion rate, latent reaction time, the contraction time, the expansion time, the half-contraction time, and the half-expansion time. An example of the initial data is given. Based on their analysis, a neural network model is constructed in the form of a single-layer perceptron consisting of twelve input neurons, twenty-five neurons of the hidden layer, and one output neuron. To increase the model adequacy using the method of ROC analysis, the optimal cut-off point for the classes of solutions at the output of the neural network is determined. A scheme for determining the drivers intoxication state is proposed, which includes the following steps: pupillary reaction video registration, papillogram construction, parameters values calculation, data analysis on the base of the neural network model, driver’s condition classification as “norm” or “rejection of the norm”, making decisions on the person being audited. A medical worker conducting driver examination is presented with a neural network assessment of his intoxication state. On the basis of this assessment, an opinion on the admission or removal of the driver from driving the vehicle is drawn. Thus, the neural network model solves the problem of increasing the efficiency of pre-trip medical examination by increasing the reliability of the decisions made.

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

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

A direct algorithm for solving a linear programming problem (LP), given in canonical form, is considered. The algorithm consists of two successive stages, in which the following LP problems are solved by a direct method: a non-degenerate auxiliary problem at the first stage and some problem equivalent to the original one at the second. The construction of the auxiliary problem is based on a multiplicative version of the Gaussian exclusion method, in the very structure of which there are possibilities: identification of incompatibility and linear dependence of constraints; identification of variables whose optimal values are obviously zero; the actual exclusion of direct variables and the reduction of the dimension of the space in which the solution of the original problem is determined. In the process of actual exclusion of variables, the algorithm generates a sequence of multipliers, the main rows of which form a matrix of constraints of the auxiliary problem, and the possibility of minimizing the filling of the main rows of multipliers is inherent in the very structure of direct methods. At the same time, there is no need to transfer information (basis, plan and optimal value of the objective function) to the second stage of the algorithm and apply one of the ways to eliminate looping to guarantee final convergence.

Two variants of the algorithm for solving the auxiliary problem in conjugate canonical form are presented. The first one is based on its solution by a direct algorithm in terms of the simplex method, and the second one is based on solving a problem dual to it by the simplex method. It is shown that both variants of the algorithm for the same initial data (inputs) generate the same sequence of points: the basic solution and the current dual solution of the vector of row estimates. Hence, it is concluded that the direct algorithm is an algorithm of the simplex method type. It is also shown that the comparison of numerical schemes leads to the conclusion that the direct algorithm allows to reduce, according to the cubic law, the number of arithmetic operations necessary to solve the auxiliary problem, compared with the simplex method. An estimate of the number of iterations is given.

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

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

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

This paper presents algorithm for modeling set of trajectories of non-stationary time series, based on a numerical scheme for approximating the sample density of the distribution function in a problem with fixed ends, when the initial distribution for a given number of steps transforms into a certain final distribution, so that at each step the semigroup property of solving the Liouville equation is satisfied. The model makes it possible to numerically construct evolving densities of distribution functions during random switching of states of the system generating the original time series.

The main problem is related to the fact that with the numerical implementation of the left-hand differential derivative in time, the solution becomes unstable, but such approach corresponds to the modeling of evolution. An integrative approach is used while choosing implicit stable schemes with “going into the future”, this does not match the semigroup property at each step. If, on the other hand, some real process is being modeled, in which goal-setting presumably takes place, then it is desirable to use schemes that generate a model of the transition process. Such model is used in the future in order to build a predictor of the disorder, which will allow you to determine exactly what state the process under study is going into, before the process really went into it. The model described in the article can be used as a tool for modeling real non-stationary time series.

Steps of the modeling scheme are described further. Fragments corresponding to certain states are selected from a given time series, for example, trends with specified slope angles and variances. Reference distributions of states are compiled from these fragments. Then the empirical distributions of the duration of the system’s stay in the specified states and the duration of the transition time from state to state are determined. In accordance with these empirical distributions, a probabilistic model of the disorder is constructed and the corresponding trajectories of the time series are modeled.

Для автономных систем ОДУ рассмотрено простейшее подмножество двухстадийных схем Розенброка с комплексными коэффициентами, численная реализация которых требует одного LU-разложения и одного вычисления Якобиана за шаг интегрирования.

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

The basic subset of two-stage Rosenbrock schemes with complex coefficients for numerical solution of autonomous systems of ordinary differential equations (ODE) has been considered. Numerical realization of such schemes requires one LU-decomposition, two computations of right side function and one computation of Jacoby matrix of the system per one step. The full theoretical investigation of accuracy and stability of such schemes have been done. New A-stable methods of the 3-rd order of accuracy with different properties have been constructed. There are high order L-decremented schemes as well as schemes with simple estimation of the main term of truncation error which is necessary for automatic evaluation of time step. Testing of new methods has been performed.

Разработан алгоритм ускоренного моделирования КМОП СБИС (Сверх Больших Интегральных Схем с Комплементарной логикой на транзисторах Металл-Окисел-Проводник) под управлением точности. Алгоритм обеспечивает возможность проведения параллельного числительного эксперимента в много процессорной вычислительной среде. Ускорение расчета осуществляется за счет применения блочно-матричной и структурной (DCCC) декомпозиций. Особенность подхода состоит в выборе моментов и способов обмена параметрами и в применении многоскоростных методов интегрирования в процессе расчета подсистем. Благодаря этому имеется возможность оценивать и контролировать погрешность по требуемым характеристикам.

We developed an algorithm for fast simulation of VLSI CMOS (Very Large Scale Integration with Complementary Metal-Oxide-Semiconductors) with an accuracy control. The algorithm provides an ability of parallel numerical experiments in multiprocessor computational environment. There is computation speed up by means of block-matrix and structural (DCCC) decompositions application. A feature of the approach is both in a choice of moments and ways of parameters synchronization and application of multi-rate integration methods. Due to this fact we have ability to estimate and control error of given characteristics.

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

Necessary and sufficient conditions for the existence of solutions of nonlinear nonautonomous periodic problem for Hill’s equation in the case of parametric resonance. A characteristic feature of the task is the need of finding, as desired solution, and the corresponding eigenfunction, which ensures solvability of the periodic problem for Hill’s equation in the case of parametric resonance. To construct solutions of the periodic problem for Hill’s equation and the corresponding eigenfunction in the case of parametric resonance proposed iterative scheme, based on the method of simple iterations with used list-square technics.

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

Modification of the lattice Boltzmann method for computation of viscous incompressible fluid flows is proposed. The method is based on the splitting of differential operator in Navier–Stokes equation and on the idea of instantaneous Maxwellisation of distribution function. The method is based on explicit schemes and didn’t have any problems with parallelization of computations. The stability of the method is demonstrated using von Neumann method in a wide range of input parameter values. The efficiency of the method proposed is demonstrated on the solution of the problem of 2D lid-driven cavity flow.