Siberian Journal of Numerical Mathematics

Volume 9, 2006

Contents

Number 1, pp. 1-108
Number 2, pp. 109-206
Number 3, pp. 207-323
Number 4, pp. 325-421


Number 1, pp. 1-108

Bogdanov V.V., Volkov Yu.S.
Selection of parameters of generalized cubic splines with convexity preserving
interpolation
(in Russian), pp. 5-22

It is shown that computation of generalized interpolating cubic splines is reduced to solving a tridiagonal system of linear
equations with column diagonal dominance with respect to knot values of the second derivative of a spline. The non-negativity conditions of the solution for such systems are found. The general scheme for choosing tension parameters of the generalized splines for convexity-preserving interpolation is offered. The resulting spline minimally differs from the classical cubic one and coincides with it if sufficient convexity conditions for the last one are satisfied. The algorithms specified are considered for different generalized cubic splines such as rational, exponential, variable power, hyperbolic splines and splines with additional knots.
Key words: convex interpolation, rational spline, shape preserving interpolation, tension parameters, monotone matrix, tridiagonal system.

Kretinin A.V.
The weighted residuals method based on neuronet approximations for simulation
of hydrodynamics problems
(in Russian), pp. 23-35

An algorithm of the numerical solution to hydrodynamics equations with representation of the solution according to the method of weighted residuals based on the general neuronet approximation over the whole flow area has been developed.
The algorithm was tested on solving the two-dimensional Navier-Stokes equations. The algorithm is applied to modeling the variable mass flow.
Key words: neuronet, hydrodynamics.

Mikhailenko B.G., Reshetova G.V.
The numerical-analytical method of solving the problem of seismic and acoustic-gravity wave propagation for the inhomogeneous model Earth-Atmosphere
(in Russian), pp. 37-46

This paper considers a numerical-analytical method of solving the problem of seismic and acoustic-gravity wave propagation for the inhomogeneous model "Earth-Atmosphere''. The seismic wave propagation is described by a system of the first order dynamic equations of elasticity theory; the propagation of acoustic-gravity waves in the atmosphere is described by the linearized Navier-Stokes equations. The algorithm proposed is based on a combination of the integral Laguerre transform with respect to time, finite integral Bessel transform along the radial coordinate with a finite difference method along the vertical coordinate. The paper presents some examples of calculation of seismic and acoustic-gravity waves for the inhomogeneous model Earth-Atmosphere for various locations of a source.
Key words: Seismic waves, acoustic-gravity waves, wave propagation, numerical-analytical method, the Bessel transform and the Laguerre transform.

Moghrabi I.A.R.
Multiple update multi-step methods for unconstrained optimization
(in English), pp. 47-53

The quasi-Newton multi-step methods were developed in \cite{2} and have revealed substantial numerical improvements over the standard single step Secant-based BFGS. Such methods use a variant of the Secant equation that the updated Hessian (or its inverse) satisfies at each iteration. In this paper, we explore algorithms whose updated Hessians satisfy multiple relations of the Secant-type in order that the numerical potentials of such techniques be investigated. We employ a rational model in developing the new methods. The model hosts a free parameter which is exploited in enforcing symmetry on the multi-updated matrix. Our results are encouraging, and the improvements incurred supercede those obtained from
other existing methods at minimal extra storage and computational overhead.
Key words: unconstrained optimization, quasi-Newton methods, multi-step methods.

Rozhenko A.I.
On calculation of scalar products of B-splines
(in Russian), pp. 55-61

The paper is devoted to algorithms of stable calculation of scalar products of B-splines. A new modification of recursive
calculations of integrals in the Gram matrix is proposed. The modified algorithm is nearly two times faster than the Gauss quadratures and the full recursion algorithm.
Key words: B-spline, divided difference, the Gram matrix.

Shishkin G.I.
Higher-order accurate method for a quasilinear singularly perturbed elliptic convection--diffusion equation (
in Russian), pp. 81-108

We consider the Dirichlet problem on a rectangle for a quasilinear singularly perturbed elliptic convection-diffusion equation in the case when the domain has no characteristic parts of its boundary; the higher derivatives of the equation contain a parameter \eps that takes arbitrary values in the half-interval (0,1]. For a linear problem of this type, the \eps-uniform rate of convergence for well-known schemes has not higher than the first order (in the maximum norm). For the boundary value problem under consideration, grid approximations are constructed that converge ε-uniformly at the rate O{N-2\ln2N}, where N specifies the number of mesh points in each variable. The piecewise uniform meshes, condensing in the boundary layer, are used. When the values of the parameter are small as compared to the effective mesh size, we apply the domain decomposition method, which is motivated by "asymptotic constructions''. We use monotone approximations of "auxiliary'' subproblems that describe the main terms of asymptotic representations of the solutions inside and outside the vicinity of the regular and the angular boundary layers. The above subproblems are solved sequentially on subdomains using uniform meshes. If the values of the parameter are not sufficiently small (as compared to the effective mesh size), then classical finite difference schemes are employed, where the first derivatives are approximated by central difference derivatives. Note that the computation of solutions of the constructed difference scheme, based on the method of "asymptotic constructions'', is essentially simplified for sufficiently small values of the parameter ε.
Key words: singularly perturbed Dirichlet problem, quasilinear elliptic convection-diffusion equation, increase in accuracy, method of asymptotic constructions, domain decomposition, piecewise uniform meshes.

Urev M.V.
The convergence of finite element method for axially symmetric magnetostatic problem
(in Russian), pp. 63-79

This paper considers a problem of calculation of stationary magnetic linear axially symmetric fields in non-homogeneous media. As distinct from conventional formulations of this problem in terms of the azimuthal vector potential component or a function of a magnetic field flow, the present paper offers the reduction to another sought for function satisfying the equation to be most convenient for investigation. The principal feature of the problem formulated is in its degeneracy on the axis of symmetry demanding the corresponding spaces with a weight when studying the problem. For the finite element method with piecewise linear elements, the convergence of an approximate solution to the exact one is proved with an error estimation not worse than in the case of the elliptic equation without degeneracy.
Key words: degenerating equation, the weight Sobolev spaces, finite element method.


Number 2, pp. 109-206

Amelkin V.A.
Recalculation, numbering and generation of serial sequences with detached natural series (in Russian), pp.109-121

The sets of integer-valued serial sequences of the length m, whose structure is determined by limitations on the quantity, total length and permitted lengths of natural series, as well as on lengths of separating 0-series are considered. The cases when lengths of boundary series may not satisfy the given constraints are considered as well. Exact solutions to problems of recalculation, coding and generation are obtained for such sets.
Key words: series, sequence of series, restrictions, enumeration.

Godunov S.K., Selivanova S.V.
Experiments on using the resonance effect for spectral analysis of finite-dimensional skew-symmetric operators
(in Russian), pp.123-136

An algorithm of spectral analysis for skew-symmetric matrices based on using the resonance effect is proposed and studied. Its application to computation of oscillation spectra for conservative systems of hyperbolic equations is discussed on the example of three-dimensional linear elasticity.
Key words: eigenvalue problem, skew-symmetric operator, resonance effect, hyperbolic equations.

Khludnev A.M., Leontiev A.N.
A problem of flow through semipermeable obstacle
(in English), pp.173-188

This paper deals with mathematical analysis of a potential flow through a thin semipermeable obstacle. The boundary value problem is characterized by the inequality type conditions imposed on a non-smooth component of the boundary. We prove solvability of the boundary value problem and analyze the solution properties. Using boundary elements, an optimization technique for the numerical solution of the problem is proposed. Numerical results for test problems are presented.
Key words: semipermeable obstacle, unilateral boundary conditions, potential flow, boundary elements.

Kuznetsov Yu.I.
The orthogonal and the nodal polynomials
(in Russian), pp.137-145

The polynomials Pk(x) of the degree k that are orthogonal on a finite set of the points xi, i=1(1)n, with weights ci > 0, are considered. It is shown that the polynomial Pk(x) is a linear functional of the nodal polynomials of the same degree, expressed by xi, ci. The vector that defines this functional is positive and normalized. Such properties of the functional describe it as average, or the center of mass, of the nodal polynomials distributed with the corresponding density.
Key words: polynomial, orthogonal, nodes, finite, set, liner, functional, average, density.

Miloserdov V.V.
Conditional optimization of discrete-stochastic numerical procedures with cubic splines applied
(in Russian), pp.147-163

In this paper, the discrete-stochastic numerical procedures of the global function approximation are considered. The procedures are built to approximate the solution to an integral equation of the second kind using the Streng-Fix approximation with cubic B-splines as basis functions. In the case of using cubic splines, a discrete component of the approximation error has a higher order with respect to the grid step as compared to the well-studied case of the multi-linear approximation. Moreover, the property of "error concentration in grid nodes'' is proved to hold for approximation with the cubic splines as well. This is because the coefficients of the approximation are, in fact, linear combinations of the function values in grid nodes. The above properties provide the upper bounds for the total approximation error. Finally, for the investigated discrete-stochastic procedures, the conditionally-optimal parameters are calculated that minimize computational costs for the procedures with the fixed error upper bounds.
Key words: discrete-stochastic procedures, Streng-Fix approximation, cubic splines, local estimators, conjugate walks method.

Novikov S.I.
Periodic interpolation with a minimum norm of the m-th derivative
(in Russian), pp.165-172

In this paper, the interpolation problem for periodic data with a bounded lp-norm is investigated for an interpolating set of smooth periodic functions. In the cases when p=2 and p=∞ , the exact values of the Lp-norms of the m-th derivative of the best interpolants are found for a certain class of sequences.
Key words: interpolation, spline, extremal problem.

Shary S.P.
Inner estimation of solution sets to non-negative interval linear systems
(in Russian), pp.189-206

This paper presents a new technique for constructing the maximum (with respect to an inclusion) inner estimates of the solution sets to the interval linear equations systems having non-negative matrices, based on the shape monotonicity of these solution sets.
Key words: interval linear system, non-negative matrix, solution set, inner estimation, maximum estimate.


Number 3, pp. 207-323

Bazanov P.V., Djosan O.V.
Methods of face feature extraction of the human identification problem
(in Russian), pp.207-214

This paper offers three different methods that are used to extract information features from a face image. We suggest effective modifications of the feature extraction methods based on the principal component analysis, wavelets, hidden Markov models.

The human face recognition experiments were carried out using the database with normalized faces. These experiments have shown advantages and disadvantages of the methods proposed.
Key words: face features extraction, human face recognition, principle component analysis, wavelets, hidden Markov models.

Borisov Yu.S.
Visualization of city environment by the plenoptic method
(in Russian), pp.215-223

We describe an image-based rendering algorithm that allows the visualization of large spatial scenes. Images taken by an ordinary digital camera are used as inputs. These images are transformed into panoramic views, which are 4D parameterization of the full plenoptic function for further storing. Using a simple proxy geometry, we can create the novel view from these structures.

The cases, when our approach can be used, are formulated. The results of our algorithm for both synthetic and real scenes are demonstrated.
Key words: image-based rendering, plenoptic function, panoramic views, virtual walkthroughs.

Ermolin E.N., Kazakov A.Yu.
The impulse-based method for the simultaneous resolution of collisions between rigid bodies
(in Russian), pp.253-262

The paper proposes an enhanced version of the impulse-based method for the numerical simulation of collisions between rigid bodies. This approach makes it possible to resolve several collisions simultaneously, allows for inelastic collisions with energy loss, and supports assembly constraints.
Key words: virtual reality, rigid bodies dynamics, collision resolution, assembly constraints.

Ganelina N.D., Frolovsky V.D.
On constructing the shortest circuits on a set of line segments
(in Russian), pp.241-252

This paper deals with the problem of defining the Hamiltonian cycle on segments by the ant colony algorithm. Parameters and properties of this algorithm as applied to the cutting chart for the NC machine and an arbitrary set of segments are studied.
Key words: ant colony, pheromone, Hamiltonian cycle.

Konouchine A.S., Gaganov V.A., Vezhnevets V.P.
Extending RANSAC-based estimators to handle unknown and varying noise level
(in English), pp.263-277

The robust parameter estimation methods are a general tool in computer vision, widely used for such tasks as multiple view relation estimation and camera calibration. In this paper, a new robust maximum-likelihood estimator AMLESAC is presented. It is a noise-adaptive version of the well-known MLESAC estimator. It adopts the same sampling strategy and seeks the solution to maximize the likelihood rather than some heuristic measure. Unlike MLESAC, it simultaneously estimates all the noise parameters: inlier share γ, inlier error standard deviation σ and outlier probability density 1/ \nu. Effective optimization for the computation speed-up is also introduced. Results are given both for synthetic and real test data for different types of models. The algorithm is demonstrated to surpass the previous approaches for the task of pose estimation and provides results equal or superior to other robust estimators in other tests.
Key words: robust estimation, sampling consensus, maximum likelihood, RANSAC, MLESAC, pose estimation, line fitting, circle fitting, non-linear optimization, iterative refinement.

Korobeynikov A.V., Turlapov V.E.
Modeling and evaluation of the Stewart platforms
(in English), pp.279-286

This paper presents an efficient algorithm for solving the forward kinematics problem and an application for the motion modeling of the Stewart platforms. The developed application is able: (i) to solve the forward kinematics problem with a given accuracy; (ii) to calculate the trajectory of a tool positioned on the mobile platform; (iii) to calculate a possible deviation of the tool from a nominal position or a trajectory if lengths of the legs are varying within given tolerances; (iv) to detect the crossing of the legs during motions of a mobile platform. A projected movement of the Stewart platform can be specified by explicit parametric expressions for platform coordinates or by the spline-interpolation of trajectory nodes. The
computational core of the application is based on the new efficient algorithm, which provides the minimum number of unknowns and the quadratic convergence rate even if two subsequently calculated positions are far apart.
Key words:CAD, CAE, kinematics, Stewart platform, parallel manipulators.

Landovsky V.V., Frolovsky V.D.
Integration methods in the problem of modelling a fabric based on the particles method
(in Russian), pp.287-298

This paper describes a fabric simulation system. On the basis of the method of particles with allowance for physical properties of a fabric, the model and the algorithm for modelling the behaviour of a fabric on the surface of a rigid polyhedral object are developed. A comparative analysis of some different integration methods is made. And some results of the simulation are presented.
Key words: modelling fabric, method of particles, power functions, physical properties of a fabric, stability, integration step.

Mestetskiy L.M.
Skeletonization of a multiply-connected polygonal domain based on its boundary adjacent tree
(in Russian), pp.299-314

The problem of a continuous skeleton construction for a multiply connected polygonal domain is considered. The polygonal domain is a closed one, whose boundary consists of a finite number of simple polygons. The O(n \log n) - algorithm for the worse case is offered, where n is the number of polygonal domain vertices. The proposed algorithm creates the dual graph for the Voronoi diagram of the domain boundary. The solution is based on the adjacent tree of all the boundary polygons created by a sweepline method. In this case, sites and polygons are called adjacent if they have a common contact empty circle. The offered approach generalizes the Lee skeleton algorithm from a simple polygon to that with holes with the same running time.
Key words: polygon with holes domain, skeleton, Delaunay graph, Lee algorithm, polygon adjacency, sweepline.

Pozin A.G.
Volumetric algorithm for 3D surface generation
(in Russian), pp.315-323

This paper describes the process of creating a single 3D model from a number of previously aligned scans. Using the volumetric algorithm makes the solution of this problem intuitively clear and easy for implementation. In addition, it describes the data structure decreasing the memory requirement needed for processing large models.
Key words: 3D scanning, surface reconstruction.

Vaganova N.A., Matsokin A.M.
The post-processing algorithms for images and video
(in Russian), pp.225-240

The blockness and ringing are the two main types of artifacts occurring as a result of the use of block image compression and video coding algorithms for a high compression ratio. Today, most of applied deblocking and deringing algorithms are time-consuming and can not be used for devices which perfect coding/decoding in the real time mode. The adaptive deblocking post-processing algorithm is offered in this paper. The algorithm allows one to underline textures without changing them and, also, eliminates ringing artifacts on the decoded images. The offered algorithms decrease disadvantages of image coding and give good contours and real textures keeping for real edges in decoded images. Moreover, the developed methods are not time-consuming and may be integrated in any type of processors. Preliminary experiments have shown that for 352x288 images, the working time was about 0.31 ms, and with a special optimization these algorithms may really work in real time (25-30 frames per s).
Key words: image post-processing, artifact removing filters, image compression, videocoding.
 


Number 4, pp. 325-421

Artemiev S.S., Yakunin M.A.
Analysis of the number of sale/purchase signals for trade algorithms (in Russian), pp.325-334

We investigate probability characteristics of the results of the trade for trade algorithms. The latter are based on smoothing a price series by exponential moving average. In the case of the model of a price series with a Gaussian distribution of price increments, the parametric analysis of mathematical expectation of the number of sale/purchase bargains and probability of making a bargain is carried out.
Key words: trade algorithm, the number of bargains, moving average.

Fedotov A.V.
Forecasting the bank resources dynamics by Monte Carlo method
(in Russian), pp.369-378

Bank liquidity is predicted on the basis of mathematical model of bank account by Monte Carlo method. Various statistical characteristics of bank profit and risk are calculated.
Key words: bank account dynamics model, Monte Carlo, liquidity risk forecast, statistical analysis.

Ismagilov T.Z.
On a smooth volume approach, integral conservation law, and upwind scheme with monotonic reconstruction
(in English), pp.345-352

This paper presents a smooth volume approach - an alternative to smooth particle formalism. The proposed approach is based on approximation of integral conservation law and can be viewed as a generalization for the finite volume method. To provide insight into properties of smooth volume schemes, a hypothesis is presented. On its basis, an extension technique for the development of smooth volume schemes is suggested. Using this technique, the finite volume upwind and the Godunov schemes with monotonic reconstruction are generalized to smooth volume schemes. The hypothesis, the technique and the resulting schemes are tested by applying them to gasdynamics shock tube problems. Precise and monotonic calculation results verify validity of our theory and properties of the schemes developed.
Key words: integral conservation laws, smooth volume method, smooth particle method, finite volume method, upwind approximation, monotonic reconstruction.

Jung M., Matsokin A.M., Nepomnyaschikh S.V. and Tkachov Yu.A.
Preconditioning by multilevel methods with locally modified grids
(in English), pp.403-421

Systems of grid equations that approximate elliptic boundary value problems on locally modified grids are considered. The triangulation, which approximates the boundary with second order of accuracy, is generated from an initial uniform triangulation by shifting nodes near the boundary according to special rules. This ``locally modified'' grid possesses several significant features: this triangulation has a regular structure, generation of the triangulation is rather fast, this construction allows the use of multilevel preconditioning (BPX-like) methods. The proposed iterative methods for solving grid elliptic boundary value problems are based on two approaches: the fictitious space method, i.e., reduction of the original problem to that in an auxiliary (fictitious) space, and the multilevel decomposition method, i.e., construction of preconditioners by decomposing functions on hierarchical grids. The convergence rate of the corresponding iterative process with the preconditioner obtained is independent of the mesh size. The construction of the grid and the preconditioning operator for the three-dimensional problem can be done in the same manner.
Key words: elliptic boundary value problems, mesh generation, finite element method, multilevel methods.

Shamin R.V.
On a numerical method for problem of a non-stationary flow of incompressible
fluid with a free surface
(in Russian), pp.379-389

A numerical method for obtaining approximate solutions to equations describing a non-stationary motion of an ideal liquid with free boundary in a gravitational field is constructed. The convergence is proved, provided that a smooth solution exists. An efficient numerical scheme is proposed.
Key words: hydrodynamics with a free surface, numerical methods.

Shevaldina E.V.
Approximation by local exponential splines with arbitrary nodes
(in Russian), pp.391-402

For the class of functions W
Ľ [a,b] = { f: f'є AC, || Ľ2 (D)f || 1}  (Ľ2 (D) = D2 - β2 I,  β>0, D is operator of differentiation) a new noninterpolating linear method of local exponential spline-approximation with arbitrary nodes is constructed. This method has some smoothing properties and inherits monotonicity
and generalized convexity of the data (values of a function f є W
Ľ  at the grid points). The error of approximation in a uniform metric of a class of functions WĽ  by these splines is exactly determined.
Key words: local method, exponential spline-approximation, the error of approximation.

Tanana V.P., Yaparova N.M.
The optimum in order method of solving conditionally-correct problems
(in Russian), pp.353-368

Necessary and sufficient conditions, which ensure sets of the Banach spaces to be classes of correctness are obtained. The
concept of solution method of conditional-correct problem is given. The quantitative characteristic of its accuracy on an
appropriate class of correctness is determined. The obtained results are used for solving one inverse problem of solid-state
physics.
Key words: the operational equation, classes of correctness, the optimum in the order, accuracy of solution method.

Vtorushin E.V.
Numerical investigation of a model problem for deforming an elastoplastic body with a crack under non-penetration condition
(in Russian), pp.335-344

The Lam$\acute{e}$ system is considered in a two-dimensional domain with a crack. The Dirichlet and the Neuman
conditions are held on the exterior boundary, and non-penetration condition is assumed to be on a crack. The convolution
product of the deviator of the stress tensor is restricted by a certain constant within the domain. Thus, we have a model problem for deforming an ideal elastoplastic body with a crack (the Henky model) subject to the Mises yield criterion. Simultaneously, the non-penetration condition is held on a crack. The problem is formulated as a variational one. We find a displacement vector as solution to minimization problem for the energy functional over a convex set. Discretization of the problem is provided by a finite element method. Examples of calculation are obtained using the Udzava algorithm.
Key words: crack, non-penetration, ideal elastoplasticity (Henky model), variational inequalities, FEM, Udzava algorithm.