On the optimal stability of the Bernstein basis
Authors:
R. T. Farouki and T. N. T. Goodman
Journal:
Math. Comp. 65 (1996), 15531566
MSC (1991):
Primary 65G99; Secondary 65D17
MathSciNet review:
1351201
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We show that the Bernstein polynomial basis on a given interval is ``optimally stable,'' in the sense that no other nonnegative basis yields systematically smaller condition numbers for the values or roots of arbitrary polynomials on that interval. This result follows from a partial ordering of the set of all nonnegative bases that is induced by nonnegative basis transformations. We further show, by means of some lowdegree examples, that the Bernstein form is not uniquely optimal in this respect. However, it is the only optimally stable basis whose elements have no roots on the interior of the chosen interval. These ideas are illustrated by comparing the stability properties of the power, Bernstein, and generalized Ball bases.
 1.
A. A. Ball, CONSURF part one: Introduction to conic lofting tile, Comput. Aided Design 6 (1974), 243249.
 2.
J.
M. Carnicer and J.
M. Peña, Shape preserving representations and optimality of
the Bernstein basis, Adv. Comput. Math. 1 (1993),
no. 2, 173–196. MR 1230256
(94i:65138), http://dx.doi.org/10.1007/BF02071384
 3.
J. M. Carnicer and J. M. Peña, Total positivity and optimal bases, in Total Positivity and its Applications (M. Gasca and C. A. Micchelli, eds.), Kluwer Academic Publishers, Dordrecht, 1996, pp. 133155.
 4.
Gerald
Farin, Curves and surfaces for computer aided geometric
design, 3rd ed., Computer Science and Scientific Computing, Academic
Press, Inc., Boston, MA, 1993. A practical guide; With 1 IBMPC floppy disk
(5.25 inch; DD). MR 1201325
(93k:65016)
 5.
R.
T. Farouki and V.
T. Rajan, On the numerical condition of polynomials in Bernstein
form, Comput. Aided Geom. Design 4 (1987),
no. 3, 191–216. MR 917780
(89a:65028), http://dx.doi.org/10.1016/01678396(87)900124
 6.
W. Gautschi, Questions of numerical condition related to polynomials, in Studies in Numerical Analysis, MAA Studies in Mathematics 24, (G. H. Golub, ed.) 1984, 140177. CMP 20:07
 7.
T. N. T. Goodman and H. B. Said, Properties of generalized Ball curves and surfaces, Comput. Aided Design 23 (1991), 554560.
 8.
T.
N. T. Goodman and H.
B. Said, Shape preserving properties of the generalised Ball
basis, Comput. Aided Geom. Design 8 (1991),
no. 2, 115–121. MR 1107847
(92c:65181), http://dx.doi.org/10.1016/01678396(91)90037C
 9.
H. B. Said, A generalized Ball curve and its recursive algorithm, ACM Trans. Graphics 8 (1989), 360371.
 10.
T. V. To, Polar Form Approach to Geometric Modeling, Dissertation No. 92, Asian Institute of Technology, Bangkok, Thailand, 1992.
 11.
J.
H. Wilkinson, The evaluation of the zeros of illconditioned
polynomials. I, II, Numer. Math. 1 (1959),
150–180. MR 0109435
(22 #321)
 12.
J. H. Wilkinson, Rounding Errors in Algebraic Processes, Dover (reprint), New York, 1963. CMP 94:14
 1.
 A. A. Ball, CONSURF part one: Introduction to conic lofting tile, Comput. Aided Design 6 (1974), 243249.
 2.
 J. M. Carnicer and J. M. Peña, Shape preserving representations and optimality of the Bernstein basis, Adv. Comp. Math. 1 (1993), 173196. MR 94i:65138
 3.
 J. M. Carnicer and J. M. Peña, Total positivity and optimal bases, in Total Positivity and its Applications (M. Gasca and C. A. Micchelli, eds.), Kluwer Academic Publishers, Dordrecht, 1996, pp. 133155.
 4.
 G. Farin, Curves and Surfaces for Computer Aided Geometric Design, Academic Press, Boston, 1993. MR 93k:65016
 5.
 R. T. Farouki and V. T. Rajan, On the numerical condition of polynomials in Bernstein form, Comput. Aided Geom. Design 4 (1987), 191216. MR 89a:65028
 6.
 W. Gautschi, Questions of numerical condition related to polynomials, in Studies in Numerical Analysis, MAA Studies in Mathematics 24, (G. H. Golub, ed.) 1984, 140177. CMP 20:07
 7.
 T. N. T. Goodman and H. B. Said, Properties of generalized Ball curves and surfaces, Comput. Aided Design 23 (1991), 554560.
 8.
 T. N. T. Goodman and H. B. Said, Shape preserving properties of the generalized Ball basis, Comput. Aided Geom. Design 8 (1991), 115121. MR 92c:65181
 9.
 H. B. Said, A generalized Ball curve and its recursive algorithm, ACM Trans. Graphics 8 (1989), 360371.
 10.
 T. V. To, Polar Form Approach to Geometric Modeling, Dissertation No. 92, Asian Institute of Technology, Bangkok, Thailand, 1992.
 11.
 J. H. Wilkinson, The evaluation of the zeros of illconditioned polynomials. Parts I & II, Numer. Math. 1 (1959), 150166. MR 22:321
 12.
 J. H. Wilkinson, Rounding Errors in Algebraic Processes, Dover (reprint), New York, 1963. CMP 94:14
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
65G99,
65D17
Retrieve articles in all journals
with MSC (1991):
65G99,
65D17
Additional Information
R. T. Farouki
Affiliation:
Department of Mechanical Engineering & Applied Mechanics, University of Michigan, Ann Arbor, Michigan 48109
Email:
farouki@engin.umich.edu
T. N. T. Goodman
Affiliation:
Department of Mathematics and Computer Science, University of Dundee, Dundee DD1 4HN, Scotland
Email:
tgoodman@mcs.dundee.ac.uk
DOI:
http://dx.doi.org/10.1090/S0025571896007594
PII:
S 00255718(96)007594
Received by editor(s):
March 2, 1995
Received by editor(s) in revised form:
August 28, 1995
Article copyright:
© Copyright 1996
American Mathematical Society
