Asymptotic expansions andL ∞-error estimates for mixed finite element methods for second order elliptic problems

Summary Asymptotic expansions for mixed finite element approximations of the second order elliptic problem are derived and Richardson extrapolation can be applied to increase the accuracy of the approximations. A new procedure, which is called the error corrected method, is presented as a further application of the asymptotic error expansion for the first order BDM approximation of the scalar field. The key point in deriving the asymptotic expansions for the error is an establishment ofL ¹-error estimates for mixed finite element approximations for the regularized Green's functions. As another application of theL ¹-error estimates for the regularized Green's functions, we shall present maximum norm error estimates for mixed finite element methods for second order elliptic problems.     

Morse theory for some lower-C 2 functions in finite dimension

Using inf-regularization methods, we prove that Morse inequalities hold for some lower-C ² functions. For this purpose, we first recall some properties of the class of lower-C ² functions and of their Moreau-Yosida approximations. Then, we establish, under some qualification conditions on the critical points, that it is possible to define a Morse index for a lower-C ² functionf. This index is preserved by the Moreau-Yosida approximation process. We prove in particular that the Moreau-Yosida approximations are twice continuolusly differentiable around such a critical point which is shown to be a strict local minimum of the restriction off and of its approximations to some affine space. In a last step, Morse inequalities are written for Moreau-Yosida approximations and with the aid of deformation retractions we prove that these inequalities also hold for some lower-C ² functions.     

Some current questions on solving linear elliptic problems

Summary Common properties of elliptic problems and their solutions are compared with those of difference equations, with emphasis on the classical Dirichlet problem. Resistance network analogies are used to construct discrete harmonic functions; a new 9 POINT NET approximation is defined on elementary domains whose solutions haveO(h ⁴) max-norm error. The convection-diffusion equation is studied with especial emphasis on new fast iterative methods for solving its difference approximations. A new analysis of the structure of the matrix representation of difference approximations reveals special features which can naturally be associated with diffusion and with convective processes.Dedicated to R. S. Varga on the occasion of his sixtieth birthday     

Approximation of the Classes B p,θ Ω of Periodic Functions of Many Variables in Uniform Metric

We obtain order estimates for the best M-term trigonometric approximations and approximations by Fourier sums for the classes B _p, of periodic functions of many variables in the uniform metric.     

Waiting-time tail probabilities in queues with long-tail service-time distributions

We consider the standardGI/G/1 queue with unlimited waiting room and the first-in first-out service discipline. We investigate the steady-state waiting-time tail probabilitiesP(W>x) when the service-time distribution has a long-tail distribution, i.e., when the service-time distribution fails to have a finite moment generating function. We have developed algorithms for computing the waiting-time distribution by Laplace transform inversion when the Laplace transforms of the interarrival-time and service-time distributions are known. One algorithm, exploiting Pollaczek's classical contourintegral representation of the Laplace transform, does not require that either of these transforms be rational. To facilitate such calculations, we introduce a convenient two-parameter family of long-tail distributions on the positive half line with explicit Laplace transforms. This family is a Pareto mixture of exponential (PME) distributions. These PME distributions have monotone densities and Pareto-like tails, i.e., are of orderx ^–r forr>1. We use this family of long-tail distributions to investigate the quality of approximations based on asymptotics forP(W>x) asx. We show that the asymptotic approximations with these long-tail service-time distributions can be remarkably inaccurate for typicalx values of interest. We also derive multi-term asymptotic expansions for the waiting-time tail probabilities in theM/G/1 queue. Even three terms of this expansion can be remarkably inaccurate for typicalx values of interest. Thus, we evidently must rely on numerical algorithms for determining the waiting-time tail probabilities in this case. When working with service-time data, we suggest using empirical Laplace transforms.     

Tables of good lattices in four and five dimensions

Summary The good lattice theory yields a powerful method of computing approximations for the integral of functions defined on [0,1]^s through averaged sums ofm evaluations. We present a continuation of the only existing table of best lattices fors=4 up tom=3298, and the first table fors=5 up tom=772.From the Ecole Polytechnique de Montréal, département de Mathématiques appliquées, C.P. 6079 Station A, Montréal QC, Canada H3C 3A7. This research was supported by Grant A3087 from the National Science and Engineering Research Council of Canada     

A note on two fixed point problems

We extend the applicability of the Exterior Ellipsoid Algorithm for approximating n-dimensional fixed points of directionally nonexpanding functions. Such functions model many practical problems that cannot be formulated in the smaller class of globally nonexpanding functions. The upper bound 2n²ln(2/) on the number of function evaluations for finding -residual approximations to the fixed points remains the same for the larger class. We also present a modified version of a hybrid bisection-secant method for efficient approximation of univariate fixed point problems in combustion chemistry.     

Spectral methods with sparse matrices

Summary Spectral methods employ global polynomials for approximation. Hence they give very accurate approximations for smooth solutions. Unfortunately, for Dirichlet problems the matrices involved are dense and have condition numbers growing asO(N ⁴) for polynomials of degree N in each variable. We propose a new spectral method for the Helmholtz equation with a symmetric and sparse matrix whose condition number grows only asO(N ²). Certain algebraic spectral multigrid methods can be efficiently used for solving the resulting system. Numerical results are presented which show that we have probably found the most effective solver for spectral systems.     

On Quasi-Interpolation with Non-uniformly Distributed Centers on Domains and Manifolds

The paper studies quasi-interpolation by scaled shifts of a smooth and rapidly decaying function. The centers are images of a smooth mapping of the hZⁿ-lattice in R^s, sn, and the scaling parameters are proportional to h. We show that for a large class of generating functions the quasi-interpolants provide high order approximations up to some prescribed accuracy. Although in general the approximants do not converge as h tends to zero, the remaining saturation error is negligible in numerical computations if a scalar parameter is suitably chosen. The lack of convergence is compensated for by a greater flexibility in the choice of generating functions used in numerical methods for solving operator equations.     

Large deviations and the maximum entropy principle for marked point random fields

Summary We establish large deviation principles for the stationary and the individual empirical fields of Poisson, and certain interacting, random fields of marked point particles in ^d . The underlying topologies are induced by a class of not necessarily bounded local functions, and thus finer than the usual weak topologies. Our methods yield further that the limiting behaviour of conditional Poisson distributions, as well as certain distributions of Gibbsian type, is governed by the maximum entropy principle. We also discuss various applications and examples.Supported by the Deutsche Forschungsgemeinschaft     

Downward Sets and their separation and approximation properties

We develop a theory of downward subsets of the space ^I, where I is a finite index set. Downward sets arise as the set of all solutions of a system of inequalities x^I,f_t(x)0 (tT), where T is an arbitrary index set and each f _t (tT) is an increasing function defined on ^I. These sets play an important role in some parts of mathematical economics and game theory. We examine some functions related to a downward set (the distance to this set and the plus-Minkowski gauge of this set, which we introduce here) and study lattices of closed downward sets and of corresponding distance functions. We discuss two kinds of duality for downward sets, based on multiplicative and additive min-type functions, respectively, and corresponding separation properties, and we give some characterizations of best approximations by downward sets. Some links between the multiplicative and additive cases are established.     

Minimum relative error approximations for 1/t

Summary We give explicit solutions to the problem of minimizing the relative error for polynomial approximations to 1/t on arbitrary finite subintervals of (0, ). We give a simple algorithm, using synthetic division, for computing practical representations of the best approximating polynomials. The resulting polynomials also minimize the absolute error in a related functional equation. We show that, for any continuous function with no zeros on the interval of interest, the geometric convergence rates for best absolute error and best relative error approximants must be equal. The approximation polynomials for 1/t are useful for finding suitably precise initial approximations in iterative methods for computing reciprocals on computers.     

Second-order epi-derivatives of integral functionals

Epi-derivatives have many applications in optimization as approached through nonsmooth analysis. In particular, second-order epi-derivatives can be used to obtain optimality conditions and carry out sensitivity analysis. Therefore the existence of second-order epi-derivatives for various classes of functions is a topic of considerable interest. A broad class of composite functions on ⁿ called fully amenable functions (which include general penalty functions composed withC ² mappings, possibly under a constraint qualification) are now known to be twice epi-differentiable. Integral functionals appear widely in problems in infinite-dimensional optimization, yet to date, only integral functionals defined by convex integrands have been shown to be twice epi-differentiable, provided that the integrands are twice epi-differentiable. Here it is shown that integral functionals are twice epi-differentiable even without convexity, provided only that their defining integrands are twice epi-differentiable and satisfy a uniform lower boundedness condition. In particular, integral functionals defined by fully amenable integrands are twice epi-differentiable under mild conditions on the behavior of the integrands.This work was supported in part by the National Science Foundation under grant DMS-9200303.     

Norm bounds for rational matrix functions

Summary If the field of values of a matrixA is contained in the left complex halfplaneH and a functionf mapsH into the unit disc then f(A)₂1 by a theorem of J.v. Neumann. We prove a theorem of this type, only the field of values ofA is used for functions which are absolutely bounded by one in only part ofH. An extension can be used to show norm-stability of single step methods for stiff differential equations. The results are applicable among others to several subdiagonal Padé approximations which are notA-stable.     

Poincaré type inequalities on the discrete cube and in the CAR algebra

We prove L ^p Poincaré inequalities with suitable dimension free constants for functions on the discrete cube {?1, 1} ⁿ . As well known, such inequalities for p an even integer allow to recover an exponential inequality hence the concentration phenomenon first obtained by Bobkov and Götze. We also get inequalities between the L ^p norms of $ \left\vert \nabla f\right\vert We prove L ^p Poincaré inequalities with suitable dimension free constants for functions on the discrete cube {−1, 1} ⁿ . As well known, such inequalities for p an even integer allow to recover an exponential inequality hence the concentration phenomenon first obtained by Bobkov and G?tze. We also get inequalities between the L ^p norms of and moreover L ^p spaces may be replaced by more general ones. Similar results hold true, replacing functions on the cube by matrices in the *-algebra spanned by n fermions and the L ^p norm by the Schatten norm C _p .     

Irrationality of Power Series for Various Number Theoretic Functions

We study formal power series whose coefficients are taken to be a variety of number theoretic functions, such as the Euler, Möbius and divisor functions. We show that these power series are irrational over [X], and we obtain lower bounds on the precision of their rational approximations.     

Convolution kernels based on thin-plate splines

Quasi-interpolation using radial basis functions has become a popular method for constructing approximations to continuous functions in many space dimensions. In this paper we discuss a procedure for generating kernels for quasi-interpolation, using functions which have series expansions involving terms liker logr. It is shown that such functions are suitable if and only if is a positive even integer and the spatial dimension is also even.     

Finite difference methods and their convergence for a class of singular two point boundary value problems

Summary We discuss the construction of three-point finite difference approximations and their convergence for the class of singular two-point boundary value problems: (x y)=f(x,y), y(0)=A, y(1)=B, 0<<1. We first establish a certain identity, based on general (non-uniform) mesh, from which various methods can be derived. To obtain a method having order two for all (0,1), we investigate three possibilities. By employing an appropriate non-uniform mesh over [0,1], we obtain a methodM ₁ based on just one evaluation off. For uniform mesh we obtain two methodsM ₂ andM ₃ each based on three evaluations off. For =0,M ₁ andM ₂ both reduce to the classical second-order method based on one evaluation off. These three methods are investigated, theirO(h ²)-convergence established and illustrated by numerical examples.     

A particle method for first-order symmetric systems

Summary We present and study a conservative particle method of approximation of linear hyperbolic and parabolic systems. This method is based on an extensive use of cut-off functions. We prove its convergence inL ² at the order as soon as the cut-off function belongs toW ^m+1.1.Dedicated to Professor Joachim Nitsche on the occasion of his 60th birthday     

Best trigonometric and bilinear approximations for the Besov classes of functions of many variables

We obtain order estimates for the best trigonometric and bilinear approximations for the classesB _p, ^r of functions of many variables.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 8, pp. 1097–1111, August, 1995.