Robustness analysis of polynomials with polynomial parameterdependency using Bernstein expansion

This paper considers the robust stability verification of polynomials with coefficients depending polynomially on parameters varying in given intervals. Two algorithms are presented, both rely on the expansion of a multivariate polynomial into Bernstein polynomials. The first one is an improvement of the so-called Bernstein algorithm and checks the Hurwitz determinant for positivity over the parameter set. The second one is based on the analysis of the value set of the family of polynomials and profits from the convex hull property of the Bernstein polynomials. Numerical results to real-world control problems are presented showing the efficiency of both algorithms     

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.     

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

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

Numerical approach for solving variable-order space–time fractional telegraph equation using transcendental Bernstein series

Engineering with Computers - This paper presents the transcendental Bernstein series (TBS) as a generalization of the classical Bernstein polynomials for solving the variable-order space–time...     

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.     

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.     

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.     

Trigonometric Bézier and Stancu polynomials over intervals and triangles

We introduce a family of trigonometric polynomials, denoted as Stancu polynomials, which contains the trigonometric Lagrange and Bernstein polynomials. This family depends only on one real parameter, denoted as design parameter. Our approach works for curves as well as for surfaces over triangles. The resulting Stancu curves respectively surfaces therefore establish a link between trigonometric interpolatory and Bernstein-Bézier curves respectively surfaces.     

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.     

Algebraic manipulation in the Bernstein form made simple via convolutions

Traditional methods for algebraic manipulation of polynomials in Bernstein form try to obtain an explicit formula for each coefficient of the result of a given procedure, such us multiplication, arbitrarily high degree elevation, composition, or differentiation of rational functions. Whereas this strategy often furnishes involved expressions, these operations become trivial in terms of convolutions between coefficient lists if we employ the scaled Bernstein basis, which does not include binomial coefficients. We also carry over this scheme from the univariate case to multivariate polynomials, Bézier simplexes of any dimension and B-bases of other functional spaces. Examples of applications in geometry processing are provided, such as conversions between the triangular and tensor-product Bézier forms.     

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

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

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.     

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.     

三角域上双变量Chebyshev 多项式及其与Bernstein 基的转换

为了更好的解决三角域上的Bézier 曲面在CAGD 中的最佳一致逼近问题, 构造出了三角域上的双变量Chebyshev 正交多项式,研究了与单变量Chebyshev 多项式相类 似的性质,并且给出了三角域上双变量Chebyshev 基和Bernstein 基的相互转换矩阵。通过 实例比较双变量Chebyshev 多项式与双变量Bernstein 多项式以及双变量Jacobi 多项式的最 小零偏差的大小,阐述了双变量Chebyshev 多项式的最小零偏差性。     

Bounds for the Range of a Bivariate Polynomial over a Triangle

The problem of finding an enclosure for the range of a bivariate polynomial p over the unit triangle is considered. The polynomial p is expanded into Bernstein polynomials. If p has only real coefficients the coefficients of this expansion, the so-called Bernstein coefficients, provide lower and upper bounds for the range. In the case that p has complex coefficients the convex hull of the Bernstein coefficients encloses the range. The enclosure is improved by subdividing the unit triangle into squares and triangles and computing enclosures for the range of p over these regions. It is shown that the sequence of enclosures obtained in this way converges to the convex hull of the range in the Hausdorff distance. Furthermore, it is described how the Bernstein coefficients on these regions can be computed economically.     

Hyper-arc consistency of polynomial constraints over finite domains using the modified Bernstein form

This paper describes an algorithm to enforce hyper-arc consistency of polynomial constraints defined over finite domains. First, the paper describes the language of so called polynomial constraints over finite domains, and it introduces a canonical form for such constraints. Then, the canonical form is used to transform the problem of testing the satisfiability of a constraint in a box into the problem of studying the sign of a related polynomial function in the same box, a problem which is effectively solved by using the modified Bernstein form of polynomials. The modified Bernstein form of polynomials is briefly discussed, and the proposed hyper-arc consistency algorithm is finally detailed. The proposed algorithm is a subdivision procedure which, starting from an initial approximation of the domains of variables, removes values from domains to enforce hyper-arc consistency.     

Solving nonlinear polynomial systems in the barycentric Bernstein basis

We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices. We use geometric subdivision to isolate multiple roots within a simplex. An algorithm implementing this method in rounded interval arithmetic is described and analyzed. We find that when the total order of polynomials is close to the maximum order of each variable, an iteration of this solver algorithm is asymptotically more efficient than the corresponding step in a similar algorithm which relies on polynomial representation in the tensor product Bernstein basis. We also discuss various implementation issues and identify topics for further study.     

Optimal computation of the Bernstein algorithm for the bound of an interval polynomial

If a polynomial is expanded in terms of Bernstein polynomial over an interval then the coefficients of the expansion may be used to provide upper and lower bounds for the value of the polynomial over the interval. When applying this method to interval polynomials straightforwardly, the coefficients of the expansion are computed with an increase in width due to dependency intervals. In this paper we show that if the computations are rearranged suitably then the Bernstein coefficients can be computed with no increase in width due to dependency intervals.     

Characterizing the measures on the unit circle with exact quadrature formulas in the space of polynomials

In the present paper we characterize the measures on the unit circle for which there exists a quadrature formula with a fixed number of nodes and weights and such that it exactly integrates all the polynomials with complex coefficients. As an application we obtain quadrature rules for polynomial modifications of the Bernstein measures on [−1,1], having a fixed number of nodes and quadrature coefficients and such that they exactly integrate all the polynomials with real coefficients.     

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.