An Adaptive Numerical Integration Algorithm with Automatic Result Verification for Definite Integrals

We present a verified numerical integration algorithm with an adaptive strategy for smooth integrands. Verified representations of the remainder term are derived and a new adaptive strategy is given which delivers a desired integral enclosure with an error usually bounded by a specified error bound. Here, we discuss the distribution of the specified error bound onto the subintervals used in the algorithm more closely and present numerical results depending on the distribution of the error. Received March 15, 1999; revised December 1, 1999     

Efficient evaluation of multivariate polynomials

In CAGD applications, the usual way to store a polynomial defined over a triangle is in the Bernstein-Bézier form, and the accepted way to evaluate it at a given point in the triangle is by the de Casteljau algorithm. In this paper we present an algorithm for evaluating Berstein-Bézier type polynomials which is significantly faster than de Casteljau. This suggests that a modified form of Bernstein-Bézier may be preferable for CAGD applications (as well as in applications of piecewise polynomials in data fitting and numerical solution of boundary-value problems).     

张量积de Casteljau算法的效率分析

在几何造型中，张量积Bernstein多项式具有非常重要的地位。在几何系统中主要应用de Casteljau算法逐个方向地计算张量积Bernstein多项式上的点，例如首先计算u-方向、然后是v-方向、w-方向等。分析了张量积形式的de Casteljau算法的效率，证明了对于不同的参数方向的计算顺序会导致不同的计算效率，并且当按照参数方向的次数递增的顺序应用de Casteljau算法时，计算量是最小的，除了理论分析之外，我们还给出了实验结果，并且实验结果与理论分析是一致的。     

A subdivision scheme for Poisson curves and surfaces

The de Casteljau evaluation algorithm applied to a finite sequence of control points defines a Bézier curve. This evaluation procedure also generates a subdivision algorithm and the limit of the subdivision process is this same Bézier curve. Extending the de Casteljau subdivision algorithm to an infinite sequence of control points defines a new family of curves. Here, limits of this stationary non-uniform subdivision process are shown to be equivalent to curves whose control points are the original data points and whose blending functions are given by the Poisson distribution. Thus this approach generalizes standard subdivision techniques from polynomials to arbitrary analytic functions. Extensions of this new subdivision scheme from curves to tensor product surfaces are also discussed.     

Adaptive interpolation of images using a new nonlinear cell-average scheme

We present a new method for image interpolation which combines a cell average version of the nonlinear interpolatory technique called PPH (Piecewise Polynomial Harmonic) and subcell resolution techniques. It is designed to perform more accurately at discontinuities, avoiding the evaluation of any extrapolation technique. Numerical experiments are shown validating the theoretical aspects of the algorithm.     

Regularized Greedy Algorithms for Network Training with Data Noise

The aim of this paper is to construct a modified greedy algorithm applicable for an ill-posed function approximation problem in presence of data noise. We provide a detailed convergence analysis of the algorithm in presence of noise, and discuss the choice of the iteration parameters. This yields a stopping rule for which the corresponding algorithm is a regularization method with convergence rates in L₂ and under weak additional assumptions also in Sobolev-spaces of positive order.Finally, we discuss the application of the modified greedy algorithm to sigmoidal neural networks and radial basis functions, and supplement the theoretical results by numerical experiments.     

Lupa? q-Bézier曲线的离散卷积生成与求值算法

Lupa? q-Bernstein算子是最早提出的有理形式下基于q-整数的q-模拟Bernstein算子。通过Lupa? q-Bernstein基函数的递推关系反向使用金字塔算法,离散卷积生成n次Lupa? q-Bernstein基函数序列。结合离散卷积满足的交换性,针对n次Lupa? q-Bézier曲线推导出其速端曲线及n!种de Casteljau算法。与Bézier曲线de Casteljau算法得到的切点不同,Lupa? q-Bézier曲线的de Casteljau算法得到的曲线上的一点是直线与曲线相交的2个割点之一。针对二次Lupa? q-Bézier曲线,给出了计算左/右割点的充分必要条件,然后通过提出双割点算法,可以同时得到左/右割点。     

Computing Interval Enclosures for Definite Integrals by Application of Triple Adaptive Strategies

In addition to the well-known and widely-used adaptive strategies for region subdivision and the choice of local quadrature rules, there still exists a third possibility for doing numerical integration adaptively, when interval computation is considered. Based on the Peano's kernels theorem and interval arithmetic, we are able to estimate the truncation error of a quadrature rule by means of different derivatives of the integrand, where the available orders of the derivatives depend on the degree of smoothness of the integrand and the exactness degree of the underlying quadrature rule. We classify the methods as the adaptive orders strategies, if they make use of the derivatives of different orders to improve each single local error estimation. In this paper, alternatives for adaptive error estimation are discussed. Moreover, a practical way for realization of the optimal error estimation is suggested. Numerical results for integrands of different classes as well as numerical comparisons of different methods are given.     

Sharp error bounds for piecewise linear interpolation of planar curves

Curves are commonly drawn by piecewise linear interpolation, but to worry about the error is rather seldom. In the present paper we give a strong mathematical error analysis for curve segments with bounded curvature and length. Though the result seems very clear, the proof turned out to be unexpectedly hard, comparable to that of the famous four vertex theorem.     

On the Multivariate Horner Scheme II: Running Error Analysis

 As an extension of our previous paper which gave forward and backward error estimates, we perform a running error analysis of the multivariate Horner scheme. This leads to a modified algorithm which computes the value of the polynomial together with an error estimate. Received November 9, 1999; revised May 29, 2000     

Recursive algorithms for the representation of parametric curves and surfaces

Recursive algorithms for the representation of parametric curves and surfaces are presented which are based upon a geometric property of the de Casteljau algorithm. The algorithms work with triangular and pyramidal arrays that provide an easy handling of the curve and the surface ‘in a large’ design.     

Generation of random variates using asymptotic expansions

Monte-Carlo methods are widely used numerical tools in various fields of application, like rarefied gas dynamics, vacuum technology, stellar dynamics or nuclear physics. A central part is the generation of random variates according to a given probability law. Fundamental techniques are the inversion principle or the acceptance-rejection method—both may be quite time-consuming if the given probability law has a complicated structure. In this paper probability laws depending on a small parameter are considered and the use of asymptotic expansions to generate random variates is investigated. The results given in the paper are restricted to first order expansions. Error estimates for the discrepancy as well as for the bounded Lipschitz distance of the asymptotic expansion are derived. Furthermore the integration error for some special classes of functions is given. The efficiency of the method is proved by a numerical example from rarefied gas flows.     

Differential constraints for bounded recursive identification with multivariate splines

The ability to perform online model identification for nonlinear systems with unknown dynamics is essential to any adaptive model-based control system. In this paper, a new differential equality constrained recursive least squares estimator for multivariate simplex splines is presented that is able to perform online model identification and bounded model extrapolation in the framework of a model-based control system. A new type of linear constraints, the differential constraints, are used as differential boundary conditions within the recursive estimator which limit polynomial divergence when extrapolating data. The differential constraints are derived with a new, one-step matrix form of the de Casteljau algorithm, which reduces their formulation into a single matrix multiplication. The recursive estimator is demonstrated on a bivariate dataset, where it is shown to provide a speedup of two orders of magnitude over an ordinary least squares batch method. Additionally, it is demonstrated that inclusion of differential constraints in the least squares optimization scheme can prevent polynomial divergence close to edges of the model domain where local data coverage may be insufficient, a situation often encountered with global recursive data approximation.     

Integer de Casteljau Algorithm for Rasterizing NURBS Curves

An integer version of the well-known de Casteljau algorithm of NURBS curves is presented here. The algorithm is used to render NURBS curves of any degree on a raster device by turning on pixels that are closest to the curve. The approximation is independent of the parametrization, that is, it is independent of the weights used. The algorithm works entirely in the screen coordinate system and produces smooth rendering of curves without oversampling. Because of the integer arithmetic used, the algorithm is easily cast in hardware.     

Generalized rational Bézier curves for the rigid body motion design

In this paper, we present a new method for the smooth interpolation of the orientations of a rigid body motion. The method is based on the geometrical Hermite interpolation in a hypersphere. However, the non-Euclidean structure of a sphere brings a great challenge to the interpolation problem. For this consideration and the requirements for practical application, we construct the spherical analogue of classical rational Bézier curves, called generalized rational Bézier curves. The new spherical curves are obtained using the generalized rational de Casteljau algorithm, which is a generalization of the classical rational de Casteljau algorithm to a hypersphere. Then, \(G^2\) Hermite interpolation problem in hypersphere is solved analytically using the generalized rational Bézier curve of degree 5. The new method offers residual free parameters including shape parameters and weights, which guarantee the existence of the interpolant to arbitrary motion data and offer great flexibility for the shape design of the motion. Numerical examples show that our method is far better behaved according to the energy functional which is regarded as a measure of the motion shape.     

Adaptive Low-Rank Approximation of Collocation Matrices

This article deals with the solution of integral equations using collocation methods with almost linear complexity. Methods such as fast multipole, panel clustering and ℋ-matrix methods gain their efficiency from approximating the kernel function. The proposed algorithm which uses the ℋ-matrix format, in contrast, is purely algebraic and relies on a small part of the collocation matrix for its blockwise approximation by low-rank matrices. Furthermore, a new algorithm for matrix partitioning that significantly reduces the number of blocks generated is presented. Received August 15, 2002; revised September 20, 2002 Published online: March 6, 2003     

A Top Down Method for Interactive Drawing

Traditional interactive drawing programs adopt a bottom-up approach, allowing the user to construct a picture by the use of discrete tools, for example, lines, circles, rectangles, and so on. This paper presents a different approach, which allows users to construct graphical objects by stretching and cutting existing objects. The representation is simply implemented, based on a ring of cubic Bezier curves, and use of the de Casteljau algorithm.     

Gaussian quadrature formulae-second peano kernels,nodes, weights and Bessel functions

The central results of this paper are bounds for the second Peano kernels of the Gaussian quadrature formulae. Hence, for these quadrature formulae, we derive asymptotically optimal error constants for classes of functions with a bounded second derivative or with a first derivative of bounded variation, or for a class of convex functions. To obtain these bounds, we first prove inequalities related to MacMahon's expansion and some further results on the Bessel functionJ _o , as well as some “trapezoid theorems for the weights of Gaussian formulae” (cf. Davis and Rabinowitz [6]) with explicit bounds for the error term.     

细分生成B样条的几何作图法

研究均匀B样条曲线细分生成的几何作图问题,给出了采用p-nary细分法细分生成任意次均匀B样条曲线的递归细分算法。在此基础上,研究了任意次均匀B样条曲线p-nary细分生成的几何作图方法。利用这种几何作图法,可以直观地在计算机上通过编程来快速准确地绘制B样曲线,更重要的是,可以使基于几何方法的任意次B样曲线的手工绘制成为可能。