Automatic Forward Error Analysis for Floating Point Algorithms

We investigate absolute and relative error bounds for floating point calculations determined by means of sequences of instructions (as, for example, given by a computer program). We get rigorous error bounds on the round-off or generated error due to the actual machine floating point operations, as well as the propagated error from one sequence to the next in a very convenient way by the computer itself. The results stated in the theorems can be used to implement software tools for the automatic computation of a priori worst case error bounds for floating point computations. These automatically computed bounds are valid simultaneously for all data vectors varying in the domain specified and their corresponding machine vectors fulfilling a maximum prescribed error bound.With great success we have used our method in the past to implement a fast interval library for elementary functions called FI_LIB [12]. Further numerical examples often show a high quality of the computed a priori bounds.     

PAC-Bayesian Compression Bounds on the Prediction Error of Learning Algorithms for Classification

We consider bounds on the prediction error of classification algorithms based on sample compression. We refine the notion of a compression scheme to distinguish permutation and repetition invariant and non-permutation and repetition invariant compression schemes leading to different prediction error bounds. Also, we extend known results on compression to the case of non-zero empirical risk.We provide bounds on the prediction error of classifiers returned by mistake-driven online learning algorithms by interpreting mistake bounds as bounds on the size of the respective compression scheme of the algorithm. This leads to a bound on the prediction error of perceptron solutions that depends on the margin a support vector machine would achieve on the same training sample.Furthermore, using the property of compression we derive bounds on the average prediction error of kernel classifiers in the PAC-Bayesian framework. These bounds assume a prior measure over the expansion coefficients in the data-dependent kernel expansion and bound the average prediction error uniformly over subsets of the space of expansion coefficients.Editor Shai Ben-David     

OBE算法对误差界低估的鲁棒性

研究了具有未知但有界(UBB)误差系统辨识的最优定界椭球(OBE)算法对误差界 低估的鲁棒性.证明了在一定的条件下,即使误差界低估,任何OBE算法都能保持其收敛性. 这一结论可用于具有UBB误差的实际系统参数估计中,以期获得不太保守的结果.     

Error bounds for initial value problems by optimization

The computation of the error bounds for approximate solutions of initial value problems for ordinary differential equations has a long and successful history. This paper presents a new scheme to compute such bounds with uncertain initial conditions using preconditioned defect estimates and optimization techniques. These bounds are based on the newly developed concept of conditional differential inequalities. The scheme is implemented in MATLAB and AMPL. The resulting enclosures are compared with the packages VALENCIA-IVP, VNODE-LP and VSPODE for bounding solutions of ODEs. The current prototype uses heuristics to solve the global optimization subproblems. Hence the bounds obtained in the numerical experiments are not fully rigorous. The latter can be achieved by using rigorous global optimization and rounding error control, but the effect on the bounds is likely to be marginal only.     

16 bit量化误差对正弦参数拟合影响的误差界

为了定量评估量化采样序列对四参数正弦拟合结果影响的误差规律,针对16 bit量化对四参数正弦拟合带来的影响,分别在有效位数、幅度、频率、初始相位和直流分量五项参数上进行了拟合误差界的搜索。选取的条件变量分别是幅度、序列所含波形的周波数、初始相位、直流分量以及序列数据点数。以两两联动的双条件组合方式进行误差界搜索,获得了各项参数的误差界随不同条件变化而变化的曲线规律,筛分出了显著影响量和不显著影响量,以及明确的误差上界和下界。以往的研究仅使用正态随机噪声方式表征其谐波失真以外的误差要素,本文揭示了量化误差影响的周期性特征,并以曲线包络方式给出了量化误差影响的误差界。量化误差对四参数拟合影响的误差界,可用于不确定度估计,以及测量条件选择。     

Error bounds for Loop subdivision surfaces

In this paper, we obtain the error bounds on the distance between a Loop subdivision surface and its control mesh. Both local and global bounds are derived by means of computing and analysing the control meshes with two rounds of refinement directly. The bounds can be expressed with the maximum edge length of all triangles in the initial control mesh. Our results can be used as posterior estimates and also can be used to predict the subdivision depth for any given tolerance.     

Error bounds for polynomial tensor product interpolation

We provide estimates for the maximum error of polynomial tensor product interpolation on regular grids in ${\mathbb{R}^d}$ . The set of partial derivatives required to form these bounds depends on the clustering of interpolation nodes. Also bounds on the partial derivatives of the error are derived.     

Error estimation in the integration of ordinary differential equations

Linear initial value problems, particularly involving first order differential equations, can be transformed into systems of higher order and treated as boundary value problems. Finite difference analogues considered for obtaining approximate solutions of these boundary value problems are proved to be fourth order convergent processes, by deriving considerable sharper bounds for the discretization error. Numerical examples are given to demonstrate the usefulness of our error bounds.     

Error bounds for Newton refinement of solutions to algebraic riccati equations

Recent error bounds derived from the Schur method of solving algebraic Riccati equations (ARE) complement residual error bounds associated with Newton refinement of approximate solutions. These approaches to the problem of error estimation not only work well together but also represent the first computable error bounds for the solution of Riccati equations. In this paper the closed-loop Lyapunov operator is seen to be central to the question of whether Newton refinement will improve an approximate solution (region of convergence), as well as providing a means of bounding the actual error in terms of the residual error. In turn, both of these issues are related to the condition of the ARE and the damping of the associated closed-loop dynamical system. Numerical results are given for seven problems taken from the literature. This research was supported by the National Science Foundation (and AFOSR) under Grant No. ECS87-18897 and the National Science Foundation under Grant No. DMS88-00817.     

Error estimates for Gauss-Chebyshev and Clenshaw Curtis quadrature formulas

For functionsf analytic in a circle we obtain bounds for the Chebyshev-Fourier coefficients off. These results are then used to obtain bounds for the errors of Gauss-Chebyshev quadratures, and the quadrature formula of Clenshaw and Curtis. Two examples are given to illustrate the error bounds.     

传递函数估计误差的硬界及其渐近性质

本文讨论带遗忘因子的最小二乘法估计传递函数的误差硬界及其渐近性质.在噪声有界 等一定假定下,当样本个数趋向无限时,误差硬界收敛于复平面内的一个圆.     

Error and complexity of random walk Monte Carlo radiosity

The author studies the error and complexity of the discrete random walk Monte Carlo technique for radiosity, using both the shooting and gathering methods. The author shows that the shooting method exhibits a lower complexity than the gathering one, and under some constraints, it has a linear complexity. This is an improvement over a previous result that pointed to an O(n log n) complexity. The author gives and compares three unbiased estimators for each method, and obtains closed forms and bounds for their variances. The author also bounds the expected value of the mean square error (MSE). Some of the results obtained are also shown to be valid for the nondiscrete gathering case. The author also gives bounds for the variances and MSE for the infinite path length estimators; these bounds might be useful in the study of biased estimators resulting from cutting off the infinite path     

Two-Mode Adaptive Fuzzy Control With Approximation Error Estimator

In this paper, we propose a two-mode adaptive fuzzy controller with approximation error estimator. In the learning mode, the controller employs some modified adaptive laws to tune the fuzzy system parameters and an approximation error estimator to compensate for the inherent approximation error. In the operating mode, the fuzzy system parameters are fixed, only the estimator is updated online. Mathematically, we show that the closed-loop system is stable in the sense that all the variables are bounded in both modes. We also establish mathematical bounds on the tracking error, state vector, control signal and the RMS error. Using these bounds, we show that controller's design parameters can be chosen to achieve desired control performance. After that, an algorithm to automatically switch the controller between two modes is presented. Finally, simulation studies of an inverted pendulum system and a Chua's chaotic circuit demonstrate the usefulness of the proposed controller.     

A Posteriori Error Estimators for a Class of Variational Inequalities

In this paper, we present an a posteriori error analysis for the finite element approximation of a variational inequality. We derive a posteriori error estimators of residual type, which are shown to provide upper bounds on the discretization error for a class of variational inequalities provided the solutions are sufficiently regular. Furthermore we derive sharp a posteriori error estimators with both lower and upper error bounds for a subclass of the obstacle problem which are frequently met in many physical models. For sufficiently regular solutions, these estimates are shown to be equivalent to the discretization error in an energy type norm. Our numerical tests show that these sharp error estimators are both reliable and efficient in guiding mesh adaptivity for computing the free boundaries.     

A Computer Oriented Approach to Get Sharp Reliable Error Bounds

We present interval methods to get reliable a priori error bounds for the machine evaluation of algorithms implementing some mathematical expression. The term expression not only means simple arithmetical expressions but also more complex program parts including loops or recursive structures (e.g. a complete elementary function routine).We sketch a method that can be used to get an upper bound for the approximation error of a polynomial or a rational approximation. We also discuss a method to compute worst case a priori error estimates for arbitrary IEEE double floating-point computations. Our theoretical results lead to reliable and easy to use public domain software tools. The application of these tools to an accurate table method shows that error bounds of high quality can be derived.     

WSNs中带有置信度和误差限的序列匹配算法

在分析WSNs数据特点的基础上,提出WSNs中基于置信度和误差限的序列匹配算法.定义数据序列的距离和基于置信度和误差限的匹配,并利用距离计算不同匹配度的节点.采用自底向上的线性拟合对数据进行处理解决数据的不对齐性,丢失性等对序列匹配带来的问题.使用真实传感器网络数据对算法进行测试,分析试验结果证实采用基于置信度和误差限的序列匹配算法的WSNs比普通WSNs更加节约能耗.     

Verified Error Bounds for Linear Systems Through the Lanczos Process

We use verified computations and the Lanczos process to obtain guaranteed lower and upper bounds on the 2-norm and the energy-norm error of an approximate solution to a symmetric positive definite linear system. The upper bounds require the a priori knowledge of a lower bound on the smallest eigenvalue.     

Computation of Sharp Rigorous Componentwise Error Bounds for the Approximate Solutions of Systems of Linear Equations

This paper is concerned with the problem of verifying the accuracy of approximate solutions of systems of linear equations. Recently, fast algorithms for calculating guaranteed error bounds of computed solutions of systems of linear equations have been proposed using the rounding mode controlled verification method and the residual iterative verification method. In this paper, a new verification method for systems of linear equations is proposed. Using this verification method, componentwise verified error bounds of approximate solutions of systems of linear equations can be calculated. Numerical results are presented to illustrate that it is possible to get very sharp error bounds of computed solutions of systems of linear equations whose coefficient matrices are symmetric and positive definite.     

Bh序列和Magnitude错误标准下m元纠错码构造

文献对Bh序列和Magnitude错误标准下m元t-sEC/AUED码的关系进行了讨论,在此基础上提出了一种Magnitude错误标准下m元可纠t个对称错的纠错码的构造方法,并相应地给出了可纠t个对称错的纠错码码字个数的下界。