On the error of compound quadrature formulas forr-convex functions

LetC _m be a compound quadrature formula, i.e.C _m is obtained by dividing the interval of integration [a, b] intom subintervals of equal length, and applying the same quadrature formulaQ _n to every subinterval. LetR _m be the corresponding error functional. Iff ^(r) > 0 impliesR _m [f] > 0 (orR _m [f] < 0),=" then=" we=" say=">C _m is positive definite (or negative definite, respectively) of orderr. This is the case for most of the well-known quadrature formulas. The assumption thatf ^(r) > 0 may be weakened to the requirement that all divided differences of orderr off are non-negative. Thenf is calledr-convex. Now letC _m be positive definite or negative definite of orderr, and letf be continuous andr-convex. We prove the following direct and inverse theorems for the errorR _m [f], where , denotes the modulus of continuity of orderr:

Stable in situ sorting and minimum data movement

In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg^(k+1) n+kn) comparisons (lg^(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation.     

New general guidance method in constrained optimal control,part 2: Application to space shuttle guidance

The application and the performance of the neighboring optimal feedback scheme presented in Part 1 of this paper is demonstrated for the heating-constrained cross-range maximization problem of a space-shuttle-orbiter-type vehicle. This problem contains five state variables, two control variables, and a state variable inequality constraint of order zero.This research was supported in part by the Deutsche Forschungsgemeinschaft under the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung.The authors wish to express their sincere and grateful appreciation to Professor Roland Bulirsch who encouraged this work.     

Nonlinear stability and convergence of finite-difference methods for the “good” Boussinesq equation

Summary The good Boussinesq equationu _tt =–u _xxxx +u _xx +(u ²) _xx has recently been found to possess an interesting soliton-interaction mechanism. In this paper we study the nonlinear stability and the convergence of some simple finite-difference schemes for the numerical solution of problems involving the good Boussinesq equation. Numerical experimentas are also reported.     

Gaussian collocation via defect correction

Summary For the numerical integration of boundary value problems for first order ordinary differential systems, collocation on Gaussian points is known to provide a powerful method. In this paper we introduce a defect correction method for the iterative solution of such high order collocation equations. The method uses the trapezoidal scheme as the basic discretization and an adapted form of the collocation equations for defect evaluation. The error analysis is based on estimates of the contractive power of the defect correction iteration. It is shown that the iteration producesO(h ²), convergence rates for smooth starting vectors. A new result is that the iteration damps all kind of errors, so that it can also handle non-smooth starting vectors successfully.     

Tracking poles and representing Hankel operators directly from data

Summary We propose and analyse a method of estimating the poles near the unit circleT of a functionG whose values are given at a grid of points onT: we give an algorithm for performing this estimation and prove a convergence theorem. The method is to identify the phase for an estimate by considering the peaks of the absolute value ofG onT, and then to estimate the modulus by seeking a bestL ² fit toG over a small arc by a first order rational function. These pole estimates lead to the construction of a basis ofL ² which is well suited to the numerical representation of the Hankel operator with symbolG and thereby to the numerical solution of the Nehari problem (computing the bestH , analytic, approximation toG relative to theL norm), as analysed in [HY]. We present the results of numerical tests of these algorithms.Partially supported by grants from the AFOSR and NSF     

Delaunay graphs are almost as good as complete graphs

LetS be any set ofN points in the plane and let DT(S) be the graph of the Delaunay triangulation ofS. For all pointsa andb ofS, letd(a, b) be the Euclidean distance froma tob and let DT(a, b) be the length of the shortest path in DT(S) froma tob. We show that there is a constantc (≤((1+√5)/2) π≈5.08) independent ofS andN such that $$\frac{{DT(a,b)}}{{d(a,b)}}< c.$$      

On the long term behavior of some finite particle systems

Summary We consider the problem of comparing large finite and infinite systems with locally interacting components, and present a general comparison scheme for the case when the infinite system is nonergodic. We show that this scheme holds for some specific models. One of these is critical branching random walk onZ ^d . Let _t denote this system, and let _t ^N denote a finite version of _t defined on the torus [–N,N] ^d Z ^d . Ford3 we prove that for stationary, shift ergodic initial measures with density , that ifT(N) andT(N)/(2N+1)^d s[0,] asN, then {v }, 0 is the set of extremal invariant measures for the infinite system _t andQ _s is the transition function of Feller's branching diffusion. We prove several extensions and refinements of this result. The other systems we consider are the voter model and the contact process.Work supported in part by the National Science Foundation under Grant DMS-8802055, by the U.S. Army Research Office through the Mathematical Sciences Institute at Cornell University and by the Deutsche Forschungsgemeinschaft through the SFB 123 at the Universität Heidelberg     

Variations on the theme of repeated distances

We give an asymptotically sharp estimate for the error term of the maximum number of unit distances determined byn points in ^{d, d}4. We also give asymptotically tight upper bounds on the total number of occurrences of the favourite distances fromn points in ^{d, d}4. Related results are proved for distances determined byn disjoint compact convex sets in ².At the time this paper was written, both authors were visiting the Technion — Israel Institute of Technology.