Error bounds for spatial discretization and waveform relaxation applied to parabolic functional differential equations

The process of semi-discretization and waveform relaxation are applied to general nonlinear parabolic functional differential equations. Two new theorems are presented, which extend and improve some of the classical results. The first of these theorems gives an upper bound for the norm of the error of finite difference semi-discretization. This upper bound is sharper than the classical error bound. The second of these theorems gives an upper bound for the norm of the error, which is caused by both semi-discretization and waveform relaxation. The focus in the paper is on estimating this error directly without using the upper bound for the error, which is caused by the process of semi-discretization and the upper bound for the error, which is caused by the waveform relaxation method. Such estimating gives sharper error bound than the bound, which is obtained by estimating both errors separately.     

Multiprocessor scheduling: combining LPT and MULTIFIT

We consider the problem of scheduling a set of n independent jobs on m identical machines with the objective of minimizing the total finishing time. We combine the two most popular algorithms, LTP and MULTIFIT, to form a new one. MULTIFIT is well known to have better error bound than LPT with the price paid in running time. Although MULTIFIT provides a better error bound, in many cases LPT still can yield better results. This motivates the development of this new combined algorithm, which uses the result of LPT as the incumbent and then applies MULTIFIT with fewer iterations. The performance of this combined algorithm is better than that of LPT because it uses LPT as an incumbent. The error bound of this combined algorithm is never worse than that of MULTIFIT. For example, the error bound of implementing this combined algorithm to the two-processor problem is , compared to the error bound of in MULTIFIT. Empirical results of the comparison for schedules obtained by the combined algorithm, MULTIFIT and LPT are also provided.     

A sharper global error bound for the generalized linear complementarity problem over a polyhedral cone under weaker conditions

In this paper, we further consider the global error bound for the generalized linear complementarity problem over a polyhedral cone (GLCP). By introducing a new technique, we establish a sharper global error bound for the GLCP under weaker conditions, which greatly improve the existing error bounds for this problem.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

A proof of Niederreiter's conjecture concerning error bounds for quasi-Monte Carlo integration

In this paper Niederreiter's error bound for quasi-Monte Carlo integration on bounded Jordan measurable subsets of the k-dimensional unit cube E^k is improved. The new error bound, which has been conjectured by Niederreiter, reduces to the corresponding error bound given by Zaremba in case of integration on convex subsets of E^k.     

Further Discussion on the Error Bound for Generalized Linear Complementarity Problem over a Polyhedral Cone

In this paper, we consider the global error bound for the generalized linear complementarity problem over a polyhedral cone (GLCP). Based on the new transformation of the problem, we establish its global error bound under milder conditions, which improves the result obtained by Sun and Wang (2009) for GLCP by weakening the assumption.     

Computation of Error Bounds for P-matrix Linear Complementarity Problems

We give new error bounds for the linear complementarity problem where the involved matrix is a P-matrix. Computation of rigorous error bounds can be turned into a P-matrix linear interval system. Moreover, for the involved matrix being an H-matrix with positive diagonals, an error bound can be found by solving a linear system of equations, which is sharper than the Mathias-Pang error bound. Preliminary numerical results show that the proposed error bound is efficient for verifying accuracy of approximate solutions. This work is partly supported by a Grant-in-Aid from Japan Society for the Promotion of Science.     

Error bounds for vector-valued functions: Necessary and sufficient conditions

In this paper, we attempt to extend the definition and existing local error bound criteria to vector-valued functions, or more generally, to functions taking values in a normed linear space. Some new derivative-like objects (slopes and subdifferentials) are introduced and a general classification scheme of error bound criteria is presented.     

New Uniform Parametric Error Bounds

A uniform parametric error bound is a uniform error estimate for feasible solutions of a family of parametric mathematical programming problems. It has been proven useful in exact penalty formulation for bilevel programming problems. In this paper, we derive new sufficient conditions for the existence of uniform parametric error bounds.     

Removing logarithms in Poisson approximation to the partial sum process of a Markov chain

He and Xia (1997, Stochastic Processes Appl. 68, pp. 101–111) gave some error bounds for a Wasserstein distance between the distributions of the partial sum process of a Markov chain and a Poisson point process on the positive half-line. However, all these bounds increase logarithmically with the mean of the Poisson point process. In this paper, using the coupling method and a general deep result for estimating the errors of Poisson process approximation in Brown and Xia (2001, Ann. Probab. 29, pp. 1373–1403), we give a new error bound for the above Wasserstein distance. In contrast to the previous results of He and Xia (1997), our new error bound has no logarithm anymore and it is bounded and asymptotically remains constant as the mean increases.     

Error Bound for Bernstein-Bézier Triangular Approximation

Based upon a new error bound for the linear interpolant to a function defined on a triangle and having continuous partial derivatives of second order, the related error bound for n-th Bernstein triangular approximation is obtained. The order of approximation is 1/n.     

基于块循环矩阵的对称张量的最佳秩-1逼近

对称张量的最佳秩-1问题是张量研究中非常重要的部分.首先,基于三阶张量的块循环矩阵,提出了求解对称张量最佳秩-1逼近问题的一个新方法.其次,针对求解对称张量的最佳秩-1逼近方法,给出了对称张量的最佳秩-1逼近不变性的一个充要条件,以及逼近误差上界的估计.最后,数值算例表明了上述方法的可行性和误差上界的正确性.     

A rational approximate solution for generalized pantograph‐delay differential equations

In this paper, a new rational approximation based on a rational interpolation and collocation method is proposed for the solutions of generalized pantograph equations. A comprehensive error analysis is provided. The first part of the error analysis gives an upper bound for the absolute error. The second part is based on residual error procedure that estimates the absolute error. Some numerical examples are given to illustrate the method. The theoretical results support the numerical results. Copyright © 2015 John Wiley & Sons, Ltd.     

A Levenberg-Marquardt method with approximate projections

The projected Levenberg-Marquardt method for the solution of a system of equations with convex constraints is known to converge locally quadratically to a possibly nonisolated solution if a certain error bound condition holds. This condition turns out to be quite strong since it implies that the solution sets of the constrained and of the unconstrained system are locally the same. Under a pair of more reasonable error bound conditions this paper proves R-linear convergence of a Levenberg-Marquardt method with approximate projections. In this way, computationally expensive projections can be avoided. The new method is also applicable if there are nonsmooth constraints having subgradients. Moreover, the projected Levenberg-Marquardt method is a special case of the new method and shares its R-linear convergence.     

Superconvergence analysis and error expansion for the Wilson nonconforming finite element

Summary. In this paper the Wilson nonconforming finite element is considered for solving a class of two-dimensional second-order elliptic boundary value problems. Superconvergence estimates and error expansions are obtained for both uniform and non-uniform rectangular meshes. A new lower bound of the error shows that the usual error estimates are optimal. Finally a discussion on the error behaviour in negative norms shows that there is generally no improvement in the order by going to weaker norms. Received July 5, 1993     

最小二乘估计精度及其界限

Puntanen[1]提出用均方误差来度量最小二乘估计的精度,以后Styan[2],Rao[3]等相继讨论了这种精度及其界限.本文考虑采用广义方差,从而引进了一种新的最小二乘估计精度的度量并讨论了它的界.     

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.     

A note on the residual type a posteriori error estimates for finite element eigenpairs of nonsymmetric elliptic eigenvalue problems

In this paper we study the residual type a posteriori error estimates for general elliptic (not necessarily symmetric) eigenvalue problems. We present estimates for approximations of semisimple eigenvalues and associated eigenvectors. In particular, we obtain the following new results: 1) An error representation formula which we use to reduce the analysis of the eigenvalue problem to the analysis of the associated source problem; 2) A local lower bound for the error of an approximate finite element eigenfunction in a neighborhood of a given mesh element T.     

An Asymptotic Expansion of the Double Gamma Function

The Barnes double gamma function G(z) is considered for large argument z. A new integral representation is obtained for log G(z). An asymptotic expansion in decreasing powers of z and uniformly valid for |Arg z|<π is derived from this integral. The expansion is accompanied by an error bound at any order of the approximation. Numerical experiments show that this bound is very accurate for real z. The accuracy of the error bound decreases for increasing Arg z.     

One Approach to the Comparison of Error Bounds at a Point and on a Set in the Solution of Ill-Posed Problems

The approximate solution of ill-posed problems by the regularization method always involves the issue of estimating the error. It is a common practice to use uniform bounds on the whole class of well-posedness in terms of the modulus of continuity of the inverse operator on this class. Local error bounds, which are also called error bounds at a point, have been studied much less. Since the solution of a real-life ill-posed problem is unique, an error bound obtained on the whole class of well-posedness roughens to a great extent the true error bound. In the present paper, we study the difference between error bounds on the class of well-posedness and error bounds at a point for a special class of ill-posed problems. Assuming that the exact solution is a piecewise smooth function, we prove that an error bound at a point is infinitely smaller than the exact bound on the class of well-posedness.