Worst-case analysis of demand point aggregation for the Euclidean p-median problem

Solving large-scale p-median problems is usually time consuming. People often aggregate the demand points in a large-scale p-median problem to reduce its problem size and make it easier to solve. Most traditional research on demand point aggregation is either experimental or assuming uniformly distributed demand points in analytical studies. In this paper, we study demand point aggregation for planar p-median problem when demand points are arbitrarily distributed. Efficient demand aggregation approaches are proposed with the corresponding attainable worst-case aggregation error bounds measured. We demonstrate that these demand aggregation approaches introduce smaller worst-case aggregation error bounds than that of the honeycomb heuristic [Papadimitriou, C.H., 1981. Worst-case and probabilistic analysis of a geometric location problem. SIAM Journal on Computing 10, 542–557] when demand points are arbitrarily distributed. We also conduct numerical experiments to show their effectiveness.     

Global error bound for convex inclusion problems

The existence of global error bound for convex inclusion problems is discussed in this paper, including pointwise global error bound and uniform global error bound. The existence of uniform global error bound has been carefully studied in Burke and Tseng (SIAM J. Optim. 6(2), 265–282, 1996) which unifies and extends many existing results. Our results on the uniform global error bound (see Theorem 3.2) generalize Theorem 9 in Burke and Tseng (1996) by weakening the constraint qualification and by widening the varying range of the parameter. As an application, the existence of global error bound for convex multifunctions is also discussed.     

New error bound for linear complementarity problems for B-matrices

A new error bound for the linear complementarity problem is obtained when the involved matrix is a B-matrix. This bound improves existing results. Finally, two numerical examples are also given to show that the bound is better than some previous results.     

Recursive error correction for general Reed-Muller codes

Reed-Muller (RM) codes of growing length n and distance d are considered over a binary symmetric channel. A recursive decoding algorithm is designed that has complexity of order nlogn and corrects most error patterns of weight (dlnd)/2. The presented algorithm outperforms other algorithms with nonexponential decoding complexity, which are known for RM codes. We evaluate code performance using a new probabilistic technique that disintegrates decoding into a sequence of recursive steps. This allows us to define the most error-prone information symbols and find the highest transition error probability p, which yields a vanishing output error probability on long codes.     

New improved error bounds for the linear complementarity problem

New local and global error bounds are given for both nonmonotone and monotone linear complementarity problems. Comparisons of various residuals used in these error bounds are given. A possible candidate for a best error bound emerges from our comparisons as the sum of two natural residuals.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.     

Interior error estimate for periodic homogenization

The aim of this Note is to give interior error estimates for problems in periodic homogenization, by using the periodic unfolding method. The interior error estimates are obtained by transposition without any supplementary hypothesis of regularity on correctors. This error is of order ?. To cite this article: G. Griso, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Estimation of prediction error variance

This note considers an estimate of the variance of the prediction error for a normal stationary time series based on the periodogram. It is shown that as T → ∞, the estimate converges almost surely to σ², the variance of the prediction error for the best linear predictor. By applying a result of Hannan [2] it thus follows that if in fitting an autoregression to the data x(1),…,x(T) the order k is greatly overstated, then the resultant estimate σ²_k of σ² will be biased downward.     

A posteriori boundary element error estimation

An a posteriori error estimator is presented for the boundary element method in a general framework. It is obtained by solving local residual problems for which a local concept is introduced to accommodate the fact that integral operators are nonlocal operators. The estimator is shown to have an upper and a lower bound by the constant multiples of the exact error in the energy norm for Symm's and hypersingular integral equations. Numerical results are also given to demonstrate the effectiveness of the estimator for these equations. It can be used for adaptive h,p, and hp methods.     

A practical error formula for multivariate rational interpolation and approximation

We consider exact and approximate multivariate interpolation of a function f(x ₁?,?.?.?.?,?x _d ) by a rational function p _n,m /q _n,m (x ₁?,?.?.?.?,?x _d ) and develop an error formula for the difference f???p _n,m /q _n,m . The similarity with a well-known univariate formula for the error in rational interpolation is striking. Exact interpolation is through point values for f and approximate interpolation is through intervals bounding f. The latter allows for some measurement error on the function values, which is controlled and limited by the nature of the interval data. To achieve this result we make use of an error formula obtained for multivariate polynomial interpolation, which we first present in a more general form. The practical usefulness of the error formula in multivariate rational interpolation is illustrated by means of a 4-dimensional example, which is only one of the several problems we tested it on.     

A posteriori error estimation of residual type for anisotropic diffusion-convection-reaction problems

This paper presents a robust a posteriori residual error estimator for diffusion-convection-reaction problems with anisotropic diffusion, approximated by a SUPG finite element method on isotropic or anisotropic meshes in R^d, d=2 or 3. The equivalence between the energy norm of the error and the residual error estimator is proved. Numerical tests confirm the theoretical results.     

On the Error Estimate of the Harmonic B_z Algorithm in MREIT from Noisy Magnetic Flux Field

Magnetic resonance electrical impedance tomography(MREIT, for short) is a new medical imaging technique developed recently to visualize the cross-section conductivity of biologic tissues. A new MREIT image reconstruction method called harmonic Bz algorithm was proposed in 2002 with the measurement of Bz that is a single component of an induced magnetic flux density subject to an injection current. The key idea is to solve a nonlinear integral equation by some iteration process. This paper deals with the convergence analysis as well as the error estimate for noisy input data Bz, which is the practical situation for MREIT. By analyzing the iteration process containing the Laplacian operation on the input magnetic field rigorously, the authors give the error estimate for the iterative solution in terms of the noisy level δ and the regularizing scheme for determiningΔBz approximately from the noisy input data. The regularizing scheme for computing the Laplacian from noisy input data is proposed with error analysis. Our results provide both the theoretical basis and the implementable scheme for evaluating the reconstruction accuracy using harmonic Bz algorithm with practical measurement data containing noise.     

Means that minimize relative error,and an associated integral equation

Determinations are made of the means that minimize various relative errors in the sense that the harmonic mean of a and b minimizes the traditional relative error on [a, b]. The general problem for averaged relative error leads to a nonlinear integral equation for which we prove existence and uniqueness results, as well as constructive solution procedures. The inverse problem of finding the measure of relative error corresponding to a given mean is also analyzed in detail. These studies shed light on both new and previously known inequalities for specific means.     

A posteriori residual error estimation of a cell-centered finite volume method

We present an a posteriori residual error estimator for the Laplace equation using a cell-centered finite volume method in the plane. For that purpose we associate to the approximated solution a kind of Morley interpolant. The error is then the difference between the exact solution and this Morley interpolant. The residual error estimator is based on the jump of normal and tangential derivatives of the Morley interpolant. The equivalence between the discrete H¹-seminorm of the error and the residual error estimator is proved. The proof of the upper error bound uses the Helmholtz decomposition of the broken gradient of the error and some quasi-orthogonality relations. To cite this article: S. Nicaise, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

On the error bounds of nonconforming finite elements

We prove that the error estimates of a large class of nonconforming finite elements are dominated by their approximation errors, which means that the well-known Cea's lemma is still valid for these nonconforming finite element methods. Furthermore, we derive the error estimates in both energy and L2 norms under the regularity assumption u ∈ H1+s(Ω) with any s 0. The extensions to other related problems are possible.     

An error estimate for least squares approximation

Upper and lower error bounds are obtained for the error of the bestL ₂ polynomial approximation of degreen for a function belonging toC ⁿ⁺¹ [?1, 1].     

Quadrature error of the load vector in the finite element method

We analyze the error in thep version of the of the finite element method when the effect of the quadrature error is taken in the load vector. We briefly study some results on theH ¹ norm error and present some new results for the error in theL ₂ norm. We investigate the quadrature error due to the numerical integration of the right hand side We present theoretical and computational examples showing the sharpness of our results.     

New error bounds for the penalty method and extrapolation

New error bounds are obtained for the Babu?ka penalty method which justify the use of extrapolation. For the problemΔu=f in Ω,u=g on ?Ω we show that, for a particular choice of boundary weight, repeated extrapolation yields a quasioptimal approximate solution. For example, the error in the second extrapolate (using cubic spline approximants) isO (h ³) when measured in the energy norm. Nearly optimalL ₂ error estimates are also obtained.     

Intermediate error estimates

Let R[f] be the remainder of some approximation method, having estimates of the form f;R[f]f; ρ_i ; f⁽ⁱ⁾ for i = 0,…, r. In many cases, ρ₀ and ρ_r are known, but not the intermediate error constants ρ₁,…,ρ_r−1. For periodic functions, Ligun (1973) has obtained an estimate for these intermediate error constants by ρ₀ and ρ_r. In this paper, we show that this holds in the nonperiodic case, too. For instance, the estimates obtained can be applied to the error of polynomial or spline approximation and interpolation, or to numerical integration and differentiation.     

On the construction of error estimators for implicit Runge-Kutta methods

For implicit Runge-Kutta methods intended for stiff ODEs or DAEs, it is often difficult to embed a local error estimating method which gives realistic error estimates for stiff/algebraic components. If the embedded method's stability function is unbounded at z=∞, stiff error components are grossly overestimated. In practice, some codes ‘improve’ such inadequate error estimates by premultiplying the estimate by a ‘filter’ matrix which damps or removes the large, stiff error components. Although improving computational performance, this technique is somewhat arbitrary and lacks a sound theoretical backing. In this scientific note we resolve this problem by introducing an implicit error estimator. It has the desired properties for stiff/algebraic components without invoking artificial improvements. The error estimator contains a free parameter which determines the magnitude of the error, and we show how this parameter is to be selected on the basis of method properties. The construction principles for the error estimator can be adapted to all implicit Runge-Kutta methods, and a better agreement between actual and estimated errors is achieved, resulting in better performance.