Все выпуски

Задача поиска PageRank вектора представляет большой научный и практический интерес ввиду своей применимости к работе современных поисковых систем. Несмотря на то, что данная задача сводится к поиску собственного вектора стохастической матрицы $P$, потребность в новых алгоритмах для ее решения обусловлена большими размерами входных данных. Для достижения не более чем линейного времени работы применяются различные рандомизированные методы, возвращающие ожидаемый ответ лишь с некоторой достаточно близкой к единице вероятностью. Нами рассматриваются два таких способа, сводящие задачу поиска вектора PageRank к задаче поиска равновесия в антагонистической матричной игре, которая затем решается с помощью алгоритма Григориадиса – Хачияна. При этом данная реализация эффективно работает в предположении о разреженности матрицы, подаваемой на вход. Насколько нам известно, до сих пор не было ни одной успешной реализации ни алгоритма Григориадиса – Хачияна, ни его применения к задаче поиска вектора PageRank. Данная статья ставит перед собой задачу восполнить этот пробел. В работе приводится описание двух версий алгоритма с псевдокодом и некоторые детали их реализации. Кроме того, в работе рассматривается другой вероятностный метод поиска вектора PageRank, а именно Markov chain Monte Carlo (MCMC), с целью сравнения результатов работы указанных алгоритмов на матрицах с различными значениями спектральной щели. Последнее представляет особый интерес, поскольку значение спектральной щели сильно влияет на скорость сходимости MCMC, и не оказывает никакого влияния на два других подхода. Сравнение проводилось на сгенерированных графах двух видов: цепочках и $d$-мерных кубах. Проведенные эксперименты, как и предсказывает теория, демонстрируют эффективность алгоритма Григориадиса – Хачияна по сравнению с MCMC для разреженных графов с маленьким значением спектральной щели. Весь код находится в открытом доступе, так чтобы все желающие могли воспроизвести полученные результаты самостоятельно, или же использовать данную реализацию в своих нуждах. Работа имеет чисто практическую направленность, никаких теоретических результатов авторами получено не было.

Finding PageRank vector is of great scientific and practical interest due to its applicability to modern search engines. Despite the fact that this problem is reduced to finding the eigenvector of the stochastic matrix $P$, the need for new algorithms is justified by a large size of the input data. To achieve no more than linear execution time, various randomized methods have been proposed, returning the expected result only with some probability close enough to one. We will consider two of them by reducing the problem of calculating the PageRank vector to the problem of finding equilibrium in an antagonistic matrix game, which is then solved using the Grigoriadis – Khachiyan algorithm. This implementation works effectively under the assumption of sparsity of the input matrix. As far as we know, there are no successful implementations of neither the Grigoriadis – Khachiyan algorithm nor its application to the task of calculating the PageRank vector. The purpose of this paper is to fill this gap. The article describes an algorithm giving pseudocode and some details of the implementation. In addition, it discusses another randomized method of calculating the PageRank vector, namely, Markov chain Monte Carlo (MCMC), in order to compare the results of these algorithms on matrices with different values of the spectral gap. The latter is of particular interest, since the magnitude of the spectral gap strongly affects the convergence rate of MCMC and does not affect the other two approaches at all. The comparison was carried out on two types of generated graphs: chains and $d$-dimensional cubes. The experiments, as predicted by the theory, demonstrated the effectiveness of the Grigoriadis – Khachiyan algorithm in comparison with MCMC for sparse graphs with a small spectral gap value. The written code is publicly available, so everyone can reproduce the results themselves or use this implementation for their own needs. The work has a purely practical orientation, no theoretical results were obtained.

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

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

In this paper we propose high-order (tensor) methods for two types of saddle point problems. Firstly, we consider the classic min-max saddle point problem. Secondly, we consider the search for a stationary point of the saddle point problem objective by its gradient norm minimization. Obviously, the stationary point does not always coincide with the optimal point. However, if we have a linear optimization problem with linear constraints, the algorithm for gradient norm minimization becomes useful. In this case we can reconstruct the solution of the optimization problem of a primal function from the solution of gradient norm minimization of dual function. In this paper we consider both types of problems with no constraints. Additionally, we assume that the objective function is $\mu$-strongly convex by the first argument, $\mu$-strongly concave by the second argument, and that the $p$-th derivative of the objective is Lipschitz-continous.

For min-max problems we propose two algorithms. Since we consider strongly convex a strongly concave problem, the first algorithm uses the existing tensor method for regular convex concave saddle point problems and accelerates it with the restarts technique. The complexity of such an algorithm is linear. If we additionally assume that our objective is first and second order Lipschitz, we can improve its performance even more. To do this, we can switch to another existing algorithm in its area of quadratic convergence. Thus, we get the second algorithm, which has a global linear convergence rate and a local quadratic convergence rate.

Finally, in convex optimization there exists a special methodology to solve gradient norm minimization problems by tensor methods. Its main idea is to use existing (near-)optimal algorithms inside a special framework. I want to emphasize that inside this framework we do not necessarily need the assumptions of strong convexity, because we can regularize the convex objective in a special way to make it strongly convex. In our article we transfer this framework on convex-concave objective functions and use it with our aforementioned algorithm with a global linear convergence and a local quadratic convergence rate.

Since the saddle point problem is a particular case of the monotone variation inequality problem, the proposed methods will also work in solving strongly monotone variational inequality problems.

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

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

The work is devoted to the construction and analysis of difference schemes for a system of hemodynamic equations obtained by averaging the hydrodynamic equations of a viscous incompressible fluid over the vessel cross-section. Models of blood as an ideal and as a viscous Newtonian fluid are considered. Difference schemes that approximate equations with second order on the spatial variable are proposed. The computational algorithms of the constructed schemes are based on the method of splitting on physical processes. According to this approach, at one time step, the model equations are considered separately and sequentially. The practical implementation of the proposed schemes at each time step leads to a sequential solution of two linear systems with tridiagonal matrices. It is demonstrated that the schemes are $\rho$-stable under minor restrictions on the time step in the case of sufficiently smooth solutions.

For the problem with a known analytical solution, it is demonstrated that the numerical solution has a second order convergence in a wide range of spatial grid step. The proposed schemes are compared with well-known explicit schemes, such as the Lax – Wendroff, Lax – Friedrichs and McCormack schemes in computational experiments on modeling blood flow in model vascular systems. It is demonstrated that the results obtained using the proposed schemes are close to the results obtained using other computational schemes, including schemes constructed by other approaches to spatial discretization. It is demonstrated that in the case of different spatial grids, the time of computation for the proposed schemes is significantly less than in the case of explicit schemes, despite the need to solve systems of linear equations at each step. The disadvantages of the schemes are the limitation on the time step in the case of discontinuous or strongly changing solutions and the need to use extrapolation of values at the boundary points of the vessels. In this regard, problems on the adaptation of splitting schemes for problems with discontinuous solutions and in cases of special types of conditions at the vessels ends are perspective for further research.

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

The article is devoted to studying the application of convex optimization methods to solve the Cauchy problem for the Helmholtz equation, which is ill-posed since the equation belongs to the elliptic type. The Cauchy problem is formulated as an inverse problem and is reduced to a convex optimization problem in a Hilbert space. The functional to be optimized and its gradient are calculated using the solution of boundary value problems, which, in turn, are well-posed and can be approximately solved by standard numerical methods, such as finite-difference schemes and Fourier series expansions. The convergence of the applied fast gradient method and the quality of the solution obtained in this way are experimentally investigated. The experiment shows that the accelerated gradient method — the Similar Triangle Method — converges faster than the non-accelerated method. Theorems on the computational complexity of the resulting algorithms are formulated and proved. It is found that Fourier’s series expansions are better than finite-difference schemes in terms of the speed of calculations and improve the quality of the solution obtained. An attempt was made to use restarts of the Similar Triangle Method after halving the residual of the functional. In this case, the convergence does not improve, which confirms the absence of strong convexity. The experiments show that the inaccuracy of the calculations is more adequately described by the additive concept of the noise in the first-order oracle. This factor limits the achievable quality of the solution, but the error does not accumulate. According to the results obtained, the use of accelerated gradient optimization methods can be the way to solve inverse problems effectively.

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

The article is devoted to first-order adaptive methods for optimization problems with relatively strongly convex functionals. The concept of relatively strong convexity significantly extends the classical concept of convexity by replacing the Euclidean norm in the definition by the distance in a more general sense (more precisely, by Bregman’s divergence). An important feature of the considered classes of problems is the reduced requirements concerting the level of smoothness of objective functionals. More precisely, we consider relatively smooth and relatively Lipschitz-continuous objective functionals, which allows us to apply the proposed techniques for solving many applied problems, such as the intersection of the ellipsoids problem (IEP), the Support Vector Machine (SVM) for a binary classification problem, etc. If the objective functional is convex, the condition of relatively strong convexity can be satisfied using the problem regularization. In this work, we propose adaptive gradient-type methods for optimization problems with relatively strongly convex and relatively Lipschitzcontinuous functionals for the first time. Further, we propose universal methods for relatively strongly convex optimization problems. This technique is based on introducing an artificial inaccuracy into the optimization model, so the proposed methods can be applied both to the case of relatively smooth and relatively Lipschitz-continuous functionals. Additionally, we demonstrate the optimality of the proposed universal gradient-type methods up to the multiplication by a constant for both classes of relatively strongly convex problems. Also, we show how to apply the technique of restarts of the mirror descent algorithm to solve relatively Lipschitz-continuous optimization problems. Moreover, we prove the optimal estimate of the rate of convergence of such a technique. Also, we present the results of numerical experiments to compare the performance of the proposed methods.

В программном комплексе FlowVision проведено численное моделирование течения жидкости в насосе для перекачки крови. Данная тестовая задача, предоставленная Центром устройств и радиологического здоровья Управления по санитарному надзору за качеством пищевых продуктов и медикаментов США, предусматривала рассмотрение течения жидкости в соответствии с несколькими расчетными режимами. При этом для каждого расчетного случая задавалось определенное значение расхода жидкости и скорости вращения ротора. Необходимые для расчетов данные в виде точной геометрии, условий потока и характеристик жидкости были предоставлены всем участникам исследования, использующим для моделирования различные программные комплексы. Во FlowVision численное моделирование проводилось для шести режимов с ньютоновской жидкостью и стандартной моделью турбулентности $k-\varepsilon$, дополнительно были проведены расчеты пятого режима с моделью турбулентности $k-\omega$ SST и с использованием реологической модели жидкости Каро. На первом этапе численного моделирования была исследована сходимость по сетке, на основании которой выбрана итоговая сетка с числом ячеек порядка 6 миллионов. В связи с большим количеством ячеек для ускорения исследования часть расчетов проводилась на кластере «Ломоносов-2». В результате численного моделирования были получены и проанализированы значения перепада давления между входом и выходом насоса, скорости между лопатками ротора и в области диффузора, а также проведена визуализация распределения скорости в определенных сечениях. Для всех расчетных режимов осуществлялось сравнение перепада давления, полученного численно, с экспериментальными данными, а для пятого расчетного режима также производилось сравнение с экспериментом по распределению скорости между лопатками ротора и в области диффузора. Анализ данных показал хорошее соответствие результатов расчетов во FlowVision с результатами эксперимента и численного моделирования в других программных комплексах. Полученные во FlowVision результаты решения теста от Управления по санитарному надзору за качеством пищевых продуктов и медикаментов США позволяют говорить о том, что данный программный комплекс может быть использован для решения широкого спектра задач гемодинамики.

A numerical simulation of fluid flow in a blood pump was performed using the FlowVision software package. This test problem, provided by the Center for Devices and Radiological Health of the US. Food and Drug Administration, involved considering fluid flow according to several design modes. At the same time for each case of calculation a certain value of liquid flow rate and rotor speed was set. Necessary data for calculations in the form of exact geometry, flow conditions and fluid characteristics were provided to all research participants, who used different software packages for modeling. Numerical simulations were performed in FlowVision for six calculation modes with the Newtonian fluid and standard $k-\varepsilon$ turbulence model, in addition, the fifth mode with the $k-\omega$ SST turbulence model and with the Caro rheological fluid model were performed. In the first stage of the numerical simulation, the convergence over the mesh was investigated, on the basis of which a final mesh with a number of cells of the order of 6 million was chosen. Due to the large number of cells, in order to accelerate the study, part of the calculations was performed on the Lomonosov-2 cluster. As a result of numerical simulation, we obtained and analyzed values of pressure difference between inlet and outlet of the pump, velocity between rotor blades and in the area of diffuser, and also, we carried out visualization of velocity distribution in certain cross-sections. For all design modes there was compared the pressure difference received numerically with the experimental data, and for the fifth calculation mode there was also compared with the experiment by speed distribution between rotor blades and in the area of diffuser. Data analysis has shown good correlation of calculation results in FlowVision with experimental results and numerical simulation in other software packages. The results obtained in FlowVision for solving the US FDA test suggest that FlowVision software package can be used for solving a wide range of hemodynamic problems.

Задачи негладкой оптимизации нередко возникают во многих приложениях. Вопросы разработки эффективных вычислительных процедур для негладких задач в пространствах больших размерностей весьма актуальны. В таких случаях разумно применятьмет оды первого порядка (субградиентные методы), однако в достаточно общих ситуациях они приводят к невысоким скоростным гарантиям. Одним из подходов к этой проблеме может являться выделение подкласса негладких задач, допускающих относительно оптимистичные результаты о скорости сходимости в пространствах больших размерностей. К примеру, одним из вариантов дополнительных предположений может послужитьуслови е острого минимума, предложенное в конце 1960-х годов Б. Т. Поляком. В случае доступности информации о минимальном значении функции для липшицевых задач с острым минимумом известен субградиентный метод с шагом Б. Т. Поляка, который гарантирует линейную скорость сходимости по аргументу. Такой подход позволил покрыть ряд важных прикладных задач (например, задача проектирования точки на выпуклый компакт или задача отыскания общей точки системы выпуклых множеств). Однако как условие доступности минимального значения функции, так и само условие острого минимума выглядят довольно ограничительными. В этой связи в настоящей работе предлагается обобщенное условие острого минимума, аналогичное известному понятию неточного оракула. Предложенный подход позволяет расширить класс применимости субградиентных методов с шагом Б. Т. Поляка на ситуации неточной информации о значении минимума, а также неизвестной константы Липшица целевой функции. Более того, использование в теоретической оценке качества выдаваемого методом решения локальных аналогов глобальных характеристик целевой функции позволяет применять результаты такого типа и к более широким классам задач. Показана возможностьпр именения предложенного подхода к сильно выпуклым негладким задачам и выполнено экспериментальное сравнение с известным оптимальным субградиентным методом на таком классе задач. Более того, получены результаты о применимости предложенной методики для некоторых типов задач с релаксациями выпуклости: недавно предложенное понятие слабой $\beta$-квазивыпуклости и обычной квазивыпуклости. Исследовано обобщение описанной методики на ситуацию с предположением о доступности на итерациях $\delta$-субградиента целевой функции вместо обычного субградиента. Для одного из рассмотренных методов найдены условия, при которых на практике можно отказаться от проектирования итеративной последовательности на допустимое множество поставленной задачи.

Non-smooth optimization often arises in many applied problems. The issues of developing efficient computational procedures for such problems in high-dimensional spaces are very topical. First-order methods (subgradient methods) are well applicable here, but in fairly general situations they lead to low speed guarantees for large-scale problems. One of the approaches to this type of problem can be to identify a subclass of non-smooth problems that allow relatively optimistic results on the rate of convergence. For example, one of the options for additional assumptions can be the condition of a sharp minimum, proposed in the late 1960s by B. T. Polyak. In the case of the availability of information about the minimal value of the function for Lipschitz-continuous problems with a sharp minimum, it turned out to be possible to propose a subgradient method with a Polyak step-size, which guarantees a linear rate of convergence in the argument. This approach made it possible to cover a number of important applied problems (for example, the problem of projecting onto a convex compact set). However, both the condition of the availability of the minimal value of the function and the condition of a sharp minimum itself look rather restrictive. In this regard, in this paper, we propose a generalized condition for a sharp minimum, somewhat similar to the inexact oracle proposed recently by Devolder – Glineur – Nesterov. The proposed approach makes it possible to extend the class of applicability of subgradient methods with the Polyak step-size, to the situation of inexact information about the value of the minimum, as well as the unknown Lipschitz constant of the objective function. Moreover, the use of local analogs of the global characteristics of the objective function makes it possible to apply the results of this type to wider classes of problems. We show the possibility of applying the proposed approach to strongly convex nonsmooth problems, also, we make an experimental comparison with the known optimal subgradient method for such a class of problems. Moreover, there were obtained some results connected to the applicability of the proposed technique to some types of problems with convexity relaxations: the recently proposed notion of weak $\beta$-quasi-convexity and ordinary quasiconvexity. Also in the paper, we study a generalization of the described technique to the situation with the assumption that the $\delta$-subgradient of the objective function is available instead of the usual subgradient. For one of the considered methods, conditions are found under which, in practice, it is possible to escape the projection of the considered iterative sequence onto the feasible set of the problem.

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

В настоящей работе схемы расщепления 3-го и 4-го порядка были применены непосредственно к решению двумерной гиперболической системы уравнений в частных производных линейной теории упругости. Это позволило повысить итоговый порядок сходимости расчетного алгоритма. В работе эмпирически оценена сходимость по нормам $L_1$ и $L_\infty$ с использованиемана литических решений определяющей системы достаточной степени гладкости. Для получения объективных результатов рассмотрены случаи продольных и поперечных плоских волн, распространяющихся как вдоль диагонали расчетной ячейки, так и не вдоль нее. Проведенные численные эксперименты подтверждают повышение точности метода и демонстрируют теоретически ожидаемый порядок сходимости. При этом увеличивается в 3 и в 4 раза время моделирования (для схем 3-го и 4-го порядка соответственно), но не возрастает потребление оперативной памяти. Предложенное усовершенствование вычислительного алгоритма сохраняет простоту его параллельной реализации на основе пространственной декомпозиции расчетной сетки.

The grid-characteristic method is successfully used for solving hyperbolic systems of partial differential equations (for example, transport / acoustic / elastic equations). It allows to construct correctly algorithms on contact boundaries and boundaries of the integration domain, to a certain extent to take into account the physics of the problem (propagation of discontinuities along characteristic curves), and has the property of monotonicity, which is important for considered problems. In the cases of two-dimensional and three-dimensional problems the method makes use of a coordinate splitting technique, which enables us to solve the original equations by solving several one-dimensional ones consecutively. It is common to use up to 3-rd order one-dimensional schemes with simple splitting techniques which do not allow for the convergence order to be higher than two (with respect to time). Significant achievements in the operator splitting theory were done, the existence of higher-order schemes was proved. Its peculiarity is the need to perform a step in the opposite direction in time, which gives rise to difficulties, for example, for parabolic problems.

In this work coordinate splitting of the 3-rd and 4-th order were used for the two-dimensional hyperbolic problem of the linear elasticity. This made it possible to increase the final convergence order of the computational algorithm. The paper empirically estimates the convergence in L1 and L∞ norms using analytical solutions of the system with the sufficient degree of smoothness. To obtain objective results, we considered the cases of longitudinal and transverse plane waves propagating both along the diagonal of the computational cell and not along it. Numerical experiments demonstrated the improved accuracy and convergence order of constructed schemes. These improvements are achieved with the cost of three- or fourfold increase of the computational time (for the 3-rd and 4-th order respectively) and no additional memory requirements. The proposed improvement of the computational algorithm preserves the simplicity of its parallel implementation based on the spatial decomposition of the computational grid.

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

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

Рассматривается влияние освобождения фактора V при активации тромбоцитов. При модификации математической модели удалось достичь количественного соответствия по динамике производства тромбина с экспериментальными данными для искусственной системы. На основе анализа чувствительности проверена гипотеза об отсутствии влияния состава липидной мембраны (числа сайтов для тех или иных факторов системы свертывания, кроме сайтов для тромбина) на динамику процесса.

Many properties of ordinary differential equations systems solutions are determined by the properties of the equations in variations. An ODE system, which includes both the original nonlinear system and the equations in variations, will be called an extended system further. When studying the properties of the Cauchy problem for the systems of ordinary differential equations, the transition to extended systems allows one to study many subtle properties of solutions. For example, the transition to the extended system allows one to increase the order of approximation for numerical methods, gives the approaches to constructing a sensitivity function without using numerical differentiation procedures, allows to use methods of increased convergence order for the inverse problem solution. Authors used the Broyden method belonging to the class of quasi-Newtonian methods. The Rosenbroke method with complex coefficients was used to solve the stiff systems of the ordinary differential equations. In our case, it is equivalent to the second order approximation method for the extended system.

As an example of the proposed approach, several related mathematical models of the blood coagulation process were considered. Based on the analysis of the numerical calculations results, the conclusion was drawn that it is necessary to include a description of the factor XI positive feedback loop in the model equations system. Estimates of some reaction constants based on the numerical inverse problem solution were given.

Effect of factor V release on platelet activation was considered. The modification of the mathematical model allowed to achieve quantitative correspondence in the dynamics of the thrombin production with experimental data for an artificial system. Based on the sensitivity analysis, the hypothesis tested that there is no influence of the lipid membrane composition (the number of sites for various factors of the clotting system, except for thrombin sites) on the dynamics of the process.