Algorithm 812. BPOLY, numerical library for polynomials in Bernstein form  V.F. Tsai, R.T. Farouki
Скачать

Название: 
Algorithm 812. BPOLY, numerical library for polynomials in Bernstein form 
Автор: 
V.F. Tsai, R.T. Farouki 
Категория: 
Информатика. Компьютеры

Тип: 
Книга 
Дата: 
22.02.2009 12:42:01 
Скачано: 
25 
Оценка: 

Описание: 
on1 x E [0, 1] was introduced in 1912 by Bernstein [1912] in a constructive proof for the theorem ofWeierstrass, concerning uniform approximation of continuous functions on finite intervals by polynomials. The slow convergence of Bernstein polynomial approximants incurred a widespread perception that the form (1) is unsuitable for "practical" computations, which persisted until de Casteljau and Bezier demonstrated its advantages in geometric design.
Another advantage of the Bernstein form, of much broader significance, is its intrinsic numerical stability as a representation for polynomials defined on finite intervals [Farouki and Rajan 1987]. Namely, the values (and roots) of P(x) on x E [0, 1] are much less sensitive to uniform perturbations or errors in the coefficients Cq, . . . , Cnn compared to other commonly used polynomial bases—e.g., the power form. In fact, the Bernstein form is optimally stable—it is impossible to construct a basis on [0, 1] that yields systematically smaller condition numbers for the values and roots of arbitrary polynomials on this interval [Farouki and Goodman 1996].
Explicit conversions between different polynomial bases become increasingly illconditioned [Daniel and Daubisse 1989; Farouki 1991a; 2000; Hermann 1996] as the degree n increases. In order to take full advantage of its stability, it is essential to formulate the problem under consideration initially in the Bernstein form, and to express all intermediate steps using it. Although perhaps less familiar, basic algorithms for Bernsteinform polynomials (arithmetic operations, evaluation, subdivision, composition, etc.) are not significantly more complicated or expensive than their familiar powerform versions [Farouki and Rajan 1988]. In this paper we describe an objectoriented library of functions for polynomials in Bernstein form that facilitates intuitive highlevel programming of polynomial computations. Relieved from having to worry about the underlying technical details—binomial coefficient operations, matching degrees of operands, etc.— the programmer can rapidly develop robust and efficient code that inherits both the intuitive geometrical features and stability properties of the Bernstein form.
Although use of the Bernstein form is commonplace in computer graphics and CAGD, its advantageous properties have only recently begun to achieve recognition in the much broader contexts of numerical analysis and 
Файл: 
193.3 КБ 
Скачать
