Lexicographic regularization and duality for improper linear programming problems

A new approach to the optimal lexicographic correction of improper linear programming problems is proposed. The approach is based on the multistep regularization of the classical Lagrange function with respect to primal and dual variables simultaneously. The regularized function can be used as a basis for generating new duality schemes for problems of this kind. Theorems on the convergence and numerical stability of the method are presented, and an informal interpretation of the obtained generalized solution is given.     

Three-level schemes of the alternating triangular method

In this paper, the schemes of the alternating triangular method are set out in the class of splitting methods used for the approximate solution of Cauchy problems for evolutionary problems. These schemes are based on splitting the problem operator into two operators that are conjugate transposes of each other. Economical schemes for the numerical solution of boundary value problems for parabolic equations are designed on the basis of an explicit-implicit splitting of the problem operator. The alternating triangular method is also of interest for the construction of numerical algorithms that solve boundary value problems for systems of partial differential equations and vector systems. The conventional schemes of the alternating triangular method used for first-order evolutionary equations are two-level ones. The approximation properties of such splitting methods can be improved by transiting to three-level schemes. Their construction is based on a general principle for improving the properties of difference schemes, namely, on the regularization principle of A.A. Samarskii. The analysis conducted in this paper is based on the general stability (or correctness) theory of operator-difference schemes.     

Regularized additive operator-difference schemes

The construction of additive operator-difference (splitting) schemes for the approximate solution Cauchy problem for the first-order evolutionary equation is considered. Unconditionally stable additive schemes are constructed on the basis of the Samarskii regularization principle for operator-difference schemes. In the case of arbitrary multicomponent splitting, these schemes belong to the class of additive full approximation schemes. Regularized additive operator-difference schemes for evolutionary problems are constructed without the assumption that the regularizing operator and the operator of the problem are commutable. Regularized additive schemes with double multiplicative perturbation of the additive terms of the problem’s operator are proposed. The possibility of using factorized multicomponent splitting schemes, which can be used for the approximate solution of steadystate problems (finite difference relaxation schemes) are discussed. Some possibilities of extending the proposed regularized additive schemes to other problems are considered.     

一阶双曲型方程组初边值问题的差分格式及其稳定性

本文比较系统地讨论了有关数值求解两个自变量的一阶双曲型方程组初边值问题的某些问题,给出了几种能用于任何类型的初边值问题的差分格式,并在很宽的条件下证明了其中的某些变系数的初边值问题的差分格式对初值和边值是稳定的、差分格式所立出的方程组是良态的.其中的某些格式已用于解决某些复杂的实际问题(应用部分见[16]).     

Construction of splitting schemes based on transition operator approximation

The stability analysis of approximate solutions to unsteady problems for partial differential equations is usually based on the use of the canonical form of operator-difference schemes. Another possibility widely used in the analysis of methods for solving Cauchy problems for systems of ordinary differential equations is associated with the estimation of the norm of the transition operator from the current time level to a new one. The stability of operator-difference schemes for a first-order model operator-differential equation is discussed. Primary attention is given to the construction of additive schemes (splitting schemes) based on approximations of the transition operator. Specifically, classical factorized schemes, componentwise splitting schemes, and regularized operator-difference schemes are related to the use of a certain multiplicative transition operator. Additive averaged operator-difference schemes are based on an additive representation of the transition operator. The construction of second-order splitting schemes in time is discussed. Inhomogeneous additive operator-difference schemes are constructed in which various types of transition operators are used for individual splitting operators.     

Units coordination and the construction of improper fractions: A revision of the splitting hypothesis

This article communicates findings from a year-long constructivist teaching experiment about the relationship between four sixth-grade students’ multiplicative structures and their construction of improper fractions. Students’ multiplicative structures are the units coordinations that they can take as given prior to activity—i.e., the units coordinations that they have interiorized. This research indicates that the construction of improper fractions requires having interiorized three levels of units. Students who have interiorized only two levels of units may operate with fractions greater than one, but they don’t produce improper fractions. These findings call for a revision in Steffe's hypothesis (Steffe, L. P. (2002). A new hypothesis concerning children's fractional knowledge. Journal of Mathematical Behavior, 20, 267-307) that upon the construction of the splitting operation, students’ fractional schemes can be regarded as essentially including improper fractions. While the splitting operation seems crucial in the construction of improper fractions, it is not necessarily accompanied by the interiorization of three levels of units.     

Operator-difference schemes for a class of systems of evolution equations

For a special system of evolution equations of first order, discrete time approximations for the approximate solution of the Cauchy problem are considered. Such problems arise after the spatial approximation in the Schrödinger equation and the subsequent separation of the imaginary and real parts and in nonstationary problems of acoustics and electrodynamics. Unconditionally stable two time level operator-difference weighted schemes are constructed. The second class of difference schemes is based on the formal passage to explicit operator-difference schemes for evolution equations of second order when explicit-implicit approximation is used for isolated equations of the system. The regularization of such schemes in order to obtain unconditionally stable operator difference schemes is discussed. Splitting schemes involving the solution of simplest problems at each time step are constructed.     

Fundamental mode exact schemes for unsteady problems

The problem of increasing the accuracy of an approximate solution is considered for boundary value problems for parabolic equations. For ordinary differential equations (ODEs), nonstandard finite difference schemes are in common use for this problem. They are based on a modification of standard discretizations of time derivatives and, in some cases, allow to obtain the exact solution of problems. For multidimensional problems, we can consider the problem of increasing the accuracy only for the most important components of the approximate solution. In the present work, new unconditionally stable schemes for parabolic problems are constructed, which are exact for the fundamental mode. Such two‐level schemes are designed via a modification of standard schemes with weights using Padé approximations. Numerical results obtained for a model problem demonstrate advantages of the proposed fundamental mode exact schemes.     

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar graphs. We also define the concept of λ-precision unit disk graphs and show that for such graphs the approximation schemes have a better time versus performance trade-off than the approximation schemes for arbitrary unit disk graphs. Moreover, compared to unit disk graphs, we show that for λ-precision unit disk graphs many more graph problems have efficient approximation schemes.Our NC-approximation schemes can also be extended to obtain efficient NC-approximation schemes for several PSPACE-hard problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann, and Widmayer. The approximation schemes for hierarchically specified unit disk graphs presented in this paper are among the first approximation schemes in the literature for natural PSPACE-hard optimization problems.     

High-order compact solvers for the three-dimensional Poisson equation

New compact approximation schemes for the Laplace operator of fourth- and sixth-order are proposed. The schemes are based on a Padé approximation of the Taylor expansion for the discretized Laplace operator. The new schemes are compared with other finite difference approximations in several benchmark problems. It is found that the new schemes exhibit a very good performance and are highly accurate. Especially on large grids they outperform noncompact schemes.     

A quantitative analysis of children's splitting operations and fraction schemes

Teaching experiments with pairs of children have generated several hypotheses about students’ construction of fractions. For example, Steffe (2004) hypothesized that robust conceptions of improper fractions depends on the development of a splitting operation. Results from teaching experiments that rely on scheme theory and Steffe's hierarchy of fraction schemes imply additional hypotheses, such as the idea that the schemes do indeed form a hierarchy. Our study constitutes the first attempt to test these hypotheses and substantiate Steffe's claims using quantitative methods. We analyze data from 84 students’ performances on written tests, in order to measure students’ development of the splitting operation and construction of fraction schemes. Our findings align with many of the hypotheses implied by teaching experiments and, additionally, suggest that students’ construction of a partitive fraction scheme facilitates the development of splitting.     

Unconditionally stable schemes for convection-diffusion problems

Convection-diffusion problems are basic ones in continuum mechanics. The main features of these problems are connected with the fact that their operators may have an indefinite sign. In this paper we study the stability of difference schemes with weights for convection-diffusion problems where the convective transport operator may have various forms. We construct unconditionally stable schemes for nonstationary convection-diffusion equations based on the use of new variables. Similar schemes are also used for parabolic equations where the operator represents the sum of diffusion operators.     

A Minty variational principle for set optimization

Extremal problems are studied involving an objective function with values in (order) complete lattices of sets generated by so-called set relations. Contrary to the popular paradigm in vector optimization, the solution concept for such problems, introduced by F. Heyde and A. Löhne, comprises the attainment of the infimum as well as a minimality property. The main result is a Minty type variational inequality for set optimization problems which provides a sufficient optimality condition under lower semicontinuity assumptions and a necessary condition under appropriate generalized convexity assumptions. The variational inequality is based on a new Dini directional derivative for set-valued functions which is defined in terms of a “lattice difference quotient.” A residual operation in a lattice of sets replaces the inverse addition in linear spaces. Relationships to families of scalar problems are pointed out and used for proofs. The appearance of improper scalarizations poses a major difficulty which is dealt with by extending known scalar results such as Diewert's theorem to improper functions.     

The solution of infinitely ill-conditioned weakly-singular problems

It is demonstrated on examples that a weak singularity (i.e., with converging improper integral) may produce in computations (depending on the algorithm employed) an infinitely ill-conditioned situation when arbitrarily small imprécisions introduced by the algorithm or by a software create divergent approximations for mathematically convergent integrals. The possibility of hidden singularities is shown, and the double error phenomenon is identified and demonstrated in a simple example. Construction of test problems is proposed to check the applicability of existing software prior to its use for the solution of real life problems with weakly-singular equations. It is shown that the application of the integration by parts formula to weakly-singular integrals may create strong singularities (i.e., unbounded terms or divergent improper integrals). Methods of removal of singularities with and without compensation are studied for the numerical solution of infinitely ill-conditioned weakly-singular problems.     

Analysis of stability and convergence in FD simulations of the 1-D ultrasonic wave propagation

Finite difference (FD) methods are a well established tool for studying the propagation of pulses and waves in nonelementary media. In the present paper, we analyze some different FD schemes for smoothing the interface between two different media, and study their stability and convergence.We find that an improper choice of interface model may lead to unstable or pseudoconvergent recurrence relationships and cause severe errors in the amplitudes of both the reflected and transmitted pulses.     

Additive schemes for certain operator-differential equations

Unconditionally stable finite difference schemes for the time approximation of first-order operator-differential systems with self-adjoint operators are constructed. Such systems arise in many applied problems, for example, in connection with nonstationary problems for the system of Stokes (Navier-Stokes) equations. Stability conditions in the corresponding Hilbert spaces for two-level weighted operator-difference schemes are obtained. Additive (splitting) schemes are proposed that involve the solution of simple problems at each time step. The results are used to construct splitting schemes with respect to spatial variables for nonstationary Navier-Stokes equations for incompressible fluid. The capabilities of additive schemes are illustrated using a two-dimensional model problem as an example.     

Numerical solution by the quasi-reversibility method of unstable problems for the first-order evolution equation

Prior bounds are derived on the solution of the perturbed problem in different versions of the quasi-reversibility method used for approximate solution of unstable problems for first-order evolution equations. An example of such a problem is provided by the problem backward in time for the equation of heat conduction. Approximate solution of perturbed problems by difference methods is considered. The investigation of the difference schemes of the quasi-reversibility method relies on the general theory of p-stability of difference schemes. Specific features of solution of problems with non-self-adjoint operators are considered. Efficient difference schemes are constructed for multidimensional problems.Translated from Matematicheskoe Modelirovanie i Reshenie Obratnykh Zadach. Matematicheskoi Fiziki, pp. 93–124, 1993.     

对流占优扩散问题的经济型流线扩散有限元法

In this paper, the economical finite difference-streamline diffusion (EFDSD) schemes based on the linear F.E. space for time-dependent linear and non-linear convection-dominated diffusion problems are constructed. The stability and error estimation with quasi-optimal order approximation are established in the norm stronger than L^2 - norm for the schemes considered. It is indicated by the results obtained that,for linear F.E. space, the EFDSD schemes have the same specific properties of stability and convergence as the traditional FDSD schemes for the problems discussed.     

反常积分学习的几个误区

总结学生在求解反常积分问题时经常出现的几类错误,并加以分析和纠正,旨在帮助学生更好地学习和理解反常积分的相关内容．     

A rational approximation and its applications to nonlinear partial differential equations on the whole line

An orthogonal system of rational functions is discussed. Some inverse inequalities, imbedding inequalities and approximation results are obtained. Two model problems are considered. The stabilities and convergences of proposed rational spectral schemes and rational pseudospectral schemes are proved. The techniques used in this paper are also applicable to other problems on the whole line. Numerical results show the efficiency of this approach.