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 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.     

Error bounds for the method of alternating projections

Given a collection of closed subspaces of a Hilbert space, the method of alternating projections produces a sequence which converges to the orthogonal projection onto the intersection of the subspaces. A large class of problems in medical and geophysical image reconstruction can be solved using this method. A sharp error bound will enable the userto estimate accurately the number of iterations necessary to achieve a desired relative error. We obtain the sharpest possible upper bound for the case of two subspaces, and the sharpest known upper bound for more than two subspaces. This work was supported by the Office of Naval Research under Contract N00014-85-K-0255.     

Error bounds for direct and composite cubature formulae-II

In this part II, narrow cubature error bounds given by Lether are used and made suitable for comparing direct and composite integration techniques for two-dimensional Gauss-Legendre formulae. The results we obtain support the conclusion that in many cases composite formulae turn out to be preferable in comparison with direct ones.

---

Sommario In questa parte II vengono utilizzati limiti di errore di cubatura particolarmente stringenti dati da Lether, rendendoli adatti al confronto fra tecniche dirette e composte per formule di integrazione bidimensionale di Gauss-Legendre. I risultati confermano che, contrariamente ad una opinione abbastanza diffusa, le formule composte possono, in molti casi, risultare preferibili alle dirette.

---

---

This work has been done within the GNAFA-CNR research activity.     

Error bounds for complementarity problems with tridiagonal nonlinear functions

In this paper we consider the complementarity problem NCP(f) with f(x) = Mx + φ(x), where M ∈ R ^n×n is a real matrix and φ is a so-called tridiagonal (nonlinear) mapping. This problem occurs, for example, if certain classes of free boundary problems are discretized. We compute error bounds for approximations \({\hat x}\) to a solution x* of the discretized problems. The error bounds are improved by an iterative method and can be made arbitrarily small. The ideas are illustrated by numerical experiments.     

Error bounds for direct and composite cubature formulae—I

In this paper direct and composite two dimensional integration formulae are compared, and conditions are given under which certain error bounds turn out to be better for either one or the other approach.

---

Sommario In questo articolo vengono confrontate formule dirette e formule composte di integrazione numerica in due dimensioni, determinando condizioni sotto cui risultano migliori certi limiti di errore per l'uno o per l'altro approccio.

---

---

This work has been done within the GNAFA-CNR research activity.     

Error bounds of multi-graph regularized semi-supervised classification

In this paper, we investigate the generalization performance of the multi-graph regularized semi-supervised classification algorithm associated with the hinge loss. We provide estimates for the excess misclassification error of multi-graph regularized classifiers and show the relations between the generalization performance and the structural invariants of data graphs. Experiments performed on real database demonstrate the effectiveness of our theoretical analysis.     

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 bounds in the averaging of hybrid systems

The authors analyze the error introduced by the averaging of hybrid systems. These systems involve linear systems which can take a number of different realizations based on the state of an underlying finite state process. The averaging technique (based on a formula from Lie algebras known as the Backer-Campbell-Hausdorff (BCH) formula) provides a single system matrix as an approximation to the hybrid system. The two errors discussed are: (1) the error induced by the truncation of the BCH series expansion and (2) the error between the actual hybrid system and its average. A simple sufficient stability test is proposed to check the asymptotic behavior of this error. In addition, conditions are derived that allow the use of state feedback instead of averaging to arrive at a time-invariant system matrix     

Error bounds for finite step approximations for solving infinite horizon controlled Markov set-chains

This note considers finite-step approximations for solving an infinite-horizon controlled Markov set-chain problem with finite state and action spaces. We develop a value-iteration type algorithm based on the optimality equation developed by Kurano et al. and analyze an error bound relative to the optimal value that satisfies the optimality equation from the successive approximation. We further analyze an error bound of the approximate control policy defined from a finite-step approximate value by applying the value-iteration type algorithm.     

Error probability bounds for nuclear detection: Improving accuracy through controlled mobility

A collection of static and mobile radiation sensors is tasked with deciding, within a fixed time interval, whether a moving target carries radioactive material. Formally, this is a problem of detecting weak time-inhomogeneous Poisson signals (target radiation) concealed in another Poisson signal (naturally occurring background radiation). Each sensor locally processes its observations to form a likelihood ratio, which is transmitted once—at the end of the decision interval—to a fusion center. The latter combines the transmitted information to optimally (in the Neyman–Pearson sense) decide whether the measurements contain a radiation signal, or just noise. We provide a set of analytically derived upper bounds for the probabilities of false alarm and missed detection, which are used to design threshold tests without the need for computationally intensive Monte Carlo simulations. These analytical bounds couple the physical quantities of interest to facilitate planning the motion of the mobile sensors for minimizing the probability of missed detection. The network reconfigures itself in response to the target motion, to allow more accurate collective decisions within the given time interval. The approach is illustrated in numerical simulations, and its effectiveness demonstrated in experiments that emulate the statistics of nuclear emissions using a pulsed laser.     

Ensembles of jittered association rule classifiers

The ensembling of classifiers tends to improve predictive accuracy. To obtain an ensemble with N classifiers, one typically needs to run N learning processes. In this paper we introduce and explore Model Jittering Ensembling, where one single model is perturbed in order to obtain variants that can be used as an ensemble. We use as base classifiers sets of classification association rules. The two methods of jittering ensembling we propose are Iterative Reordering Ensembling (IRE) and Post Bagging (PB). Both methods start by learning one rule set over a single run, and then produce multiple rule sets without relearning. Empirical results on 36 data sets are positive and show that both strategies tend to reduce error with respect to the single model association rule classifier. A bias–variance analysis reveals that while both IRE and PB are able to reduce the variance component of the error, IRE is particularly effective in reducing the bias component. We show that Model Jittering Ensembling can represent a very good speed-up w.r.t. multiple model learning ensembling. We also compare Model Jittering with various state of the art classifiers in terms of predictive accuracy and computational efficiency.     

A neural network ensemble method with jittered training data for time series forecasting

Improving forecasting especially time series forecasting accuracy is an important yet often difficult task facing decision makers in many areas. Combining multiple models can be an effective way to improve forecasting performance. Recently, considerable research has been taken in neural network ensembles. Most of the work, however, is devoted to the classification type of problems. As time series problems are often more difficult to model due to issues such as autocorrelation and single realization at any particular time point, more research is needed in this area.In this paper, we propose a jittered ensemble method for time series forecasting and test its effectiveness with both simulated and real time series. The central idea of the jittered ensemble is adding noises to the input data and thus augments the original training data set to form models based on different but related training samples. Our results show that the proposed method is able to consistently outperform the single modeling approach with a variety of time series processes. We also find that relatively small ensemble sizes of 5 and 10 are quite effective in forecasting performance improvement.     

Error analysis of estimators that use combinations of stochastic sampling strategies for direct illumination

We present a theoretical analysis of error of combinations of Monte Carlo estimators used in image synthesis. Importance sampling and multiple importance sampling are popular variance‐reduction strategies. Unfortunately, neither strategy improves the rate of convergence of Monte Carlo integration. Jittered sampling (a type of stratified sampling), on the other hand is known to improve the convergence rate. Most rendering software optimistically combine importance sampling with jittered sampling, hoping to achieve both. We derive the exact error of the combination of multiple importance sampling with jittered sampling. In addition, we demonstrate a further benefit of introducing negative correlations (antithetic sampling) between estimates to the convergence rate. As with importance sampling, antithetic sampling is known to reduce error for certain classes of integrands without affecting the convergence rate. In this paper, our analysis and experiments reveal that importance and antithetic sampling, if used judiciously and in conjunction with jittered sampling, may improve convergence rates. We show the impact of such combinations of strategies on the convergence rate of estimators for direct illumination.