Siberian Journal of Numerical Mathematics

Volume 13, 2010

Contents

Number 1, pp. 1-121
Number 2, pp. 123-241
Number 3, pp. 243-359
Number 4, pp. 361-475


Number 1, pp. 1-121

 

Bandman O.L.

A cellular-automata method for studying porous media properties (in Russian), pp.  1-13

 

    A cellular-automata (CA) approach for investigation of properties of porous media with  tortuous channels and  different smoothness of pore walls is proposed. This approach is aimed at combining two different CA models: the first one is intended for constructing the morphology of a porous material, the second - for simulation of a fluid flow through it. The porous media morphology is obtained as a result of evolution of a cellular automaton, forming a «steady pattern». The result  obtained is then used  for simulating a fluid flow through a porous medium by  Lattice Gas CA model application. The method has been tested on a small fragment  of a porous material  and implemented for  investigating a carbon electrode of a hydrogen fuel cell on a multiprocessor cluster.

Key words: mathematical modeling, fine grained parallelism, cellular-automaton, Lattice-Gas hydrodynamics, porous medium, pattern formation, fluid flow in porous media.

 

Boyarintsev Yu.E.

On nonlinear algebraic differential systems reducible to non-degenerate systems of ordinary differential equations. Theory and numerical methods of solution (in Russian), pp. 15-21

 

    In this paper, we consider algebraic differential systems of the form dAx/dt = Bx+f(x,t) with a regular pair of matrices (A, В). The conditions of reducibility of such systems to non-degenerate systems of ordinary differential equations (ODE) of first order with respect to the derivative x'(t) are given. Methods for the numerical solution of x'(t)  are proposed.

Key words: algebraic differential, nonlinear, numerical method of solution.

 

Kotel'nikov E.A.

Applying a reduced gradient in the quadratic programming (in Russian), pp. 23-31

 

    This paper considers specific aspects of implementing the algorithm for solving problems of the quadratic programming, which is based on the reduced gradient method. In the current subspace of the superbasis variables, minimization is carried out by the conjugate gradient method. Some examples of solution of test problems are given.

Key words: quadratic programming, reduced gradient, conjugate gradient, basis, superbasis.

 

Kremer I.A., Urev M.V.

Solution of a regularized problem for a stationary magnetic field in a non-homogeneous conducting medium by a finite element method (in Russian), pp. 33-49

 

    In this paper, we substantiate the use of a vector finite element method for solving a regularized stationary magnetic problem, which is formulated in terms of a vector magnetic potential. To approximate the generalized solution, we make use of the Nedelec second kind vector elements of first order on tetrahedrons. Existence and uniqueness of the solution to a discrete regularized problem and its convergence to a generalized solution for the case of an inhomogeneous domain (according to electromagnetic properties) are justified. Some issues of the numerical solution to a discrete regularized problem are discussed. Approaches to optimize the algorithms are shown on a series of numerical experiments.

Key words: stationary Maxwell's equations, regularization, discontinuous coefficients, vector finite elements.

 

Kuzin V.I.,  Kravtchenko V.V.

Application of non-conforming finite elements for solving problems of diffusion and advection (in Russian), pp. 51-65

 

    The object of this paper is non-conforming finite elements and non-conforming finite element schemes for solving the diffusion-advection equation. This investigation is aimed at finding new schemes for solving parabolic equations. The method of the study is a finite element method, variational-difference schemes, tests. Two types of schemes are examined: the one is obtained with the help of the Bubnov-Galerkin method from a poor problem definition (non-monotone scheme) and the other one is a monotone up-stream type scheme, obtained from an approximate poor problem definition with a special approximation of skew-symmetric terms.

Key words: non-conforming finite elements, diffusion and advection equation, finite  element method, Bubnov-Galerkin method, up-stream type scheme.

 

Moskalensky E.D.

On detecting a wavefront described by 2D eikonal equation, when velocity in a medium depends on one spatial variable (in Russian), pp. 67-73

 

    In this paper, a 2D eikonal equation  fx2 + fy2 = (ky + b)2α is considered.    If its solution is found, then the relation f(x,y) = C determines the location of a wavefront. However, finding such solutions is still an open question. In this paper, we propose to directly find a curve in the parametric form, corresponding to the wavefront, without solving the equation as it is.

Key words: wave propagation, eikonal equation.

 

StrekalovskyA.S., Orlov A.V., Malyshev A.V.

A local search for the quadratic-linear bilevel programming problem (in Russian), pp. 75-88

 

    The quadratic-linear bilevel programming problem is considered. Its optimistic statement is reduced to a non-convex mathematical programming problem with the quadratic-bilinear structure. An approximate algorithm of a local search  in the problem obtained is proposed, proved and tested.

Key words: bilevel programming, optimistic solution, non-convex optimization problems, local search, test problems generating, computational simulation.

 

TananaV.P., Bulatova M.G.

An error estimation of an approximate solution of one inverse problem of thermal diagnostics (in Russian), pp. 89-100

 

    In thermal diagnostics of rocket engines [1], it is necessary to take into account the physical properties of composite materials used. This brings about the solution to inverse boundary value problems for the parabolic equation with discontinuity coefficients. High requirements imposed upon the accuracy of approximate solutions of the given class of problems make it possible to obtain error estimations of the methods used.

Key words: optimal method, operator equations, regularization.

 

Khatuntseva O.N.

Features of description of physical processes in fractal spaces (in Russian), pp. 101-109

 

    This paper offers a method of description of  physical processes that take place in fractal spaces with the use of differential equations. The latter describe similar processes in the Euclidean spaces, introducing an additional coordinate that specifies the point-wise scale of fractal partitioning at each point.

Key words: fractal, fractional dimension, scaling.

 

Shevaldina E.V.

Local £-splines preserving the differential operator kernel (in Russian), pp. 101-121

 

    In this paper, the local £-splines of odd order with uniform nodes are constructed. These splines preserve basic functions from the kernel of the linear differential operator £ with constant real coefficients and pairwise different roots of a characteristic polynomial. The pointwise error estimation of an approximation value using constructed splines on appropriate classes of differentiable functions is given.

Key words: local £-splines, differential operator, the error of an approximation.


Number 2, pp. 123-241

 

Laevsky Yu.M.

The wells problem for a stationary equation of diffusion (in Russian), pp. 123-142 

 

    The paper deals with the wells problem for which non-local boundary conditions are given. It is shown that this problem is equivalent to a mixed formulated problem without wells. For such a statement, an error estimate of the mixed finite element method for the 2D case is studied.

Key words: wells, mixed formulation, mixed finite element method, error estimate.

 

Mastryukov A.F., Mikhailenko B.G.

The solution to the 2D Maxwell equations by Laguerre spectral method (in Russian), pp. 143-160

 

    In this paper, a spectral method for solving 2D Maxwell equations with relaxation of electromagnetic parameters is presented. The method proposed is based on the expansion of equations solution in the Laguerre functions in the temporal domain.

    The operation of functions convolution that is a part of formulas, describing relaxation processes is reduced to the sum of harmonics products. Maxwell's equations transform to a system of linear algebraic equations for harmonics of the solution. In the algorithm, the inner parameter of the Laguerre transform is used. With large values of this parameter, the solution is shifted to the field of high harmonics. This is done to simplify the numerical algorithm and to increase the efficiency of the problem solution.

    The results of comparison between the accuracy of the Laguerre method and a finite-difference method both for 2D medium structure and for a layered medium are given. The results of comparison of efficiency of the spectral and the finite difference methods for the axial and for the plane geometries of the problem are presented.

Key words: Maxwell's equations, electromagnetic wave, relaxation time, conductivity, dielectric permittivity, Laguerre method, finite difference, axial symmetry, linear system equations, accuracy.

 

Mironov V.V.

A strongly-polynomial algorithm for solving the general problem of least modules  (in Russian), pp. 161-181

 

    The algorithm of polynomial algebraic complexity (a strongly-polynomial algorithm) to solve a classical problem of mathematical programming concerning minimization of the weighted sum of modules of part of variables with linear constraints (equalities imposed on all variables) has been substantiated. The algorithm is given in its explicit form. The estimation of the algorithm complexity is presented. The simulation has been carried out.

Key words: algorithm, complexity of algorithm, least modules.

 

Svetov I.E., Polyakova A.P.

Reconstruction of 2-tensor fields, given in a unit circle, by their ray transforms based on LSM with B-splines (in Russian), pp. 183-199

 

    The numerical method for solving a tensor tomography problem of reconstructing a symmetric 2-tensor field, given in a unit circle, is offered. Potential and (or) solenoidal part of the desired field with fixed properties on the boundary are found from transverse and (or) longitudinal ray transforms, calculated along the straight lines crossing the support of the field. The solution is sought by means of the least-squares method with the use, as approximating sequence, of local bases, constructed on the basis of B-splines.

Key words: Tensor tomography, potential field, solenoidal field, least-squares method, B-splines, approximation, fast Fourier transform.

 

Strekalovsky A.S., Orlov A.V., Malyshev A.V.

Numerical solution of a class of bilevel programming problems (in Russian), pp.  201-212

 

    The quadratic-linear bilevel programming problem is considered. Its optimistic statement is reduced to a series of non-convex mathematical programming problems. An approximate algorithm of the global search in the problems obtained is proposed. Numerical solutions of randomly generated test problems are given and analyzed.

Key words: bilevel programming, optimistic solution, non-convex optimization problems, global search, computational simulation.

 

Cherepennikov V.B., Ermolaeva P.G.

Smooth solutions of an initial-value problem for some differential difference equations (in Russian), pp. 213-226

 

    The problem area of the present paper is an initial-value problem with the initial function for the linear differential difference equation of neutral type. The problem is stated, which is bound up with finding an initial function such that the solution of the initial-value problem, generated by this function, possesses some desired smoothness at the points multiple to the delay. For the purpose of solving this problem, we use the method of polynomial quasi-solutions, whose basis is formed by the concept of an unknown function of the form of a polynomial of some degree. In the case of its substitution into the initial problem, there appears some incorrectness in the sense of dimension of polynomials, which is compensated by introducing into the equation some residual, for which a precise analytical formula, which characterizes the measure of disturbance of the considered initial-value problem.

    It is shown that if a polynomial quasi-solution of degree N has been chosen as initial function for the initial-value problem in question, then the solution generated will have smoothness at the abutment points not smaller than degree N.

Key words:  linear differential difference equations, initial-value problem, smooth solutions, polynomial quasisolutions method.

 

Shumilov B.M., Esharov E.A., Arkabaev N.K.

Construction and optimization of predictions on the basis of first degree recurrent splines (in Russian), pp. 227-241

 

    This paper addresses to the problem of the point and the interval predictions of the time series on basis of recurrent first degree splines with depth 1. The conditions of optimality for coefficients of the calculated scheme are found. The results of numerical experiments for analytically given functions with errors are presented. A comparison with classical methods of prediction of the time series is given.

Key words: spline, recurrence algorithm, optimization, prediction, time series.


Number 3, pp. 243-359

 

Volkov Yu.S.

The inverses of cyclic band matrices and the convergence of interpolation processes for derivatives of periodic interpolation splines (in Russian), pp. 243-253

 

    The estimates for entries of matrices inverse to the cyclic band matrices and for the matrix norms are presented. The results obtained are used for determining the convergence conditions of Interpolation processes by periodic odd degree splines for different derivatives. In particular, the positive solution to the C. de Boor problem on unconditional convergence of one of the two middle derivatives in the periodic case is proposed.

Key words: banded matrix, cyclic banded matrix, inverse matrix, norm of matrix, spline, interpolation, convergence.

 

Golubeva E.N.

Studying the role of temperature and salinity anomalies in formation of the World ocean meridional circulation modes (in Russian), pp. 255-267

 

    A numerical model of the ocean circulation is intended for the use in a coupled ocean-ice-atmosphere climate model. Preliminary experiments conducted on a numerical grid with a coarse spatial resolution over one thousand/year period reproduce the World ocean dynamics under the influence of the climatic surface forcing. Based on the introduction of anomalies into the surface sources, the sensitivity of the global ocean circulation to the thermohaline conditions in the northern regions of the Atlantic Ocean is investigated.

Key words: numerical model, large-scale ocean dynamics, global thermohaline circulation.

 

Zhelezovskii S.E.

Error estimates in the projection-difference method for a hyperbolic-parabolic system of abstract differential equations (in Russian), pp. 269-284

 

    The Cauchy problem for a hyperbolic-parabolic system of abstract differential equations in a Hilbert space is considered that generalizes a number of linear coupled thermoelasticity problems. The energy error estimates for the projection-difference method as applied to the Cauchy problem are established without imposing any special conditions on the projection subspaces. 

Key words: projection-difference method, error estimates, abstract differential equations, hyperbolic-parabolic system, coupled thermoelasticity problems.

 

Zorkaltsev V.I., Lebedeva L.M., Perzhabinsky S.M.

A model of power shortage evaluation of electric power systems with quadratic losses of power in power lines (in Russian), pp. 285-295

 

    A model of power shortage evaluation of electric power systems with quadratic losses of power in power lines is studied. This model is intended for the analysis of reliability problems of electric power systems. The way of presentation of this model in the form of a convex problem is shown. The interior point algorithm is proposed for the model realization. This algorithm takes into account the quadratic approximations of constraints functions. The results of the experimental study are presented.

Key words: model of power shortage evaluation of electric power systems, interior point method, quadratic approximations.

 

Maslovskaya L.V., Maslovskaya O.M.

Building graph separators with the recursive rotation algorithm for nested dissections method (in Russian), pp. 297-321

 

    The recursive rotation algorithm is built and investigated. This algorithm is one of versions of the nested dissections algorithm. The Liu algorithm builds a matrix graph separator by the rotation of an elimination tree. The rotation of the elimination tree decreases its height. In this case, the nodes of a matrix graph are previously re-ordered by one of the well-known Cuthill-McKee algorithms, reverse to the Cuthill-McKee algorithm, or King algorithm. Then this procedure is recursively repeated. Comparison between the recursive rotation algorithm and the multilevel and spectral methods of graph separation for the 2D finite elements grids is made.

Key words: rotation of elimination tree, separators, recursive rotation algorithm, finite elements grids.

 

Mastryukov A.F.

The inverse problem for acoustics equations. The multi-level adaptive algorithm (in Russian), pp. 323-341

 

    This paper presents a numerical solution to the inverse problem for the acoustic equations using an optimization method for a stratified medium. Based on the allocation of the acoustic wave field on the medium surface, the 1D allocations of a medium density as well as velocity and absorption coefficient of the acoustic wave are determined.

    The absorption is considered in a sample piece of the Foigt skew field. The conjugate gradients and the Newton methods are used for minimization.

    To increase the efficiency of the numerical algorithm, we propose a multi-level adaptable algorithm. This algorithm is based on the partitioning the whole algorithm of the solution to the inverse problem into a series of consecutive levels. Each of such levels is characterized by the number of parameters, defined at it. While passing from one level on another level, the number of parameters adaptively changes in terms of the value of a functional and convergence rate.

    Selection of minimization parameters is illustrated on the results of the inverse problem solution in a spectral domain, when the desired values are presented as a Tchebychev polynomial series, and minimization is carried out according to the value of this quantity at a point.

    The efficiency of the method proposed is compared to the non-adaptive method of solution. The selection of the most optimal parameters of the multi-level method is presented.

    It is shown that the multi-level algorithm possesses certain advantages as compared to the one without partitioning into levels. The algorithm proposed first of all allows obtaining a more exact solution to the inverse problem.

Key words: inversion, inverse problem, acoustic, velocity, attenuation, density, adaptive, multi-level, optimization method, efficiency, precision.

 

Tarakanov V.I., Nesterenko M.V.

An iterative algorithm of investigation and numerical solution of spectral problems for a linear bunch of compact, partially symmetric operators (in Russian), pp. 343-359

 

    The character of the spectrum is investigated and eigenfrequencies are calculated with the use of a new iterative algorithm on an example of a spectral problem on eigenfrequencies of a beam of a variable section loaded with the moment of torsion.

Key words: operator, spectrum, iterative algorithm.


Number 4, pp. 361-475

 

Amelkin V.A.

Algoritms for enumeration of single-transition serial sequences (in Russian), pp. 361-373

 

    Sets of n-valued single-transition serial sequences consisting of two serial subsequences (an increasing one and a decreasing one) determined by constraints on the number of series and on their lengths and heights are considered.

    Enumeration problems for sets of finite sequences in which the difference in height between the neighboring series is not less than some given value are solved. Algorithms that assign smaller numbers to the lexicographically lower-order sequences and smaller numbers to the lexicographically higher-order sequences are obtained.

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

 

Antonova T.V.

New methods for localizing the discontinuities of a noisy function (in Russian), pp. 375-386

 

    For a problem of localizing the singularities (discontinuities of the first kind) of a noisy function in в Lp (1≤ p<∞), new classes of regularizing methods are constructed. These methods determine the number of discontinuities and approximate their positions. Also, upper and lower bound of the localizing singularities and the separability threshold, is obtain. It is proved that the methods are order-optimal by accuracy as well as separability on some classes of functions with discontinuities.

Key words: ill-posed problems, localization of singularities, discontinuities of the first kind, regularizing method, separability threshold.

 

Demidov G.V., Martynov V.N.

A step-by-step method with Laguerre functions for solving evolutionary problems (in Russian), pp. 413-422

 

    In this paper, a step-by-step modification of a well-known approach of Mikhailenko and Konyukh for solving dynamic problems is proposed. The approach is based on the Laguerre transform with respect to time. In this modification the Laguerre transform is applied to a sequence of finite time intervals. The solution obtained at the end of a time interval is used as the initial data for problem solving on the next time interval. The method is illustrated by the examples of a harmonic oscillator problem and a 1D wave equation. The accuracy and stability of the method are analyzed. This approach allows obtaining a solution of high accuracy on large time intervals.

Key words: dynamic problems, Laguerre transformation, step-by-step method, accuracy, stability.

 

Golubyatnikov V.P., Golubyatnikov I.V., and Likhoshvai V.A.

On the existence and stability of cycles in 5-dimensional models of gene networks (in Russian), pp. 403-411

 

    We obtain sufficient conditions for the existence and stability of closed trajectories in five-dimensional nonlinear dynamical systems which model gene networks with negative feedbacks.

Key words: gene networks, nonlinear dynamical systems, stationary points, periodic trajectories.

 

Mikhailov G.N., Medvedev I.N.

Vector estimators of the Monte Carlo method: dual representation and optimization (in Russian), pp. 423-438

 

    In this paper, a detailed analysis of the vector Monte-Carlo estimator theory for solving a system of integral equations is given. A dual representation for the variances of such estimators is introduced. With the dual representation we minimize the majorant mean-square error of a global solution estimator (of the histogram type). Also, for the first time we give a detailed description of the scalar Monte-Carlo algorithms for solving a system of integral equations and a comparison between the scalar and vector algorithms.

Key words: vector estimator of Monte-Carlo method, solving systems of integral equations, dual estimator representation, optimization, scalar Monte-Carlo algorithm.

 

Smelov V.V., Popov A.S.

An analog to the Gauss quadrature implemented on a specific trigonometric basis (in Russian), pp. 439-450

 

    A new quadrature formula based on a nonstandard basis of trigonometric functions is constructed. The quadrature is comparable in accuracy to the Gauss quadrature formula and is used with the same class of functions. However, this quadrature has nothing to do with the quadrature for periodic functions, which is also based on trigonometric functions.

Key words: quadrature formula, weight function, nodes and coefficients of a quadrature, approximation.

 

Tanana V.P.

An order-optimal method for solving an inverse problem for a parabolic equation (in Russian), pp. 451-465

 

    An order-optimal method for solving an inverse problem for a parabolic equation with a variable coefficient is proposed.

Key words: operator equations, regularization, optimal method, error estimation, ill-posed problem.

 

Tarkov M.S.

Construction of Hamiltonian cycles by recurrent neural networks in graphs of distributed computer systems (in Russian), pp. 467-475

 

    An algorithm based on a recurrent neural Wang's network and the WTA («Winner takes all») principle is applied to the construction of Hamiltonian cycles in graphs of distributed computer systems (CSs). The algorithm is used for: 1) regular graphs (2D- and 3D-tori, and hypercubes) of distributed CSs and 2) 2D-tori disturbed by removing an arbitrary edge. The neural network parameters for the construction of Hamiltonian cycles and sub-optimal cycles with a length close to that of Hamiltonian ones are determined. Our experiments show that the iteration method (Jacobi, Gauss-Seidel, or SOR) used for solving the system of differential equations describing a neural network strongly affects the process of cycle construction and depends upon the number of torus nodes.

Key words: recurrent neural networks, distributed computer systems, parallel algorithms, Hamiltonian cycle, graphs, torus, hypercube, Jacobi method, Gauss-Seidel, SOR.

 

Vinogradova P.V., Zarubin A.G.

Asymptotic error estimates of a linearized projection-difference method for a differential equation with a monotone operator (in Russian), pp. 387-401

 

    In this paper, we study a projection-difference method for the Cauchy problem for an operator-differential equation with a self-adjoint leading operator A(t) and a non-linear monotone subordinate operator K(.) in a Hilbert space. This method leads to solving a system of linear algebraic equations at each time level. Error estimates for the approximate solutions as well as for the fractional powers of the operator A(t) are obtained. The method is applied to a model parabolic problem.

Key words: operator-differential equation, monotone operator, difference scheme, convergence rate, Faedo-Galerkin method.