Siberian Journal of Numerical Mathematics

Volume 16, 2013

Contents

Number 1, pp. 1-95
Number 2, pp. 97-199
Number 3, pp. 201-301
Number 4, pp. 303-404


Number 1, pp. 1-95 

 

Antyufeev V.S.

Theorem of training for a competition algorithm (in Russian), pp. 1-9

 

This paper is an extension of [1], where a new decision algorithm was proposed. In its operation, the unit resembles artificial neural networks. However the functioning of the algorithm proposed is based on the different concepts. It does not use the concept of a net, a neuron. The theorem of training for the new competition algorithm is proved.

Key words: theorem of training, probabilistic convergence, artificial neural network.

Zadorin A.I., Tikhovskaya S.V.

Solution of second order nonlinear singular perturbation ordinary differential equation based on the Samarskii scheme (in Russian), pp. 11-25

 

A boundary value problem for a second order nonlinear singular perturbation ordinary differential equation is considered. We propose the method based on the Newton and the Picard linearizations using known modified Samarskii scheme on the Shishkin mesh in the case of a linear problem. It is proved that the constructed difference schemes are of second order and uniformly convergent. To decrease the number of the arithmetical operations, we propose a two-grid method. The results of some numerical experiments are discussed.

Key words: second order nonlinear ordinary differential equation, singular perturbation, Newton method, Picard method, Samarskii scheme, Shishkin mesh, uniform convergence, two-grid algorithm.

 

Zorkaltsev V.I., Perzhabinsky S.M.

Theoretical justification of interior point algorithms for solving optimization problems with nonlinear constraints (in Russian), pp. 27-38

 

A family of interior point algorithms is considered. These algorithms can be used for solving mathematical programming problems with nonlinear inequality constraints. The weighted Euclidean rates are applied to find a descent direction for improving a solution. These rates are varying in iterations. Theoretical justification of the algorithms with some assumptions (such as non-degeneracy of a problem) is presented.

Key words: interior point method, weighted Euclidean rate, linearization.

 

Kabanikhin S.I., Krivorotko O.I., and Shishlenin M.A.

A numerical method for solving inverse thermoacoustic problem  (in Russian), pp. 39-44 

 

In this paper, we consider the inverse problem of determining the initial condition of the initial boundary value problem for the wave equation with additional information about solving the direct initial boundary value problem that is measured at the boundary of the domain. The main objective of our research is to construct a numerical algorithm for solving the inverse problem based on the method of simple iteration (MSI) and to study the resolution of the inverse problem and its dependence on the number and location of measurement points. We consider three two-dimensional inverse problems. The results of numerical calculations are presented. We show that the MSI for each iteration step reduces the value of the object functional. However, due to the ill-posedness of an inverse problem the difference between the exact and the approximate solutions of the inverse problem decreases up to some fixed number kmin and then monotonically increases. This reflects the regularizing properties of the MSI, in which the iteration number is a regularization parameter.

Key words: thermoacoustic problem, inverse and ill-posed problems, wave equation, method of simple iteration.

 

Kostin V.I., Lisitsa V.V., Reshetova G.V., Tcheverda V.A.

Finite difference simulation of elastic waves propagation through 3D heterogeneous multiscale media based on locally refined grids  (in Russian), pp. 45-55

 

In order to simulate the interaction of seismic waves with microheterogeneities (like cavernous/fractured reservoirs), a finite difference technique based on locally refined in time and in space grids is used. The need to use these grids is due to essentially different scales of heterogeneities in the reference medium and in the reservoir. Parallel computations are based on Domain Decomposition of the target area into elementary subdomains in both the reference medium (a coarse grid) and the reservoir (a fine grid). Each subdomain is assigned to its specific Processor Unit which forms two groups: for the reference medium and for the reservoir. The data exchange between PU within the group is performed by non-blocking iSend/iReceive MPI commands. The data exchange between the two groups is done simultaneously with coupling a coarse and a fine grids and is controlled by a specially designated PU. The results of numerical simulation for a realistic model of fracture corridors are presented and discussed.

Key words: seismic waves, finite difference techniques, domain decomposition, interpolation, groups of processor elements.

 

Popov A.S.

The cubature formulas on a sphere invariant with respect to a dihedral group of rotations with inversion D6h  (in Russian), pp. 57-62

 

An algorithm of searching for the best (in a sense) cubature formulas on a sphere that are invariant with respect to a dihedral group of rotations with inversion D6h has been veloped. This algorithm was applied to find parameters of all the best cubature formulas of this group of symmetry up to the 23rd order of accuracy n. In the course of the study carried out, the exact values of parameters of the corresponding cubature formulas were found for n ≤ 11, and the approximate ones were obtained by the numerical solution of systems of nonlinear algebraic equations by a Newton-type method for the other n. For the first time, the ways of obtaining the best cubature formulas for the sphere were systematically investigated for the case of the group which is not a subgroup of the groups of symmetry of the regular polyhedrons.

Key words:

numerical integration, invariant cubature formulas, invariant polynomials, dihedral group of rotations.

Pchelintsev A.N.

On constructing the generally periodical solutions of a complicated structure of a non-autonomous system of differential equations  (in Russian), pp. 63-70

 

In this paper, a numerical scheme of constructing approximate generally periodical solutions of a complicatedtructure of a non-autonomous system of ordinary differential equations with the periodical right-hand sides on the surface of a torus is considered. The existence of such solutions as well as convergence of the method of successive approximations are shown. There are given results of the computational experiment.

Key words: generally-periodical solution, system of ordinary differential equations, Fourier series, almost periodical solution, irrational winding of torus.

 

Saberi Najafi H., Edalatpanah S.A. 

Comparison analysis for improving preconditioned SOR-type iterative method  (in Russian), pp. 71-80

  

In this article, on the basis of nonnegative matrices, some preconditioners from class of (I+S)-type based on the SOR method have been studied. Moreover, we prove the monotonicity of spectral radiuses of iterative matrices with respect to the parameters in [12]. Also, some splittings and preconditioners are compared and derived by comparisons. A numerical example is also given to illustrate our results.

Key words: preconditioning, comparison theorems, spectral radius, SOR, L-, M-matrix.

 

Chistyakov V.F., Chistyakova E.V.

Application of the least square method to the solving linear differential-algebraic equations (in Russian), pp. 81-95

 

We consider application of the least square method to the numerical solution of a linear system of ordinary differential equations (ODEs) with an identically singular matrix multiplied a higher derivative by the desired vector-function. We discuss the behavior of the gradient method for minimizing the functional of the residual square in the Sobolev space and some other issues. The results of the numerical experiments are given.

Key words: differential-algebraic equations, index, least square method, gradient methods.


Number 2, pp. 97-199

Averina T.A.
A modified algorithm for statistical simulation of multistructural systems with distributed change of structure (in Russian), pp. 97-105

 

An algorithm for statistical simulation of random-structure systems with distributed transitions has been constructed. The proposed algorithm is based on numerical methods for solving stochastic differential equations, and uses a modified maximum cross-section method when the transition intensity depends on the vector of state.

Key words:
numerical methods, stochastic differential equations, systems with random structure.

Akimova E.N., Belousov D.V., Misilov V.E.

Algorithms for solving inverse geophysical problems on parallel computing systems (in Russian), pp. 107-121

 

For solving inverse gravimetry problems, efficient stable parallel algorithms based on iterative gradient methods are proposed. For solving systems of linear algebraic equations with block-tridiagonal matrices arising in geoelectrics problems, a parallel matrix sweep algorithm, a square root method, and a conjugate gradient method with preconditioner are proposed. The algorithms are implemented numerically on the MVS-IMM parallel computing system, NVIDIA graphics processors, and the Intel multi-core CPU with the use of new computing technologies. The parallel algorithms are incorporated into a developed system of remote computations «Specialized Web-Portal for Solving Geophysical Problems on Multiprocessor Computers». Problems with «quasi-model» and real data are solved.

Key words: inverse gravimetry problems, parallel algorithms, direct and iterative methods, parallel computing systems.

Akysh A.Sh. 

Convergence of splitting method for the nonlinear Boltzmann equation (in Russian), pp.  123-131

 

The question of convergence of the splitting method scheme for the nonlinear Boltzmann equation is considered. On the basis of the splitting method scheme, boundedness of positive solutions in the space of continuous functions is obtained. By means of the solution boundedness and found a priori estimates, convergence of the splitting method scheme and uniqueness of the limiting element are proved. The found limiting element satisfies the equivalent integral Boltzmann equation. Thereby global solvability of the nonlinear Boltzmann equation in time is shown. 

Key words: splitting method, convergence of the splitting method scheme, nonlinear Boltzmann equation, global solvability of the nonlinear Boltzmann equation in time, existence and uniqueness of a solution to the Boltzmann equation, a priori estimates.

Aleksandrov V.M.

Transferring a system with unknown disturbance under optimal control to a state of dynamic balance and to ε-vicinity of a final state  (in Russian), pp. 133-145

 

The problem of transferring a linear system to a state of dynamic balance under simultaneous action of an unknown disturbance and time-optimal control is considered. Optimal control is calculated along the phase trajectory, and it is periodically updated for discrete phase coordinate values. It is proved that the phase trajectory comes to the dynamic equilibrium point and makes undamped periodic motions (a stable limit cycle). The location of the dynamic equilibrium point and the limit cycle form are considered as functions of different parameters. With the disturbance calculated in the process of control, the accuracy of transferring to the required final state increases. A method for estimating attainable accuracy is presented. Results of simulation and numerical calculations are given.

Key words: optimal control, speed, computing time, disturbance, phase trajectory, dynamic balance, limit cycle, transferring accuracy, linear system.

Babkina L.A, Garmai Yu.P., Lebedev D.V., Pantina, R.A., Filatov M.V., Isaev-Ivanov V.V.

Using Zernike moments for analysis of images (in Russian), pp. 147-163

 

A method for analyzing AFM images of the cell nuclei of higher organisms by expanding these images by Zernike moments is proposed. This method allows for expanding the pilot image by Zernike moments whose spatial harmonics are Zernike polynomials. It is shown that the reverse procedure of image reconstruction using Zernike polynomials converges to the experimental image and the expansion amplitude is a quantitative spectral characteristic when comparing the morphological features of different images. It is shown that expansion amplitudes can be used as input vectors for cluster analysis of images by PCA. 

Key words: image analysis, Zernike moments, atomic force microscopy, cell nuclei of higher organisms, PCA.

Matsokin A.M. 

Preconditioner for a Laplace grid operator on a condensed grid (in Russian), pp. 165-170

    
    In this paper, it is proved that a Laplace grid operator approximating a Dirichlet boundary value problem for the Poisson equation by the finite element method with piecewise-linear functions on an evenly condensed grid that is topologically equivalent to a rectangular grid (i.e. obtained by
shifting the rectangular grid nodes) is equivalent, in the range, to the operator of a 5-point difference scheme on a uniform grid.
Key words: Dirichlet boundary value problem for the Poisson equation, finite element method with piecewise-linear functions, condensed grid (topologically equivalent to a rectangular grid), preconditioner.

Fadeev S.I., Kogai V.V., Mironova V.V., Omelyanchuk N.A., and Likhoshvai V.A.

Mathematical modeling of matter distribution in cells assembling into a ring (in Russian), pp. 171-184

 

    In this paper, a mathematical model describing substance transport in a circular cell ensemble is considered. The model is represented by an autonomous system of equations. With a model of continuation with respect to a parameter, it is shown that stationary solutions may have different symmetry representing closed curves. Periodic solutions have the same property, whereas the component plots repeat each other by a simple shift.

Key words: cell ensemble, gene networks, autonomous system, circular model, stationary solution, auto-oscillations, model for continuation with respect to parameters.

Hou T. 

Superconvergence and a posteriori error estimates of RT1 mixed methods for elliptic control problems with an integral constraint (in Russian), pp. 185-199


    In this paper, we investigate the superconvergence property and a posteriori error estimates of mixed finite element methods for a linear elliptic control problem with an integral constraint. The state and co-state are approximated by order k=1 Raviart-Thomas mixed finite element spaces, and the control variable is approximated by piecewise constant functions. Approximations of the optimal control of the continuous optimal control problem will be constructed by a projection of the discrete adjoint state. It is proved that these approximations have convergence order h2. Moreover, we derive a posteriori error estimates both for the control variable and the state variables. Finally, a numerical example is given to demonstrate the theoretical results.

Key words: elliptic equations, optimal control problems, superconvergence, a posteriori error estimates, mixed finite element methods, postprocessing.


Number 3, pp. 201-301 

 

Gurii Ivanovich Marchuk - outstanding scientist, organizer of science and the citizen (in Russian), pp. 201-204

Amelkin V.A.

Enumeration problems of sets of increasing and decreasing n-valued serial sequences with double-ended constraints on series heights (in Russian), pp. 205-215

 

Enumeration problems for n-valued serial sequences are considered. Sets of increasing and decreasing sequences whose structure is specified by constraints on lengths of series and on a difference in heights of the neighboring series in the case when this difference lies between δ1 and δ2 are examined.

Formulas for powers of these sets and algorithms for the direct and reverse numerations (assigning smaller numbers to the lexicographically lower-order sequences or smaller numbers to the lexicographically higher-order sequences) are obtained.

Key words: serial sequences, series length, series height, constraints.

Antyufeev V.S. 

Finding the most probable non-negative solution of systems of linear algebraic equations by the likelihood method (in Russian), pp. 217-228

 

A probabilistic method for regularization is proposed. This method enables one to obtain a non-negative solution to systems of linear algebraic equations. A theorem of existence of the best possible solution is proved. A numerical example of the method application is given. 

Key words: system of linear equations, non-negative regularization, probability distribution, stochastic ensemble.

Zabinyako G.I., Kotel'nikov E.A.

Minimization of nonlinear functions with linear constraints (in Russian), pp. 229-242

 

In this paper, some aspects of numerical realization of algorithms from the software package for solving problems of minimization of nonlinear functions including non-smooth functions with allowance for the linear constraints set by sparse matrices are considered. Examples of the solution of test problems are presented. 

Key words: nonlinear programming, reduced gradient, method of conjugate gradients, quasi-Newton method, subgradient method, basis, superbasis.

Penenko V.V., Tsvetova E.A.

Variational methods for constructing of monotone approximations for atmospheric chemistry models (in Russian), pp. 243-256 

 

A new method for constructing efficient monotone numerical schemes for solving direct, adjoint, and inverse atmospheric chemistry problems is presented. It is a systhesis of a variational principles combined with splitting and decomposition methods and a constructive realization of the Eulerian integrating factors (EIM) by means of the local adjoint problem technique. To provide the efficiency of calculations, a method to decompose the multi component substances transformation operators in terms of mechanisms of reactions is also proposed. With the analytical EIMs, the decomposed systems of stiff ODEs are reduced to the equivalent systems of integral equations. To solve them, non-iterative multistage algorithms of given order of accuracy are developed. An original variational method for constructing of mutually consistent algorithms for direct and adjoint problems, and sensitivity studies for complex models with constraints is developed. 

Key words: variational principle, stiff systems ODE, integrating multipliers, discrete-analytical approximations, atmospheric chemistry, algorithms for sensitivity studies.

Savelyev L.J. 

A minimum of the centered discrete random variables dispersion (in Russian), pp. 257-265 

 

The problem of isolation of discrete random values and vectors with discrete distributions having a given average value and a minimum dispersion is solved. The vector model is associated with statistical methods of calculation of multiple integrals and solutions to systems of the integral equations. 

Key words: discrete distribution, random variable, random vector, average value, dispersion.

Sorokin S.B.

Analytical solution of generalized spectral problem in the method of recalculating boundary conditions for a biharmonic equation (in Russian), pp. 267-274

An iterative algorithm with an efficient preconditioner for the numerical solution of an elastic problem in approximation of plate theory with mixed boundary conditions is proposed and substantiated. Exact constants of energy equivalence for optimization of iteration method are obtained. Inversion of the preconditioner is equivalent to the double inversion of a discrete analog of the Laplace operator with the Dirichlet boundary conditions.

Key words: biharmonic equation, boundary conditions, iterative method, Poisson's equation, plate, Dirichlet problem.

Cherepennikov V.B.

Numerical analytical method of studying some linear functional differential equations (in Russian), pp. 275-285

 

This paper presents the results of studies of the scalar linear functional-differential equation of a delay type (t)=a(t)x(t-1)+b(t)x(t/q)+f(t), q>1. The main attention is being given to the original problem with the initial point, when the initial condition is specified at the initial point, and the classical solution, whose substitution into the original equation transforms it into the identity, is sought for. The method of polynomial quasi-solution, based on representation of an unknown function x(t) as polynomial of degree N is applied as the method of investigation. Substitution of this function in the original equation results in the residual δ(t)=O(tN), for which an accurate analytical representation is obtained. In this case, the polynomial quasi-solution is understood as exact solution in the form of polynomial of degree N, disturbed because of the residual of the original initial problem. The theorems of existence of polynomial quasi-solutions for the considered linear functional-differential equation and exact polynomial solutions have been proved. The results of the numerical experiment are presented.
Key words: functional differential equations, initial value problem, polynomial quasi-solutions, exact solutions.

 

Shumilov B.M. 

Cubic multiwavelets orthogonal to polynomials and a splitting algorithm (in Russian), pp. 287-301

 

In this paper, an implicit method of decomposition of hermit cubic splines using the new type multiwavelets with supercompact supports is investigated. The splitting algorithm of wavelet-transformations on the parallel solution of two three-diagonal systems of the linear equations with strict diagonal domination is reasonable. The results of numerical experiments are presented. 

Key words: hermit splines, multiwavelets, implicit relations of decomposition, parallelization.

 


Number 4, pp. 303-404 

 

Artemiev S.S., Korneev V.D., Yakunin M.A.

Numerical solution to stochastic differential equations with a random structure on supercomputers (in Russian), pp. 303-311

         In this paper we investigate the precision of estimate of the expectation of solutionsto stochastic differential equations with a random structure. The dependence of the precision of estimate on the size of the integration step of the generalized Euler method and on the volume of the simulated trajectories is shown. A strong loss of the precision of estimate at deterministic or random times of changing the SDE structure is shown on an example of a simple equation. This requires the use of supercomputers for the statistical modeling. The results of the numerical experiments carried out in the Siberian SuperСomputer Center are presented. 

Key words: stochastic differential equations, parallelization, supercomputer, the methods of statistical modeling, the generalized Euler method.

 

Zadorin A.I., Zadorin N.A.

An analogue of Newton-Cotes formula with four nodes for a function with a boundary-layer component  (in Russian), pp. 313-323

 

The construction of the Newton-Cotes formulas is based on approximating an integrand by the Lagrange polynomial. The error of such quadrature formulas can be serious for a function with a boundary-layer component. In this paper, an analogue to the Newton-Cotes rule with four nodes is constructed. The construction is based on using non-polynomial interpolation that is accurate for a boundary layer component. Estimates of the accuracy of the quadrature rule, uniform on gradients of the boundary layer component, are obtained. Numerical experiments have been performed.

Key words: one-variable function, boundary-layer component, high gradients, definite integral, non-polynomial interpolation, quadrature rule, error estimate.

Mastryukov A.F.

The numerical solution of the inverse problem for Maxwell's equations based on the Laguerre functions  (in Russian), pp. 325-335

 

The inverse problem is solved by an optimization method using the Laguerre functions. Numerical simulations are carried out for the one-dimensional Maxwell's equations in the wave and diffusion approximations. Spatial distributions of permittivity and conductivity of the medium are determined from a known solution at a certain point. The Laguerre harmonics function is minimized. The minimization is performed by the conjugate gradient method. Results of determining permittivity and conductivity are presented. The influence of shape and spectrum of a source of electromagnetic waves on the accuracy of solution of the inverse problem is investigated. The accuracies of the solutions with a broadband and a harmonic sources of electromagnetic waves are compared.
Key words: numerical algorithm, Maxwell's equations, electromagnetic wave, conductivity, inverse problem, the Laguerre method, finite difference, linear equations, accuracy.

 

Nikolaev V.E., Ivanov G.I., Rozhin I.I.

Numerical modeling of the influence of heat exchange of reservoir beds with enclosing rocks on gas production from a single well (in Russian), pp. 337-346

 

In the computational experiment, the influence of heat exchange through top and bottom of the gas-bearing reservoir on the dynamics of temperature and pressure fields in the process of real gas production from a single well is investigated. The experiment was carried out with a modified mathematical model of non-isothermal gas filtration, obtained from the energy and mass conservation laws and the Darcy law. The physical and caloric equations of state together with the Newton-Rihman law of heat exchange of a gas reservoir with surrounding enclosing rocks are used as closing relations. It is shown that the influence of the heat exchange with environment on the temperature field of a gas-bearing reservoir is localized in a narrow zone near its top and bottom, though the size of this zone increases with time.

Key words: mathematical modeling, non-isothermal filtration, real gas, finite difference methods.

Okuonghae R.I. 

A class of A(α)-stable numerical methods for stiff problems in ordinary differential equations (in Russian), pp. 347-364

 

The A(α)-stable numerical methods (ANM) for the number of steps k ≤ 7 for stiff initial value problems (IVPs) in ordinary differential equations (ODEs) are proposed. The discrete schemes proposed from their equivalent continuous schemes are obtained. The scaled time variable t in a continuous method, which determines the discrete coefficients of the discrete method is chosen in such a way as to ensure that the discrete scheme attains a high order and A(α)-stability. We select the value of α for which the schemes proposed are absolutely stable. The new algorithms are found to have a comparable accuracy with that of the backward differentiation formula (BDF) discussed in [12] which implements the Ode15s in the Matlab suite.

Key words: stiff IVPs, continuous LMM, collocation and interpolation approach, boundary locus.

Rozhenko A.I., Shaidorov T.S.

On spline approximation with a reproducing kernel method (in Russian), pp. 365-376

 

Spline approximation with a reproducing kernel of a semi-Hilbert space is studied. Conditions are formulated that uniquely identify the natural Hilbert space by a reproducing kernel, a trend of spline, and the approximation domain. The construction of spline with external drift is proposed. It allows one to approximate functions having areas of big gradients or first-kind breaks. The conditional positive definiteness of some known radial basis functions is proved.

Key words: spline, reproducing kernel, trend, radial basis function, external drift.

 

Rybakov K.A.

An approximate solution of the optimal nonlinear filtering problem for stochastic differential systems by statistical modeling (in Russian), pp. 377-391

 

An algorithm for solving the optimal nonlinear filtering problem by statistical modeling is proposed. It is based on reducing the filtration problem to the analysis of stochastic systems with terminating and branching paths, using a structure similarity of the Duncan-Mortensen—Zakai equations and the generalized Fokker-Planck-Kolmogorov equation. The solution of such problem of analysis can be approximately found by using numerical methods for solving stochastic differential equations and methods for modeling inhomogeneous Poisson flows.

Key words: branching processes, conditional density, the Duncan-Mortensen-Zakai equation, Monte Carlo method, optimal filtering problem, stochastic system.

Tarakanov V.I., Lysenkova S.A., Nesterenko M.V.

The precession of a parametric oscillation pendulum with the Cardano suspension (in Russian), pp. 393-404

 

The probability of the precession of a pendulum with the Cardano suspension in conditions of an oscillation point of suspension based on the mathematical proof is investigated.

Key words: operator, spectrum, iterative algorithm, parametric oscillation, stability.