Siberian Journal of Numerical Mathematics

Volume 11, 2008

Contents

Number 1, pp. 1-114
Number 2, pp. 115-238
Number 3, pp. 239-356
Number 4, pp. 357-474


Number 1, pp. 1-114

Artemiev S.S., Villius A.S., Voinov A.N.
Stock exchange modeling with a price model involving variable variance and correlation coefficients
(in Russian), pp.19-28

The price model with the variance and correlation coefficients as random processes is analyzed. Parametric analysis is realized by means of "direct" and "inverse" trade algorithms. Results of numerical experiments are obtained with the use of INVERT program.
Key words:
parametric analysis, trade algorithm, Monte Carlo method, profitability, risk.

Averina T.A., Rybakov K.A.
Two methods for analyzing stochastic multi-structural systems with distributed structure changes
(in Russian), pp.1-18

The statistical simulation method and the spectral method for the stochastic multi-structural systems analysis are considered. There are given algorithms for the analysis problem solution. Numerical examples are given to illustrate the efficiency of the proposed methods.
Key words: stochastic multi-structural systems, switching diffusions, analysis problem, generalized Fokker-Planck-Kolmogorov equations, statistical simulation method, spectral method.

Chobanu M.K.
Synthesis of the main elements of multi-dimensional multi-rate systems. Part I. Nonseparable decimation matrices
(in Russian), pp.95-113

A synthesis method for multi-dimensional decimation matrices is developed for a given number of channels and dimension. Decimation matrices are used in multi-dimensional multi-rate systems. The method is based on application of eigenvalues techniques and the Groebner bases.
A full parametrization of decimation matrices is given for two-and three-dimensional cases. Peculiarities of the four-dimensional case are considered.
Key words: nonseparable decimation matrix, multi-rate system, multi-dimensional filter bank, eigenvalue, the Groebner bases.

Kabanikhin S.I, Hasanov A., Penenko A.V
The gradient-based method for solving the inverse coefficient heat-conduction problem
(in Russian), pp.41-54

An iterative gradient descent method has been applied to the inverse coefficient heat-conduction problem with overdetermined boundary conditions. Some theoretical estimates have been obtained for variation of the target functional with respect to the variation of the coefficient. Using these estimates, an approximated gradient of the target functional has been constructed. In the numerical experiments, the iteration convergence rates for different gradient descent parameters were compared.
Key words: coefficient identification, inverse heat conduction problem, gradient, adjoint problem, gradient descent parameter.

Kotel'nikov E.A.
Non-convex quadratic optimization on a parallelepiped
(in Russian), pp.69-81

The approximating-combinatorial method for solving optimization problems is used for the search for a global maximum of a quadratic function on a parallelepiped. The approximating functions in this method are majorants of an object function. The majorants are constructed on subsets of parallelepiped of admissible solutions. The method is based on a diagonal or block-diagonal LDLT-factorization of a matrix of an object function.
Key words: non-convex quadratic programming, non-convex optimization, branch and bound algorithm, factorization of symmetric matrix.

Kovtanyuk A.E. and Prokhorov I.V.
Numerical solution of the inverse problem for the polarized-radiation transfer equation
(in Russian), pp.55-68

In this paper, an inverse problem for the time-independent vector transfer equation for polarized radiation in an isotropic medium is studied. In this problem, it is required to find the attenuation factor from a known solution of the equation at the medium interface. An approach, based on using special external radiative sources, is proposed for solving this problem. A formula is derived which relates the Radon transform of the attenuation factor with the radiation-flux density at the boundary. The numerical experiments have shown an advantage of the algorithm for the polarized-radiation transfer equation over the one for scalar case.
Key words: vector transfer equation, polarized radiation, attenuation factor, Radon transform, Monte Carlo method.


Lu Zuliang, Zhang Hongwei.
V-cycle multi-grid method of viscoelastic fluid flow obeying an Oldroyd B type constitutive law
(in Russian), pp.83-94

For the time-dependent viscoelastic fluid flow obeying an Oldroyd B type constitutive law in three dimensional domains, we put forward a V-cycle multi-grid method. At the same time, we discuss existence, uniqueness and error estimates of the approximate solution. The approximate stress, velocity and pressure are, respectively, σk discontinuous, uk continuous, pk continuous.
Key words:
viscoelastic fluid flow obeying an Oldroyd B type constitutive law, V-cycle multi-grid method, convergence analysis.

Wang Hai-jun, Cao De-xin, Li Su-bei.
Interval entropy method for equality constrained multiobjective optimization Problems
(in Russian), pp.29-39

Based on the maximum entropy principle and the idea of penalty function, an evaluation function to solve multiobjective optimization problems with equality constraints is given. Combining with interval analysis method, we define generalized Krawczyk operator, design interval iteration with constrained functions and new region deletion test rules, present an interval algorithm for equality constrained multiobjective optimization problems, and also prove relevant properties. The theoretic analysis and numerical results indicate that the algorithm is effective and reliable.
Key words: multiobjective optimization, equality constraints, generalized Krawczyk operator, maximum entropy
function, interval algorithm.

 


Number 2, pp. 115-238

Artemiev S.S., Yakunin M.A.
Analysis of asymptotic distributions of some profitability characteristics of the trade algorithms
(in Russian), pp.115-125

We investigate the asymptotic behavior of a model sequence of price increments and the probability characteristics of a trade algorithm. The asymptotic normality of such characteristics as the number of buy/sell transactions and the value of total profitability has been proved for the stationary m-dependent sequence of price increments. The approximate formulas for the calculation of their mathematical expectations and variances as functions of parameters of a price series and a trade algorithm have been obtained. Some results of the numerical experiments are given.
Key words:
total profitability, trade algorithm, asymptotic distribution, mixing sequence.

Chobanu M.K.
Synthesis of the parameters of multi-dimensional multi-rate systems. Multidimensional fractional delay filters
(in Russian), pp.219-238

The problem of multi-dimensional multi-rate systems design by application of a lifting technique is considered. In order to solve it, it is proposed to apply the design method of multidimensional digital filters with a fractional delay. A symmetric structure is given for τ=(1/2, 1/2), as well as a new structure based on application of the multidimensional Taylor series.

The impulse and the frequency responses are given for the filters with a fractional space delay, their L2 norm being found.
Key words:
non-separable multi-rate system, multi-dimensional Taylor series, multi-dimensional filter bank, fractional delay filter.

Karchevsky A.L.
A correct flow chart for numerical solution to an inverse problem by optimization method
(in Russian), pp.139-149

In this paper, two flow charts for solving the same inverse problem by an optimization method are presented. On numerical examples it is shown that the first flow chat often used by researchers requires much more computer costs than the second one. This is because of the necessity of using a fine net and due to an increase in the number of minimization iterations of the residual functional for its decrease up to a certain value.
Key words:
inverse problem, optimization method, residual functional.

Lazareva G.G., Mironova V.V., Omelyanchuk N.A., Shvab I.V., Vshivkov V.A., Gorpinchenko D.N., Nikolaev S.V., Kolchanov N.A.
Mathematical modeling of vegetation morphogenesis
(in Russian), pp.151-166

The state-of-the-arts in biology needs the analysis of a bulk of experimental data. Mathematical modeling of biological processes is one of the ways to do it, with a purpose of revealing regularities, proving hypotheses and reasonable predictions. Evolution of organisms is especially attractive for mathematical modeling because it integrates a large number of different types of processes, whose state varies depending on time and location. In the present paper, the authors review the models of biological processes as related to plants evolution. The models have been classified and the approaches and mathematical techniques of modeling complicated problems are described.
Key words: morphogenesis, plants evolution, mathematical model, genetic regulation, cell division, model classification, review.


Leonov A.S.
On elimination of accuracy saturation of regularizing algorithms
(in Russian), pp.167-186

A general approach to modification of well-known methods for the solution of linear ill-posed problems is proposed. The approach enables us to exclude a possible ``saturation of accuracy'' of methods on classes of sourcewise representable solutions. As a result, the modified methods possess the optimal order of accuracy on each of these classes. Numerical examples for the solution of 1D and 2D inverse problems are presented.
Key words: ill-posed problems, accuracy saturation, soursewise represented solutions.


Likhachov A.V.
Regularizing filtrating of projections for two-dimensional tomography algorithms
(in Russian), pp.187-200

The regularizing filters for tomography algorithms are proposed and investigated. The method for regularization parameter determination was developed on the basis of a discrepancy criterion. The numerical simulations were carried out. In particular, the proposed filtration of projections was compared to be Shepp-Logan one.
Key words:
tomography, regularizing algorithm, discrepancy criterion.

Prigarin S.M., Hahn K., Winkler G.
Comparative analysis of two numerical methods to measure Hausdorff dimension of the fractional Brownian motion
(in Russian), pp.201-218

The objective of the paper is to study by Monte Carlo simulation statistical properties of two numerical methods (the extended counting method and the variance counting method) developed to estimate the Hausdorff dimension of a time series and applied to the fractional Brownian motion.
Key words: fractal set, Hausdorff dimension, extended counting method, variance counting method, generalized Wiener process, fractional Brownian motion.

Zhelezovskii S.E.
Error estimate in the projection-difference method for an abstract quasilinear hyperbolic equation with a non-smooth right-hand side
(in Russian), pp.127-137

We analyze the convergence of a three-level scheme of the projection-difference method for an abstract quasilinear hyperbolic equation in a Hilbert space with variable operator coefficients and a non-smooth (only Bochner integrable) right-hand side. We fix an energy error estimate without any special conditions imposed on the projection subspaces.
Key words:
abstract hyperbolic equation, projection-difference method, error estimate.
 


Number 3, pp. 239-356

Aleksandrov V.M.
Sequential synthesis of the optimal time control by liner systems with disturbances
(in Russian), pp.251-270


A method of sequential synthesis of the optimal time control of a linear system with unknown disturbances is considered. A system of linear algebraic equations is obtained that connects the increments of the phase coordinates to the increments of the initial conditions of the normalized adjoint system and that of the control completion time. The evaluations consist in solving repeatedly the system of linear algebraic equations and integrating the matrix differential equation on the displacement intervals of the control switching times and that of the final control time. The procedure of correcting the switching times and the completion time in moving the phase trajectory of the controlled object is examined. Simple and constructive conditions are obtained for the following: occurrence of discontinuous mode; moving a representative point along the switching manifolds; transformation of the optimal control structure in moving the phase trajectory of the system with uncontrollable disturbance. The computational algorithm is given. The sequence of controls is proved to converge locally at a quadratic rate, and globally to the optimal time control.
Key words: optimal control, speed, duration of computation, linear system, disturbance, phase trajectory, switching time, adjoint system, variation, iteration.

Amelkin V.A.
Enumeration problems of oriented serial sequences
(in Russian), pp.271-282


The sets of $n$-valued $m$-sequences of a serial structure are considered. In addition to the conventional concepts of length of a series and the number of series in a sequence, the concepts of height of a series and series heights sequence are introduced. The structure of the sequences that are called oriented is determined from limitations on the number and the length of series, on order of sequencing of series of various heights.

A general approach to solving enumeration problems for sets of such sequences is proposed. It is based on formulas for the number of arrangements of elements in cells and the power of a set of height sequences. Exact solutions for some
limitations which are important applications are obtained.
Key words:
series, series length, series height, limitations, serial sequences.

Averina T.A., Artemiev C.C.
Analysis of the accuracy of Monter Carlo methods for boundary-value problems using probabilistic representation
(in Russian), pp.239-250


Problems of the accuracy of statistical simulation algorithms are investigated for boundary-value problems of mathematical physics for the elliptic equations. These algorithms are based on a probabilistic representation of these solutions with the use of appropriate systems of the stochastic differential equations. The problems in question are due to the necessity to simulate long SDE trajectories and the estimation of expectation of random variables with asymmetric distribution. Numerical results are given.
Key words: boundary-value problems, stochastic differential equations, numerical methods.

Dvinsky A.L., Novikov E.A.
Approximation of the Jacobi matrix in (m, 3)-methods of solving stiff systems
(in Russian), pp.283-295

The theorem that the maximal order of accuracy of L-stable (m, k)-methods with freezing the Jacobi matrix is equal to four.
Key words:
stiff systems, one-step methods, (m, k)-methods, freezing the Jacobi matrix, the maximal order of accuracy.

Kamenskii G.A., Kuzmin G.N.
The direct numerical Euler method for finding extrema of non-local functionals
(in Russian), pp.297-309

There is considered a direct numerical method, which is the generalization of the Euler method for the non-local functionals depending on functions with deviations of different signs, as well as for non-local functionals depending on functions of two independent variables.
Key words: direct numerical method, extremum, non-local functional.

Kel'manov A.V., Mikhailova L.V., Khamidullin S.A.
Optimal detection of a recurring tuple of reference fragments in a quasi-periodic sequence
(in Russian), pp.311-327


The a posteriori (off-line) approach to solving the problem of maximum-likelihood detection of a recurring tuple containing reference fragments in a numerical quasi-periodic sequence is studied. The case is analyzed, where (1) the total number of fragments in a sequence is unknown; (2) the index of a sequence term corresponding to the beginning of a fragment is a deterministic (not random) value; (3) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is shown that the problem under consideration is reduced to testing a set of simple hypotheses about the mean of a random Gaussian vector. The cardinality of this totality exponentially grows as the vector dimension (i.e., the length of a sequence understudy) increases. It is established that the search for a maximum-likelihood hypothesis is equivalent to finding the arguments which yield a maximum for an auxiliary objective function. It is shown that maximizing this objective function is reduced to solving a special optimization problem. It is proven that this special problem is a polynomial-solvable one. The exact algorithm for solving this problem is substantiated, which underlies the algorithm for the optimal (maximum-likelihood) detection of the recurring tuple. The kernel of this algorithm is the algorithm for solution of a special (basic) optimization problem. The results of numerical simulation are presented.
Key words:
quasi-periodic sequence, a posteriori processing, recurring tuple of reference fragments, noise-proof maximum-likelihood detection, discrete optimization, efficient algorithm.

Kuznetsov V.V., Levyakov S.V.
A finite-variation method in the nonlinear shell mechanics
(in Russian), pp.329-340


A numerical algorithm is proposed for calculating the coefficients of the first and second order variations of the strain energy of a nonlinear finite element model of a shell, which are necessary to determine the equilibrium states of a shell and investigate their stability. Several numerical schemes based on various finite difference approximations are considered. For these schemes, the accuracy, convergence, and computation time are studied using popular geometrically-nonlinear problems of elastic plates and shells.
Key words: finite-variation method, thin shell, large displacements, strain energy, finite element.

Kuznetsov Yu.I.
Clusters of point matrices
(in Russian), pp.341-346


Clusters of point matrices In this paper, in addition to classical orthogonal polynomials, we introduce the orthogonal polynomials of degree n-1 at n points. They result from interpolational polynomials. The name ``point matrices" is justified by the fact that we do not consider a class of similar or congruent matrices that play the key role in a linear space and connected with its bases. We consider matrices with a fixed set of nodes (or points)  x1,...,xn. A certain matrix cluster corresponds to each set of nodes. A simple connection between eigenproblems of the Hunkel matrix H and the symmetric Jacjbi matrix T has been obtained.
Key words:
matrix, point, node, Krylov space, eigenvalue, Jacobi matrix, Hankel matrix, Frobenius matrix, Vandermonde matrix, similarity transformation.

Prigarin S.M., Marshak A.L.
Simulation of vector semi-binary homogeneous random fields and modeling of broken clouds
(in Russian), pp.347-356

A vector-valued homogeneous random field will be called semi-binary if its single-point marginal distribution is a mixture of a singular distribution and a continuous one. In this paper, we present methods of numerical simulation of semi-binary fields on the basis of the correlation structure and the marginal distribution. As an example, we construct a combined model of cloud top height and optical thickness using satellite observations results.
Key words:
simulation of stochastic fields, semi-binary and quasi-Gaussian random fields, correlations, marginal distribution, simulation of stochastic structure of clouds.
 


Number 4, pp. 357-474

Congratulation on the anniversary of Romanov Vladimir Gavrilovich (in Russian), pp.357-358

Lavrent'ev M.M., Kabanihin S.I.
On the anniversary of Romanov Vladimir Gavrilovich
(in Russian), pp.359-360
 

Gilyova L.V., Shaidurov V.V.
Convergence of the multigrid cascadic algorithm for second order finite elements in a domain with a smooth boundary
(in Russian), pp.361-384

In this paper, the cascadic multigrid algorithm for a grid problem obtained by discretization of a second order elliptic equation with second order finite elements on triangles is substantiated. The efficiency of the algorithm is proved. This means that the number of arithmetic operations required to achieve the order of accuracy of an approximate solution equal to that of the discretization error linearly depends on the number of unknowns. The rate of convergence is found to be higher than that for linear finite elements in spite of a higher order of accuracy.
Key words:
finite element method, quadratic elements, multigrid iterative algorithms, curvilinear triangular elements.

Gusev S.A.

Estimation of derivatives with respect to parameters of a functional of a diffusion process moving in a domain with absorbing boundary (in Russian), pp.385-404

 

In this paper, a statistical method for estimation of derivatives with respect to parameters of a functional of a diffusion process moving in a domain with absorbing boundary is proposed. The considered functional defines the probability representation of the solution of the corresponding parabolic first boundary value problem. The problem posed is solved by the numerical solution of stochastic differential equations (SDE) by the Euler method. The evaluation of an error of the proposed method is derived, and estimations of variance of the obtained parametric derivatives are given. Some numerical results are presented.

Key words: diffusion process, stochastic differential equations, absorbing boundary, derivatives with respect to parameters, Euler method.

 

 

Eltsov N.P., Ogorodnikov V.A., and Prigarin S.M.

A study of bounded cascade models of random fields on a plane (in Russian), pp.405-412

 

Cascade models of random processes and fields are intensively applied for the mathematical modeling of different objects and phenomena. In this paper, we study properties of the bounded cascade models on a plane, their one-dimensional distributions and correlation structure. The results obtained can help in analyzing the adaptability of cascade models for various application problems.

Key words: mathematical modeling, random processes and fields, cascade models.

 

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

Organization of parallel calculations in some problems of discrete optimization (in Russian), pp.413-422

 

The organization of parallel calculations with the use of the MPI functions in problems of discrete optimization is considered. The method of branches and borders is applied to problems of the integer linear and the integer quadratic programming, as well as to problems of set covering. The efficiency of algorithms is analyzed on the basis of numerical experiments.

Key words: method of branches and borders, asynchronous process, problems of integer linear and integer quadratic programming, problems of set covering.


Monakhov O.G.

A parallel genetic algorithm for optimization of trading strategies (in Russian), pp.423-432

 

An approach for optimization of trading strategies (algorithms) based on indicators of financial markets and evolutionary computation is described. A parallel version of the genetic algorithm for the search of optimal parameters of trading strategies for maximization of a trading profit is presented.

Key words: trading strategy, parallel genetic algorithm, technical analysis, financial indicator, template, evolutionary computation.

 

Popov A.S.

The cubature formulas on a sphere that are invariant with respect to the icosahedral group of rotations (in Russian), pp.433-440

 

An algorithm for constructing the cubature formulas on a sphere that are invariant with respect to the icosahedral group of rotations is proposed. This algorithm is applied to construct the new cubature formulas that have the algebraic order of accuracy n = 19, 20, 21, 23, 24, 25. Parameters of these cubature formulas are given to 16 significant digits. The table, which contains the main characteristics of all the best today cubature formulas of the icosahedral group of rotations up to the 35th order of accuracy, is given. A real variant of F. Klein's formula that states the connection between the basic invariant forms of the icosahedral group of rotations is given.

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

 

Saveliev L.J.

Calculation of the moments of sums for the autoregression process with signum by management (in Russian), pp.441-456

 

An autoregression sequence with simple management is considered. There is a sign of the previous term used in the recurrent equation determining this sequence. Multiplying this sign transforms this equation to a nonlinear one and essentially complicates the process. Such a signature management seems to be expedient, when an increment of the initial process is adjusted.

The distributions and the moments of some random variables concerned with this process are investigated. The autoregression processes and examples of their application are described in detail in the literature [1-4].

Key words: autoregression, one-and-a-half normal distribution, expectation, variance, calculation accuracy.

 

Shary S.P.

Randomized algorithms in interval global optimization (in Russian), pp.457-474

 

This paper is a critical survey of the interval optimization methods aimed at computing the global optima of multivariable functions. To overcome some drawbacks of traditional deterministic interval techniques, we outline the ways of constructing stochastic (randomized) algorithms in interval global optimization, in particular those based on the ideas of a random search and simulated annealing.

Key words: global optimization, interval methods, randomization, stochastic methods, random search, simulated annealing.