Siberian Journal of Numerical Mathematics

Volume 20, 2017

Contents

Number 1, pp. 1-120
Number 2, pp. 121-221
Number 3, pp. 223-344
Number 4, pp. 345-351


Number 1, pp. 1-120

 

Averina T.A., Rybakov K.A.

An approximate solution of the prediction problem for stochastic jump-diffusion systems (in Russian), pp. 1-13

In this paper we discuss the evolution of the new approach to the prediction problem for nonlinear stochastic differential systems with a Poisson component. The proposed approach is based on reducing the prediction problem to the analysis of stochastic jump-diffusion systems with terminating and branching paths. The solution of the prediction problem can be approximately found by using numerical methods for solving stochastic differential equations and methods for modeling inhomogeneous Poisson flows.

Keywords: branching processes, conditional density, Duncan-Mortensen-Zakai equation, Kolmogorov-Feller equation, Monte Carlo method, optimal filtering problem, prediction problem, stochastic jump-diffusion system.

Galashov A.E., Kel'manov A.V.

On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets (in Russian), pp. 15-22

We consider a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from the Euclidean space. A minimum of the sum over all required subsets of the sum of the squared distances from the elements of these subsets to their geometric centers is used as a search criterion. We have proved that if the coordinates of the input points are integer, and the space dimension and the number of required subsets are fixed (i.e. bounded by some constants), then the problem is a pseudopolynomial-time solvable one.

Keywords: Euclidean space, subsets search, clustering, NP-hard problem, exact pseudopolynomial-time algorithm.

Marchuk An.G.

The assessment of tsunami heights above the parabolic bottom relief within the wave-ray approach (in Russian), pp. 23-35

In this paper, the kinematics of the tsunami wave ray and the wavefront above an uneven bottom is studied. The formula to determine the wave height along a ray tube has been obtained. The exact analytical solution for the wave-ray trajectory above the parabolic bottom topography has been derived. Within the wave-ray approach this solution gives the possibility to determine the tsunami wave heights in an area with a parabolic bottom relief. The distribution of the wave-height maxima in the area with the parabolic bottom was compared to the one obtained by the numerical computation with a shallow-water model.

Keywords: tsunami propagation, shallow-water equations, wave ray, wavefront kinematics.

Mahato H.S.

Numerical simulations for a two-scale model in a porous medium (in Russian), pp. 37-46

This paper deals with numerical simulations of a system of diffusion-reaction equations in the context of a porous medium. We start by giving a microscopic model and then an upscaled version (i.e., homogenized or continuum model) of it from previous works of the author. Since with the help of homogenization we obtain a macroscopic description of a model which is microscopically heterogeneous, via these numerical simulations we show that this macroscopic description approximates the microscopic model, which contains heterogeneities and oscillating terms at the pore scale, such as diffusion coefficients.

Keywords: periodic medium, two-scale model, averaging, numerical simulations.

Namm R.V., Tsoy G.I.

A modified dual scheme for solving an elastic crack problem (in Russian), pp. 47-58

The dual scheme for solving a crack problem in terms of displacements is considered. The dual solution method is based on a modified Lagrangian functional. In addition, the method convergence is investigated under natural assumptions on H1-regularity of the crack problem solution. The duality relation for the primal and dual problems has been proposed.

Keywords: elastic crack problem, duality scheme, modified Lagrangian functional, sensitivity functional, duality relation, weak lower semicontinuity.

Prashanth M., Motsa S.

Semilocal convergence of a continuation method in Banach spaces (in Russian), pp. 59-75

This paper is concerned with the semilocal convergence of a continuation method between two third-order iterative methods, namely, Halley's method and the convex acceleration of Newton's method, also known as super-Halley's method. This convergence analysis is discussed using a recurrence relations approach. This approach simplifies the analysis and leads to improved results. The convergence is established under the assumption that the second Fréchet derivative satisfies the Lipschitz continuity condition. An existence-uniqueness theorem is given. Also, a closed form of error bounds is derived in terms of a real parameter α € [0,1]. Two numerical examples are worked out to demonstrate the efficiency of our approach. On comparing the existence and uniqueness region and error bounds for the solution obtained by our analysis with those obtained by using majorizing sequences [15], we observed that our analysis gives better results. Further, we observed that for particular values of α our analysis reduces to Halley's method (α = 0) and convex acceleration of Newton's method (α = 1), respectively, with improved results.

Keywords: Halley's method, convex acceleration of Newton's method, continuation method, Banach space, Lipschitz condition, Fréchet derivative.

Rudoy E.M., Kazarinov N.A., Slesarenko V.Yu.

Numerical simulation of the equilibrium of an elastic two-layer structure with a crack (in Russian), pp. 77-90

The equilibrium problem for two elastic bodies pasted together along some curve is considered. There exists a crack on a part of the curve. Nonlinear boundary conditions providing a mutual non-penetration between crack faces are set. The main objective of the paper is to construct and to approve an algorithm for the numerical solution of the equilibrium problem. The algorithm is based on the two approaches: the domain decomposition method and the Uzawa method. The numerical experiment illustrates the efficiency of the algorithm.

Keywords: two-layer structure, crack, non-penetration condition, variational inequality, domain decomposition method, Uzawa algorithm.

Choubey N., Jaiswal J.P.

Two- and three-point with memory methods for solving nonlinear equations (in Russian), pp. 91-106

The main objective and inspiration in the construction of two- and three-point with memory methods is to attain the utmost computational efficiency without any additional function evaluations. At this juncture, we have modified the existing fourth and eighth order without memory methods with optimal order of convergence by means of different approximations of self-accelerating parameters. The parameters are calculated by a Hermite interpolating polynomial, which accelerates the order of convergence of the without memory methods. In particular, the R-order convergence of the proposed two- and three-step with memory methods is increased from four to five and eight to ten. One more advantage of these methods is that the condition f'(x) ≠ 0 in the neighborhood of the required root, imposed on Newton's method, can be removed. Numerical comparison is also stated to confirm the theoretical results.

Keywords: iterative method, without memory scheme, with memory scheme, computational efficiency, numerical result.

Shumilov B.M.

About semi-orthogonal spline-wavelets with derivatives, and the algorithm with splitting (in Russian), pp. 107-120

This paper deals with the use of a scalar product with derivatives for constructing semi-orthogonal spline-wavelets. The reduction of supports of such wavelets in comparison with classical semi-orthogonal wavelets is shown. For the splines of the 3rd degree, the algorithm of wavelet-transformation in the form of the solution to a three-diagonal system of the linear equations with strict diagonal prevalence has been obtained. The results of numerical experiments on the calculation of derivatives of a discretely set function are presented.

Keywords: B-splines, wavelets, implicit decomposition relations.


Number 2, pp. 121-221

Ayupova N.B., Golubyatnikov V.P., Kazantsev M.V. 

On existence of a cycle in one asymmetric model of a molecular repressilator (in Russian), pp. 121-129 

We consider a nonlinear 6-dimensional dynamic system which is a model of functioning of one simple molecular repressilator and find sufficient conditions of existence of a cycle C in the phase portrait of this system. An invariant neighborhood of C which retracts to C has been constructed.

Keywords: nonlinear dynamical systems, gene networks models, phase portrait's discretization, hyperbolic equilibrium points, cycles, Brower's fixed point theorem.

Blatov I.A., Zadorin A.I., Kitaeva E.V. 

About the uniform convergence of parabolic spline interpolation on the class of functions with large gradients in the boundary layer (in Russian), pp. 131-144 

A problem of the Subbotin parabolic spline-interpolation of functions with large gradients in the boundary layer is considered. In the case of a uniform grid it has been proved and in the case of the Shishkin grid it has been experimentally shown that with a parabolic spline-interpolation of functions with large gradients the error in the exponential boundary layer can unrestrictedly increase with a fixed number of grid nodes. A modified parabolic spline has been constructed. Estimates of the interpolation error of the constructed spline don't depend from a small parameter. 

Keywords: singular perturbation, boundary layer, Shishkin mesh, parabolic spline, modification, estimation of error.

Voronin K.V., Grigoriev A.V., Laevsky Yu.M. 

On an approach to modeling wells (in Russian), pp. 145-155 

This paper deals with a numerical study of the diffusion problem in the presence of wells, at which integral boundary conditions are used. It is shown that the method proposed earlier is fully efficient and offers certain advantages as compared with the direct modeling of wells based on the finite element method. The results of calculations for the two wells are presented.

Keywords: wells, mixed formulation, mixed finite element method, error estimate.

Jaiswal J.P. 

Analysis of semilocal convergence in Banach spaces under relaxed condition and computational efficiency (in Russian), pp. 157-168 

The present paper is concerned with the study of semilocal convergence of a fifth-order method for solving nonlinear equations in Banach spaces under mild conditions. An existence and uniqueness theorem is proved and followed by error estimates. The computational superiority of the considered scheme over the identical order methods is also examined, which shows the efficiency of the present scheme from a computational point of view. Lastly, an application of the theoretical development is made in a nonlinear integral equation. 

Keywords: nonlinear equation, Banach space, weak condition, semilocal convergence, error bound.

Monakhov O.G., Monakhova E.A.

A parallel algorithm of the multivariant evolutionary synthesis of nonlinear models (in Russian), pp. 169-180 

A parallel algorithm for solving the problem of constructing of nonlinear models (mathematical expressions, functions, algorithms, programs) based on given experimental data, a set of variables, basic functions and operations is proposed. The proposed algorithm of the multivariant evolutionary synthesis of nonlinear models has a linear representation of the chromosome, the modular operations in decoding the genotype to the phenotype for interpreting a chromosome as a sequence of instructions, the multivariant method for presenting a multiplicity of models (expressions) using a single chromosome. A comparison of the sequential version of the algorithm with a standard algorithm of genetic programming and the algorithm of the Cartesian Genetic Programming offers advantage of the algorithm proposed both in the time of obtaining a solution (by about an order of magnitude in most cases), and in the probability of finding a given function (model). In the experiments on the parallel supercomputer systems, estimates of the efficiency of the proposed parallel algorithm have been obtained showing linear acceleration and scalability. 

Keywords: parallel multivariant evolutionary synthesis, genetic algorithm, genetic programming, Cartesian genetic programming, nonlinear models.

Sabelfeld K.K., Kablukova E.G.

A stochastic model of the nanowires growth by molecular beam epitaxy (in Russian), pp. 181-199 

In this paper a stochastic model of the nanowire growth by molecular beam epitaxy based on probability mechanisms of surface diffusion, mutual shading, adatoms rescattering and survival probability is proposed. A direct simulation algorithm based on this model is implemented, and a comprehensive study of the growth kinetics of a family of nanowires initially distributed at a height of about tens of nanometers to heights of about several thousands of nanometers is carried out. The time range corresponds to growing nanowires experimentally for up to 3-4 hours. In this paper we formulate a statement, which is numerically confirmed: under certain conditions, which can be implemented in real experiments, the nanowires height distribution becomes narrower with time, i.e. in the nanowires ensemble their heights are aligned in the course of time. For this to happen, it is necessary that the initial radius distribution of nanowires be narrow and the density of the nanowires on a substrate be not very high. 

Keywords: nanowires, adatoms, surface diffusion, survival probability, multiple scattering, self-preserved height distribution.

Singh Swarn, Singh Suruchi, Arora R.

Numerical solution of second order one dimensional hyperbolic equation by exponential B-spline collocation method (in Russian), pp. 201-213 

In this paper, we propose a method based on collocation of exponential B-splines to obtain numerical solution of nonlinear second order one dimensional hyperbolic equation subject to appropriate initial and Dirichlet boundary conditions. The method is a combination of B-spline collocation method in space and two stage, second order strong-stability-preserving Runge-Kutta method in time. The proposed method is shown to be unconditionally stable. The efficiency and accuracy of the method are successfully described by applying the method to a few test problems. 

Keywords: damped wave equation, exponential B-spline method, SSPRK(2,2), telegraphic equation, tri-diagonal solver, unconditionally stable method.

Hou T., Wang K., Xiong Y., Xiao X., Zhang Sh.

Discrete maximum-norm stability of a linearized second order finite difference scheme for Allen-Cahn equation  (in Russian), pp.  215-222 

In this paper, we use finite difference methods for solving the Allen-Cahn equation which contains small perturbation parameters and strong nonlinearity. We consider a linearized second-order three level scheme in time and a second-order finite difference approach in space, and we establish discrete boundedness stability in maximum norm: if the initial data is bounded by 1, then the numerical solutions in later times can also be bounded uniformly by 1. We will show that the main result can be obtained under certain. 

Keywords: Allen-Cahn equation, finite difference method, discrete boundedness stability, maximum norm.


Number 3, pp. 223-344


Aleksandrov V.M.

Optimal resource consumption control of perturbed systems  (in Russian), pp. 223-238

A method for calculating the optimal consumption of the resource control of perturbed dynamic systems. This method includes both normal and singular solutions. According to the method proposed the problem is subdivided into three independent tasks: 1) a consideration of the effects of perturbations on the system; 2) computation of the optimal control structure; 3) computation of the switching moments of optimal control. A consideration of the effects of perturbations on the system and transfer to a non-zero final state are reduced to the transformation of the initial and final states of the systems. The structure calculation is based on the relation between deviations in the initial conditions of the conjugate systems and deviations of the phase trajectory at the completion instant. An iterative algorithm has been developed, its characteristics being considered. The results of modeling and numerical calculations are given. 

Keywords: optimal control, resource consumption, perturbation, moving time, switching moments, iterative process, conjugate system, phase trajectory.

Bondarev E.A.,Voevodin A.F., Argunova K.K., Rozhin I.I. 

The choice of the equation of state in mathematical models of pipeline transportation of natural gas  (in Russian), pp. 239-249

 

By comparison with reliable experimental data in a wide range of pressure and temperature, it has been shown that the Redlich-Kwong equation of state appropriately reflects all the characteristics of the coefficient of compressibility, the throttling factor and the normalized difference of specific isobaric and isochoric heat capacities. It has been found that this equation corresponds to the inequalities required to ensure a set of equations of gas flow in pipelines to be hyperbolic. 

Keywords: equation of state, natural gas, hyperbolic equations.

Kremlev A.N. 

The plane wave refraction on convex and concave obtuse angles in geometric acoustics approximation  (in Russian), pp. 251–271 

The strict analytical solution to the eikonal equation for the plane wave refracted on convex and concave obtuse angles has been built. It has a shock line for the ray vector field and the first arrival times at the convex angle and a rarefaction cone with diffracted waves at the concave angle. This cone corresponds to the Keller diffraction cone in the geometric diffraction theory. The comparison of the first arrival times, the Hamilton-Jacoby equation times for downward waves and the conservation ray parameter equation times was made. It is shown that these times are equal only for pre-critical incident angles and are different for sub-critical angles. It is shown that the most energetic wave arrival times, which have dominant practical importance, are equal to the times calculated for the conservation ray parameter equation. The numerical algorithm proposed for these times calculation may be used for arbitrary velocity models. 

Keywords: eikonal equation, Hamilton-Jacobi equation, ray parameter, refraction on convex and concave obtuse angle, first arrival times, analytical viscosity solution, head wave, Godunov finite difference scheme.

Lu Z., Li L., Cao L., Hou Ch.

A priori error estimates of finite volume method for nonlinear optimal control problem  (in Russian), pp. 273–287 

In this paper, we study a priori error estimates for a finite volume element approximation of a nonlinear optimal control problem. The schemes use discretizations base on a finite volume method. For the variational inequality, we use a method of the variational discretization concept to obtain the control. Under some reasonable assumptions, we obtain some optimal order error estimates. The approximate order for the state,  costate,  and control variables is O(h2) or O(h2|ln h|)$ in the sense of L2-norm or L-norm. A numerical experiment is presented to test the theoretical results. Finally, we give some conclusions and future works.

Keywords: a priori error estimates, nonlinear optimal control problem, finite volume method, variational discretization.

Mashukov V.I.

The outer layer method for solving boundary value problems of the elasticity theory  (in Russian), pp. 289–296 

This paper presents an algorithm for solving boundary value problems of the elasticity theory, suitable to solve contact problems and those whose scope of deformation contains thin layers of a medium. The solution is represented as a linear combination of subsidiary solutions and fundamental solutions to the Lame equations. Singular points of fundamental solutions of the Lame equations are located as an external layer of the deformation around the perimeter. Coefficients of the linear combination are determined by minimizing deviations of a linear combination from the boundary conditions. To minimize deviations, the conjugate gradient method is applied. Examples of calculations for mixed boundary conditions are presented. 

Keywords: theory, elasticity, boundary integral equations, external layer, two-dimensional, objectives, conjugate gradients method.

Sorokin S.B.

A difference scheme for a conjugate-operator model of the heat conduction problem in the polar coordinates  (in Russian), pp. 297–312 

In the polar coordinates, a discrete analog of the conjugate-operator model of the heat conduction problem preserves the structure of the original model. The difference scheme converges with the second order of accuracy for the cases of discontinuous parameters of the medium in the Fourier law and irregular grids. An efficient algorithm for solving the discrete conjugate-operator model in the case when the thermal conductivity tensor is a single operator.

Keywords: problem of heat conductivity, mathematical model, discrete analog, polar coordinates, convergence, difference scheme.

Shalimova I.A., Sabelfeld K.K.

Solution to a stochastic Darcy equation by the polynomial chaos expansion  (in Russian), pp. 313–327 

This paper deals with the solution of a boundary value problem for the Darcy equation with a random hydraulic conductivity field. We use an approach based on the polynomial chaos expansion in the probability space of input data. We use the probabilistic collocation method to calculate the coefficients of the polynomial chaos expansion. A computational complexity of this algorithm is defined by the order of a polynomial chaos expansion and the number of terms in the Karhunen-Loève expansion. We calculate different Eulerian and Lagrangian statistical characteristics of the flow by the Monte Carlo and probabilistic collocation methods. Our calculations show a significant advantage of the probabilistic collocation method in comparison with the conventional direct Monte Carlo algorithm. 

Keywords: polynomial chaos, probabilistic collocation method, Darcy equation, Monte Carlo method, Karhunen-Loève expansion.

Ehigie J.O., Jator S.N., Okunuga S.A.

A multi-point numerical integrator with trigonometric coefficients for initial value problems with periodic solutions  (in Russian), pp. 329–344 

Based on a collocation technique, we introduce a unifying approach for deriving a family of multi-point numerical integrators with trigonometric coefficients for the numerical solution of periodic initial value problems. A practical 3-point numerical integrator is presented, whose coefficients are generalizations of classical linear multistep methods such that the coefficients are functions of an estimate of the angular frequency ω. The collocation technique yields a continuous method, from which the main and complementary methods are recovered and expressed as a block matrix finite difference formula which integrates a second order differential equation over non-overlapping intervals without predictors. Some properties of the numerical integrator are investigated and presented. Numerical examples are given to illustrate the accuracy of the method.

Keywords: block method, periodic solution, trigonometric coefficients, collocation technique.


Number 4, pp. 345-451

Voronin K.V., Laevsky Yu.M.

The flux predictor-corrector scheme for solving a 3D heat transfer problem  (in Russian), pp. 345-358 

In this paper we propose and study the flux predictor-corrector scheme in the three-dimensional case. This scheme is depleted of drawbacks of that constructed on the basis of the Douglas-Gunn prototype-scheme. The scheme proposed demonstrates the second order of accuracy. 

Keywords: mixed finite element method, heat flux, splitting scheme, predictor-corrector scheme.

Gasnikov A., Gasnikova E., Dvurechensky P., Mohammed A., Chernousova E.

About the power law of the PageRank vector distribution. Part 1. Numerical methods for finding the PageRank vector  (in Russian), pp. 359–378 

In Part 1 of this paper, we consider the web-pages ranking problem also known as the problem of finding the PageRank vector or Google problem. We discuss the connection of this problem with the ergodic theorem and describe different numerical methods to solve this problem together with their theoretical background, such as Markov Chain Monte Carlo and equilibrium in a macrosystem. 

Keywords: Markov chain, ergodic theorem, multinomial distribution, measure concentration, maximum likelihood estimate, Google problem, gradient descent, automatic differentiation, power law distribution.

Kelmanov A.V., Romanchenko S.M., Khamidullin S.A.

An approximation scheme for a problem of finding a subsequence  (in Russian), pp. 379–392 

We consider a strongly NP-hard Euclidean problem of finding a subsequence in a finite sequence. The criterion of the solution is a minimum sum of squared distances from the elements of a sought subsequence to its geometric center (centroid). It is assumed that a sought subsequence contains a given number of elements. In addition, a sought subsequence should satisfy the following condition: the difference between the indices of each previous and subsequent points is bounded with given lower and upper constants. We present an approximation algorithm of solving the problem and prove that it is a fully polynomial-time approximation scheme (FPTAS) when the space dimension is bounded by a constant. 

Keywords: euclidean space, sequence, minimum sum of squared distances, NP-hardness, FPTAS.

Kurdyaeva Yu., Kshevetskii S., Gavrilov N., Golikova E.

Correctness of the problem of propagation of nonlinear acoustic-gravity waves in the atmosphere from pressure variations on the lower boundary  (in Russian), pp. 393–412 

Currently, there are international microbarograph networks, with high resolution recording the wave pressure variations on the Earth's surface. This increases the interest in the problems of wave propagation in the atmosphere from variations in the atmospheric pressure. A complete system of nonlinear hydrodynamic equations for an atmospheric gas with lower boundary conditions in the form of wavelike variations on the Earth's surface is considered. Since the wave amplitudes near the Earth's surface are small, linearized equations are used in the analysis of the problem correctness. With the help of the wave energy functional method, it is shown that in the non-dissipative case, the solution of the boundary value problem is uniquely determined by the variable pressure field on the Earth's surface. The corresponding dissipative problem is correct if, in addition to the pressure field, suitable conditions on the velocity and temperature on the Earth's surface are given. In the case of an isothermal atmosphere, the problem admits analytical solutions that are harmonic in the variables x and t. A good agreement between numerical solutions and analytical ones is shown. The study has shown that in the boundary value problem, the temperature and density can rapidly vary near the lower boundary. An example of the solution of a three-dimensional problem with variable pressure on the Earth's surface, taken from experimental observations, is given. The developed algorithms and computer programs can be used to simulate the atmospheric waves from pressure variations on the Earth's surface. 

Keywords: numerical simulation, atmospheric model, acoustic-gravity waves, nonlinearity, correctness, boundary problem, supercomputer program.

Popov A.S.

The cubature formulas on a sphere invariant to the icosahedral group of rotations with inversion  (in Russian), pp. 413–423 

An algorithm of the search for the best (in a sense) cubature formulas on a sphere that are invariant with respect to the transformations of the icosahedral group of rotations with inversion is described. This algorithm is applied to finding the parameters of all the best cubature formulas of this symmetry type up to the 79th order of accuracy. The parameters of the new cubature formulas of the 21st, 25th and 29th orders of accuracy to 16 significant digits are given.

Keywords: numerical integration, invariant cubature formulas, invariant polynomials, icosahedral group of rotations.

Urev M.V., Imomnazarov Kh.Kh., Tang Jian-Gang

A boundary value problem for one overdetermined stationary system emerging in the two-velocity hydrodynamics  (in Russian), pp. 425–437 

In this paper we investigate the two-velocity stationary hydrodynamics system with a single pressure and inhomogeneous divergent and boundary conditions for the two velocities. This system is overdetermined. By replacing the unknown functions, the problem is reduced to a homogeneous one. The solution of the resulting system is reduced to the consecutive solutions of the two boundary value problems: the Stokes problem for a single velocity and pressure, and overdetermined system for the other velocity. We present the generalized statements of these problems and their discrete approximation using the finite element method. To solve the overdetermined problem we apply a version of the regularization methods. 

Keywords: overdetermined two-velocity stationary hydrodynamics system, Lagrange multiplier, finite element method.

Chugunov V.N., Ikramov Kh.D.

A description of pairs of the quasi-commuting Toeplitz and Hankel matrices  (in Russian), pp. 439–444 

We say that the square matrices A and B are of the same order quasi-commute if AB = σ BA for some scalar σ. Classical relations of commutation and anti-commutation are particular cases of this definition. We give a complete description of pairs of the quasi-commuting Toeplitz and Hankel matrices for σ ≠ ± 1. 

Keywords: Toeplitz matrix, Hankel matrix, ϕ-circulant, quasi-commuting matrices.

Shevaldin V.T., Shevaldina O.Ya.

The Lebesgue constant of local cubic splines with equally-spaced knots  (in Russian), pp. 445–451 

It is proved that the uniform Lebesgue constant (the norm of a linear operator from C to C) of local cubic splines with equally-spaced knots, which preserve cubic polynomials, is equal to 11/9. 

Keywords: Lebesgue constants, local cubic splines, equally-spaced knots.