Студенческий сайт КФУ (ex ТНУ) » Учебный раздел » Информатика. Компьютеры » Книга » 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

Режим просмотра:
 
Название: Algorithm 812. BPOLY, numerical library for polynomials in Bernstein form
Автор: V.-F. Tsai, R.T. Farouki (Загрузил Denis aka Rock Lee)
Категория: Информатика. Компьютеры
Дата добавления: 22.02.2009
Скачиваний: 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 ill-conditioned [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 Bernstein-form polynomials (arithmetic operations, evaluation, subdivision, composition, etc.) are not significantly more complicated or expensive than their familiar power-form versions [Farouki and Rajan 1988]. In this paper we describe an object-oriented library of functions for polynomials in Bernstein form that facilitates intuitive high-level 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


Комментарии