Bounds for an interval polynomial

We discuss the evaluation of the range of values of an interval polynomial over an interval. Several algorithms are proposed and tested on numerical examples. The algorithms are based on ideas by Cargo and Shiska [2] and Rivlin [4]. The one basic algorithm uses Bernstein polynomials. It is shown to converge to the exact bounds and it has furthermore the property that if the maximum respectively the minimum of the polynomials occurs at an endpoint of the interval then the bound is exact. This is a useful property in routines for polynomials zeros. The other basic method is based on the meanvalue theorem and it has the advantage that the degree of approximation required for a certain apriori tolerance is smaller than the degree required in the Bernstein polynomial case. The mean value method is shown to be at least quadratically convergent and the Bernstein polynomial method is shown to be at least linearly convergent.     

Bernstein多项式的快速复合算法

在计算机辅助几何设计中,Bernstein多项式的复合是一个重要的研究课题。目前,实现复合的方法主要有Blossoming算法和优化的Blossoming算法。这类方法虽然是数值稳定的,但是计算量很大,存储空间和程序复杂性方面也要求较高,文中基于多项式插值和符号运算,提出了一种新的复合算法。理论分析表明,新算法不但保持了数值稳定性,而且在计算量,存储空间和程序复杂性方面明显优于已有算法。     

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

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

Multivariate Bernstein polynomials and convexity

It is well-known that in two or more variables Bernstein polynomials do not preserve convexity. Here we present two variations, one stronger than the classical notion, the other one weaker, which are preserved and do coincide with classical convexity in the univariate case. Moreover, it will be shown that even the weaker notion is sufficient for the monotonicity of successive Bernstein polynomials, strengthening the well-known result that monotonicity holds for classically convex functions.     

Static and dynamic numerical device modeling for transient circuit simulation

This paper presents algorithms and their implementations for table look-up modeling of static and dynamic behavior of electronic devices for transient simulation. More specifically, multivariate Bernstein polynomials are used to interpolate the operating point from tabular input-output data. For most device characteristics quadratic tensor product of input-output polynomial functions in Bernstein form offer operating point values within a few percent of the analytical function value. This range of accuracy is acceptable for most transient simulation scenarios. The algorithm outlined here consists of dot product evaluations and thus it is computationally simpler than analytical models.     

Integral and non-negativity preserving Bernstein-type polynomial approximations

In this paper, we consider the problem of approximating a function by Bernstein-type polynomials that preserve the integral and non-negativity of the original function on the interval [0, 1], obtaining the Kantorovich–Bernstein polynomials, but providing a novel approach with advantages in numerical analysis. We then develop a Markov finite approximation method based on piecewise Bernstein-type polynomials for the computation of stationary densities of Markov operators, providing numerical results for piecewise constant and piecewise linear algorithms.     

基于约束Jacobi基的多项式反函数逼近及应用

求解多项式反函数是CAGD中的一个基本问题.提出一种带端点Ck约束的反函数逼近算法.利用约束Jacobi基作为有效工具, 推导了它与Bernstein基的转换公式,采用Bernstein多项式的升阶、乘积、积分与组合运算, 给出了求解反函数系数的具体算法.该算法稳定、简易, 克服了以往计算反函数的系数时每次逼近系数需全部重新计算的缺陷.最后通过具体逼近实例验证了文中算法的正确性和有效性, 同时给出了它在PH曲线准弧长参数化中的应用.     

Inclusion Isotonicity of Convex–Concave Extensions for Polynomials Based on Bernstein Expansion

In this paper the expansion of a polynomial into Bernstein polynomials over an interval I is considered. The convex hull of the control points associated with the coefficients of this expansion encloses the graph of the polynomial over I. By a simple proof it is shown that this convex hull is inclusion isotonic, i.e. if one shrinks I then the convex hull of the control points on the smaller interval is contained in the convex hull of the control points on I. From this property it follows that the so-called Bernstein form is inclusion isotone, which was shown by a longish proof in 1995 in this journal by Hong and Stahl. Inclusion isotonicity also holds for multivariate polynomials on boxes. Examples are presented which document that two simpler enclosures based on only a few control points are in general not inclusion isotonic. Received September 12, 2002; revised February 5, 2003 Published online: April 7, 2003     

Application of Bernstein Expansion to the Solution of Control Problems

We survey some recent applications of Bernstein expansion to robust stability, viz. checking robust Hurwitz and Schur stability of polynomials with polynomial parameter dependency by testing determinantal criteria and by inspection of the value set. Then we show how Bernstein expansion can be used to solve systems of strict polynomial inequalities.     

On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers

We elaborate on a correspondence between the coefficients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions that use only integer arithmetic (in contrast to the Bernstein basis) and are feasible over unbounded regions. Then, we study an algorithm to split this representation and obtain a subdivision scheme for the domain of multivariate polynomial functions. This implies a new algorithm for real root isolation, MCF, that generalizes the Continued Fraction (CF) algorithm of univariate polynomials.A partial extension of Vincent’s Theorem for multivariate polynomials is presented, which allows us to prove the termination of the algorithm. Bounding functions, projection and preconditioning are employed to speed up the scheme. The resulting isolation boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. Finally, we present new complexity bounds for a simplified version of the algorithm in the bit complexity model, and also bounds in the real RAM model for a family of subdivision algorithms in terms of the real condition number of the system. Examples computed with our C++ implementation illustrate the practical aspects of our method.     

On a generalization of Bernstein polynomials and Bézier curves based on umbral calculus

In Winkel (2001) a generalization of Bernstein polynomials and Bézier curves based on umbral calculus has been introduced. In the present paper we describe new geometric and algorithmic properties of this generalization including: (1) families of polynomials introduced by Stancu (1968) and Goldman (1985), i.e., families that include both Bernstein and Lagrange polynomial, are generalized in a new way, (2) a generalized de Casteljau algorithm is discussed, (3) an efficient evaluation of generalized Bézier curves through a linear transformation of the control polygon is described, (4) a simple criterion for endpoint tangentiality is established.     

Polytope-based computation of polynomial ranges

Polynomial ranges are commonly used for numerically solving polynomial systems with interval Newton solvers. Often ranges are computed using the convex hull property of the tensorial Bernstein basis, which is exponential size in the number n of variables. In this paper, we consider methods to compute tight bounds for polynomials in n variables by solving two linear programming problems over a polytope. We formulate a polytope defined as the convex hull of the coefficients with respect to the tensorial Bernstein basis, and we formulate several polytopes based on the Bernstein polynomials of the domain. These Bernstein polytopes can be defined by a polynomial number of halfspaces. We give the number of vertices, the number of hyperfaces, and the volume of each polytope for n=1,2,3,4, and we compare the computed range widths for random n-variate polynomials for n?10. The Bernstein polytope of polynomial size gives only marginally worse range bounds compared to the range bounds obtained with the tensorial Bernstein basis of exponential size.     

An identity for multivariate Bernstein polynomials

We prove an identity for multivariate Bernstein polynomials on simplices, which may be considered a pointwise orthogonality relation. Its integrated version provides a new representation for the polynomial dual basis of Bernstein polynomials. An identity for the reproducing kernel is used to define quasi-interpolants of arbitrary order.     

Adaptive reconstruction of bone geometry from serial cross-sections

Many biomedical applications, such as the design of customized orthopaedic implants, require accurate mathematical models of bone geometry. The surface geometry is often generated by fitting closed parametric curves, or contours, to the edge points extracted from a sequence of evenly spaced planar images acquired using computed tomography (CT), magnetic resonance imaging (MRI), or ultrasound imaging. The Bernstein basis function (BBF) network described in this paper is a novel neural network approach to performing functional approximation tasks such as curve and surface fitting. In essence, the BBF architecture is a two-layer basis function network that performs a weighted summation of nonlinear Bernstein polynomials. The weight values generated during network training are equivalent to the control points needed to create a smooth closed Bézier curve in a variety of commercially available computer-aided design software. Modifying the number of basis neurons in the architecture is equivalent to changing the degree of the Bernstein polynomials. An increase in the number of neurons will improve the curve fit, however, too many neurons will diminish the network's ability to generate a smooth approximation of the cross-sectional boundary data. Additional constraints are imposed on the learning algorithm in order to ensure positional and tangential continuity for the closed curve. A simulation study and real world experiment are presented to show the effectiveness of this functional approximation method for reverse engineering bone structures from serial medical imagery.     

混合有理Bézier曲面及其三维重建

文章将Bernstein基函数与有理Bernstein基函数相结合,构造了一类新型有理曲面-混合有理Bézier曲面;给出了该类曲面的生成方法并讨论了曲面的性质。另一方面,在一种基于Newton-Thiele型非线性方法的插值曲面的三维重建理论基础上,讨论了由离散点集重建混合有理Bézier曲面的问题,为图形图象处理等研究领域提供了新的算法理论。     

General distortion of an ensemble of biparametric surfaces

When the shape of an object has been numerically defined, it is sometimes necessary to distort it to improve either its technical performance or its aesthetic appearance.After briefly recalling the major properties of space curves and surfaces defined by Bernstein polynomials, it is shown how the result can be automatically obtained by distorting an auxiliary triparametric set of references.The principle of an approximate method for high-order curves and surfaces is explained.     

A note on the Bernstein algorithm for bounds for interval polynomials

In computing the range of values of a polynomial over an intervala≤x≤b one may use polynomials of the form $$\left( {\begin{array}{*{20}c} k \\ j \\ \end{array} } \right)\left( {x - a} \right)^j \left( {b - x} \right)^{k - j} $$ called Bernstein polynomials of the degreek. An arbitrary polynomial of degreen may be written as a linear combination of Bernstein polynomials of degreek≥n. The coefficients of this linear combination furnish an upper/lower bound for the range of the polynomial. In this paper a finite differencelike scheme is investigated for this computation. The scheme is then generalized to interval polynomials.     

Parameterization of the discriminant set of a polynomial

The discriminant set of a real polynomial is studied. It is shown that this set has a complex hierarchical structure and consists of algebraic varieties of various dimensions. A constructive algorithm for a polynomial parameterization of the discriminant set in the space of the coefficients of the polynomial is proposed. Each variety of a greter dimension can be geometrically considered as a tangent developable surface formed by one-dimensional linear varieties. The role of the directrix is played by the component of the discriminant set with the dimension by one less on which the original polynomial has a single multiple root and the other roots are simple. The relationship between the structure of the discriminant set and the partitioning of natural numbers is revealed. Various algorithms for the calculation of subdiscriminants of polynomials are also discussed. The basic algorithms described in this paper are implemented as a library for Maple.     

Eliciting dependability requirements: a control cases based approach

At present,great demands are posed on software dependability.But how to elicit the dependability requirements is still a challenging task.This paper proposes a novel approach to address this issue.The essential idea is to model a dependable software system as a feedforward-feedback control system,and presents the use cases+control cases model to express the requirements of the dependable software systems.In this model,while the use cases are adopted to model the functional requirements,two kinds of control cases(namely the feedforward control cases and the feedback control cases)are designed to model the dependability requirements.The use cases+control cases model provides a unified framework to integrate the modeling of the functional requirements and the dependability requirements at a high abstract level.To guide the elicitation of the dependability requirements,a HAZOP based process is also designed.A case study is conducted to illustrate the feasibility of the proposed approach.     

Iterated Bernstein operators for distribution function and density estimation: Balancing between the number of iterations and the polynomial degree

Despite its slow convergence, the use of the Bernstein polynomial approximation is becoming more frequent in Statistics, especially for density estimation of compactly supported probability distributions. This is due to its numerous attractive properties, from both an approximation (uniform shape-preserving approximation, etc.) and a statistical (bona fide estimation, low boundary bias, etc.) point of view. An original method for estimating distribution functions and densities with Bernstein polynomials is proposed, which takes advantage of results about the eigenstructure of the Bernstein operator to refine a convergence acceleration method. Furthermore, an original data-driven method for choosing the degree of the polynomial is worked out. The method is successfully applied to two data-sets which are important benchmarks in the field of Density Estimation.